3. 1. Метод статистических испытаний. 2 страница

* Например:

i
	0,9876	0,97 5353 76
	0,5353	0,28 6546 09
	0,6546	0,42 8501 16
	0,8501	0,72 2670 01
	0,2670	0,07 1289 00

* Этот самый первый метод предложил в 1946 году математик Джон фон Нейман.

* В начале 50-х годов некоторые ученые проводили эксперименты с методом середины квадратов. Оказалось, что вырабатываемые последовательности имеют

* тенденцию вырождаться в короткие циклы повторяющихся чисел.

* Вместе с тем, отметим, что работая с 38-ми разрядными двоичными числами, Н. Метрополис обнаружил последовательность, состоящую из 750000 неодинаковых ПСЧ. Это подтверждает, что применяя данный метод, можно получить полезные результаты. Тем не менее без предварительных трудоемких вычислений ему не стоит излишне доверять.

* Метод выделения дробной части произведения натуральных чисел на иррациональное число.

* Последовательность ПСЧ вырабатывается с помощью соотношения:

* , где - дробная часть числа z, или или и т. д.

* Числа полученной последовательности имеют хорошую равномерность, но неудовлетворительную случайность.

* Метод перемешивания.

* Метод основан на перемешивании содержимого разрядов мантиссы ПСЧ и использовании логических операций ЭВМ (сдвига, сложения по модулю 2, логического сложения).

* Например: случайное число x сдвигается вправо и влево на j разрядов и результаты сдвига поразрядно складываются по модулю 2. Существуют и более сложные алгоритмы получения ПСЧ методом перемешивания.

* Недостаток данного метода, как и методов рассмотренных выше, в том, что для него нельзя теоретически гарантировать выполнение определенных свойств случайной последовательности и отсутствие вырождения.

* Метод вычетов.

* Наилучшие из известных сегодня датчиков случайных чисел представляют собой частные случаи следующей схемы, предложенной Д. Х. Леммером в 1948 году. Искомая последовательность ПСЧ x получается из соотношения:

* , где .

* Специального упоминания заслуживает частный случай С=0 (то есть ), тогда процесс выработки случайных чисел происходит несколько быстрее. Ограничение С=0 уменьшает длину периода последовательности, но при этом все еще можно получить большой период.

* Вырабатываемая последовательность ПСЧ не всегда оказывается удовлетворительной, если выбирать значения произвольно.

* Например, при , m=10 последовательность выглядит:

i					...
					...
	0,6	0,9	0,7	0,6	...

При выборе необходимо соблюдать некоторые правила, руководствуясь следующими теоретически обоснованными принципами:

1) В качестве начального значения X необходимо брать целое число , причем для случая С=0 числа и должны быть взаимно простыми.

2) Число m должно быть достаточно велико, поскольку количество различных значений не может быть больше m. Другой фактор, влияющий на выбор m: скорость выработки чисел. Так как деление - сравнительно медленная операция, то ее можно избежать при вычислении mod m за счет удобного выбора m, приняв его равным размеру слова (то есть на единицу больше максимального числа, размещающегося в слове ЭВМ).

Однако при выборе младшие разряды чисел ведут себя менее случайно, чем старшие.

Подобной ситуации не возникает, когда . В этом случае младшие биты ведут себя так же случайно, как и старшие.

Другая возможность - это выбор в качестве m наибольшего простого числа, меньшего чем .

Для большинства приложений младшие биты не существенны и выбор является вполне удовлетворительным.

3) Выбор значения . Для того, чтобы получить последовательность ПСЧ с максимально возможным периодом равным m, необходимо выполнить условия:

* ( -1) должно быть кратно r, для любого простого r, являющегося делителем m,

* ( -1) должно быть кратно 4, если m кратно 4.

Если , то значение выбирается таким, чтобы . При таком выборе величины гарантируется, что датчик случайных чисел выдаст все ( при С=0) возможных различных значений x прежде, чем они начнут повторяться.

Множитель должен превосходить величину , желательно чтобы он был больше чем , но меньше чем .

4) Выбор значения С:

Числа С и m должны быть взаимно простыми, если кроме того , коэффициент корреляции между числами последовательности будет небольшим. С обоснованием этих принципов можно ознакомиться в [3].

