Метод усечения

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

Наиболее простой способ называется методом «середины квадрата».

1.   Берется произвольное число x₀, состоящее из k разрядов.

2.   Величина x₀ возводится в квадрат.

3.   Средние k разрядов результата и составляют очередное число x₁.

Указанная процедура циклически повторяется. Практически после 20-30 циклов устанавливается последовательность с распределением, близким к равномерному. Например,

пусть , тогда ;

, ;

, ; и т.д.

Это был первый алгоритм для получения псевдослучайных чисел на ЭВМ, предложенный Дж. Фон-Нейманом.

Значительно лучшие результаты дает видоизмененный метод «середины произведения».

1.   Произвольно выбирается пара чисел x₀ и x₁.

2.   Составляется их произведение x₀x₁.

3.   Средние цифры произведения используются в качестве очередного числа x₂.

Далее процесс повторяется циклически.

Требования к случайным числам

Строго говоря, невозможно с помощью рекуррентных соотношений получить последовательность случайных чисел, которые являются независимыми реализациями случайной величины X, равномерно распределенной на интервале [0, 1], так как число используемых двоичных или десятичных разрядов в ЭВМ ограничено. На самом деле мы получаем так называемые казиравномерные случайные числа, при достаточно большом числе разрядов казиравномерная случайная величина хорошо аппроксимирует равномерную случайную величину.

С помощью программного генератора получаются числа x₁, …, x_n, которые рассматриваются как случайные, нужно еще проверить, являются ли они в действительности последовательностью независимых случайных величин равномерно распределенных на интервале [0, 1]. Для этого применяются критерии согласия между эмпирическим и теоретически распределениями, критерии стохастической независимости следующих друг за другом вырабатываемых чисел и критерии случайности. Эти группы критериев в основном охватывают проверку тех свойств, которыми должны обладать случайные числа.

С помощью критериев согласия проверятся гипотеза о том, что выборка x₀, x₁, …, x_n произведена из генеральной совокупности с определенным распределением вероятностей.

Наиболее часто применяются для этой цели критерий согласия Пирсона (критерий частот) и критерии, учитывающие различные свойства данной генеральной совокупности.

Если проверяется равномерность распределения на интервале [0, 1], то случайные числа должны удовлетворять следующим свойствам:

1)  среднее значение чисел не должно существенно отличаться от 1/2;

2)  среднее значение квадратов чисел не должно существенно отличаться от 1/3;

3)  дисперсия чисел не должна существенно отличаться от 1/12;

4)  коэффициенты ассиметрии и эксцесса не должны существенно отличаться соответственно от 0 и -1.2;

5)  разделим интервал [0, 1] на m непересекающихся множеств Х₁, ..., Х_m:

,

.

Доля чисел в последовательности x₀, x₁, … которая попадает в интервал

  , должна несущественно отличаться от величины 

.

Рассмотрим наиболее часто употребляемый критерий .

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

Зная теоретический закон распределения, всегда можно определить вероятность p_i попадания случайной величины в интервал Х_i.

Очевидно, что p₁+...+p_m=1, а n₁+...+n_m=n. Тогда теоретическое число значений случайной величины Х, попавших в интервал Х_i можно определить как np_i.

Результаты проведенных расчетов обычно объединяют в следующую таблицу:

Интервалы	…	Хi	…
Эмпирические частоты	…	ni	…
Теоретические частоты	…	npi	…

Если эмпирические частоты сильно отличаются от теоретических, то проверяемую гипотезу о законе распределения отвергают, в противоположном случае - принимают.

В качестве меры отклонения эмпирических значений от теоретических выбирают величину

,

которая при n   имеет распределение с k=(m-1) степенями свободы.

Правило применения критерия сводится к следующему. Рассчитывается значение . При этом необходимым условием является наличие в каждом из интервалов по меньшей мере 10-15 наблюдений.

Обычно фиксируют достаточно большую вероятность a, которую называют доверительной вероятностью или коэффициентом доверия. Вероятность 1-a называют уровнем значимости. Это означает, что в рассматриваемой задаче событие с вероятностью большей или равной a считают достоверным, а событие с вероятностью 1-a невозможным при единичном испытании.

Далее выбирается уровень значимости и по таблице распределения c² определяется

  . 

Если

,

 то этот результат не противоречит гипотезе и она принимается; если же

,

то это означает, что (наступило невозможное событие, и) гипотеза должна быть отвергнута.

Этот вывод зависит от выбранной доверительной вероятности и поэтому не носит абсолютного характера. Чаще других используют доверительные вероятности 0,95 и 0,99; соответствующие уровни значимости называют 5%-ным и 1%-ным уровнями.

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