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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 46 промежуточных версий 6 участников)
Строка 1: Строка 1:
<wikitex>
+
 
 
==Распределение==
 
==Распределение==
[[Файл:Распределение1_4.JPG‎|200px|thumb|right|Геометрическое распределение с p = 3/4]]
+
{{Определение
'''Распределение — '''одно из основных понятий теории вероятностей и математической статистике. Распределение вероятностей какой-либо случайной величины задается в простейшем случае указанием возможных значений этой величины и соответствующих им вероятностей, в более сложных — т. н. функцией распределения или плотностью вероятности.
+
|definition =
 +
Пусть <tex>\xi</tex> является случайной величиной, а <tex>A</tex> {{---}} ее множеством значений. Функция <tex>P: 2^A  \rightarrow \mathbb R,</tex> определенная как <tex>P(B) = P(\xi  \in B),</tex> называется '''распределением случайной величины''' (англ. ''probability distribution''), то есть представляет собой набор  вероятностей, с которыми случайная величина принимает те или иные значения. }}
 +
[[Файл:РаспределениеUPD.jpeg‎|200px|thumb|right|Геометрическое распределение с <tex>p = \dfrac {3} {4}</tex>]]
 +
 
 +
Закон распределения дискретной случайной величины <tex>\xi</tex> задается таблицей:
 +
 
 +
<tex>\xi: \begin{pmatrix}
 +
x_1 & x_2 & \ldots & x_n \\
 +
p_1 & p_2 & \ldots & p_n\end{pmatrix}, </tex>
 +
 
 +
где <tex>x_1 < x_2 < \ldots < x_n</tex> {{---}} всевозможные значения величины <tex>\xi,</tex> а <tex>p_i(i = 1, \ldots,
 +
n)</tex> {{---}} их вероятности, то есть <tex>p_i = P(\xi = x_i).</tex>
 +
 
 +
При этом должно выполняться равенство: <tex>p_1 + p_2 + \ldots + p_n = 1.</tex>
 +
 
 +
Это равенство означает, что при испытании одно из значений заведомо реализуется. Таблица показывает, как суммарная вероятность <tex>100\%</tex> распределяется по возможным значениям случайной величины.
 +
 
 +
Для непрерывных случайных величин задание закона распределения в виде такой таблицы невозможно, поэтому его задают двумя другими способами:
 +
 
 +
:#С помощью [[Дискретная_случайная_величина#.D0.A4.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D1.8F_.D1.80.D0.B0.D1.81.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|функции распределения]] <tex>F (x);</tex>
 +
:#С помощью [[Дискретная_случайная_величина#.D0.A4.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D1.8F_.D0.BF.D0.BB.D0.BE.D1.82.D0.BD.D0.BE.D1.81.D1.82.D0.B8_.D1.80.D0.B0.D1.81.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F_.D0.B2.D0.B5.D1.80.D0.BE.D1.8F.D1.82.D0.BD.D0.BE.D1.81.D1.82.D0.B5.D0.B9|плотности вероятности]] <tex>f (x).</tex>
  
 
==Примеры распределений==
 
==Примеры распределений==
* Биномиальное распределение
+
===Биномиальное распределение (закон Бернулли)===
* Нормальное распределение
+
{{Определение
* Равномерное распределение
+
|definition=
 +
Дискретная случайная величина <tex>\xi</tex> называется '''биномиальной''' (англ. ''binomial random variable'') с параметрами <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> где <tex>i = 1, \ldots, n;</tex> <tex>q = 1 - p,</tex>  <tex>p \in (0, 1).</tex>}}
 +
 
 +
===Нормальное распределение (распределение Гаусса)===
 +
{{Определение
 +
|definition=
 +
Непрерывную случайную величину <tex>\xi</tex> называют '''нормальной''' (англ. ''normal deviate'') с параметрами <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> называется '''равномерно распределенной''' (англ. ''uniformly distributed random variable'') на <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>}}
  
 
==Симуляция распределений==
 