Метод вычетов может быть реализован по-разному путем обобщения схемы, предложенной Д. Х. Леммером.

Например: Для случая, когда m представляется степенью двойки интересный квадратичный метод предложил Р. Ковэю.

mod .

Этот метод почти идентичен методу середины квадратов с той разницей, что он гарантирует большой период.

Простейший случай зависимости от более чем одного из предыдущих значений реализуется в последовательности Фибоначчи:

mod m.

Однако Проверка показала, что числа получаемые из этого соотношения являются недостаточно случайными, поэтому в настоящее время данная формула интересна главным образом, как прекрасный “плохой пример”.

Метод вычетов позволяет получить достаточно большие последовательности неповторяющихся ПСЧ. Обычно, если m приближается к размеру машинного слова, мы имеем дело с периодами порядка и больше.

Программные ДСЧ равномерно распределенные в [0,1] оформляются в виде процедур с именем RAND.

Пример: Формализованная форма ДСЧ по методу вычетов имеет вид:

Отметим, что ; - начальное значение X. должно принадлежать , иначе первое значение X будет

неслучайным.

С помощью данного датчика можно получить две последовательности чисел максимальной длинны если - нечетное число.

Для перехода от одной нечетной последовательности к другой, необходимо прибавить к любому числу первой последовательности число 2.

Выбор в качестве четного числа нецелесообразен, поскольку при этом длина последовательности уменьшается и может принимать значения .

Это обусловленно следующим. Если кратно , то и все числа последовательности так же будут кратны .

Работа ДСЧ в цикле может быть представлена следующим образом:

Рис. 3.1.5

3.1.4 Проверка ДСЧ RAND.

3.1.4.1 Этапы проверки качества равномерно

распределенных ПСЧ.

Многие предлагаемые ДСЧ недостаточно хороши. Пользователи как правило используют эти датчики ничего не зная об их недостатках, что приводит к ошибочным результатам вычислений.

Например, в математическое обеспечение ЭВМ серии EC был включен датчик RANDU, рекомендованный специалистами IBM:

Позже было дано строгое доказательство непригодности датчика. Поэтому, прежде чем использовать ДСЧ в решении задачи методом статистических испытаний с заданной точностью e и достоверностью a необходимо исследовать его на пригодность.

В первую очередь необходимо определить количество всех различных чисел ПСЧ (длину отрезка апериодичности - L), вырабатываемых ДСЧ.

Дело в том, что ДСЧ может быть использован в той или иной задаче лишь в случае, если выполняется условие , где N - количество случайных чисел необходимое для решения задачи статистическим методом с учетом заданной точности e и достоверности a.

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

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

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

В качестве таких предположений принимаются:

1) гипотеза о “случайности” ПСЧ;

2) гипотеза о “равномерности” закона распределения ПСЧ;

3) гипотеза о некоррелированности ПСЧ и отдельных разрядов этих чисел.

Для проверки гипотез о “случайности” и “равномерности” закона распределения ПСЧ наиболее часто применяется критерий согласия (“хи-квадрат”).

1.1.4.2. Критерий согласия - Пирсона.

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

Идея применения критерия согласия заключается в следующем.

Предположим, что произведено N независимых опытов, в каждом из которых СВ X приняла определенное значение. Результаты опытов оформлены в виде статистического ряда:

			...
			...
			...

На основании данного статистического материала необходимо проверить гипотезу H, состоящую в том, что СВ X подчиняется некоторому определенному теоретическому закону распределения. Этот закон может быть задан в той или иной форме: например, в виде плотности распределения вероятностей f(x), или же в виде совокупности вероятностей , где - вероятность того, что СВ X попадает в пределы j-ого разряда.

Между статистическим и теоретическим распределениями неизбежны некоторые расхождения.

Необходимо ответить на вопрос: объясняются ли эти расхождения только случайными обстоятельствами, связанными с ограниченным числом наблюдений, или они являются существенными и связаны с тем, что гипотеза о подчинении СВ X данному закону распределения не верна.

