Симуляция одним распределением другого

Закон распределения дискретной случайной величины [math]\xi[/math] задается таблицей:

[math]\xi: \begin x_1 & x_2 & \ldots & x_n \\ p_1 & p_2 & \ldots & p_n\end, [/math]

где [math]x_1 \lt x_2 \lt \ldots \lt x_n[/math] — всевозможные значения величины [math]\xi,[/math] а [math]p_i(i = 1, \ldots, n)[/math] — их вероятности, то есть [math]p_i = P(\xi = x_i).[/math]

При этом должно выполняться равенство: [math]p_1 + p_2 + \ldots + p_n = 1.[/math]

Это равенство означает, что при испытании одно из значений заведомо реализуется. Таблица показывает, как суммарная вероятность [math]100\%[/math] распределяется по возможным значениям случайной величины.

Для непрерывных случайных величин задание закона распределения в виде такой таблицы невозможно, поэтому его задают двумя другими способами:

С помощью функции распределения [math]F (x);[/math]
С помощью плотности вероятности [math]f (x).[/math]

Примеры распределений [ править ]

Биномиальное распределение (закон Бернулли) [ править ] Определение: Дискретная случайная величина [math]\xi[/math] называется биномиальной (англ. binomial random variable) с параметрами [math](n, p),[/math] если она принимает значения от [math]0[/math] до [math]n[/math] и вероятности вычисляются по формуле [math]p_i = P(\xi = i) = \dbinom p^k q^,[/math] где [math]i = 1, \ldots, n;[/math] [math]q = 1 - p,[/math] [math]p \in (0, 1).[/math] Нормальное распределение (распределение Гаусса) [ править ] Определение: Непрерывную случайную величину [math]\xi[/math] называют нормальной (англ. normal deviate) с параметрами [math](a, \sigma)[/math] и пишут [math]\xi = N (a, \sigma),[/math] если ее плотность вероятности дается формулой [math]f(x) = \dfrac .[/math] Равномерное распределение [ править ] Определение: Непрерывная случайная величина [math]\xi[/math] называется равномерно распределенной (англ. uniformly distributed random variable) на [math][a, b],[/math] если ее плотность вероятности дается формулой [math] f(x)= \begin \dfrac , & \mbox x \in [a, b] \\ 0, & \mbox \end[/math]
Симуляция распределений [ править ]

Для того, чтобы создать необходимое распределение вероятностей, достаточно иметь последовательность независимых случайных величин типа "честной монеты".

Например, для создания схемы с двумя исходами $A_1$ и $A_2$: $P(A_1)=\dfrac$ $,$ $P(A_2)=\dfrac$ можно из датчика случайных двоичных величин получить два результата "честной монеты" $\delta_1$ и $\delta_2$ и, например, при $\delta_1 = \delta_2 = 1$ выработать исход $A_2$, а в остальных случаях $A_1$.

Аналогично для схемы с четырьмя исходами $P(A_1)=\dfrac$ $,$ $P(A_2)=\dfrac$ $,$ $P(A_3)=\dfrac$ $,$ $P(A_4)=\dfrac$ можно получить четыре результата "честной монеты" $\delta_1$ $,$ $\delta_2$ $,$ $\delta_3$ $,$ $\delta_4$ и любым способом сопоставить трём из 16 возможных наборов исход $A_1$, одному $-$ $A_2$, восьми $-$ $A_3$, четырём $-$ $A_4$.

Если же вероятности исходов не кратны $2^$, можно применить два различных варианта действий.

Можно приблизить вероятности двоичными дробями (с любой точностью), далее работать с полученными приближёнными значениями

Пусть все вероятности $n_i$ $-$ дроби со знаменателем $r$. Найдём $k$, для которого $r < 2^k$. Предложим схему с $k$ результатами "честной монеты", в которой $r$ наборов используются для выработки случайного исхода, а остальные $2^-r$ наборов объявляются "неудачными" и требуют повторного эксперимента (пока не встретится удачный). Чем выше доля полезных исходов равная $r2^$, тем схема будет эффективнее.

