Симуляция одним распределением другого — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Примеры распределений)
Строка 17: Строка 17:
  
 
==Примеры распределений==
 
==Примеры распределений==
* Биномиальное распределение
+
===Биномиальное распределение (закон Бернулли)===
* Нормальное распределение
+
{{Определение
* Равномерное распределение
+
|definition=
 +
Дискретная случайная величина <tex>\xi</tex> называется '''биномиальной''' с параметрами <tex>(n, p),</tex> если она принимает значения от <tex>0</tex> до <tex>n</tex> и вероятности вычисляются по формуле <tex>p_i = P(\xi = i) = \dbinom{n}{k} p^k q^{n - k}.</tex>}}
 +
===Нормальное распределение (распределение Гаусса)===
 +
{{Определение
 +
|definition=
 +
Непрерывную случайную величину \xi называют '''нормальной''' с параметрами <tex>(a, \sigma)</tex> и пишут <tex>\xi = N (a, \sigma),</tex> если ее плотность вероятности дается формулой
 +
<tex>f(x) = \dfrac {1} {\sigma \sqrt{2\pi}} {\large e^{-\frac {(x - a)^2} {2\sigma^2}}}.</tex>}}
 +
===Равномерное распределение===
 +
{{Определение
 +
|definition=
 +
Непрерывная случайная величина <tex>\xi</tex> называется '''равномерно распределенной''' на <tex>[a, b],</tex> если ее плотность вероятности дается формулой
  
 +
<tex>
 +
f(x)=
 +
\begin{cases}
 +
\dfrac {1} {b - a}, & \mbox{if } x \in [a, b] \\
 +
0, & \mbox{otherwise.}
 +
\end{cases}</tex>}}
  
 
==Симуляция распределений==
 
==Симуляция распределений==

Версия 23:55, 10 марта 2018

Распределение

Определение:
Распределение вероятностей — закон, описывающий область значений случайной величины и вероятность их исхода.
Геометрическое распределение с p = 3/4

Законом распределения дискретной случайной величины [math]\xi[/math] называется таблица: [math]\xi: \begin{pmatrix} x_1 & x_2 & \ldots & x_n \\ p_1 & p_2 & \ldots & p_n\end{pmatrix}, [/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]\xi[/math] называется биномиальной с параметрами [math](n, p),[/math] если она принимает значения от [math]0[/math] до [math]n[/math] и вероятности вычисляются по формуле [math]p_i = P(\xi = i) = \dbinom{n}{k} p^k q^{n - k}.[/math]

Нормальное распределение (распределение Гаусса)

Определение:
Непрерывную случайную величину \xi называют нормальной с параметрами [math](a, \sigma)[/math] и пишут [math]\xi = N (a, \sigma),[/math] если ее плотность вероятности дается формулой [math]f(x) = \dfrac {1} {\sigma \sqrt{2\pi}} {\large e^{-\frac {(x - a)^2} {2\sigma^2}}}.[/math]

Равномерное распределение

Определение:
Непрерывная случайная величина [math]\xi[/math] называется равномерно распределенной на [math][a, b],[/math] если ее плотность вероятности дается формулой [math] f(x)= \begin{cases} \dfrac {1} {b - a}, & \mbox{if } x \in [a, b] \\ 0, & \mbox{otherwise.} \end{cases}[/math]


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

Для того, чтобы создать необходимое распределение вероятностей, достаточно иметь последовательность независимых случайных величин типа "честной монеты". Например, для создания схемы с двумя исходами $A_1$ и $A_2$: $P(A_1)=\dfrac{3}{4}$ $,$ $P(A_2)=\dfrac{1}{4}$ можно из датчика случайных двоичных величин получить два результата "честной монеты" $\delta_1$ и $\delta_2$ и, например, при $\delta_1 = \delta_2 = 1$ выработать исход $A_2$, а в остальных случаях $A_1$. Аналогично для схемы с четырьмя исходами $P(A_1)=\dfrac{3}{16}$ $,$ $P(A_2)=\dfrac{1}{16}$ $,$ $P(A_3)=\dfrac{8}{16}$ $,$ $P(A_4)=\dfrac{4}{16}$ можно получить четыре результата "честной монеты" $\delta_1$ $,$ $\delta_2$ $,$ $\delta_3$ $,$ $\delta_4$ и любым способом сопоставить трём из 16 возможных наборов исход $A_1$, одному $-$ $A_2$, восьми $-$ $A_3$, четырём $-$ $A_4$. Если же вероятности исходов не кратны $2^{-k}$, можно применить два различных варианта действий.

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

Количество результатов "честной монеты" $\lambda$, которые необходимы для формирования случайного исхода, $-$ это случайная величина. Её математическое ожидание: $E\lambda = \dfrac{1}{2}\cdot1+\dfrac{1}{4}\cdot2+\dfrac{1}{8}\cdot3+\dfrac{1}{16}\cdot3+\dfrac{1}{16}\cdot4 = 1\dfrac{7}{8}$ Можно сделать схему более экономной, используя свойство датчика случайных чисел формировать не отдельные результаты "честной монеты", а целые наборы их, например в виде числа, равномерно распределённого в $[0, 1]$. Образуем по данному набору вероятностей $p_i$ накопленные суммы $s_i$: $s_0 = 0; s_i = s_{i-1} + p_i, i > 0$. Случайный исход будет вырабатываться так: по полученному из датчика случайному числу $\gamma$ определяется такой индекс $i$, для которого $s_{i-1} < \gamma \leqslant s_i$. Найденное значение индекса $i$ и определяет исход $A_i$.

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

Общий случай

В распределении q количество элементарных исходов равно 2

Допустим у нас есть распределение [math]p.[/math] Нам нужно получить распределение [math]q[/math].

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

Количество элементарных исходов распределения q равно n

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

[math] k^t \geqslant 2n, t \geqslant \log\limits_{k}2n [/math]

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

Sim pic3.JPG

[math]p_i, \sum\limits_{i}p_i = 1,[/math]

[math]q_j, \sum\limits_{j}q_j = 1[/math]

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


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

См. также

Литература