Для того, чтобы принять или опровергнуть гипотезу H, рассмотрим некоторую величину U, характеризующую степень расхождения теоретического и статического распределений. В качестве величины U, например, можно взять сумму квадратов отклонений теоретических вероятностей от соответствующих наблюдаемых частот с некоторыми коэффициентами (“весами”) :

Коэффициенты (“веса” разрядов) вводятся потому, что в общем случае отклонения, относящиеся к различным разрядам, нельзя считать равноправными по значимости.

Действительно, одно и то же по абсолютной величине отклонение может быть малозначительным,

если сама вероятность велика, и очень заметным, если она мала. Поэтому естественно “веса” взять обратно пропорциональным вероятностям разрядов .

К. Пирсон показал, что если , то при больших N закон распределения величины U обладает весьма простыми свойствами: он практически не зависит от функции распределения F(x) и от числа опытов N, а зависит только от числа разрядов M, а именно, этот закон при увеличении N приближается к так называемому “распределению ”.

При таком выборе коэффициентов мера расхождения обычно обозначается :

(9)

Для удобства вычислений (чтобы не иметь дела с дробными величинами с большим числом нулей) можно ввести N под знак суммы и, учитывая, что привести формулу (9) к виду:

(10)

Используя тождество: и равенства:

можно преобразовать формулу (10) к виду:

Причем, в большинстве случаев такая запись облегчает вычисления.

Какие же рассчитанные значения можно считать разумными при условии если гипотеза H верна?

Для распределения составлены специальные таблицы. Пользуясь этими таблицами, можно для каждого значения и числа степеней свободы l найти вероятность P того, что величина, распределенная по закону , превзойдет это значение.

В данной таблице входами являются:

- число степеней свободы (независимых слагаемых) l, которое равно числу разрядов k минус число наложенных связей S;

- значение вероятности .

Числа, стоящие в таблице, представляют собой соответствующие значения .

Рис. 3.1.6

Для того, чтобы дать правило проверки состоятельности гипотезы H с достоверностью a, определим табличное значение для и сопоставим его с вычисленным значением .

Тогда для случая можно с достоверностью a предположить, что расхождение между статистическим и теоретическим распределением обусловлено чисто случайными причинами, т. е. гипотеза H состоятельна (не противоречит опытным данным).

При следует считать гипотезу H противо-речащей опытным данным и она отбрасывается как несостоятельная.

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

Пример: Произведено N=100 независимых опытов, в каждом из которых СВ X приняла определенное значение. Результаты опытов оформлены в виде статистического ряда:

	[2;4)	[4;6)	[6;8)	[8;10)	[10;12]

Необходимо с достоверностью a=0,95 проверить состоятельность гипотезы о равномерном распределении СВ X в интервале [2;12].

Решение:

В соответствии с гипотезой о равномерном распределении .

Определяем меру расовмещения:

Определяем табличное значение .

Так как то с достоверностью a=0,95 можно предположить, что статистический материал не противоречит гипотезе о равномерном распределении СВ X в интервале [2;12].

Разумеется имеет смысл применять критерий , основанный на предельном распределении меры расхождения при , когда количество испытаний N достаточно велико. На практике достаточно большими можно считать такие значения N, при которых любое из не менее 5-10.

Применение критерия согласия - Пирсона для проверки гипотез о “случайности” и “равномерности” закона распределения ПСЧ.

Исходные данные проверки:

- ДСЧ;

- количество проверяемых чисел - N;

- количество двоичных разрядов в представлении числа - К;

- количество подинтервалов (разрядов) интервала [0;1] - M;

Последовательность проверки:

1. Определяется абсолютная статистическая частота попадания СВ в j-ый разряд ( или );

2. Вычисляется теоретическое значение (в соответствии с гипотезой) вероятности попадания СВ в j-ый разряд - ;

3.Вычисляется значение меры расхождения где q равно либо К, либо М;

4. Вычисленное значение сравнивается с табличным , где a - заданная достоверность; l - число степеней свободы распределения или число независимых слагаемых , т. е. l равно либо К, либо М-1.

Если - гипотеза состоятельна, т. е. достоверна;

если - гипотеза несостоятельна, т. е.

недостоверна.

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

3.1.4.3 Определение длинны отрезка апериодичности.

В общем случае последовательность чисел, выдаваемая ДСЧ представима в виде