Х 0 - початкове значення, 0 ? Х 0 lt; m .
Послідовність випадкових чисел {Х n } можна отримати, вважаючи
Х n + 1 =(a Х n + c) mod m, n ? 0 , (4.1)
де mod - операція взяття залишку від ділення. Послідовність (4.1) називається лінійною конгруентної послідовністю. Наприклад, для m=10 і Х 0 =a=c=7 отримаємо послідовність 7, 6, 9, 0, 7, 6, 9, 0, 7 ...
У прикладі відображений факт, що конгруентність послідовність завжди утворює петлі, тобто обов'язково існує цикл, що повторюється нескінченне число разів. Ця властивість є загальним для всіх послідовностей виду X n + 1 =f (X n ), де f - функція, яка перетворює кінцеве безліч саме в себе. Повторювані цикли називають періодами. Завдання генерації випадкових послідовностей полягає у використанні щодо довгого періоду, що пов'язано з вибором досить великого m , так як період не може мати більше m елементів. Інший фактор - швидкість генерування. При виборі множника а слід брати до уваги висновки наступної теореми.
Приклад. Для m=120 призначити а і побудувати послідовність випадкових чисел в інтервалі [0,1].
Рішення . Виберемо з =7, a =5, тоді при x 0 =1 отримаємо наступні числа: X 1 =12, X 2 =67, X 3 =102, ... Далі генеруємо u 0 =1/120, u 1 =12/120, u 2 =67/120, u 3 =102/120, ...
У зв'язку з досить простим отриманням випадкових чисел виникає така загальноприйнята помилкова ідея - достатньо взяти хороший генератор випадкових чисел і трохи його модифікувати для того, щоб отримати ще більш випадкову послідовність. Часто це не так. Наприклад, відомо, що формула (4.1) дозволяє отримати більш-менш хороші випадкові числа. Чи може послідовність, отримана з
X n + 1 =((a X n ) mod (m + 1) + c) mod m
бути ще більш випадковою? Відповідь: нова послідовність є менш випадкової з більшою часткою ймовірності, тобто ми потрапляємо в область генераторів типу X n + 1 =f (X n ) з обраною довільно функцією f . Доведено, що такі послідовності, поводяться гірше, ніж послідовності, отримані при використанні більш регулярних функцій (4.1).
Відзначимо, що період лінійної конгруентної послідовності досить довгий; коли m приблизно дорівнює довжині слова комп'ютера, зазвичай виходять періоди порядку 10 9 або більше, а в типових обчисленнях використовується лише мала частина всієї послідовності.
Розглянемо адитивний генератор, запропонований Дж.Ж. Мітчелом і Д.Ф. Муром:
X n =(X n - 24 + X n - 55 ) mod m, n ? 55 , (4.2)
де m - парне число, числа 24 і 55 - спеціальні числа, вибрані для того, щоб визначити таку по...
