Викиконспекты - Вклад участника [ru]

Граница Чернова

2019-04-20T13:33:32Z

176.59.3.0:

{{Определение
|definition = '''Граница Чернова''' (англ. ''Chernoff bound'') дает оценку вероятности того, что сумма n одинаково распределенных независимых случайных величин больше (или меньше) некоторого значения.
}}

==Неравенство и его доказательство==
{{Теорема
| id = thChernov
| about = Граница Чернова
| statement = Пусть даны <tex>X_1 X_2 \ldots X_n</tex> {{---}} одинаково распределенные независимые случайные величины, принимающие значения из множества <tex>\{0, 1\}</tex>,

<tex>m = {E} \sum\limits_{i=1}^{n} X_i</tex>,

Тогда:

<tex>{P} (|\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m| \geqslant \delta) \leqslant 2e^{-2 \delta ^2 n}</tex>
| proof = Так как <tex>X_1 X_2 \ldots X_n</tex> {{---}} одинаково распределенные и принимают значения из множества <tex>\{0, 1\}</tex>:

<tex>{P}(X_i = 1) = p</tex>

<tex>{P}{(X_i = 0) = 1 - p = q}</tex>

<tex>{E} X_i = p</tex>

Пусть <tex>\bar{X_i} = X_i - p</tex>, тогда <tex>{E}\bar{X_i} = 0</tex>

Преобразуем выражение <tex>{P} (\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m \geqslant \delta)</tex>. (<tex>t</tex> {{---}} любое положительное число):

<tex>{P}(\dfrac{1}{n}\sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m \geqslant \delta) = {P} (\dfrac{1}{n}\sum\limits_{i=1}^{n}\bar{X_i} \geqslant \delta) = {P}(e^{t\sum\limits_{i=1}^{n} \bar{X_i}} \geqslant e^{t \delta n})</tex>

Используем [[Неравенство Маркова| неравенство Маркова]] для оценки полученного выражения:

<tex>{P}(e^{ t\sum\limits_{i=1}^{n}\bar{X_i}} \geqslant e^{t \delta n}) \leqslant \dfrac{{E} (e^{ t\sum\limits_{i=1}^{n}\bar{X_i}})}{e^{t \delta n}}</tex>

[[Математическое ожидание случайной величины| Матожидание]] можно преобразовать:

<tex>{E} (e^{ t\sum\limits_{i=1}^{n}\bar{X_i}}) = \prod\limits_{i = 1}^{n}{E}(e^{t \bar{X_i}})</tex>

Оценим <tex>{E}(e^{t \bar{X_i}})</tex> с учётом того, что <tex>p \in [0, 1]</tex>

<tex>{E}(e^{t \bar{X_i}}) = p e^{tq} + qe^{-pt} \leqslant e ^ {\frac{t^2}{8}}</tex>

<tex>{P}(e^{ t\sum\limits_{i=1}^{n}\bar{X_i}} \geqslant e^{t \delta n}) \leqslant \dfrac{e^{n\frac{t^2}{8}}}{e^{t \delta n}}</tex>

При <tex>t = 4\delta</tex>:
<tex>\mathbb {P}(e^{ t\sum\limits_{i=1}^{n}\bar{X_i}} \geqslant e^{t \delta n}) \leqslant e^{-2 \delta^2 n}</tex>

Аналогично доказывается, что: <tex>{P} (\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m \leqslant -\delta) \leqslant e^{-2 \delta^2 n}</tex>

Таким образом: <tex>{P} (|\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m| \geqslant \delta) \leqslant 2e^{-2 \delta ^2 n}</tex>
}}

== Пример ==
Граница Чернова используется, когда нужно оценить вероятность того, что сумма одинаково распределенных событий будет отличаться от матожидания этой суммы больше чем на <tex>\delta</tex>

Пусть монетку подбросили 1000 раз. Оценить вероятность того, что выпало больше 550 орлов.

<tex>m = {E} \sum\limits_{i=1}^{n} X_i = n{E} X_i = \dfrac{n}{2}</tex>

<tex>\delta = \dfrac{1}{20}</tex>

<tex>{P} (|\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{2}| \geqslant \dfrac{1}{20}) \leqslant 2e^{-2 \dfrac{1000}{400}} = 2e^{-5}</tex>

== См. также ==
* [[Неравенство Маркова]]
* [[Математическое ожидание случайной величины]]

