Изменения

{{Определение|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''), то есть представляет собой набор вероятностей, с которыми случайная величина принимает те или иные значения. }}[[Файл:Распределение1_4РаспределениеUPD.JPG‎jpeg‎|200px|thumb|right|Геометрическое распределение с <tex>p = \dfrac {3} {4}</4tex>]]'''Распределение — '''Закон распределения дискретной случайной величины <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> если ее плотность вероятности дается формулой

<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>

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

Индекс $i$ можно определять непосредственно просмотром $s_i$ подряд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}. Если $k$ велико, можно применять специальные приёмы ускоренного поиска, например, деление множества индексов примерно пополам.

Самую эффективную Можно сделать схему предложил в 1977 гболее экономной, если использовать датчик, равномерно формирующий число из диапазона $[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, 1]$ на $k$ одинаковых частей</tex> <tex>\dfrac{3}{16}, соответствующих этим исходам</tex> <tex>\dfrac{4}{16}, </tex> <tex>\dfrac{12}{16}</tex> и определить, в какую часть отрезка попало значение случайного датчика $x$<tex>1</tex> соответственно. А это выясняется очень просто: нужно взять целую часть произведения Значению $k \cdot x$. Такчто при исходах gamma = 0, 1, 2, 3 значению 5$ будет соответствовать $x i = 0.3333$ соответствует , то есть оно будет определять исход события $1A_3.$Таким же образом,поскольку $4x \gamma = 10,985$ определяет исход события $A_4.332$.

Можно "подгонять" распределение под равномерное, передавая часть "вероятностной массы" от одних исходов другим. Если четыре исхода должны иметь вероятности, те же четыре исхода должны иметь вероятности, соответственно, $0.25k$велико, $0.31$, $0.19$ и $0.25$, то исход $2$, получая, как все другие, долю $0.25$ и нуждаясь в доле $0.19$, может быть своеобразным "донором" и отдать исходу $1$, нуждающемуся в доле $0.31$, свои лишние шесть сотых. Эта передача воплощается в следующих действиях при генерировании случайного исхода: берется случайное числоможно применять специальные приёмы ускоренного поиска, например можможно использовать непосредственно дробную часть числа $k \cdot x$, и если это число меньше чем $0.19 \cdot 4 = 0.76$, то результатом будет исход $2$, а если больше, то исход $1$ (здесь случай равенства несуществен, его можно приписать к любой альтернативе). Эта передача обеспечит нужное увеличение доли для исхода $1$ и уменьшение $-$ для исхода $2$. Исход $1$ служит здесь "реципиентом" для "донора", исхода $2$деление множества индексов примерно пополам.

Такую передачу ==Общий случай=={|class = "вероятностной массыwikitable" можно проводить в каждом диапазоне, причем если style="владельцами диапазоновtext-align:center;" удобно назначать различные исходы, то реципиентами разных диапазонов могут быть одни и те же исходы| рис. Например, взяв ту же схему с четырьмя исходами, назначим реципиентом при исходе $0$ исход $3$ с долей $0.07$, приисходе $<tex>1$ $-$ исход $2$ с долей $0</tex> || рис.11$, при исходе $<tex>2$ $-$ исход $3$ с долей $0</tex> || рис.14$,наконец, при исходе $<tex>3$ $-$ исход $1$ с долей $0$. Подсчитаем окончательную вероятность получения каждого исхода:<center/tex>$p_0 |-|width = 0"280px"| [[Файл:Sim pic1.25- 0JPG|270px]] ||width = "280px"|[[Файл:Sim pic2.07 JPG‎|270px]] ||width = 0"280px"|[[Файл:Sim pic3.18$,JPG‎|270px]] |}

$p_1 = 0Допустим у нас есть распределение <tex>p.25 - 0</tex> Нам нужно получить распределение <tex>q</tex>.11 + 0 = 0.14$,

$p_2 Для начала рассмотрим случай, когда все <tex>p_i = 0.25 - 0.14 + 0\dfrac{1}{k},</tex> а в распределении <tex>q </tex> количество элементарных исходов равно <tex>2</tex> <tex>(</tex>рис.11 = 0<tex>1).22$,</tex>

$p_3 = 0Проводим эксперимент: если попадаем в область пересекающуюся с <tex> q_1 </tex> и <tex> q_2,</tex> то увеличиваем ее и повторяем эксперимент. На рис.25 + 0<tex>1</tex> красным обозначено распределение <tex> q.07 + 0</tex> Вероятность того, что на этом шаге эксперимент не закончится {{---}} <tex>\dfrac{1}{k}.14 </tex> Математическое ожидание количества экспериментов {{---}} <tex> \dfrac{k}{k-1}, max(\dfrac{k}{k-1}) = 2</tex> <tex>(</tex>при <tex>k = 02).46$.</centertex>

Такую схему можно создать для любого распределения вероятностейТеперь рассмотрим случай, причем у каждого исходакогда все элементарные исходы <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> раз.

Пример: Возьмем распределение $p_A = 0.07$, $p_B = 0.31$, $p_C = 0.35$ и $p_D = 0.27$. Для него мы можем получить:<centertex>{| class="wikitable"|-! Донор !! Барьер !! Реципиент !! Остаток у реципиента|-| A || $0.07 k^t \cdot 4$ || B || $0.31 - 0.18 = 0.13$|-| B || $0.13 geqslant 2n, t \cdot 4$ || D || $0.27 - 0.12 = 0.15$|-| D || $0.15 geqslant \cdot 4$ || C || $0.35 - 0.10 = 0.25$|-| C || $0.25 log\cdot 4$ || A || $0$|limits_{k}2n </centertex>При моделировании эти числа используются так: разыгрывается случайное число $x \in [0, 1]$, пусть получилось $x = 0.531$. Это число умножается на $k$: $0.531 \times 4 = 2.124$. Целая часть произведения определяет строку таблицы, считая от нуля, значит, третью сверху строку с основным исходом $D$ и дополнительным $C$. Дробная часть произведения $0.124$ сравнивается с барьером $0.6$, и так как барьер выше, то принимается основной исход.

==Общий случай==[[Файл:Sim pic1.JPG‎|150px|left|thumb|В распределении q количество элементарных исходов равно 2]]Допустим у нас есть распределение Отрезок разбился на <tex>p.k^t </tex> Нам нужно получить распределение <tex>qотрезков.</tex>: Для начала рассмотрим случай, когда все <tex>p_i = \frac{1}{k}Стык будет не более,</tex> а чем в распределении <tex>q </tex> количество элементарных исходов равно <tex>2половине отрезков.</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>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> раз. <tex> k^t \ge 2n, t \ge \log\limits_{k}2n approx 2t </tex>

==ЛитератураИсточники информации==*Боровков А.А. Математическая статистика: оценка параметров, проверка гипотез. {{- --}} М., Физматлит, 1984, {{---}} стр. 71.*[http://sheen.me/books/spec/apia.djvu Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн {{--- }} Алгоритмы. Построение и анализ 1244c{{---}} М. : ООО "И. Д. Вильямс", 2013. {{---}} 1328 с. {{---}} стр. 1254.]*Романовский И.В. Дискретный анализ{{---}} Элементы теории вероятностей и математической статистики (теория и задачи): учебное пособие. {{---}} Омск, издатель ИП Скорнякова Е.В., 2012. {{---}} 189 с. {{---}} стр. 34.  [[Категория:Дискретная математика и алгоритмы]] [[Категория: Теория вероятности ]]