Соболь И.М. Численные методы Монте-Карло (1973), страница 7

Г!о значениям уы уь уь и уо можно сосчитать величины 9!ау для нескольких проверок. Самые важные среди них (индсксы М или М' обычно не пишут): = ~~ Х ( ' — 0 )дг) с 9 степенями свободы, соответствующая проверке ча» стот, и У'= —, Х (У! — 001)У) 100 т,т=о с 99 степенями свободы, соответствующая проверке пар. Кроме того, иногда вычисляют величины 9 9 )1'=0 1,, Х ( ы — 0,1Л")' ° у.'=0 1„,Х (.; — 0,1й')'-, 0,1а' 0,! 'т=о каждая с 9 степенями свободы; эти величины соответствуют проверке частот среди цифр с нечетными и четными номерами. Используют также критерий независимости строк и столбцов матрицы у!;, которому соответствует величина = [х,—,",.,-~ с 81 степенью свободы [44) Впрочем, последний критерий иа ираки!ке оказывается весьма близким к проверке пар Второй тест (проверка серий), Сосчитаем количества и, серий длины 1 в последовательности цифр еь ..., Ел при 1=1, 2,,, пт, и пусть и, ! — количество серий с 1)т+1 (они объединяются в одну группу).

Обозначим обгцее количество серий через и= =и!+ .. +п +л бйг Величина у' с пт степенями свободы вычисляется по формуле Х~= '~ + т (и, — лР,) (л,„! ! — !!Ры,!) ~й ЛР! ЛРл!+! где р,=9 10 ', р„+! = 10 — "'). 1 и стлтистичесхля пРоверкл случлиных "!исел 39 Обозна юм через Л случайнуго длину серии, начпнающейся с цифры ел+г(т. е. ел+г~ел). Очевидно, рг Р (в =1) = Р (ел+!= ел„г —...—— ел+гФвл ьг+г) =(01)1 — '09=9 10 — с и от номера серии не-зависит. Такилг образом, каждая ссрия мозкет с вероятностью Рг иметь длину 1, Количество Шсерий длины ! среди л серий подюняется биномиальному распределению и Унлг =пр, В качестве примера в табл.

2 приведено распределение по длине серий, полученных при проверке Ф=-50 000 |сел в (7о). Таблица 2 и' 4 и, ча чг ! О Теоретическис злю чення Эмпирические зна- чеюю 45 000 405 40 оОО йгг! > 40 503 45 035 сш!0 417 40 яРГ 40 531,5 ЛгГ)53,2 405,3 45,0 По даю ым последних двух с~рок вычисляеч Х'=1,39. При и=3 атому зиачен~по соответствует Р=0,7!. л(опол интел ьн ы е тесты. В качестве дополнительных тестов следует в первую очередь рекомендовать проверку частот независимых троек зз,+гез,егезлчз, затем чегверок е4, ге44 ге44«аещ.4 и т. д.— основания для такой рекомендации приведены в 9 4 гл. 7. Так как количество различных троек, четверок и т.

д. весьма велико ()Оз, )04, ...), то подсчет всех типов групп имеет смысл проводить лишь для достаточно больших Ф. Пря меньших У группы можно объединять по различным признакам. Например, при упомянутой выше проверке комбинаций четверки и,+! ... е,44 классифицируются по количеству совпадающих цифр в группе (признак, напоминающий комбинацив при игре в покер). Во многих работах предлагаются различные дополшпельные тесты. Имеет место даже чрезмерное увлечение такими тестами.

Несмотря на справедливость принципа «каши маслом не испортишь», надо четко представлять себе, что все такие тесты только необходимы. Положительный результат любого теста означает только, что этот результат не противоречит гипотезе 4О ПОЛУЧЕННЕ СЛУЧАЙНЫХ ВЕЛНЧНН НА ЭВМ !ГЛ Г о случайности цифр еь ..., е, но, может быть, какойнпбудь другой тест эту гипотезу опровергнет...'). З.З.

