Изменения

==Некоторые вспомогательные определения и леммыПроизводящая функция моментов==

|definition = '''Производящая функция моментов''' (англ. ''moment-generating function'') случайной величины <tex>X</tex> {{---}} функция из <tex>\mathbb R</tex> в <tex>\mathbb R</tex>, определяемая и определяется как: <br><tex>M_x(t) =</tex> <tex>{E}(e^{tX})</tex>.}} {{Определение |definition = Распишем производящую функцию моментов по формуле Тейлора: <br><tex>M_x(t) =</tex> <tex>{E}(e^{tX}) =</tex> <tex>{E}(1 + tX + \dfrac{1}{2}t^2 X^2 + \cdots + \dfrac{1}{n!}t^n X^n + \cdots ) =</tex> <tex>\sum\limits_{i = 1}^{\infty} \dfrac{1}{i!} {E}(X^i)</tex> <br>Величина <tex>{E}(X^i)</tex> называется '''i-ым моментом''' (англ. ''i-th moment'') случайной величины <tex>X</tex>.

|statement= Если <tex>X = \sum_sum\limits_{i=1}^{n} X_i</tex>, где <tex>X_1 X_2 \cdots X_n</tex> {{---}} независимые случайные величины, то:<br>

|proof= <tex>M_X(t) =</tex> <tex>{E}(e^{tX}) =</tex> <tex>{E}(e^{t \sum_sum\limits_{i=1}^{n} {X_i}}) = </tex> <tex>{E}( {\prod_prod\limits_{i=1}^{n} {e^{t X_i}}}) =</tex> <tex>\prod_prod\limits_{i=1}^{n} {{E}( {e^{t X_i}}}) =</tex> <tex> \prod\limits_{i=1}^{n} M_{X_i} (t)</tex>

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

<tex>X = \sum_sum\limits_{i=1}^{n} X_i</tex>

<tex>{P} (X \geqslant (1 + \delta)m) \leqslant e^{m(\delta - (1 + \delta)\ln(1 + \delta))} \leqslant e^{- \frac{\delta^2}{2 + \delta}m }</tex>, для <tex>\delta > 0</tex>

<tex>{P}(x X \geqslant a) =</tex> <tex>{P}(e^x {tX} \geqslant e^a{ta}) \leqslant </tex> <tex>\dfrac{{E}(e^{tX})}{e^a{ta}}</tex>

Воспользуемся [[#lemma1|первойлеммой о производящей функции моментов суммы случайных величин ]] и [[#lemma2|второйлеммой об ограниченности производящей функции моментов]] леммами:

<tex>\dfrac{{E}(e^{tX})}{e^a{ta}} \leqslant</tex> <tex>\dfrac{\prod\limitslimits_{i = 1}^{n}e^{p(e^t - 1)}}{e^{ata}} =</tex> <tex>\dfrac{e^{(e^t - 1)\sum\limitslimits_{i = 1}^{n}p}}{e^{ata}}</tex>

Заметим, что <tex>\sum\limitslimits_{i = 1}^{n} p = m</tex>, кроме того <tex>a = (1 + \delta)m</tex> (по замене).

<tex>\dfrac{e^{(e^t - 1)\sum\limitslimits_{i = 1}^{n}p}}{e^{ata}} = </tex> <tex>e^{m(e^t - 1 - t - t\delta)}</tex>

==ПримерСравнение с оценкой неравенством Чебышева==

Честную монету подбросили <tex>1000</tex> раз. Оценим вероятность тогоГраница Чернова даёт намного более точную оценку, что выпало больше <tex>550</tex> орлов с помощью [[Неравенство Маркова#Неравенство чем неравенство Чебышева | неравенства Чебышева]] и [[Граница Чернова#Относительная оценка | мультипликативной формы границы Чернова]].

Пусть честную монету подбросили <tex>XN</tex> раз. Оценим вероятность того, что сумма бросков <tex>S</tex> отклонилась от матожидания больше, чем на <tex>\delta = \sqrt{\dfrac{\ln N}{---N}} сумма результатов бросков.</tex> с помощью [[Неравенство Маркова#Неравенство Чебышева | неравенства Чебышева]] и [[Граница Чернова#Абсолютная оценка | аддитивной формы границы Чернова]]

По неравенству Чебышева: <tex>P(|\dfrac{XS}{1000N} - \dfrac{1}{2}| \geqslant \delta) \leqslant \dfrac{111}{104N\delta^2}) \leqslant = \dfrac{1211}{4004\ln N}</tex>

Оценка границей Чернова: <tex>P(X |\geqslant (1 + dfrac{S}{N} - \dfrac{1}{102}) | \geqslant \cdot 500delta) \leqslant e2e^{-2N\dfrac{50}{21}delta^2} \approx = \dfrac{12}{100N^2}</tex>

==Применение==Оценка границей Чернова используется в решении проблем уравновешивания множеств <ref>[https://en.wikipedia.org/wiki/Set_balancing Wikipedia {{---}} Set balancing]</ref> и маршрутизации пакетов в разреженных сетях. Задача уравновешивания двух множеств возникает при планировании статистических экспериментов. Обычно при планировании эксперимента известны свойства каждого участника, задача состоит в том, чтобы разделить участников на две группы: контрольную и тестовую, так, чтобы каждое свойство было как можно более сбалансированно между двумя группами.  Граница Чернова даёт намного более точную оценкуиспользуется в теории вычислительного обучения для оценки того, что алгоритм с большой вероятностью имеет небольшую ошибку на достаточно большом наборе обучающих данных.