Симуляция одним распределением другого — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 36 промежуточных версий 5 участников)
Строка 1: Строка 1:
<wikitex>
+
 
 
==Распределение==
 
==Распределение==
[[Файл:Распределение1_4.JPG‎|200px|thumb|right|Геометрическое распределение с p = 3/4]]
+
{{Определение
'''Распределение — '''одно из основных понятий в теории вероятностей и математической статистике. Распределение вероятностей какой-либо случайной величины задается в простейшем случае указанием возможных значений этой величины и соответствующих им вероятностей, в более сложных — т. н. функцией распределения или плотностью вероятности.
+
|definition =
 +
Пусть <tex>\xi</tex> является случайной величиной, а <tex>A</tex> {{---}} ее множеством значений. Функция <tex>P: 2^A  \rightarrow \mathbb R,</tex> определенная как <tex>P(B) = P(\xi  \in B),</tex> называется '''распределением случайной величины''' (англ. ''probability distribution''), то есть представляет собой набор  вероятностей, с которыми случайная величина принимает те или иные значения. }}
 +
[[Файл:РаспределениеUPD.jpeg‎|200px|thumb|right|Геометрическое распределение с <tex>p = \dfrac {3} {4}</tex>]]
 +
 
 +
Закон распределения дискретной случайной величины <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>
 +
 
 +
Это равенство означает, что при испытании одно из значений заведомо реализуется. Таблица показывает, как суммарная вероятность <tex>100\%</tex> распределяется по возможным значениям случайной величины.
 +
 
 +
Для непрерывных случайных величин задание закона распределения в виде такой таблицы невозможно, поэтому его задают двумя другими способами:
 +
 
 +
:#С помощью [[Дискретная_случайная_величина#.D0.A4.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D1.8F_.D1.80.D0.B0.D1.81.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|функции распределения]] <tex>F (x);</tex>
 +
:#С помощью [[Дискретная_случайная_величина#.D0.A4.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D1.8F_.D0.BF.D0.BB.D0.BE.D1.82.D0.BD.D0.BE.D1.81.D1.82.D0.B8_.D1.80.D0.B0.D1.81.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F_.D0.B2.D0.B5.D1.80.D0.BE.D1.8F.D1.82.D0.BD.D0.BE.D1.81.D1.82.D0.B5.D0.B9|плотности вероятности]] <tex>f (x).</tex>
  
 
==Примеры распределений==
 
==Примеры распределений==
* Биномиальное распределение
+
===Биномиальное распределение (закон Бернулли)===
* Нормальное распределение
+
{{Определение
* Равномерное распределение
+
|definition=
 +
Дискретная случайная величина <tex>\xi</tex> называется '''биномиальной''' (англ. ''binomial random variable'') с параметрами <tex>(n, p),</tex> если она принимает значения от <tex>0</tex> до <tex>n</tex> и вероятности вычисляются по формуле <tex>p_i = P(\xi = i) = \dbinom{n}{k} p^k q^{n - k},</tex> где <tex>i = 1, \ldots, n;</tex> <tex>q = 1 - p,</tex>  <tex>p \in (0, 1).</tex>}}
  
 +
===Нормальное распределение (распределение Гаусса)===
 +
{{Определение
 +
|definition=
 +
Непрерывную случайную величину <tex>\xi</tex> называют '''нормальной''' (англ. ''normal deviate'') с параметрами <tex>(a, \sigma)</tex> и пишут <tex>\xi = N (a, \sigma),</tex> если ее плотность вероятности дается формулой
 +
<tex>f(x) = \dfrac {1} {\sigma \sqrt{2\pi}} {\large e^{-\frac {(x - a)^2} {2\sigma^2}}}.</tex>}}
 +
 +
===Равномерное распределение===
 +
{{Определение
 +
|definition=
 +
Непрерывная случайная величина <tex>\xi</tex> называется '''равномерно распределенной''' (англ. ''uniformly distributed random variable'') на <tex>[a, b],</tex> если ее плотность вероятности дается формулой
 +
 +
<tex>
 +
f(x)=
 +
\begin{cases}
 +
\dfrac {1} {b - a}, & \mbox{if } x \in [a, b] \\
 +
0, & \mbox{otherwise.}
 +
\end{cases}</tex>}}
  
 
==Симуляция распределений==
 
==Симуляция распределений==
 
Для того, чтобы создать необходимое распределение вероятностей, достаточно иметь последовательность независимых случайных величин типа "честной монеты".
 
Для того, чтобы создать необходимое распределение вероятностей, достаточно иметь последовательность независимых случайных величин типа "честной монеты".
 +
 
