Обычно распределения, отличные от равномерного, получаются двухшаговым способом - сперва генерируются равномерно распределённые числа, затем они преобразуются к требуемому распределению (по одному, как
, где
- функция, обратная к требуемому распределению, по два на входе и два на выходе, как в методе Бокса-Мюллера, или несколько в одно, как в методах, основанных на ЦПТ).
Соответственно, вопрос распадается на два подвопроса. Как проверить равномерность и как проверить переход от равномерного к желаемому.
Теория равномерных ГСЧ достаточно развита, для ознакомления с основными результатами можно почитать второй том Кнута, а вкратце:
Ограничиваются генераторами равномерно распределённых целых чисел, а когда нужно действительное число - приводят его к нужному диапазону действительных. Попытки сразу генерировать действительные приводила к численной неустойчивости. Равномерность в этом случае достигается, если каждое возможное значение в цикле получается одинаковое число раз. Для чаще всего применяемых генераторов, в которых
, новое С.Ч. зависит только от одного предыдущего, каждое число в цикле только единожды. Для мультипликативных генераторов вида
проверить это свойство для данных a, b, M легко, применяя элементарную теорию чисел, и выбираются обыкновенно такие, что генератор получается "полноцикловым", что обеспечивает равномерность. Если это не убеждает, а также для генераторов, для которых нет столь развитой теории, можно тупо перебрать все значения, ища повторения (хранить все мыслимые значения не надо, практичнее сравнивать
и
) и убедиться, что длина цикла максимально.
Равномерность не единственное требование для ГСЧ. Генератор
вполне равномерный, но, наверно, худший ГСЧ из мыслимых. Некоррелированность проверяется также аналитически, более сложные требования к случайности приходится проверять численными экспериментами.
Методы приведения равномерно распределённой величины к желаемому распределению доказаны, как правило, аналитически. Численные проверки делают скорее, чтобы убедиться в том, что аналитическая формула запрограммирована верно.
(Оффтоп)
Лет 30 с лишним тому, перечитав Кнута, взялся я делать "лучший в мире нормальный ГСЧ". Включал он в себя 16 равномерных генераторов со сравнительно небольшими, но простыми периодами, результат которых преобразовывался в действительные числа с нулевым средним, единичной дисперсией и четвёртым моментом, равным 3 (то есть "почти нормальным"). Ещё один генератор, на регистрах сдвига, менял значения отдельных отсчётов из этих 16 (когда выдавал единичный бит). Затем вектор перетасовывался при помощи ещё одного генератора (кажется, "середина квадрата") и "оптимальной сортировки для 16 значений" из третьего тома Кнута, делалось Фурье по 16 точкам, что было неким приложением Центральной Предельной Теоремы, ещё раз менялись знаки сдвиговым генератором и тасовалось, помнится, при помощи "генератора Фибоначчи" (периоды этих генераторов также были взаимно просты). Что давало повторение где-то после
отсчётов, на нашу Вселенную должно было хватить, а различие генераторов должно было нивелировать специфические их недостатки (более сложные, чем коррелированость, взаимозависимости чисел). Полученный вектор выдавался по одному на запрос, а после 16 запросов генерировался новый вектор из 16 чисел, то есть на одно число операций было немногим больше, чем для генерации одного случайного числа с равномерным распределением.
Впрочем, численный эксперимент (достаточно обширный; Мудрое Начальство выдало ОВЦУ - загружать ЭВМ в третью смену, и зав. отделом срочно придумал инициативную тему "Исследование свойств генераторов случайных чисел", и машина молотила по 8 часов, генерируя С.Ч. и собирая статистику по их свойствам, так что получилось удачно) существенных преимуществ перед простым Боксом-Мюллером не показал. Просто хорошее упражнение по численному программированию вышло.
