Генераторы псевдослучайных чисел

Генератор псевдослучайных чисел — это детерминистская рекуррентная формула, которая, исходя из начального зерна, производит длинную воспроизводимую последовательность чисел, имитирующую независимые выборки из равномерного распределения на единичном интервале.

Definition

Генератор псевдослучайных чисел — это алгоритм, определяемый состоянием, функцией перехода, которая изменяет состояние, и функцией вывода, которая сопоставляет каждое состояние числу, производя периодическую последовательность, предназначенную для статистической неразличимости от равномерных случайных чисел.

Scope

Эта тема охватывает построение равномерных генераторов (линейных конгруэнтных, с запаздыванием Фибоначчи, с обобщенным регистром сдвига с обратной связью и комбинированных генераторов), структурные свойства, определяющие их качество, такие как длина периода и поведение решетки или равномерного распределения, а также эмпирические и теоретические тесты, используемые для их сертификации. Криптографически стойкие генераторы упоминаются только как контрастирующая цель проектирования.

Core questions

• Какие рекуррентные формулы обеспечивают длинные периоды и хорошую многомерную равномерность?
• Как измеряется качество генератора по его решеточной структуре и равномерному распределению?
• Какие эмпирические тестовые батареи обнаруживают отклонения от случайности?
• Как генераторы инициализируются и комбинируются для увеличения периода и улучшения статистических свойств?

Key concepts

• Зерно и состояние
• Длина периода
• Равномерное распределение
• Решеточная структура
• Спектральный тест
• Комбинированные генераторы

Key theories

Генераторы линейных рекуррентных соотношений

Линейные конгруэнтные рекуррентные соотношения и рекуррентные соотношения с регистрами сдвига изменяют целочисленное состояние с помощью модульной арифметики; их период и решеточная структура последовательных выходов определяются теоретико-числовыми свойствами множителя и модуля.

Равномерное распределение и Mersenne Twister

Генераторы, основанные на скрученных обобщенных регистрах сдвига с обратной связью, достигают огромных периодов и доказуемого равномерного распределения во многих измерениях, что делает их широко используемым стандартом для статистического моделирования.

Clinical relevance

Генератор по умолчанию в статистическом пакете определяет воспроизводимость и достоверность каждого результата симуляции, бутстрапа и метода Монте-Карло, который он производит; понимание периода и равномерного распределения помогает практикам избегать генераторов, чьи скрытые закономерности могут искажать многомерные симуляции.

History

Лемер предложил линейный конгруэнтный метод в 1949 году; последующий анализ выявил дефекты решетки плохо выбранных параметров, что послужило мотивом для спектрального теста, комбинированных генераторов и, в конечном итоге, для разработок с длинным периодом и равномерным распределением, таких как Mersenne Twister в 1998 году.

Key figures

• Donald Knuth
• Pierre L'Ecuyer
• Makoto Matsumoto
• Derrick Henry Lehmer

Seminal works

• knuth1997
• matsumoto1998

Frequently asked questions

Что делает один генератор псевдослучайных чисел лучше другого?

Хороший генератор имеет очень длинный период, равномерно распределяет свои выходы даже во многих измерениях, проходит стандартные статистические тестовые батареи, а также быстр и воспроизводим. Плохие генераторы могут иметь короткие периоды или видимые решеточные паттерны, которые искажают симуляции.

Почему важно зерно?

Зерно фиксирует начальное состояние, поэтому вся последовательность определяется им. Запись зерна делает симуляцию точно воспроизводимой, в то время как небрежный выбор зерен может привести к перекрывающимся или коррелированным потокам в параллельных запусках.