==Симуляция распределений==
 
Для того, чтобы создать необходимое распределение вероятностей, достаточно иметь последовательность независимых случайных величин типа "честной монеты".
 
Для того, чтобы создать необходимое распределение вероятностей, достаточно иметь последовательность независимых случайных величин типа "честной монеты".
 +
 
Например, для создания схемы с двумя исходами $A_1$ и $A_2$:
 
Например, для создания схемы с двумя исходами $A_1$ и $A_2$:
<center>$P(A_1)=\frac{3}{4}$ $,$  $P(A_2)=\frac{1}{4}$</center>
+
$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$.
 +
 
 
Аналогично для схемы с четырьмя исходами
 
Аналогично для схемы с четырьмя исходами
<center>$P(A_1)=\frac{3}{16}$ $,$ $P(A_2)=\frac{1}{16}$ $,$ $P(A_3)=\frac{8}{16}$ $,$ $P(A_4)=\frac{4}{16}$</center>
+
$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$ наборов объявляются "неудачными" и требуют повторного эксперимента (пока не встретится удачный). Чем выше доля полезных исходов равная  $r2^{-k}$, тем схема будет эффективнее.
+
:#Пусть все вероятности $n_i$ $-$ дроби со знаменателем $r$. Найдём $k$, для которого $r < 2^k$. Предложим схему с $k$ результатами "честной монеты", в которой $r$ наборов используются для выработки случайного исхода, а остальные $2^{k}-r$ наборов объявляются "неудачными" и требуют повторного эксперимента (пока не встретится удачный). Чем выше доля полезных исходов равная  $r2^{-k}$, тем схема будет эффективнее.
Количество случайных двоичных разрядов $\lambda$, которые необходимы для формирования случайного исхода, $-$  это случайная величина. Её математическое ожидание:
+
 
