5.7: Генерація псевдовипадкових чисел

Last updated
Save as PDF

Page ID: 28720

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

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

Цифри не виявляють жодної статистичної кореляції один з одним.
Числа, здається, рівномірно розподілені в діапазоні (0,1).
Послідовно існує багато, багато (щонайменше 1 000 000) чисел.
Всі можливі числа в послідовності генеруються перед повторенням будь-якого числа.

Оскільки алгоритми генерації псевдовипадкових чисел є детермінованими, послідовність чисел може бути відновлена, коли це необхідно. Це важливо в моделюванні як для налагодження, так і для експериментів з використанням загальних випадкових чисел. Уявіть собі складність видалення помилки з моделі, якщо результати були випадковим чином різні кожного разу, коли модель була виконана!

Послідовність псевдовипадкових чисел називається потоком. Наявність декількох потоків випадкових чисел дозволяє вибірку з кожного конкретного розподілу ймовірностей, що використовується в моделі, бути пов'язаним з певним потоком. Наприклад, на двох станціях у серійній моделі час між прибуттями та час роботи на станції А буде присвоєно різні потоки. Це означає, наприклад, що якщо розподіл ймовірностей моделювання часу роботи на станції А були змінені, час між прибуттями залишиться незмінним.

Як і в попередньому розділі, буде представлений один підхід до генерації псевдовипадкових чисел. Інші підходи до генерації псевдовипадкових чисел наведені в Banks, Carson, Nelson і Nicol (2009), а також Law (2007). Шмайзер (1980) забезпечує комплексне обстеження.

Мабуть, найбільш поширеним типом алгоритму генерації псевдовипадкових чисел, щодо використання в мовах моделювання, є лінійний конгруенціальний генератор (Lehmer, 1951). Лінійний конгруенціальний генератор (LCG) має вигляд:

\ begin {вирівняти} Z_ {i} =\ лівий (a^ {*} Z_ {i-1} +c\ праворуч)\ bmod (m)\ тег {5-3}\ end {вирівнювання}

\ begin {вирівняти} r_ {i} =Z_ {i}/м\ тег {5-4}\ end {вирівнювання}

Z _i - це набір цілих чисел, які варіюються від 0 до m-1. Ціле число Z _i - залишок, а m - дільник. Іншими параметрами генератора є множник a, приріст c і перше ціле число Z ₀. Псевдовипадкове число r _i отримується шляхом ділення Z _i на m, на щастя, для наших цілей, значення параметрів (a, c, m та Z ₀), які призводять до бажаних властивостей, перерахованих вище, використовуються комерційними мовами моделювання.

Генератор є рекурсивним, тобто Z _i є функцією Z _i-1. Зауважте, що не більше m різних Z _i і, таким чином, r _i (псевдовипадкові числа) можуть бути отримані. Після того, як Z ₀ генерується вдруге, вся послідовність Z _i, і, отже, r _i, буде повторюватися і в тій же послідовності, що і перший раз.

Розглянемо приклад LCG, показаний в таблиці 5-3. Значення параметрів LCG наведені в таблиці. Зверніть увагу, що Z _i в діапазоні від 0-8. Всі дев'ять з Z _я генеруються до того, як будь-яке значення повторюється. Таким чином, r _i, здається, так само рівномірно розподілені в діапазоні (0,1), як можуть бути дев'ять чисел. Статистична кореляція між r _i є низькою, 0,030. Оскільки кількість згенерованих значень становить всього 9, значення m занадто мало для ефективного LCG. Однак цього вистачає для прикладу.

Таблиця 5-3: Приклад LCG
		я	З _я	р _i
М	9	0	8	0.889
А	4	1	1	0.111
C	5	2	0	0.000
		3	5	0,556
		4	7	0,778
		5	6	0.667
		6	2	0,222
		7	4	0,444
		8	3	0,333
		9	8	0.889
		10	1	0.111
		11	0	0.000
		12	5	0,556