Изменения
→Общий случай
==Общий случай==
{|class = "wikitable" style="text-align:center;"| рис. <tex>1</tex> || рис. <tex>2</tex> || рис. <tex>3</tex> |-|width = "210px"| [[Файл:Sim pic1.JPG|200px]] ||width = "210px"|[[Файл:Sim pic2.JPG|170px200px]] |left|thumbwidth = "210px"|В распределении q количество элементарных исходов равно 2[[Файл:Sim pic3.JPG|200px]]|}
Допустим у нас есть распределение <tex>p.</tex> Нам нужно получить распределение <tex>q</tex>.
Для начала рассмотрим случай, когда все <tex>p_i = \dfrac{1}{k},</tex> а в распределении <tex>q </tex> количество элементарных исходов равно <tex>2</tex> <tex>(</tex>рис. <tex>1).</tex> Проводим эксперимент: если попадаем в область пересекающуюся с <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>
<tex> k^t \geqslant 2n, t \geqslant \log\limits_{k}2n </tex>
Отрезок разбился на <tex> k^t </tex> отрезков. Стык будет не более, чем в половине отрезков. Математическое ожидание количества экспериментов <tex> \approx 2t </tex>
<tex>p_i, \sum\limits_{i}p_i = 1,</tex> <tex>q_j, \sum\limits_{j}q_j = 1</tex> Берем <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>
