Псевдовипадкова послідовність

Псевдовипадкові послідовності (числа) — послідовності, що отримуються за цілком невипадковим алгоритмом, але мають властивості, дуже подібні до властивостей реалізацій випадкових чисел.

Псевдовипадкове число — елемент отриманої за певним алгоритмом числової послідовності, властивості якої наближаються до випадкової. Негативною особливістю псевдовипадкових чисел (як імітаційної моделі випадкових чисел) є періодичність отриманої послідовності.

Отримання

Реалізація статистичних моделей за допомогою обчислювальних машин передбачає можливість отримання достатньою мірою випадкових показників (що є нетривіальним завданням, оскільки електронно-обчислювальна машина працює на основі чітко прописаної логіки та детерміністичного підходу), а також імітацію законів розподілу, що часто використовуються на практиці.

Зазвичай генерування псевдовипадкової послідовності передбачає два етапи^[1][2]. На першому генерують псевдовипадкові числа, що мають рівномірний розподіл на відрізку від нуля до одиниці. На другому цю послідовність перетворюють у послідовність, що має заданий закон розподілу.

Генерація рівномірно розподілених чисел

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

Існує ряд методів, які відповідають критеріям перевірки «випадковості» побудови таких чисел з розподілом близьким до рівномірного (хоча ці числа взаємозалежні).

Зазвичай використовують деяке рекурентне співвідношення. Це значить, що кожне наступне число α_k+1 утворюють із попереднього α_k (або групи попередніх чисел), використовуючи деякий алгоритм, який використовує арифметичні та логічні операції.

Часто застосовується метод остач, який належить до так званих аналітичних методів і полягає в побудові послідовності {α_n} згідно із рекурентним співвідношенням α_n+1 = Kα_n (mod M), де К та M — деякі константи.

Для генерування псевдовипадкових чисел, що мають рівномірний розподіл на відрізку від нуля до одиниці використовують методи:

• метод остач (лінійний конгруентний метод);
• метод середніх квадратів (метод фон Неймана);
• метод трикутного відображення;
• метод логістичного відображення.

Перетворення в послідовність з заданим розподілом

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

Обов'язковим етапом генерування псевдовипадкових чисел є перевірка періодичності й випадковості отриманої послідовності та її відповідності заданому закону розподілу.

Дивись також

• Портал «Математика»

• Генератор псевдовипадкових чисел
• Список криптографічних алгоритмів

Примітки

1. Бахрушин В. Є. Математичні основи моделювання систем: Навчальний посібник для студентів. — Запоріжжя, 2008. — 294 с.
2. Бусленко Н. П. Моделирование сложных систем. — М. : Наука, 1968.

Посилання

• Енциклопедія кібернетики, А. И. Березовський, т. 2, ст. 254.