Изменения

Перейти к: навигация, поиск

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

5197 байт добавлено, 07:27, 18 декабря 2011
Нет описания правки
что при исходах 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$. Подсчитаем окончательную вероятность получения каждого исхода:
<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$.
</center>
 
А создание по этой схеме очередного значения будет таким же простым, как и раньше: только в каждом диапазоне нужно будет решать, какой выбирать исход, основной или дополнительный. Сложность розыгрыша не зависит от количества исходов.
 
Такую схему можно создать для любого распределения вероятностей, причем у каждого исхода-донора будет только один исход-реципиент. Схема создается последовательно. На каждом шаге выбирается донор, не полностью использующий свою долю, и реципиент, которому требуется добавка. Конечно, после каждой передачи нужно исключить из рассмотрения донора и уменьшить долю реципиента, так что на следующих итерациях он может сам стать донором.
 
Пример: Возьмем распределение $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>
==См. также==
285
правок

Навигация