Симуляция одним распределением другого — различия между версиями
Borisov (обсуждение | вклад) (→Симуляция распределений) |
Borisov (обсуждение | вклад) (→Симуляция распределений) |
||
| Строка 8: | Строка 8: | ||
* Равномерное распределение | * Равномерное распределение | ||
| + | <wikitex> | ||
==Симуляция распределений== | ==Симуляция распределений== | ||
| − | + | Для того, чтобы создать необходимое распределение вероятностей, достаточно иметь последовательность независимых случайных величин типа "честной монеты". | |
| − | + | Например, для создания схемы с двумя исходами $A_1$ и $A_2$: | |
| − | + | <center>$P(A_1)=\frac{3}{4}$ $,$ $P(A_2)=\frac{1}{4}$</center> | |
| − | + | можно из датчика случайных двоичных разрядов получить два двоичных разряда $\delta_1$ и $\delta_2$ и, например, при $\delta_1 = \delta_2 = 1$ выработать исход $A_2$, а в остальных случаях $A_1$. | |
| − | + | Аналогично для схемы с четырьмя исходами | |
| − | + | <center>$P(A_1)=\frac{3}{16}$ $,$ $P(A_2)=\frac{1}{16}$ $,$ $P(A_3)=\frac{8}{16}$ $,$ $P(A_4)=\frac{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$ наборов объявляются "неудачными" и требуют повторного эксперимента (пока не встретится удачный). Чем выше доля полезных исходов равная $r2^{-k}$, тем схема будет эффективнее. | |
| − | + | Количество случайных двоичных разрядов $\lambda$, которые необходимы для формирования случайного исхода, $-$ это случайная величина. Её математическое ожидание: | |
| − | + | <center>$E\lambda = \frac{1}{2}\cdot1+\frac{1}{4}\cdot2+\frac{1}{8}\cdot3+\frac{1}{16}\cdot3+\frac{1}{16}\cdot4 = 1\frac{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 s_i$. Найденное значение индекса $i$ и определяет исход $A_i$. | |
| − | [ | + | |
| − | + | Индекс $i$ можно определять непосредственно просмотром $s_i$ подряд. Если $k$ велико, можно применять специальные приёмы ускоренного поиска, например, деление множества индексов примерно пополам. | |
| − | + | ||
| − | + | Самую эффективную схему предложил в 1977 г. А. Уолкер. | |
| + | </wikitex> | ||
==См. также== | ==См. также== | ||
Версия 06:48, 18 декабря 2011
Содержание
Распределение
Распределение — одно из основных понятий теории вероятностей и математической статистике. Распределение вероятностей какой-либо случайной величины задается в простейшем случае указанием возможных значений этой величины и соответствующих им вероятностей, в более сложных — т. н. функцией распределения или плотностью вероятности.
Примеры распределений
- Биномиальное распределение
- Нормальное распределение
- Равномерное распределение
<wikitex>
Симуляция распределений
Для того, чтобы создать необходимое распределение вероятностей, достаточно иметь последовательность независимых случайных величин типа "честной монеты". Например, для создания схемы с двумя исходами $A_1$ и $A_2$:
можно из датчика случайных двоичных разрядов получить два двоичных разряда $\delta_1$ и $\delta_2$ и, например, при $\delta_1 = \delta_2 = 1$ выработать исход $A_2$, а в остальных случаях $A_1$. Аналогично для схемы с четырьмя исходами
можно получить четыре двоичных разряда $\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$ наборов объявляются "неудачными" и требуют повторного эксперимента (пока не встретится удачный). Чем выше доля полезных исходов равная $r2^{-k}$, тем схема будет эффективнее.
Количество случайных двоичных разрядов $\lambda$, которые необходимы для формирования случайного исхода, $-$ это случайная величина. Её математическое ожидание:
Можно сделать схему более экономной, используя свойство датчиков случайных чисел формировать не отдельные двоичные разряды, а целые наборы их, например в виде числа, равномерно распределённого в $[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 s_i$. Найденное значение индекса $i$ и определяет исход $A_i$.
Индекс $i$ можно определять непосредственно просмотром $s_i$ подряд. Если $k$ велико, можно применять специальные приёмы ускоренного поиска, например, деление множества индексов примерно пополам.
Самую эффективную схему предложил в 1977 г. А. Уолкер. </wikitex>
См. также
Литература
- Боровков А.А. Математическая статистика: оценка параметров, проверка гипотез. - М., Физматлит, 1984.
- Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы. Построение и анализ 1244c.