Например, для создания схемы с двумя исходами $A_1$ и $A_2$:
 
Например, для создания схемы с двумя исходами $A_1$ и $A_2$:
<center>$P(A_1)=\frac{3}{4}$ $,$  $P(A_2)=\frac{1}{4}$</center>
+
$P(A_1)=\dfrac{3}{4}$ $,$  $P(A_2)=\dfrac{1}{4}$
можно из датчика случайных двоичных величин получить два  результата "честой монеты" $\delta_1$ и $\delta_2$  и, например, при $\delta_1 = \delta_2 = 1$  выработать исход $A_2$, а в остальных случаях $A_1$.
+
можно из датчика случайных двоичных величин получить два  результата "честной монеты" $\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>
+
$P(A_1)=\dfrac{3}{16}$ $,$ $P(A_2)=\dfrac{1}{16}$ $,$ $P(A_3)=\dfrac{8}{16}$ $,$ $P(A_4)=\dfrac{4}{16}$
 
можно получить четыре результата "честной монеты" $\delta_1$ $,$ $\delta_2$ $,$ $\delta_3$ $,$ $\delta_4$ и любым способом сопоставить трём из 16 возможных наборов исход $A_1$, одному $-$ $A_2$, восьми $-$ $A_3$, четырём $-$ $A_4$.
 
можно получить четыре результата "честной монеты" $\delta_1$ $,$ $\delta_2$ $,$ $\delta_3$ $,$ $\delta_4$ и любым способом сопоставить трём из 16 возможных наборов исход $A_1$, одному $-$ $A_2$, восьми $-$ $A_3$, четырём $-$ $A_4$.
 +
 
Если же вероятности исходов не кратны $2^{-k}$, можно применить два различных варианта действий.
 
Если же вероятности исходов не кратны $2^{-k}$, можно применить два различных варианта действий.
 
:#Можно приблизить вероятности двоичными дробями (с любой точностью), далее работать с полученными приближёнными значениями
 
:#Можно приблизить вероятности двоичными дробями (с любой точностью), далее работать с полученными приближёнными значениями
 
:#Пусть все вероятности $n_i$ $-$ дроби со знаменателем $r$. Найдём $k$, для которого $r < 2^k$. Предложим схему с $k$ результатами "честной монеты", в которой $r$ наборов используются для выработки случайного исхода, а остальные $2^{k}-r$ наборов объявляются "неудачными" и требуют повторного эксперимента (пока не встретится удачный). Чем выше доля полезных исходов равная  $r2^{-k}$, тем схема будет эффективнее.
 
:#Пусть все вероятности $n_i$ $-$ дроби со знаменателем $r$. Найдём $k$, для которого $r < 2^k$. Предложим схему с $k$ результатами "честной монеты", в которой $r$ наборов используются для выработки случайного исхода, а остальные $2^{k}-r$ наборов объявляются "неудачными" и требуют повторного эксперимента (пока не встретится удачный). Чем выше доля полезных исходов равная  $r2^{-k}$, тем схема будет эффективнее.
 +
 
Количество результатов "честной монеты" $\lambda$, которые необходимы для формирования случайного исхода, $-$  это случайная величина. Её математическое ожидание:
 
Количество результатов "честной монеты" $\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$ велико, можно применять специальные приёмы ускоренного поиска, например, деление множества индексов примерно пополам.
+
$E\lambda = \dfrac{1}{2}\cdot1+\dfrac{1}{4}\cdot2+\dfrac{1}{8}\cdot3+\dfrac{1}{16}\cdot3+\dfrac{1}{16}\cdot4 = 1\dfrac{7}{8}.$
 +
 
 +
Можно сделать схему более экономной, если использовать датчик, равномерно формирующий число из диапазона $[0, 1]$. Образуем по данному набору вероятностей $p_i$ накопленные суммы $s_i$, такие, что $s_0 = 0;  s_i = s_{i-1} + p_i,$ для  $i > 0$. Случайный исход будет вырабатываться так: по полученному из датчика случайному числу $\gamma$ находится такой индекс $i$, для которого $s_{i-1} < \gamma \leqslant s_i$. Найденное значение индекса $i$ и определяет исход $A_i$. Индекс $i$ можно определять непосредственно просмотром $s_i$ подряд.  
 +
 
 +
