285
правок
Изменения
Нет описания правки
При моделировании эти числа используются так: разыгрывается случайное число $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>
==См. также==
