Изменения

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

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

519 байт добавлено, 22:10, 10 марта 2018
Нет описания правки
<wikitex>
==Распределение==
[[Файл:Распределение1_4.JPG‎|200px|thumb|right|Геометрическое распределение с p = 3/4]]
{{Определение
|definition =
'''Распределение вероятностей'''{{---}} закон, описывающий область значений случайной величины и вероятность их исхода. }}[[Файл:Распределение1_4.JPG‎|200px|thumb|right|Геометрическое распределение с p = 3/4]] Законом распределения дискретной случайной величины <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>
==Примеры распределений==
Для того, чтобы создать необходимое распределение вероятностей, достаточно иметь последовательность независимых случайных величин типа "честной монеты".
Например, для создания схемы с двумя исходами $A_1$ и $A_2$:
<center>$P(A_1)=\fracdfrac{3}{4}$ $,$ $P(A_2)=\fracdfrac{1}{4}$</center>
можно из датчика случайных двоичных величин получить два результата "честной монеты" $\delta_1$ и $\delta_2$ и, например, при $\delta_1 = \delta_2 = 1$ выработать исход $A_2$, а в остальных случаях $A_1$.
Аналогично для схемы с четырьмя исходами
<center>$P(A_1)=\fracdfrac{3}{16}$ $,$ $P(A_2)=\fracdfrac{1}{16}$ $,$ $P(A_3)=\fracdfrac{8}{16}$ $,$ $P(A_4)=\fracdfrac{4}{16}$</center>
можно получить четыре результата "честной монеты" $\delta_1$ $,$ $\delta_2$ $,$ $\delta_3$ $,$ $\delta_4$ и любым способом сопоставить трём из 16 возможных наборов исход $A_1$, одному $-$ $A_2$, восьми $-$ $A_3$, четырём $-$ $A_4$.
Если же вероятности исходов не кратны $2^{-k}$, можно применить два различных варианта действий.
:#Пусть все вероятности $n_i$ $-$ дроби со знаменателем $r$. Найдём $k$, для которого $r < 2^k$. Предложим схему с $k$ результатами "честной монеты", в которой $r$ наборов используются для выработки случайного исхода, а остальные $2^{k}-r$ наборов объявляются "неудачными" и требуют повторного эксперимента (пока не встретится удачный). Чем выше доля полезных исходов равная $r2^{-k}$, тем схема будет эффективнее.
Количество результатов "честной монеты" $\lambda$, которые необходимы для формирования случайного исхода, $-$ это случайная величина. Её математическое ожидание:
<center>$E\lambda = \fracdfrac{1}{2}\cdot1+\fracdfrac{1}{4}\cdot2+\fracdfrac{1}{8}\cdot3+\fracdfrac{1}{16}\cdot3+\fracdfrac{1}{16}\cdot4 = 1\fracdfrac{7}{8}$</center>Можно сделать схему более экономной, используя свойство датчика случайных чисел формировать не отдельные результаты "честной монеты", а целые наборы их, например в виде числа, равномерно распределённого в $[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 leqslant s_i$. Найденное значение индекса $i$ и определяет исход $A_i$.
Индекс $i$ можно определять непосредственно просмотром $s_i$ подряд. Если $k$ велико, можно применять специальные приёмы ускоренного поиска, например, деление множества индексов примерно пополам.
Допустим у нас есть распределение <tex>p.</tex> Нам нужно получить распределение <tex>q</tex>.
Для начала рассмотрим случай, когда все <tex>p_i = \fracdfrac{1}{k},</tex> а в распределении <tex>q </tex> количество элементарных исходов равно <tex>2.</tex> Проводим эксперимент: если попадаем в область пересекающуюся с <tex> q_1 </tex> и <tex> q_2,</tex> то увеличиваем ее и повторяем эксперимент. На рисунке слева красным обозначенно распределение <tex> q. </tex> Вероятность того, что на этом шаге эксперимент не закончится {{---}} <tex>\fracdfrac{1}{k}.</tex> Математическое ожидание количества экспериментов {{---}} <tex> \fracdfrac{k}{k-1}, max(\fracdfrac{k}{k-1}) = 2 (</tex>при <tex>k = 2) </tex>
[[Файл:Sim pic2.JPG‎|170px|right|thumb|Количество элементарных исходов распределения q равно n]]
Теперь рассмотрим случай, когда все элементарные исходы <tex>p_i</tex> по-прежнему равновероятны <tex>(p_i = \fracdfrac{1}{k}),</tex>а количество элементарных исходов распределения <tex>q</tex> равно <tex>n (\sum\limits_{j=1}^{n}q_j = 1).</tex> Повторим эксперимент <tex> t </tex> раз.
<tex> k^t \ge geqslant 2n, t \ge geqslant \log\limits_{k}2n </tex>
Отрезок разбился на <tex> k^t </tex> отрезков. Стык будет не более, чем в половине отрезков. Математическое ожидание количества экспериментов <tex> \approx 2t </tex>
<tex>q_j, \sum\limits_{j}q_j = 1</tex>
Берем <tex>p_i</tex>, и пусть оно максимальной длины. Проводим <tex>t</tex> экспериментов. <tex>{p_i}^t < \fracdfrac{1}{2n}, </tex> все остальные еще меньше. Суммарная длина отрезков не больше <tex>\fracdfrac{1}{2}.</tex> Нужно <tex> t \ge geqslant \log\limits_{p}\fracdfrac{1}{2n} </tex>
Таким образом, из любого исходного распределения можно получить нужное нам распределение.
Вывод: из любого исходного распределения можно получить любое нужное нам распределение.
</wikitex>
==См. также==
*[[Условная вероятность]]
==Литература==
*Боровков А.А. Математическая статистика: оценка параметров, проверка гипотез. {{- --}} М., Физматлит, 1984, {{---}} стр. 71.*[http://sheen.me/books/spec/apia.djvu Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн {{--- }} Алгоритмы. Построение и анализ 1244c{{---}} М. : ООО "И. Д. Вильямс", 2013. {{---}} 1328 с. {{---}} стр. 1254.]*Романовский И.В. Дискретный анализ{{---}} Элементы теории вероятностей и математической статистики (теория и задачи): учебное пособие. {{---}} Омск, издатель ИП Скорнякова Е.В., 2012. {{---}} 189 с. {{---}} стр. 34. 
[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Теория вероятности ]]
Анонимный участник

Навигация