Псевдовипадкові числа
Нехай .- послідовність незалежних випадкових величин (білий шум у вузькому розумінні), кожна з яких має рівномірний розподіл з щільністю
, ,
В рамках методу статистичних випробувань введену вище послідовність називають випадковими числами (або базовим білим шумом).
Основна проблема імітаційного моделювання випадкових чисел (і взагалі, будь-яких випадкових елементів) на ЕОМ полягає в тому, що всі сучасні ЕОМ функціонують за певними алгоритмами, заданими програмним чи апаратним способом. Алгоритм - це детермінована впорядкована сукупність команд, інструкцій і операторів, яка задає обчислювальний чи будь-який інший інформаційний процес (який називається, в даному випадку, алгоритмічним), який починається з вводу певних вхідних даних і спрямований на отримання результату, що повністю визначається цими вхідними даними.
Таким чином, реалізувати стохастичний експеримент на ЕОМ універсального призначення з допомогою якого-небудь алгоритму, по суті, неможливо. Тому, замість випадкових чисел, використовують, так звані, псевдовипадкові числа, які отримуються за цілком невипадковим алгоритмом, але мають властивості, дуже подібні до властивостей реалізацій випадкових чисел.
Одним з найбільш
вивчених у теоретичному плані та вживаних
у практичних застосуваннях методів
генерування на ЕОМ псевдовипадкових
чисел, є метод лишків (лінійний конгруентний
метод), відповідно до якого спочатку
отримують послідовність натуральних
чисел
за рекурентним алгоритмом виду:
,
де
,
M,N - задані
взаємно прості натуральні числа.
Послідовність
псевдовипадкових чисел
отримується як
(1.2)
У чому полягає генерування
ББШ на основі методу лишків.
Генератори випадкових чисел.
Існують три способи дістати рівномірну випадкову послідовність чисел, розподілених на відрізку [0, 1]: табличний, програмний і фізичне генерування.
Фізичний пристрій чи програма на ЕОМ породження РВП [0, 1] називається генератором (датчиком) випадкових чисел.
Фізичне генерування випадкових чисел використовувалося людством уже давно. До появи ЕОМ як генератори випадкових чисел використовувалися різні механічні пристрої — колесо рулетки, спеціальні гральні кості та пристрої, які перемішували фішки з номерами, що витягувалися вручну по одній. Деякі з таких засобів дають цілком задовільні результати в разі невеликої кількості фішок або чисел.
Останнім часом фізичне генерування РВП [0, 1] базується на використанні формули (5.10), згідно з якою при генеруванні наступного m-розрядного випадкового двійкового числа необхідно дістати m реалізацій випадкової величини Z, що набуває значення 0 або 1 з однаковою ймовірністю 0,5.
Реалізації
випадкової величини Z можна дістати,
скориставшись такими фізичними явищами:
— радіоактивне випромінювання;
— власні шуми електронних ламп.
Сутність методу, що грунтується на радіоактивному випромінюванні, полягає у такому.
1. Обирається джерело радіоактивного випромінювання з інтенсивністю l.
2. Залежно від значення l обирається відрізок часу Dt.
3. За допомогою лічильника визначається кількість часточок, що їх випромінює джерело за час Dt.
4. Застосовується схема:
1) якщо кількість часточок парна, то = 0;
2) якщо кількість часточок непарна, то = 1.
Примітка. Лічильник часточок працює у двійковій системі числення, тому значення — число молодшого розряду.
Щоб дістати m-розрядне випадкове двійкове число, достатньо m разів звернутися до лічильника радіоактивних часточок.
Власними шумами електронних ламп називають явище існування вихідної напруги U при нульовій вхідній. Посилюючи власні шуми, можна дістати реалізацію стаціонарного випадкового процесу U (t)(рис.6.1).
Попередньо обирають
деякий рівень відсікання a,
для якого в довільний момент часу
t маєвиконуватись
умова
Випадкова
величина
імітується за схемою
(6.1)
Щоб дістати
m-розрядне випадкове двійкове число РВП
[0, 1], достатньо провести m вимірюваньшуму
лампи в моменти часу
і скористатися перетворенням (6.1).
Послідовність квазірівномірних випадкових чисел за допомогою фізичного генерування утворюється спеціальними електронними приставками до ЕОМ — фізичними генераторами випадкових чисел. Для знаходження наступного випадкового числа РВП [0, 1] під час проведення машинних розрахунків досить один раз звернутися до цього пристрою.
Переваги методу фізичного генерування:
1) швидкість здобування чисел надвисока (проміжок часу звертання до електронного пристрою ЕОМ дуже малий);
2) місця в оперативній пам’яті не займає;
3) запас чисел необмежений.
Вади методу фізичного генерування:
1) не можна повторити спроби (немає змоги фізичний датчик зафіксувати на певному випадковому числі);
2) потрібне періодичне коригування датчиків, оскільки фізичні властивості їх з часом змінюються;
3) необхідно мати спеціальний пристрій до ЕОМ.
Фізичне генерування випадкових чисел використовується здебільшого там, де дуже часто розв’язуються задачі методом Монте-Карло. Проте останнім часом навіть за цих умов надається перевага програмним генераторам випадкових чисел.
19. Методи перевірки якості
згенерованих псевдовипадкових чисел
