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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Распределение)
(Метки: правка с мобильного устройства, правка из мобильной версии)
(Симуляция распределений)
(Метки: правка с мобильного устройства, правка из мобильной версии)
Строка 48: Строка 48:
 
==Симуляция распределений==
 
==Симуляция распределений==
 
Для того, чтобы создать необходимое распределение вероятностей, достаточно иметь последовательность независимых случайных величин типа "честной монеты".
 
Для того, чтобы создать необходимое распределение вероятностей, достаточно иметь последовательность независимых случайных величин типа "честной монеты".
 +
 
Например, для создания схемы с двумя исходами $A_1$ и $A_2$:
 
Например, для создания схемы с двумя исходами $A_1$ и $A_2$:
 
$P(A_1)=\dfrac{3}{4}$ $,$  $P(A_2)=\dfrac{1}{4}$
 
$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$.
 
можно из датчика случайных двоичных величин получить два  результата "честной монеты" $\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}$
 
$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$.
 
можно получить четыре результата "честной монеты" $\delta_1$ $,$ $\delta_2$ $,$ $\delta_3$ $,$ $\delta_4$ и любым способом сопоставить трём из 16 возможных наборов исход $A_1$, одному $-$ $A_2$, восьми $-$ $A_3$, четырём $-$ $A_4$.
 +
 
Если же вероятности исходов не кратны $2^{-k}$, можно применить два различных варианта действий.
 
Если же вероятности исходов не кратны $2^{-k}$, можно применить два различных варианта действий.
 
:#Можно приблизить вероятности двоичными дробями (с любой точностью), далее работать с полученными приближёнными значениями
 
:#Можно приблизить вероятности двоичными дробями (с любой точностью), далее работать с полученными приближёнными значениями
 
:#Пусть все вероятности $n_i$ $-$ дроби со знаменателем $r$. Найдём $k$, для которого $r < 2^k$. Предложим схему с $k$ результатами "честной монеты", в которой $r$ наборов используются для выработки случайного исхода, а остальные $2^{k}-r$ наборов объявляются "неудачными" и требуют повторного эксперимента (пока не встретится удачный). Чем выше доля полезных исходов равная  $r2^{-k}$, тем схема будет эффективнее.
 
:#Пусть все вероятности $n_i$ $-$ дроби со знаменателем $r$. Найдём $k$, для которого $r < 2^k$. Предложим схему с $k$ результатами "честной монеты", в которой $r$ наборов используются для выработки случайного исхода, а остальные $2^{k}-r$ наборов объявляются "неудачными" и требуют повторного эксперимента (пока не встретится удачный). Чем выше доля полезных исходов равная  $r2^{-k}$, тем схема будет эффективнее.
 +
 
Количество результатов "честной монеты" $\lambda$, которые необходимы для формирования случайного исхода, $-$  это случайная величина. Её математическое ожидание:
 
Количество результатов "честной монеты" $\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}$
 
$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$.
 
Можно сделать схему более экономной, используя свойство датчика случайных чисел формировать не отдельные результаты "честной монеты", а целые наборы их, например в виде числа, равномерно распределённого в $[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$.
  

Версия 00:16, 11 марта 2018

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

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

Законом распределения дискретной случайной величины [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]100\%[/math] распределяется по возможным значениям случайной величины.

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

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

[math]2.[/math] С помощью плотности вероятности [math]f (x).[/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]


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

См. также

Литература