Моделирование случайных величин (лекция 4)

1.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Моделирование случайных величин
«Теория информационных процессов и систем»
Лекция 4

2.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Способы получения случайных величин
физические генераторы (датчики) случайных
величин;
программные
генераторы
(датчики)
псевдослучайных чисел – позволяют получить
периодические детерминированные числовые
последовательности с большим периодом,
называемые псевдослучайными.
2

3.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Линейные конгруэнтные генераторы (ЛКГ)
i+1 = (a i+c) (mod m),
i (0, m-1), |(0, m-1)|=m
Теорема: ЛКГ имеет полный период, когда выполняются
следующие условия:
m и c являются взаимно простыми числами;
если m делится на простое число q, то a-1 тоже
делится на q;
если m делится на 4, то a-1 тоже делится на 4.
3

4.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Линейные конгруэнтные генераторы (ЛКГ)
Пример 1:
i+1 = (a i+c) (mod m),
m=5, c=3, a=6, 0=4.
1 = (6•4+3) (mod 5)=2,
2 = (6•2+3) (mod 5)=0,
3 = (6•0+3) (mod 5)=3,
4 = (6•3+3) (mod 5)=1,
5 = (6•1+3) (mod 5)=4,
6 = (6•4+3) (mod 5)=2.
4

5.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Линейные конгруэнтные генераторы (ЛКГ)
Пример 2:
i+1 = (a i+c) (mod m),
m=5, c=5, a=6, 0=4.
1 = (6•4+5) (mod 5)=4,
2 = (6•4+5) (mod 5)=4.
5

6.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Мультипликативные генераторы
i+1 = (a i) (mod m),
i (1, m-1), |(1, m-1)|=m-1
Теорема: Мультипликативный генератор имеет период
m-1, когда выполняются следующие условия:
m является простым числом;
a-1 является первообразным элементом по модулю
m, т.е. наименьшее целое число l, для которого al–1
делится на m, есть l = m-1.
6

7.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Мультипликативные генераторы
Пример 3:
i+1 = (a i) (mod m),
m=5, a=2, 0=4.
1 = (2•4) (mod 5)=3,
2 = (2•3) (mod 5)=1,
3 = (2•1) (mod 5)=2,
4 = (2•2) (mod 5)=4,
5 = (2•4) (mod 5)=3.
7

8.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Мультипликативные генераторы
Пример 4:
i+1 = (a i) (mod m),
m=5, a=4, 0=4.
1 = (4•4) (mod 5)=1,
2 = (4•1) (mod 5)=4,
3 = (4•4) (mod 5)=1.
8

9.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Моделирование дискретной случайной величины
Необходимо получить последовательность значений xi
случайной величины X с распределением:
x1
x2
…
xn
p1
p2
…
pn
Интегральная функция распределения:
n
FX ( x) = P ( X £ x) = å pi ; xn £ x £ xn+1 ; n = 1, 2,...;
i =1
FX ( x) = 0; x < x1
9

10.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Моделирование дискретной случайной величины
Метод обратной функции
Если - равномерно распределенная на интервале
(0,1) случайная величина, то искомая случайная
величина X получается с помощью преобразования
X = FX-1 ( ),
где FX-1 - функция, обратная FX.
Общая формула
x = min{x : F ( x) ³ }
10

11.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Моделирование дискретной случайной величины
Интервал (0,1) разбивается на n частей с длинами
p1,p2,…,pn. Полученные интервалы нумеруются
цифрами 1,2,…n. Координаты точек деления y0=0,
y1=p1, y2=p1+p2, yn=p1+p2+…+pn.
Выбирается стандартно равномерно распределенная
случайная величина и строится точка y = .
Если эта точка попадает в интервал с номером i, то
X=xi.
11

12.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Пример
x
1
2
3
p
0.2
0.5
0.3
={0.43, 0.75, 0.11, 0.98, 0.35, 0.64, 0.23}
x={ 2,
3,
1,
3,
2,
2,
2}
12

13.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Распределение Бернулли
Алгоритм
эквивалентен
методу
обратного
преобразования, если и 1 - поменять местами.
1. Генерируем ~ U(0,1).
2. Если <= p, возвращаем X = 1; в противном случае
возвращаем X = 0.
p – вероятность успеха в испытании Бернулли
13

