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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 70: Строка 70:
 
При моделировании эти числа используются так: разыгрывается случайное число $x \in [0, 1]$, пусть получилось $x = 0.531$. Это число умножается на $k$: $0.531 \times 4 = 2.124$. Целая часть произведения определяет строку таблицы, считая от нуля, значит, третью сверху строку с основным исходом $D$ и дополнительным $C$. Дробная часть произведения $0.124$ сравнивается с барьером $0.6$, и так как барьер выше, то принимается основной исход.
 
При моделировании эти числа используются так: разыгрывается случайное число $x \in [0, 1]$, пусть получилось $x = 0.531$. Это число умножается на $k$: $0.531 \times 4 = 2.124$. Целая часть произведения определяет строку таблицы, считая от нуля, значит, третью сверху строку с основным исходом $D$ и дополнительным $C$. Дробная часть произведения $0.124$ сравнивается с барьером $0.6$, и так как барьер выше, то принимается основной исход.
  
 +
==Общий случай==
 +
[[Файл:Sim pic1.JPG‎|150px|left|thumb|В распределении q количество элементарных исходов равно 2]]
 +
Допустим у нас есть распределение <tex>p.</tex> Нам нужно получить распределение <tex>q.</tex>:
 +
 +
Для начала рассмотрим случай, когда все <tex>p_i = \frac{1}{k},</tex> а в распределении <tex>q </tex>  количество элементарных исходов равно <tex>2.</tex>
 +
Проводим эксперимент: если попадаем в область пересекающуюся с <tex> q_1 </tex> и <tex> q_2,</tex> то увеличиваем ее и повторяем эксперимент. На рисунке слева красным обозначенно распределение <tex> q. </tex> Вероятность того, что на этом шаге эксперимент не закончится {{---}} <tex>\frac{1}{k}.</tex> Математическое ожидание количества экспериментов {{---}} <tex> \frac{k}{k-1}, max(\frac{k}{k-1}) = 2 (</tex>при <tex>k = 2) </tex>
 +
 +
[[Файл:Sim pic2.JPG‎|150px|right|thumb|Количество элементарных исходов распределения q равно n]]
 +
Теперь рассмотрим случай, когда все элементарные исходы <tex>p_i</tex> по-прежнему равновероятны <tex>(p_i = \frac{1}{k}),</tex>а количество элементарных исходов распределения <tex>q</tex> равно <tex>n (\sum\limits_{j=1}^{n}q_j = 1).</tex> Повторим эксперимент <tex> t </tex> раз.
 +
 +
<tex> k^t \ge 2n, t \ge \log\limits_{k}2n </tex>
 +
 +
Отрезок разбился на <tex> k^t </tex> отрезков. Стык будет не более, чем в половине отрезков. Математическое ожидание количества экспериментов <tex> \approx 2t </tex>
 +
 +
[[Файл:Sim pic3.JPG‎|150px|left|thumb]]
 +
<tex>p_i, \sum\limits_{i}p_i = 1, q_j, \sum\limits_{j}q_j = 1. </tex> Берем <tex> p_i </tex> и пусть оно максимальной длины. Проводим <tex> t </tex> экспериментов. <tex>{p_i}^t < \frac{1}{2n}, </tex> все остальные еще меньше. Суммарная длина отрезков не больше <tex>\frac{1}{2}.</tex> Нужно <tex> t \ge \log\limits_{p}\frac{1}{2n} </tex>
 +
 +
 +
 +
 +
 +
Вывод: из любого исходного распределения можно получить любое нужное нам распределение.
 
</wikitex>
 
</wikitex>
 
==См. также==  
 
==См. также==  

Версия 09:48, 14 января 2012

<wikitex>

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

Геометрическое распределение с p = 3/4

Распределение — одно из основных понятий в теории вероятностей и математической статистике. Распределение вероятностей какой-либо случайной величины задается в простейшем случае указанием возможных значений этой величины и соответствующих им вероятностей, в более сложных — т. н. функцией распределения или плотностью вероятности.

Примеры распределений

  • Биномиальное распределение
  • Нормальное распределение
  • Равномерное распределение


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

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

$P(A_1)=\frac{3}{4}$ $,$ $P(A_2)=\frac{1}{4}$

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

