Изменения

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

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

18 байт добавлено, 01:05, 16 января 2011
Нет описания правки
* <tex>p = \frac{1}{k}, q_1 </tex> и <tex> q_2, q_1 + q_2 = 1.</tex> Проводим эксперимент, если попадаем в область пересекающуюся с <tex> q_1 </tex> и <tex> q_2,</tex> то увеличиваем ее и повторяем эксперимент. Вероятность неудачи на шаге {{---}} <tex>\frac{1}{k}</tex> Математическое ожидание количества экспериментов {{---}} <tex> \frac{k}{k-1}, max(\frac{k}{k-1}) = 2</tex> <tex>(k = 2) </tex>
* <tex>p = \frac{1}{k}, q_j, \sum\limits_{j}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>
* <tex>p_i, \sum\limits_{i}p_i = 1, q_j, \sum\limits_{j}q_j = 1. </tex> Берем p_i и пусть оно максимальной длины. Проводим <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>
Вывод: из любого исходного распределения можно получить любое.
==См. также==
Анонимный участник

Навигация