14.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Биномиальное распределение
Биномиальное распределение задает вероятность k
удачных исходов в n реализациях некоторого
эксперимента:
pk = P ( X = k ) = C p q
k
n
k
n -k
,
n!
где q = 1-p, C =
- биномиальные коэффициенты.
k !(n - k )!
k
n
M[ X ] = np;D[X] = npq.
14

15.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Биномиальное распределение
I. Сумма n независимых и одинаково распределенных величин с
распределением Бернулли имеет биномиальное распределение.
1. Генерируем Y1, Y2, …, Yn как независимые и одинаково
распределенные случайные величины с распределением
Бернулли.
2. Возвращаем X = Y1 + Y2 + … + Yn.
Время выполнения алгоритма пропорционально величине n.
II. Метод обратного преобразования:
p0 = (1 - p ) n ;
pk
n - k +1 p
=
pk -1
k
1- p
15

16.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Распределение Пуассона
Дискретная случайная величина X называется
распределенной по закону Пуассона с параметром
>0, если ее возможные значения – все
неотрицательные целые числа: 0,1,2, …, а
вероятность события {X = x} выражается формулой:
k -
pk = P ( X = k ) = e , k = 0,1,2,...
k!
M[ X ] = D X = .
16

17.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Распределение Пуассона
I. Метод обратных функций
Ряд пуассоновского распределения имеет вид:
x
0
P
-
Следовательно,
e
1
e
-
2
…
k
…
2 -
e
2!
…
k -
e
k!
…
p0 = e - , pk pk -1 = k .
17

18.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Распределение Пуассона
II. Пусть 1, 2, …, n, … – последовательность независимых
равномерно распределенных на (0, 1] случайных величин. Тогда
случайная величина
n
= max{n ³ 0 : Õ i > e - }, > 0
i =1
описывается распределением Пуассона.
Элемент выборки может быть получен путем последовательного
увеличенияn числа членов n в произведении, пока не нарушится
условие
> e - .
Õ
i
i =1
Максимальное значение n, удовлетворяющее этому условию, очередное значение случайной величины.
18

19.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Распределение Пуассона
II. Алгоритм:
1. Инициализируемa = e
-
, b = 1, i = 0.
2. Генерируем i+1 ~ U(0, 1) и заменяем b на b i+1.
Если b < a, возвращаем X = i. В противном случае
переход к шагу 3.
3. Увеличиваем i на единицу и возвращаемся к шагу 2.
19

20.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Геометрическое распределение
I. Метод обратных функций, основанный на пересчете
pn = (1 – p) pn-1, p0 = p.
II. Моделирование испытаний Бернулли с вероятностью успеха p
до первого успеха с подсчетом количества неудач.
III. Накопленная вероятность Sn+1 = p0 + …+ pn для геометрического
распределения имеет вид:
n
S n+1 = å p (1 - p )i = 1 - (1 - p ) n+1
i =0
20

21.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Геометрическое распределение
Распределение
случайной
величины
X
называется
геометрическим с параметром p (p (0,1)), если значения
случайной величины X – все натуральные числа, а вероятность
события {X = x} выражается формулой:
pk = P ( X = k ) = q k -1 p, k = 1,2,...,
где q = 1 – p.
Вероятности
pk
образуют
бесконечную
геометрическую прогрессию со знаменателем q.
убывающую
1
q
M[ X ] = ; D X = 2 .
p
p
21

22.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Геометрическое распределение
III. Поэтому событие {X = n} приобретает вид:
ln(1 - )
{ X = n} = {S n < < S n+1} = {n <
£ n + 1}
ln(1 - p)
X = êëln(1 - ) ln(1 - p) úû
Алгоритм:
1. Генерируем ~ U(0, 1).
2. Возвращаем X = êë ln(1 - ) ln(1 - p ) úû .
Константа ln(1-p) вычисляется заранее.
При больших значениях p рекомендуется использовать другие
алгоритмы.
22

23.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Моделирование непрерывных случайных величин
Метод обратной функции
Для нахождения значения непрерывной случайной
величины X, распределенной в интервале (a,b) с
плотностью p(x) необходимо решить уравнение:
x
ò p ( t) d t =
a
где ~ U(0, 1).
23