Генератор случайных чисел, иллюстрация закона больших чисел.

Оглавление
Введение
Генератор псевдослучайных чисел
ГПСЧ с источником энтропии или ГСЧ
Физические ГСЧ
Табличные ГСЧ
Алгоритмические ГСЧ
Закон больших чисел
Список литературы

Генератор случайных чисел, иллюстрация закона больших чисел.

где a,с,т - натуральные числа, mod функция деления по модулю. Наибольший период датчика равен т однако, он зависит от a и с. Ясно, что чем больше период, тем лучше; однако реально наибольшее т ограничено разрядной сеткой ЭВМ. В любом случае используемая в конкретной задаче выборка случайных чисел должна быть короче периода, иначе задача будет решена неверно. Обычно генераторы выдают отношение хп/т, которое всегда меньше 1, т.е. генерируют последовательность псевдослучайных чисел на отрезке [0, 1]. Вопрос о случайности конечной последовательности чисел гораздо сложнее, чем выглядит на первый взгляд. Так последовательно генерируемые псевдослучайные числа могут появляться не идеально равномерно, а проявлять тенденцию к образованию групп. Один из тестов на
равномерность состоит в делении отрезка [0, 1] на М равных частей­ - «корзин», и помещения каждого нового числа в соответствующую «корзину». В итоге получается гистограмма, в которой высота каждого столбика пропорциональна количеству попавших в «корзину» случайных чисел. Генерация псевдослучайных чисел с использованием математического пакета MathCad представляется следующим образом:
Для генерации псевдослучайных чисел используют метод Неймана. Необходимо генерировать случайные числа с некоторой функцией распределения f(х) на интервале [a, b]. Введем функцию сравнения w(х)=const. Генерируем два случайных числа, определяющих
равновероятные координаты в прямоугольнике АВСD с помощью генератора: х=a+(b-a)r; у=wr. Если точка М(х,у) не попадает под кривую f(х), то ее отбрасывают. В случае попадания точки М(х,у) по кривую f(х), ее оставляют. При проведении компьютерного моделирования широко используется метод статистических испытаний (Монте-Карло). Метод Монте-Карло относится к численным методам. Этот метод
основан на получении большого числа реализаций случайного (стохастического) процесса, который проводится таким образом, чтобы его вероятностные характеристики­ совпадали с аналогичными величинами решаемой задачи. Метод Монте-Карло (вариационный) используют для вычисления многочисленных интегралов при решении уравнения Шредингера, моделирования облучения твердых тел ионами в приближении бинарных столкновений, разряженных газов. Это лишь некоторые приложения рассматриваемого метода. Отметим, что кроме алгоритмического метода генерации случайных чисел, используют аппаратный и табличный методы. Аппаратный метод: в нем генератор представляет собой прибор, в котором есть источник шума (теплового, квантового, радиоактивного). Тепловой шум может создавать радиолампа или полупроводниковый прибор, однако данный вариант не
очень надежен, так как накладываются шумы от внешней температуры. Источник квантового шума - туннельный диод или какой-либо другой полупроводниковый прибор. Это самый дешевый способ. Есть также проблема надежности из-за влияния окружающей среды.
Радиоактивный способ - надежно, но дорого. Аппарат создает электронные импульсы, величина между которыми меняется случайным образом. Далее специальная схема оцифровки
Генераторы случайных чисел по способу получения чисел делятся на:
физические;
табличные;
алгоритмические.
Физические ГСЧ
Примером физических ГСЧ могут служить: монета («орел» — 1, «решка» — 0); игральные кости; поделенный на секторы с цифрами барабан со стрелкой; аппаратурный генератор шума (ГШ), в качестве которого используют шумящее тепловое устройство, например, транзистор/
Схема аппаратного метода генерации случайных чисел
Диаграмма получения случайных чисел аппаратным методом
Табличные ГСЧ
Табличные ГСЧ в качестве источника случайных чисел используют специальным образом составленные таблицы, содержащие проверенные некоррелированные, то есть никак не зависящие друг от друга, цифры. В таблице приведен небольшой фрагмент такой таблицы. Обходя таблицу слева направо сверху вниз, можно получать равномерно распределенные от 0 до 1 случайные числа с нужным числом знаков после запятой (в нашем примере мы используем для каждого числа по три знака). Так как цифры в таблице не зависят друг от друга, то таблицу можно обходить разными способами, например, сверху вниз, или справа налево, или, скажем, можно выбирать цифры, находящиеся на четных позициях.
Случайные цифры
Равномерно распределенные
от 0 до 1 случайные числа
9
2
9
2
4
2
6
0.929
9
5
7
3
4
9
3
0.204
5
9
1
6
6
5
7
6
0.269
…
…
Достоинство данного метода в том, что он дает действительно случайные числа, так как таблица содержит проверенные некоррелированные цифры. Недостатки метода: для хранения большого количества цифр требуется много памяти; большие трудности порождения и проверки такого рода таблиц, повторы при использовании таблицы уже не гарантируют случайности числовой последовательности, а значит, и надежности результата.
Алгоритмические ГСЧ
Числа, генерируемые с помощью этих ГСЧ, всегда являются псевдослучайными (или квазислучайными), то есть каждое последующее сгенерированное число зависит от предыдущего:
ri + 1 = f(ri).
Последовательности, составленные из таких чисел, образуют петли, то есть обязательно существует цикл, повторяющийся бесконечное число раз. Повторяющиеся циклы называются периодами.
Достоинством данных ГСЧ является быстродействие; генераторы практически не требуют ресурсов памяти, компактны. Недостатки: числа нельзя в полной мере назвать случайными, поскольку между ними имеется зависимость, а также наличие периодов в последовательности квазислучайных чисел.
Закон больших чисел
Основными понятиями теории вероятностей являются понятия случайного события и случайной величины. При этом предсказать заранее результат испытания, в котором может появиться или не появиться то или иное событие или какое-либо определенное значение случайной величины, невозможно, так как исход испытания зависит от многих случайных причин, не поддающихся учету.
Однако при неоднократном повторении испытаний наблюдаются закономерности, свойственные массовым случайным явлениям. Эти закономерности обладают свойством устойчивости. Суть этого свойства состоит в том, что конкретные особенности каждого отдельного случайного явления почти не сказываются на среднем результате большой массы подобных явлений, а характеристики случайных событий и случайных величин, наблюдаемых в испытаниях, при неограниченном увеличении числа испытаний становятся практически не случайными.
Пусть производится большая серия однотипных опытов. Исход каждого отдельного опыта является случайным, неопределенным. Однако, несмотря на это, средний результат всей серии опытов утрачивает случайный характер, становится закономерным.
Для практики очень важно знание условий, при выполнении которых совокупное действие очень многих случайных причин приводит к результату, почти не зависящему от случая, так как позволяет предвидеть ход явлений. Эти условия и указываются в теоремах, носящих общее название закона больших чисел.
Под законом больших чисел не следует понимать какой-то один общий закон, связанный с большими числами. Закон больших чисел - это обобщенное название нескольких теорем, из которых следует, что при неограниченном увеличении числа испытаний средние величины стремятся к некоторым постоянным.
К ним относятся теоремы Чебышева и Бернулли. Теорема Чебышева является наиболее общим законом больших чисел, теорема Бернулли - простейшим.
В основе доказательства теорем, объединенных термином "закон больших чисел", лежит неравенство Чебышева, по которому устанавливается вероятность отклонения Х от ее математического ожидания:
Пример. Устройство состоит из 100 независимо работающих элементов. Вероятность отказа каждого элемента за время Т равна 0,03. Оценить вероятность того, что абсолютная величина разности между числом (математическом ожиданием) отказов за время Т окажется: а) меньше двух; б) не меньше двух.
Решение. а). Обозначим через Х число отказавших элементов за время Т. Тогда М[Х] = np = 100 ? 0,03 = 3 и D[X] = npq = 100 ? 0,03 ? 0,97 = 2,91 (см. пример ). Воспользуемся неравенством Чебышева:
подставив в него M[X] = 3, D[X] = 2,91, = 2, получим
б). События и противоположны, поэтому сумма их вероятностей равна единице. Следовательно,
Пример . Оценить вероятность события - M[X]< 3, где - среднее квадратичное отклонение случайной величины X.
Решение. Полагая = 3, получим в правой части неравенства число Таким образом, вероятность события не меньше, чем
В действительности для подавляющего большинства встречающихся на практике случайных величин эта вероятность значительно ближе к единице, чем