Рассмотрим приведенный выше пример с четырьмя исходам. В данном случае суммы $s_0, \ldots, s_4$ будут принимать значения <tex>0,</tex> <tex>\dfrac{3}{16},</tex> <tex>\dfrac{4}{16},</tex> <tex>\dfrac{12}{16}</tex> и <tex>1</tex> соответственно. Значению $\gamma = 0,5$ будет соответствовать $i = 3$, то есть оно будет определять исход события $A_3.$ Таким же образом, $\gamma = 0,985$ определяет исход события $A_4.$
 +
 
 +
Если $k$ велико, можно применять специальные приёмы ускоренного поиска, например, деление множества индексов примерно пополам.
  
 
==Общий случай==
 
==Общий случай==
[[Файл:Sim pic1.JPG‎|150px|left|thumb|В распределении q количество элементарных исходов равно 2]]
+
{|class = "wikitable" style="text-align:center;"
 +
| рис. <tex>1</tex> ||  рис. <tex>2</tex> ||  рис. <tex>3</tex>
 +
|-
 +
|width = "280px"| [[Файл:Sim pic1.JPG|270px]] ||width = "280px"|[[Файл:Sim pic2.JPG‎|270px]] ||width = "280px"|[[Файл:Sim pic3.JPG‎|270px]]  
 +
|}
 +
 
 
Допустим у нас есть распределение <tex>p.</tex> Нам нужно получить распределение <tex>q</tex>.
 
Допустим у нас есть распределение <tex>p.</tex> Нам нужно получить распределение <tex>q</tex>.
  
Для начала рассмотрим случай, когда все <tex>p_i = \frac{1}{k},</tex> а в распределении <tex>q </tex>  количество элементарных исходов равно <tex>2.</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> 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> q_1 </tex> и <tex> q_2,</tex> то увеличиваем ее и повторяем эксперимент. На рис. <tex>1</tex> красным обозначено распределение <tex> q. </tex> Вероятность того, что на этом шаге эксперимент не закончится {{---}} <tex>\dfrac{1}{k}.</tex> Математическое ожидание количества экспериментов {{---}} <tex> \dfrac{k}{k-1},
Теперь рассмотрим случай, когда все элементарные исходы <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> раз.
+
max(\dfrac{k}{k-1}) = 2</tex>   <tex>(</tex>при <tex>k = 2).</tex>
  
<tex> k^t \ge 2n, t \ge \log\limits_{k}2n </tex>  
+
 
 +
Теперь рассмотрим случай, когда все элементарные исходы <tex>p_i</tex> по-прежнему равновероятны <tex>(p_i = \dfrac{1}{k}),</tex>а количество элементарных исходов распределения <tex>q</tex> равно <tex>n (\sum\limits_{j=1}^{n}q_j = 1)</tex>  <tex>(</tex>рис. <tex>2).</tex> Повторим эксперимент <tex> t </tex> раз.
 +
 
 +
<tex> k^t \geqslant 2n, t \geqslant \log\limits_{k}2n </tex>  
  
 
Отрезок разбился на <tex> k^t </tex> отрезков. Стык будет не более, чем в половине отрезков. Математическое ожидание количества экспериментов <tex> \approx 2t </tex>
 
Отрезок разбился на <tex> k^t </tex> отрезков. Стык будет не более, чем в половине отрезков. Математическое ожидание количества экспериментов <tex> \approx 2t </tex>
  
[[Файл:Sim pic3.JPG‎|150px|left|thumb]]
 
<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>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>  
+
<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>
  
  
Вывод: из любого исходного распределения можно получить любое нужное нам распределение.
+
Таким образом, из любого исходного распределения мы можем получить нужное нам распределение.
</wikitex>
+
 
 
==См. также==  
 
==См. также==  
 
*[[Условная вероятность]]
 
*[[Условная вероятность]]
Строка 57: Строка 108:
 
*[[Дисперсия случайной величины]]
 
*[[Дисперсия случайной величины]]
  