Проверка псевдослучайных чисел. В качестве основных тестов для проверки псевдослучайных чисел , у„используют те же тесты, что и для проверки таблиц; проверяются первые десятичные цифры а,= =Ц(10т,). гйигурирующая в первом тесте величина Уо Рааиа КОЛИЧЕСТВУ ПаР (У„Н тт,) таКИХ, ЧтО О,! с -ум-1(0,1(г+1), 0,1 ! 'уз,(0,! (!+1). более детальную проверку распределения чисел уь ..., т„можно осуществить с помощью критерия соз. Если расположить эти числа в вариационвый ряд гн! < ум! < < 7<и! то нз (20) вытекает, что Однако, как уже отмечалось в п, 3.1,4, при очень боль= ших ггг построение варнационного ряда весьма трудоемко. Естественно, что прн проверке псевдослучайных чисел всегда используют различные дополнительные тесты для проверки последующих десятичных цифр у,. Иногда десятичные (нли двоичные) цифры чисел у, выделяюг и проверяют независимо. Конечно, лучше было бы использовать тесты и.

3.2 с более мелким разбиением, но уже при совместной проверке двух десятичных цифр пришлось бы вычислять матрицу (ув) размером 100К ;зг',!00. Поэтому на практике ограничиваются более простыми проверками, и далекие цифры чисел у, обычно оказываются хуже проверенными. В пользу указанной системы тестов можно привести аргумент практического характера: в литературе, пожалуй, нет примеров, когда числа, удовлетворяющие всем '! Более того, имея конечную группу пнфр еь ... вй, всегда можно придумать такой тест, завислп!ий ог конкрвгнал значений аь ..., ан, который опровергает нашу гипотезу. Но не надо такие тесты придумывать!, 3! стлтистичсскАя пРОВеРкА случаи>тых чисгл 4! тестам, оказались бы непригоднымн для решения конкретной задачи (в которой не предъявлялись повышенные требования к точности решения); есть, однако, примеры неудачных расчетов с помошыо чисел, которые не удовлетворяли одному из тестов.

В частности, из-за того, что числа, упомянутые в п. 2.2.4, пе удовлетворяли тесту проверки пар, плохо моделировалось нормальное распределение. Таким образом, строго говоря, разумность приведенной системы тестов — факт эмпирический. В действительности эти тесты не гарантируют универсальной при'годности чисел. Поэтому иногда целесообразно вводить дополнительные тесты, связанные с характером решаемых задач. Впрочем, успешное решение нужной задачи — самая лучшая проверка случайных чисел. 3.4. О проверке датчиков случайных чисел. Для проверки чисел, выдаваемых датчиком, можно использовать те же тесты, что и для проверки псевдослучайных чисел. Особенность проверки датчиков в том, что проверяются не те числа, которые используются в счете.

Поэтому, кроме проверки «качества» выдаваемых чисел, должна еще как-то гарантироваться устойчивость работы датчика. Мы не будем останавливаться па технических способах контроля. Отметим только, что обычно расчет тестов, вроде рассмотренных в пп. 3.2 и 3.3, проводят и до, и после расчета нужной задачи, если она не слишком продолжительна во времени.

З.б. О проверке большик массивов случайных чисел. Так как в расчетах часто нспользуетгя не вся таблица, а только часть ее, то имеет смысл проверить также части таблицы. Например, таблицу, содсржашую А> цифр, разбивают на з частей по АГ> =А>/з цифр и проверяют каждую нз этих частей. Если з)50, то вполне вероятно среди значений ХА>, СОответСтвуюШих одному !Каяону-ннбудь) крите- 2 рию, встретить значение, отвечаюшее р(0,0!. Это не означает, что вся >аблица плоха; просто данную часть не надо использовать как самостоятельную таблицу в расчетах, в которых требуется маг> случайных цифр. Можно проверить, согласуются лн з полученных значений с теоретическим распределением Хз для данного критерия.

Такая проверна нередко используется в качестве дополнительного теста. И с этой точки зрения ясно, что отдельные «плохие» значения х А> > обязаны появляться, если гипотеза справедлива и з достаточно велико. 42 полученни Глучанн!!х Величин нл эпм !Гл ! Некоторые авторы цредлагвюг использовать гакую проверку таблицы по частнм вместо проверки таблицы как целого.

К сожалея>но, это неверная рекомендации. Автору известен пример, когда 500000 цифр проверялись и как целая таблица и по частям: 20 частей по 25 000 цифр. Все части удовлетворяла всем пяти хритерням первого теста (п. 3.2), распределение полученных значений ХН для 2 наждого из крвтернев хорошо согласовалось с теоретическим распределением )(2. Однако весь массив из 500 000 цифр не удовлетворял ни одному из критериев первого теста (причем для одного из критериев было Р(О,ООООП) Такому несколько неожиданному результату можно дать следующее объяснение Можно предположить, что рассматриваемая последовательность цифр имеет распределение, несколько отличающееся от равномерного, но для расчета по Й, цифрам такое отличие допуствмо. Отсюда не следует, что зто отличие по-презкнему будет допустимым для расчета, в котором используются АГ»М~ цифр.

Наоборот, если увеличение количества цифр вызвано желанием увеличить точность расчета, то ясно, что при достаточно большом Л) отличие зто станет недопустимыч Итак, к большим массивам случайных цифр (нли чисел) предьявляются большие требования.

Этот факт хорошо известен практикам: подобрать хорошую псевдослучайную последовательность, содержащую 10' — 1О' чисел, гораздо проще, чем подобрать такую же последовательность, содерхгащую 102 — !Оз чисел "). Это следует иметь в виду также прп проверке датчиков случайных чисел: нехорошо проверять датчик тестами, охнатывающими !О' — 1О' чисел, а в расчете использовать !О' †!О' чисел. Упражнения к главе 1 1, Доказать, что коэффициент корреляции случайных величин у и Чс Д(ну) при целом д»1 равен 1(е. 2.

Как с помощью таблицы случайных нифр (стр. 295) моделировать последовательность независимых испытаний, в каждом из которых веуоятность наступления некоторого события Л равна Р(Л) =0,7п2? 3. Предполсзким, что количество ч элементарных частиц, попадающих в детектор за время Ы, подчиняется распределению Пуассона со средним значением йзт=айй Пусть Ц=У(шоб2]. Доказать, что при абг- со вероятности Р(В=О) и Р(2=1) стремятся к 172. На этом принципе построены некоторые датчики случайных цифр.

4. Рассмотреть случайную вели ~яму Л=Д(еу') с целым е и доказать, что Р(Ч(х) =х+угх!д+ 0(х/ !' й) при х)0 н а -~со (К. Д. Точер (!74)). ~) Иногда высказывают мнение, что критерии 72 нли ыз слишком жестки при очень больших Аг. Однако, как показывают формулы (27) и (30) гл. 7, именно постоянство Хм или шм регулирует упо- 2 2 мянутое в тексте повышение требований к большим массивам случайных чисел, если требовать, чтобы погрешности, фигурирующие в этих формулах, убывали как 1()гй1.