== Источники информации ==
* [https://www.lektorium.tv/lecture/12871 Лекториум CS-центра {{---}} Лекция Дмитрия Ицыксона]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория вероятности]]

Граница Чернова

2019-04-20T13:30:18Z

176.59.3.0:

{{Определение
|definition = '''Граница Чернова''' (англ. ''Chernoff bound'') дает оценку вероятности того, что сумма n одинаково распределенных независимых случайных величин больше (или меньше) некоторого значения.
}}

==Неравенство и его доказательство==
{{Теорема
| id = thChernov
| about = Граница Чернова
| statement = Пусть даны <tex>X_1 X_2 \ldots X_n</tex> {{---}} одинаково распределенные независимые случайные величины, принимающие значения из множества <tex>\{0, 1\}</tex>,

<tex>m = {E} \sum\limits_{i=1}^{n} X_i</tex>,

Тогда:

<tex>{P} (|\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m| \geqslant \delta) \leqslant 2e^{-2 \delta ^2 n}</tex>
| proof = Так как <tex>X_1 X_2 \ldots X_n</tex> {{---}} одинаково распределенные и принимают значения из множества <tex>\{0, 1\}</tex>:

<tex>{P}(X_i = 1) = p</tex>

<tex>{P}{(X_i = 0) = 1 - p = q}</tex>

<tex>{E} X_i = p</tex>

Пусть <tex>\bar{X_i} = X_i - p</tex>, тогда <tex>{E}\bar{X_i} = 0</tex>

Преобразуем выражение <tex>{P} (\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m \geqslant \delta)</tex>. (<tex>t</tex> {{---}} любое положительное число):

<tex>{P}(\dfrac{1}{n}\sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m \geqslant \delta) = {P} (\dfrac{1}{n}\sum\limits_{i=1}^{n}\bar{X_i} \geqslant \delta) = {P}(e^{t\sum\limits_{i=1}^{n} \bar{X_i}} \geqslant e^{t \delta n})</tex>

Используем [[Неравенство Маркова| неравенство Маркова]] для оценки полученного выражения:

<tex>{P}(e^{ t\sum\limits_{i=1}^{n}\bar{X_i}} \geqslant e^{t \delta n}) \leqslant \dfrac{{E} (e^{ t\sum\limits_{i=1}^{n}\bar{X_i}})}{e^{t \delta n}}</tex>

[[Математическое ожидание случайной величины| Матожидание]] можно преобразовать:

<tex>{E} (e^{ t\sum\limits_{i=1}^{n}\bar{X_i}}) = \prod_{i = 1}^{n}{E}(e^{t \bar{X_i}})</tex>

Оценим <tex>{E}(e^{t \bar{X_i}})</tex> с учётом того, что <tex>p \in [0, 1]</tex>

<tex>{E}(e^{t \bar{X_i}}) = p e^{tq} + qe^{-pt} \leqslant e ^ {\frac{t^2}{8}}</tex>

<tex>{P}(e^{ t\sum_{i=1}^{n}\bar{X_i}} \geqslant e^{t \delta n}) \leqslant \dfrac{e^{n\frac{t^2}{8}}}{e^{t \delta n}}</tex>

При <tex>t = 4\delta</tex>:
<tex>\mathbb {P}(e^{ t\sum_{i=1}^{n}\bar{X_i}} \geqslant e^{t \delta n}) \leqslant e^{-2 \delta^2 n}</tex>

Аналогично доказывается, что: <tex>{P} (\dfrac{1}{n} \sum_{i=1}^{n} X_i - \dfrac{1}{n} m \leqslant -\delta) \leqslant e^{-2 \delta^2 n}</tex>

Таким образом: <tex>{P} (|\dfrac{1}{n} \sum_{i=1}^{n} X_i - \dfrac{1}{n} m| \geqslant \delta) \leqslant 2e^{-2 \delta ^2 n}</tex>
}}

== Пример ==
Граница Чернова используется, когда нужно оценить вероятность того, что сумма одинаково распределенных событий будет отличаться от матожидания этой суммы больше чем на <tex>\delta</tex>

Пусть монетку подбросили 1000 раз. Оценить вероятность того, что выпало больше 550 орлов.

<tex>m = {E} \sum_{i=1}^{n} X_i = n{E} X_i = \dfrac{n}{2}</tex>

<tex>\delta = \dfrac{1}{20}</tex>

<tex>{P} (|\dfrac{1}{n} \sum_{i=1}^{n} X_i - \dfrac{1}{2}| \geqslant \dfrac{1}{20}) \leqslant 2e^{-2 \dfrac{1000}{400}} = 2e^{-5}</tex>

== См. также ==
* [[Неравенство Маркова]]
* [[Математическое ожидание случайной величины]]

== Источники информации ==
* [https://www.lektorium.tv/lecture/12871 Лекториум CS-центра {{---}} Лекция Дмитрия Ицыксона]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория вероятности]]

Граница Чернова

2019-04-20T13:27:02Z

176.59.3.0:

{{Определение
|definition = '''Граница Чернова''' (англ. ''Chernoff bound'') дает ,более .
}}

==Неравенство и его доказательство==
{{Теорема
| id = thChernov
| about = Граница Чернова
| statement = Пусть даны <tex>X_1 X_2 \ldots X_n</tex> {{---}} одинаково распределенные независимые случайные величины, принимающие значения из множества <tex>\{0, 1\}</tex>,

<tex>m = {E} \sum\limits_{i=1}^{n} X_i</tex>,

Тогда:

<tex>{P} (|\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m| \geqslant \delta) \leqslant 2e^{-2 \delta ^2 n}</tex>
| proof = Так как <tex>X_1 X_2 \ldots X_n</tex> {{---}} одинаково распределенные и принимают значения из множества <tex>\{0, 1\}</tex>:

<tex>{P}(X_i = 1) = p</tex>

<tex>{P}{(X_i = 0) = 1 - p = q}</tex>

<tex>{E} X_i = p</tex>

Пусть <tex>\bar{X_i} = X_i - p</tex>, тогда <tex>{E}\bar{X_i} = 0</tex>

Преобразуем выражение <tex>{P} (\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m \geqslant \delta)</tex>. (<tex>t</tex> {{---}} любое положительное число):

<tex>{P}(\dfrac{1}{n}\sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m \geqslant \delta) = {P} (\dfrac{1}{n}\sum\limits_{i=1}^{n}\bar{X_i} \geqslant \delta) = {P}(e^{t\sum\limits_{i=1}^{n} \bar{X_i}} \geqslant e^{t \delta n})</tex>

Используем [[Неравенство Маркова| неравенство Маркова]] для оценки полученного выражения:

<tex>{P}(e^{ t\sum\limits_{i=1}^{n}\bar{X_i}} \geqslant e^{t \delta n}) \leqslant \dfrac{{E} (e^{ t\sum\limits_{i=1}^{n}\bar{X_i}})}{e^{t \delta n}}</tex>

[[Математическое ожидание случайной величины| Матожидание]] можно преобразовать:

<tex>{E} (e^{ t\sum\limits_{i=1}^{n}\bar{X_i}}) = \prod_{i = 1}^{n}{E}(e^{t \bar{X_i}})</tex>

Оценим <tex>{E}(e^{t \bar{X_i}})</tex> с учётом того, что <tex>p \in [0, 1]</tex>

<tex>{E}(e^{t \bar{X_i}}) = p e^{tq} + qe^{-pt} \leqslant e ^ {\frac{t^2}{8}}</tex>

<tex>{P}(e^{ t\sum_{i=1}^{n}\bar{X_i}} \geqslant e^{t \delta n}) \leqslant \dfrac{e^{n\frac{t^2}{8}}}{e^{t \delta n}}</tex>

При <tex>t = 4\delta</tex>:
<tex>\mathbb {P}(e^{ t\sum_{i=1}^{n}\bar{X_i}} \geqslant e^{t \delta n}) \leqslant e^{-2 \delta^2 n}</tex>

Аналогично доказывается, что: <tex>{P} (\dfrac{1}{n} \sum_{i=1}^{n} X_i - \dfrac{1}{n} m \leqslant -\delta) \leqslant e^{-2 \delta^2 n}</tex>

Таким образом: <tex>{P} (|\dfrac{1}{n} \sum_{i=1}^{n} X_i - \dfrac{1}{n} m| \geqslant \delta) \leqslant 2e^{-2 \delta ^2 n}</tex>
}}

== Пример ==
Граница Чернова используется, когда нужно оценить вероятность того, что сумма одинаково распределенных событий будет отличаться от матожидания этой суммы больше чем на <tex>\delta</tex>

Пусть монетку подбросили 1000 раз. Оценить вероятность того, что выпало больше 550 орлов.

<tex>m = {E} \sum_{i=1}^{n} X_i = n{E} X_i = \dfrac{n}{2}</tex>

<tex>\delta = \dfrac{1}{20}</tex>

<tex>{P} (|\dfrac{1}{n} \sum_{i=1}^{n} X_i - \dfrac{1}{2}| \geqslant \dfrac{1}{20}) \leqslant 2e^{-2 \dfrac{1000}{400}} = 2e^{-5}</tex>

== См. также ==
* [[Неравенство Маркова]]
* [[Математическое ожидание случайной величины]]

== Источники информации ==
* [https://www.lektorium.tv/lecture/12871 Лекториум CS-центра {{---}} Лекция Дмитрия Ицыксона]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория вероятности]]