==Литература==
+
==Источники информации==
*Боровков А.А. Математическая статистика: оценка параметров, проверка гипотез. - М., Физматлит, 1984.
+
*Боровков А.А. Математическая статистика: оценка параметров, проверка гипотез. {{---}} М., Физматлит, 1984, {{---}} стр. 71.
*[http://sheen.me/books/spec/apia.djvu Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы. Построение и анализ 1244c.]
+
*[http://sheen.me/books/spec/apia.djvu Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн {{---}} Алгоритмы. Построение и анализ {{---}} М. : ООО "И. Д. Вильямс", 2013. {{---}} 1328 с. {{---}} стр. 1254.]
*Романовский И.В. Дискретный анализ
+
*Романовский И. В. {{---}} Элементы теории вероятностей и математической статистики (теория и задачи): учебное пособие. {{---}} Омск, издатель ИП Скорнякова Е.В., 2012. {{---}} 189 с. {{---}} стр. 34.
 +
 
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
  
 
[[Категория: Теория вероятности ]]
 
[[Категория: Теория вероятности ]]

Текущая версия на 19:07, 4 сентября 2022

Распределение

Определение:
Пусть [math]\xi[/math] является случайной величиной, а [math]A[/math] — ее множеством значений. Функция [math]P: 2^A \rightarrow \mathbb R,[/math] определенная как [math]P(B) = P(\xi \in B),[/math] называется распределением случайной величины (англ. probability distribution), то есть представляет собой набор вероятностей, с которыми случайная величина принимает те или иные значения.
Геометрическое распределение с [math]p = \dfrac {3} {4}[/math]

Закон распределения дискретной случайной величины [math]\xi[/math] задается таблицей:

[math]\xi: \begin{pmatrix} x_1 & x_2 & \ldots & x_n \\ p_1 & p_2 & \ldots & p_n\end{pmatrix}, [/math]

где [math]x_1 \lt x_2 \lt \ldots \lt x_n[/math] — всевозможные значения величины [math]\xi,[/math] а [math]p_i(i = 1, \ldots, n)[/math] — их вероятности, то есть [math]p_i = P(\xi = x_i).[/math]

При этом должно выполняться равенство: [math]p_1 + p_2 + \ldots + p_n = 1.[/math]

Это равенство означает, что при испытании одно из значений заведомо реализуется. Таблица показывает, как суммарная вероятность [math]100\%[/math] распределяется по возможным значениям случайной величины.

Для непрерывных случайных величин задание закона распределения в виде такой таблицы невозможно, поэтому его задают двумя другими способами:

  1. С помощью функции распределения [math]F (x);[/math]
  2. С помощью плотности вероятности [math]f (x).[/math]

Примеры распределений

Биномиальное распределение (закон Бернулли)

Определение:
Дискретная случайная величина [math]\xi[/math] называется биномиальной (англ. binomial random variable) с параметрами [math](n, p),[/math] если она принимает значения от [math]0[/math] до [math]n[/math] и вероятности вычисляются по формуле [math]p_i = P(\xi = i) = \dbinom{n}{k} p^k q^{n - k},[/math] где [math]i = 1, \ldots, n;[/math] [math]q = 1 - p,[/math] [math]p \in (0, 1).[/math]


Нормальное распределение (распределение Гаусса)

Определение:
Непрерывную случайную величину [math]\xi[/math] называют нормальной (англ. normal deviate) с параметрами [math](a, \sigma)[/math] и пишут [math]\xi = N (a, \sigma),[/math] если ее плотность вероятности дается формулой [math]f(x) = \dfrac {1} {\sigma \sqrt{2\pi}} {\large e^{-\frac {(x - a)^2} {2\sigma^2}}}.[/math]


Равномерное распределение

Определение:
Непрерывная случайная величина [math]\xi[/math] называется равномерно распределенной (англ. uniformly distributed random variable) на [math][a, b],[/math] если ее плотность вероятности дается формулой [math] f(x)= \begin{cases} \dfrac {1} {b - a}, & \mbox{if } x \in [a, b] \\ 0, & \mbox{otherwise.} \end{cases}[/math]


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

Для того, чтобы создать необходимое распределение вероятностей, достаточно иметь последовательность независимых случайных величин типа "честной монеты".

Например, для создания схемы с двумя исходами $A_1$ и $A_2$: $P(A_1)=\dfrac{3}{4}$ $,$ $P(A_2)=\dfrac{1}{4}$ можно из датчика случайных двоичных величин получить два результата "честной монеты" $\delta_1$ и $\delta_2$ и, например, при $\delta_1 = \delta_2 = 1$ выработать исход $A_2$, а в остальных случаях $A_1$.

Аналогично для схемы с четырьмя исходами $P(A_1)=\dfrac{3}{16}$ $,$ $P(A_2)=\dfrac{1}{16}$ $,$ $P(A_3)=\dfrac{8}{16}$ $,$ $P(A_4)=\dfrac{4}{16}$ можно получить четыре результата "честной монеты" $\delta_1$ $,$ $\delta_2$ $,$ $\delta_3$ $,$ $\delta_4$ и любым способом сопоставить трём из 16 возможных наборов исход $A_1$, одному $-$ $A_2$, восьми $-$ $A_3$, четырём $-$ $A_4$.

Если же вероятности исходов не кратны $2^{-k}$, можно применить два различных варианта действий.

  1. Можно приблизить вероятности двоичными дробями (с любой точностью), далее работать с полученными приближёнными значениями
  2. Пусть все вероятности $n_i$ $-$ дроби со знаменателем $r$. Найдём $k$, для которого $r < 2^k$. Предложим схему с $k$ результатами "честной монеты", в которой $r$ наборов используются для выработки случайного исхода, а остальные $2^{k}-r$ наборов объявляются "неудачными" и требуют повторного эксперимента (пока не встретится удачный). Чем выше доля полезных исходов равная $r2^{-k}$, тем схема будет эффективнее.

Количество результатов "честной монеты" $\lambda$, которые необходимы для формирования случайного исхода, $-$ это случайная величина. Её математическое ожидание:

$E\lambda = \dfrac{1}{2}\cdot1+\dfrac{1}{4}\cdot2+\dfrac{1}{8}\cdot3+\dfrac{1}{16}\cdot3+\dfrac{1}{16}\cdot4 = 1\dfrac{7}{8}.$

Можно сделать схему более экономной, если использовать датчик, равномерно формирующий число из диапазона $[0, 1]$. Образуем по данному набору вероятностей $p_i$ накопленные суммы $s_i$, такие, что $s_0 = 0; s_i = s_{i-1} + p_i,$ для $i > 0$. Случайный исход будет вырабатываться так: по полученному из датчика случайному числу $\gamma$ находится такой индекс $i$, для которого $s_{i-1} < \gamma \leqslant s_i$. Найденное значение индекса $i$ и определяет исход $A_i$. Индекс $i$ можно определять непосредственно просмотром $s_i$ подряд.

Рассмотрим приведенный выше пример с четырьмя исходам. В данном случае суммы $s_0, \ldots, s_4$ будут принимать значения [math]0,[/math] [math]\dfrac{3}{16},[/math] [math]\dfrac{4}{16},[/math] [math]\dfrac{12}{16}[/math] и [math]1[/math] соответственно. Значению $\gamma = 0,5$ будет соответствовать $i = 3$, то есть оно будет определять исход события $A_3.$ Таким же образом, $\gamma = 0,985$ определяет исход события $A_4.$

Если $k$ велико, можно применять специальные приёмы ускоренного поиска, например, деление множества индексов примерно пополам.

Общий случай

рис. [math]1[/math] рис. [math]2[/math] рис. [math]3[/math]
Sim pic1.JPG Sim pic2.JPG Sim pic3.JPG

Допустим у нас есть распределение [math]p.[/math] Нам нужно получить распределение [math]q[/math].

Для начала рассмотрим случай, когда все [math]p_i = \dfrac{1}{k},[/math] а в распределении [math]q [/math] количество элементарных исходов равно [math]2[/math] [math]([/math]рис. [math]1).[/math]

Проводим эксперимент: если попадаем в область пересекающуюся с [math] q_1 [/math] и [math] q_2,[/math] то увеличиваем ее и повторяем эксперимент. На рис. [math]1[/math] красным обозначено распределение [math] q. [/math] Вероятность того, что на этом шаге эксперимент не закончится — [math]\dfrac{1}{k}.[/math] Математическое ожидание количества экспериментов — [math] \dfrac{k}{k-1}, max(\dfrac{k}{k-1}) = 2[/math] [math]([/math]при [math]k = 2).[/math]


Теперь рассмотрим случай, когда все элементарные исходы [math]p_i[/math] по-прежнему равновероятны [math](p_i = \dfrac{1}{k}),[/math]а количество элементарных исходов распределения [math]q[/math] равно [math]n (\sum\limits_{j=1}^{n}q_j = 1)[/math] [math]([/math]рис. [math]2).[/math] Повторим эксперимент [math] t [/math] раз.

[math] k^t \geqslant 2n, t \geqslant \log\limits_{k}2n [/math]

Отрезок разбился на [math] k^t [/math] отрезков. Стык будет не более, чем в половине отрезков. Математическое ожидание количества экспериментов [math] \approx 2t [/math]


[math]p_i, \sum\limits_{i}p_i = 1,[/math] [math]q_j, \sum\limits_{j}q_j = 1[/math]

Берем [math]p_i[/math], и пусть оно максимальной длины [math]([/math]рис. [math]3).[/math] Проводим [math]t[/math] экспериментов. [math]{p_i}^t \lt \dfrac{1}{2n}, [/math] все остальные еще меньше. Суммарная длина отрезков не больше [math]\dfrac{1}{2}.[/math] Нужно [math] t \geqslant \log\limits_{p}\dfrac{1}{2n} .[/math]


Таким образом, из любого исходного распределения мы можем получить нужное нам распределение.

См. также

Источники информации