Количество результатов "честной монеты" $\lambda$, которые необходимы для формирования случайного исхода, $-$ это случайная величина. Её математическое ожидание:

$E\lambda = \dfrac\cdot1+\dfrac\cdot2+\dfrac\cdot3+\dfrac\cdot3+\dfrac\cdot4 = 1\dfrac.$

Можно сделать схему более экономной, если использовать датчик, равномерно формирующий число из диапазона $[0, 1]$. Образуем по данному набору вероятностей $p_i$ накопленные суммы $s_i$, такие, что $s_0 = 0; s_i = s_ + p_i,$ для $i > 0$. Случайный исход будет вырабатываться так: по полученному из датчика случайному числу $\gamma$ находится такой индекс $i$, для которого $s_ < \gamma \leqslant s_i$. Найденное значение индекса $i$ и определяет исход $A_i$. Индекс $i$ можно определять непосредственно просмотром $s_i$ подряд.

Рассмотрим приведенный выше пример с четырьмя исходам. В данном случае суммы $s_0, \ldots, s_4$ будут принимать значения [math]0,[/math] [math]\dfrac,[/math] [math]\dfrac,[/math] [math]\dfrac[/math] и [math]1[/math] соответственно. Значению $\gamma = 0,5$ будет соответствовать $i = 3$, то есть оно будет определять исход события $A_3.$ Таким же образом, $\gamma = 0,985$ определяет исход события $A_4.$

Если $k$ велико, можно применять специальные приёмы ускоренного поиска, например, деление множества индексов примерно пополам.

Общий случай [ править ]
рис. [math]1[/math] рис. [math]2[/math] рис. [math]3[/math]
Допустим у нас есть распределение [math]p.[/math] Нам нужно получить распределение [math]q[/math] .

Для начала рассмотрим случай, когда все [math]p_i = \dfrac,[/math] а в распределении [math]q [/math] количество элементарных исходов равно [math]2[/math] [math]([/math] рис. [math]1).[/math]

Проводим эксперимент: если попадаем в область пересекающуюся с [math] q_1 [/math] и [math] q_2,[/math] то увеличиваем ее и повторяем эксперимент. На рис. [math]1[/math] красным обозначено распределение [math] q. [/math] Вероятность того, что на этом шаге эксперимент не закончится — [math]\dfrac.[/math] Математическое ожидание количества экспериментов — [math] \dfrac, max(\dfrac) = 2[/math] [math]([/math] при [math]k = 2).[/math]

Теперь рассмотрим случай, когда все элементарные исходы [math]p_i[/math] по-прежнему равновероятны [math](p_i = \dfrac),[/math] а количество элементарных исходов распределения [math]q[/math] равно [math]n (\sum\limits_^q_j = 1)[/math] [math]([/math] рис. [math]2).[/math] Повторим эксперимент [math] t [/math] раз.

[math] k^t \geqslant 2n, t \geqslant \log\limits_2n [/math]

Отрезок разбился на [math] k^t [/math] отрезков. Стык будет не более, чем в половине отрезков. Математическое ожидание количества экспериментов [math] \approx 2t [/math]

[math]p_i, \sum\limits_p_i = 1,[/math] [math]q_j, \sum\limits_q_j = 1[/math]

Берем [math]p_i[/math] , и пусть оно максимальной длины [math]([/math] рис. [math]3).[/math] Проводим [math]t[/math] экспериментов. [math]^t \lt \dfrac, [/math] все остальные еще меньше. Суммарная длина отрезков не больше [math]\dfrac.[/math] Нужно [math] t \geqslant \log\limits_
\dfrac .[/math]

Таким образом, из любого исходного распределения мы можем получить нужное нам распределение.
📎📎📎📎📎📎📎📎📎📎