$P(A_1)=\frac{3}{16}$ $,$ $P(A_2)=\frac{1}{16}$ $,$ $P(A_3)=\frac{8}{16}$ $,$ $P(A_4)=\frac{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$ наборов объявляются "неудачными" и требуют повторного эксперимента (пока не встретится удачный). Чем выше доля полезных исходов равная $r2^{-k}$, тем схема будет эффективнее.

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

$E\lambda = \frac{1}{2}\cdot1+\frac{1}{4}\cdot2+\frac{1}{8}\cdot3+\frac{1}{16}\cdot3+\frac{1}{16}\cdot4 = 1\frac{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 \le s_i$. Найденное значение индекса $i$ и определяет исход $A_i$.

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

Самую эффективную схему предложил в 1977 г. А. Уолкер.

Схема Уолкера

Если бы все исходы имели одинаковые вероятности, моделировать такое распределение было бы очень просто. В такой ситуации достаточно разделить отрезок $[0, 1]$ на $k$ одинаковых частей, соответствующих этим исходам, и определить, в какую часть отрезка попало значение случайного датчика $x$. А это выясняется очень просто: нужно взять целую часть произведения $k \cdot x$. Так что при исходах 0, 1, 2, 3 значению $x = 0.333$ соответствует исход $1$, поскольку $4x = 1.332$.

Можно "подгонять" распределение под равномерное, передавая часть "вероятностной массы" от одних исходов другим. Если четыре исхода должны иметь вероятности, те же четыре исхода должны иметь вероятности, соответственно, $0.25$, $0.31$, $0.19$ и $0.25$, то исход $2$, получая, как все другие, долю $0.25$ и нуждаясь в доле $0.19$, может быть своеобразным "донором" и отдать исходу $1$, нуждающемуся в доле $0.31$, свои лишние шесть сотых. Эта передача воплощается в следующих действиях при генерировании случайного исхода: берется случайное число, например можможно использовать непосредственно дробную часть числа $k \cdot x$, и если это число меньше чем $0.19 \cdot 4 = 0.76$, то результатом будет исход $2$, а если больше, то исход $1$ (здесь случай равенства несуществен, его можно приписать к любой альтернативе). Эта передача обеспечит нужное увеличение доли для исхода $1$ и уменьшение $-$ для исхода $2$. Исход $1$ служит здесь "реципиентом" для "донора", исхода $2$.

Такую передачу "вероятностной массы" можно проводить в каждом диапазоне, причем если "владельцами диапазонов" удобно назначать различные исходы, то реципиентами разных диапазонов могут быть одни и те же исходы. Например, взяв ту же схему с четырьмя исходами, назначим реципиентом при исходе $0$ исход $3$ с долей $0.07$, при исходе $1$ $-$ исход $2$ с долей $0.11$, при исходе $2$ $-$ исход $3$ с долей $0.14$, наконец, при исходе $3$ $-$ исход $1$ с долей $0$. Подсчитаем окончательную вероятность получения каждого исхода:

$p_0 = 0.25- 0.07 = 0.18$,

$p_1 = 0.25 - 0.11 + 0 = 0.14$,

$p_2 = 0.25 - 0.14 + 0.11 = 0.22$,

$p_3 = 0.25 + 0.07 + 0.14 = 0.46$.

А создание по этой схеме очередного значения будет таким же простым, как и раньше: только в каждом диапазоне нужно будет решать, какой выбирать исход, основной или дополнительный. Сложность розыгрыша не зависит от количества исходов.

Такую схему можно создать для любого распределения вероятностей, причем у каждого исхода-донора будет только один исход-реципиент. Схема создается последовательно. На каждом шаге выбирается донор, не полностью использующий свою долю, и реципиент, которому требуется добавка. Конечно, после каждой передачи нужно исключить из рассмотрения донора и уменьшить долю реципиента, так что на следующих итерациях он может сам стать донором.

Пример: Возьмем распределение $p_A = 0.07$, $p_B = 0.31$, $p_C = 0.35$ и $p_D = 0.27$. Для него мы можем получить:

Донор Барьер Реципиент Остаток у реципиента
A $0.07 \cdot 4$ B $0.31 - 0.18 = 0.13$
B $0.13 \cdot 4$ D $0.27 - 0.12 = 0.15$
D $0.15 \cdot 4$ C $0.35 - 0.10 = 0.25$
C $0.25 \cdot 4$ A $0$

При моделировании эти числа используются так: разыгрывается случайное число $x \in [0, 1]$, пусть получилось $x = 0.531$. Это число умножается на $k$: $0.531 \times 4 = 2.124$. Целая часть произведения определяет строку таблицы, считая от нуля, значит, третью сверху строку с основным исходом $D$ и дополнительным $C$. Дробная часть произведения $0.124$ сравнивается с барьером $0.6$, и так как барьер выше, то принимается основной исход.

Общий случай

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

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

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

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

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

[math] k^t \ge 2n, t \ge \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, q_j, \sum\limits_{j}q_j = 1. [/math] Берем [math] p_i [/math] и пусть оно максимальной длины. Проводим [math] t [/math] экспериментов. [math]{p_i}^t \lt \frac{1}{2n}, [/math] все остальные еще меньше. Суммарная длина отрезков не больше [math]\frac{1}{2}.[/math] Нужно [math] t \ge \log\limits_{p}\frac{1}{2n} [/math]



Вывод: из любого исходного распределения можно получить любое нужное нам распределение.

</wikitex>

См. также

Литература