Главная > Математика > Численные методы Монте-Карло
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2.3. Оценка L для алгоритмов вида ...

Для оценки длины отрезка апериодичности, характерного для последовательностей вида (4), можно воспользоваться следующей элементарной вероятностной моделью. Пусть имеется конечное множество, содержащее N различных чисел. Произведем последовательность независимых опытов, в каждом из которых из этого множества извлекается и записывается одно число. Вероятность извлечения каждого числа в каждом из опытов равна (выборка с возвратом). Обозначим через L случайную величину: номер опыта, в котором впервые будет извлечено уже записанное число.

Теорема 3. В указанной модели для любого

Доказательство. Обозначим записанные числа через Легко вычислить вероятность того, что L окажется равным где :

так как

а вероятность того, что совпадет с одним из различных чисел равна

Фиксируем произвольное и пусть . Тогда

Легко видеть, что

Так как то поэтому

и интересующую нас вероятность можно записать в форме

Рассмотрим теперь разбиение интервала точками где (рис. 7), и составим интегральную сумму для функции этому разбиению:

Из неравенства видно, что при

Рис. 7.

. Поэтому последнее слагаемое в этой сумме стремится при к нулю, и

Отсюда и из соотношения (9) следует (8). Теорема доказана.

Следствие. Так как математическое ожидание неотрицательной случайной величины с функцией распределения равно , то из (8) следует, что при

Рассмотренная в настоящем пункте модель предложена в статье [75], там же получена формула (10), а теорема 3 доказана Л. Н. Большевым и Д. И. Голенко. Несмотря на грубость модели, оценки (8) и (10) оказались полезными во многих опытах, связанных со способами «перемешивания», когда теоретико-числовая оценка периода практически невозможна, В качестве N выбирается количество возможных значений функции в конкретной ЭВМ; тогда можно ожидать, что длина отрезка апериодичности окажется порядка

Например, в методе п. 2.2.3 на ЭВМ «Стрела» значение функции Ф( (до нормализации) записывается в форме значит, На практике для ряда подобных алгоритмов были экспериментально обнаружены отрезки апериодичности длиной от до 3,5 105

Замечание. В книге [19] параграф, содержащий теорему 3, называется «Критерий проверки периодичности последовательности псевдослучайных чисел». Однако по этому «критерию» судить о качестве псевдослучайных чисел нельзя. У некоторых вполне удовлетворительных последовательностей, полученных по формуле (б), длина L гораздо больше, чем оценка (10) (фактически ). В то же время некоторые последовательности с не удовлетворяют ни одному из основных тестов § 3.

<< Предыдущий параграф Следующий параграф >>
Оглавление