Генератори випадкових чисел

Застосування МСВ у ймовірнішому моделюванні систем потребує проведення великої кількості випробовувань. Для цього потрібні довгі послідовності випадкових чисел. Кількість випадкових чисел, які реалізуються для формування одного випробовування коливається у досить широких межах. Тому наявність простих та економічних способів формування послідовності випадкових чисел багато у чому визначає можливість практичного використання МСВ. Одержання випадкових чисел за допомогою генераторів, безпосередньо з’єднаних з комп’ютером, може здійснюватися за допомогою апаратних або програмних методів.

Апаратний або фізичний спосіб генерування випадкових чисел допускає застосування електронних генераторів випадкових сигналів. Їх дія застосована на деяких фізичних випадкових явищах, наприклад, шумах в електронних і напівпровідникових приладах. Під час застосування апаратних генераторів випадковий електричний сигнал перетворюють у двійковий код за допомогою спеціальних аналогово-цифрових перетворювачів. Основними недоліками способу є нестабільність ймовірнісних характеристик випадкової функції і неможливість повторного одержання однієї і тієї ж реалізації. Можна використовувати готові таблиці випадкових чисел, які слід розміщати пам’яті комп’ютера або на зовнішньому накопичувачі.

Для формування випадкових чисел із заданими законами розподілу вихідними даними є випадкові числа, отримані програмними генераторами рівномірно розподілених випадкових величин в інтервалі (0, 1), які вбудовані практично у всі мови програмування. Спеціалізовані програмні засоби ймовірнісного моделювання як правило мають власні вбудовані процедури генерування випадкових величин із заданими законами розподілу.

Найбільш розповсюдженими є програмні генератори, які допускають відтворення випадкових чисел за допомогою реалізації рекурентних алгоритмів. Оскільки ці алгоритми є детерміновані, то числа, які знаходяться програмними генераторами є псевдовипадковими або квазівипадковими. До генераторів випадкових чисел пред’являються такі вимоги:

- генерувати статистично незалежні випадкові числа, рівномірно розподілені в інтервалі (0,1);

- послідовність чисел має бути такою, що відтворюється;

- генератор повинен бути швидкодіючим, а використання комп’ютерної пам’яті мінімальним;

- легко створювати незалежні послідовності випадкових чисел.

У стохастичних моделях важливим є отримання випадкових чисел з довільним законом розподілу F (x). Тому найчастіше застосовувана на практиці двоетапна процедура у різних методах генерування випадкових чисел.

На першому етапі генерується послідовність випадкових чисел рівномірно розподілених в інтервалі (0,1)

. (2.1)

На другому етапі здійснюється функціональне перетворення Ф послідовності випадкових чисел r_i у послідовність випадкових чисел х_i, що мають заданий розподіл F (x_і)

(2.2)

Таким чином, r_i Î (0, 1) є основою для генерації різних розподілів. Тому спочатку зупинимося на отриманні випадкових чисел r_i Î (0, 1), а пізніше розглянемо процедури, за допомогою яких ці числа перетворюються у випадкові величини, розподілені за різними законами розподілу.

Для формування рівномірно розподілених випадкових чисел в інтервалі (0, 1) можуть використовуватися такі методи:

· метод квадратів;

· метод добутків;

· конгруентні методи;

· модифікації вищенаведених методів.

Метод середин квадратів є одним з найпростіших методів алгоритмічного генерування випадкових величин r_i Î (0, 1) з максимально можливою довжиною періоду.

Суть методу полягає у виборі n -розрядного цілого числа, яке підноситься до квадрату. З отриманого 2 n -розрядного числа виділять n-середніх розрядів, які розглядаються як дробова частина випадкового числа r_i Î (0, 1). Виділені на попередньому етапі n середніх розрядів розглядаються як нове вихідне n -розрядне число.

Розглянемо застосування методу на прикладі. Для наглядності будемо оперувати десятковими числами, а не двійковими, як це реалізується у програмних генераторах. Результатами застосування алгоритму для вибраного чотирьохрозрядного числа 7153 показано у табл. 2.1.

Таблиця 2.1.

	51 1654 09	0,1654
	02 7357 16	0,7357
	54 1254 49	0,1254
	01 5725 16	0,5725
	32 7756 25	0,7756
	60 1555 36	0,1555

Метод добутків аналогічний до методу квадратів. У ньому перемножуються два n -розрядні цілі числа. Перше число (ядро) є незмінним, а друге (множник) формується з n правих розрядів отриманого 2 n -розрядного числа, як добутку ядра і множника. Застосування цього методу показано у табл. 2.2. Тут вибране ядро дорівнює 5167, а множник 3279.

Таблиця 2.2.

Множник	Добуток	Випадкове число
3729	19 26 77 43	0,2677
	40 0080 81	0,0080
	41 7545 27	0,7545
	23 391009	0,3910
	05 2135 03	0,2135
	...	...

Найбільш широке застосування знайшли конгруентні генератори випадкових чисел [9, 12]. Два цілих числа А і В є конгруентними за модулем m, якщо їх різниця (А - В) є числом, яке ділиться на m без остачі (тобто є кратними)

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

, (2.3)

де і = 1, 2,...; a, c, m – цілі константи.

Якщо с > 0, то генератор називається змішаним, а якщо с = 0 – мульти-плікативним.

Змішаний метод генерування випадкових чисел. У цьому випадку використовуються такі співвідношення (2.4)

, , (2.4)

де х_і – псевдовипадкове число, а, с, m – невід’ємні цілі числа, які задовільня­ють умови: , с > 0, m > a, m > c, m > x ₀, x ₀ – початкове значення послідовності.

Якщо задано початкове значення x _0, константи а, с, то можна визначити послідовність цілих чисел { x₁, x₂,..., x_i,... }, що є рівномірно розподілені в інтервалі (0, m). Поділивши ці числа на m, отримаємо послідовність псевдови­падкових чисел r_i, і = 1, 2,... з рівномірним розподілом в інтервалі (0,1).

Теоретично можна отримати послідовність випадкових чисел з періодом Т = m, якщо с і m є взаємно прості числа, а а має порядок .

Мультиплікативний метод. Якщо с = 0, то отримаємо мульти­плі­ка­тивний конгруентний метод, який передбачає використання співвідношення

, . (2.5)

Цей метод більш швидкодіючий ніж попередній, але отримання послідовності випадкових чисел з повним періодом є неможливим.

Для розглянутих вище методів за модуль m вибирають m = qⁿ, де q – основа системи числення, що виконується у комп’ютері, n – довжина розрядної сітки комп’ютера. Для 32 – розрядного комп’ютера m – найбільше число, яке може бути відтворене дорівнює 2³²-1=2147483647 (один розряд відводиться під знак числа).

Використовується ще генератор, що використовує числа Фібоначчі.

.

Для побудови програм генерування випадкових чисел за допомогою конгруентних методів, необхідно мати на увазі, певні умови вибору пара­метрів генератора х ₀, l, m, М, які визначають його основні робочі характерис­тики (закон розподілу, довжину періоду, кореляційні властивості тощо). У працях [8, 12] показано, що для M > l, M > m, M > x ₀ виходять якісні послідовності (за критерієм c ², довжині відрізка аперіодичності L). У [12] коротко викла­даються правила визначення констант l, m, М для конгруентних генераторів. Ці правила дають лише загальні рекомендації для вибору l, m, М.