<center>$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}$</center>
+
Количество результатов "честной монеты" $\lambda$, которые необходимы для формирования случайного исхода, $-$  это случайная величина. Её математическое ожидание:
Можно сделать схему более экономной, используя свойство датчиков случайных чисел формировать не отдельные двоичные разряды, а целые наборы их, например в виде числа, равномерно распределённого в $[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$.
+
 
 +
$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$ подряд.
 +
 
 +
Рассмотрим приведенный выше пример с четырьмя исходам. В данном случае суммы $s_0, \ldots, s_4$ будут принимать значения <tex>0,</tex> <tex>\dfrac{3}{16},</tex> <tex>\dfrac{4}{16},</tex> <tex>\dfrac{12}{16}</tex> и <tex>1</tex> соответственно. Значению $\gamma = 0,5$ будет соответствовать $i = 3$, то есть оно будет определять исход события $A_3.$ Таким же образом, $\gamma = 0,985$ определяет исход события $A_4.$
 +
 
 +
Если $k$ велико, можно применять специальные приёмы ускоренного поиска, например, деление множества индексов примерно пополам.
 +
 
 +
==Общий случай==
 +
{|class = "wikitable" style="text-align:center;"
 +
| рис. <tex>1</tex> ||  рис. <tex>2</tex> ||  рис. <tex>3</tex>
 +
|-
 +
|width = "280px"| [[Файл:Sim pic1.JPG|270px]] ||width = "280px"|[[Файл:Sim pic2.JPG‎|270px]] ||width = "280px"|[[Файл:Sim pic3.JPG‎|270px]]
 +
|}
 +
 
 +
Допустим у нас есть распределение <tex>p.</tex> Нам нужно получить распределение <tex>q</tex>.
 +
 
 +
Для начала рассмотрим случай, когда все <tex>p_i = \dfrac{1}{k},</tex> а в распределении <tex>q </tex>  количество элементарных исходов равно <tex>2</tex>  <tex>(</tex>рис. <tex>1).</tex>
  
Индекс $i$ можно определять непосредственно просмотром $s_i$ подряд. Если $k$ велико, можно применять специальные приёмы ускоренного поиска, например, деление множества индексов примерно пополам.
+
Проводим эксперимент: если попадаем в область пересекающуюся с <tex> q_1 </tex> и <tex> q_2,</tex> то увеличиваем ее и повторяем эксперимент. На рис. <tex>1</tex> красным обозначено распределение <tex> q. </tex> Вероятность того, что на этом шаге эксперимент не закончится {{---}} <tex>\dfrac{1}{k}.</tex> Математическое ожидание количества экспериментов {{---}} <tex> \dfrac{k}{k-1},  
 +
max(\dfrac{k}{k-1}) = 2</tex>  <tex>(</tex>при <tex>k = 2).</tex>
  
Самую эффективную схему предложил в 1977 г. А. Уолкер.
 
  
==Схема Уолкера==
+
Теперь рассмотрим случай, когда все элементарные исходы <tex>p_i</tex> по-прежнему равновероятны <tex>(p_i = \dfrac{1}{k}),</tex>а количество элементарных исходов распределения <tex>q</tex> равно <tex>n (\sum\limits_{j=1}^{n}q_j = 1)</tex>  <tex>(</tex>рис. <tex>2).</tex> Повторим эксперимент <tex> t </tex> раз.
Если бы все исходы имели одинаковые вероятности, моделировать такое распределение было бы очень просто. В такой ситуации достаточно разделить отрезок $[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$.
+
<tex> k^t \geqslant 2n, t \geqslant \log\limits_{k}2n </tex>
  
Такую передачу "вероятностной массы" можно проводить в каждом диапазоне, причем если "владельцами диапазонов" удобно назначать различные исходы, то реципиентами разных диапазонов могут быть одни и те же исходы. Например, взяв ту же схему с четырьмя исходами, назначим реципиентом при исходе $0$ исход $3$ с долей $0.07$, при
+
Отрезок разбился на <tex> k^t </tex> отрезков. Стык будет не более, чем в половине отрезков. Математическое ожидание количества экспериментов <tex> \approx 2t </tex>
исходе $1$ $-$ исход $2$ с долей $0.11$, при исходе $2$ $-$ исход $3$ с долей $0.14$,
 
наконец, при исходе $3$ $-$ исход $1$ с долей $0$. Подсчитаем окончательную вероятность получения каждого исхода:
 
<center>
 
$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$.
+
<tex>p_i, \sum\limits_{i}p_i = 1,</tex> <tex>q_j, \sum\limits_{j}q_j = 1</tex>
</center>
 
  
А создание по этой схеме очередного значения будет таким же простым, как и раньше: только в каждом диапазоне нужно будет решать, какой выбирать исход, основной или дополнительный. Сложность розыгрыша не зависит от количества исходов.
+
Берем <tex>p_i</tex>, и пусть оно максимальной длины <tex>(</tex>рис. <tex>3).</tex> Проводим <tex>t</tex> экспериментов. <tex>{p_i}^t < \dfrac{1}{2n}, </tex> все остальные еще меньше. Суммарная длина отрезков не больше <tex>\dfrac{1}{2}.</tex> Нужно <tex> t \geqslant \log\limits_{p}\dfrac{1}{2n} .</tex>
  
Такую схему можно создать для любого распределения вероятностей, причем у каждого исхода-донора будет только один исход-реципиент. Схема создается последовательно. На каждом шаге выбирается донор, не полностью использующий свою долю, и реципиент, которому требуется добавка. Конечно, после каждой передачи нужно исключить из рассмотрения донора и уменьшить долю реципиента, так что на следующих итерациях он может сам стать донором.
 
  
Пример: Возьмем распределение $p_A = 0.07$, $p_B = 0.31$, $p_C - 0.35$ и $p_D - 0.27$. Для него мы можем получить:
+
Таким образом, из любого исходного распределения мы можем получить нужное нам распределение.
<center>
 
{| class="wikitable"
 
|-
 
! Донор !! Барьер !! Реципиент !! Остаток у реципиента
 
|-
 
| 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$
 
|}
 
</center>
 
При моделировании эти числа используются так: разыгрывается случайное число $x \in [0, 1]$, пусть получилось $x = 0.531$. Это число умножается на $k$: $0.531 \times 4 = 2.124$. Целая часть произведения определяет строку таблицы, считая от нуля, значит, третью сверху строку с основным исходом $D$ и дополнительным $C$. Дробная часть произведения $0.124$ сравнивается с барьером $0.6$, и так как барьер выше, то принимается основной исход.
 
  
</wikitex>
 
 
==См. также==  
 
==См. также==  
 
*[[Условная вероятность]]
 
*[[Условная вероятность]]
Строка 76: Строка 108:
 
*[[Дисперсия случайной величины]]
 
*[[Дисперсия случайной величины]]
  
==Литература==
+
==Источники информации==
*Боровков А.А. Математическая статистика: оценка параметров, проверка гипотез. - М., Физматлит, 1984.
+
*Боровков А.А. Математическая статистика: оценка параметров, проверка гипотез. {{---}} М., Физматлит, 1984, {{---}} стр. 71.
*[http://sheen.me/books/spec/apia.djvu Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы. Построение и анализ 1244c.]
+
*[http://sheen.me/books/spec/apia.djvu Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн {{---}} Алгоритмы. Построение и анализ {{---}} М. : ООО "И. Д. Вильямс", 2013. {{---}} 1328 с. {{---}} стр. 1254.]
*Романовский И.В. Дискретный анализ
+
*Романовский И. В. {{---}} Элементы теории вероятностей и математической статистики (теория и задачи): учебное пособие. {{---}} Омск, издатель ИП Скорнякова Е.В., 2012. {{---}} 189 с. {{---}} стр. 34.
 +
 
 +
 
 +
[[Категория:Дискретная математика и алгоритмы]]
 +
 
 +
[[Категория: Теория вероятности ]]

Текущая версия на 19:07, 4 сентября 2022

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

Определение:
Пусть [math]\xi[/math] является случайной величиной, а [math]A[/math] — ее множеством значений. Функция [math]P: 2^A \rightarrow \mathbb R,[/math] определенная как [math]P(B) = P(\xi \in B),[/math] называется распределением случайной величины (англ. probability distribution), то есть представляет собой набор вероятностей, с которыми случайная величина принимает те или иные значения.
Геометрическое распределение с [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] распределяется по возможным значениям случайной величины.

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

  1. С помощью функции распределения [math]F (x);[/math]
  2. С помощью плотности вероятности [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{n}{k} p^k q^{n - k},[/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 {1} {\sigma \sqrt{2\pi}} {\large e^{-\frac {(x - a)^2} {2\sigma^2}}}.[/math]


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

Определение:
Непрерывная случайная величина [math]\xi[/math] называется равномерно распределенной (англ. uniformly distributed random variable) на [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$ подряд.

Рассмотрим приведенный выше пример с четырьмя исходам. В данном случае суммы $s_0, \ldots, s_4$ будут принимать значения [math]0,[/math] [math]\dfrac{3}{16},[/math] [math]\dfrac{4}{16},[/math] [math]\dfrac{12}{16}[/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]
Sim pic1.JPG Sim pic2.JPG Sim pic3.JPG

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

Для начала рассмотрим случай, когда все [math]p_i = \dfrac{1}{k},[/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{1}{k}.[/math] Математическое ожидание количества экспериментов — [math] \dfrac{k}{k-1}, max(\dfrac{k}{k-1}) = 2[/math] [math]([/math]при [math]k = 2).[/math]


Теперь рассмотрим случай, когда все элементарные исходы [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]([/math]рис. [math]2).[/math] Повторим эксперимент [math] t [/math] раз.

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

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


[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]([/math]рис. [math]3).[/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]


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

См. также

Источники информации