Lymma Hoeffdings - Hoeffdings lemma - Wikipedia

v teorie pravděpodobnosti, Hoeffdingovo lemma je nerovnost který ohraničuje funkce generující momenty ze všech ohraničený náhodná proměnná.^[1] Je pojmenována po Finština –americký matematický statistik Wassily Hoeffding.

Důkaz Hoeffdingova lemmatu se používá Taylorova věta a Jensenova nerovnost. Hoeffdingovo lemma je samo o sobě použito v důkazu McDiarmidova nerovnost.

Prohlášení o lemmatu

Nechat X být libovolná náhodná proměnná se skutečnou hodnotou očekávaná hodnota ${ displaystyle mathbb {E} [X] = eta}$, takový, že ${ displaystyle a leq X leq b}$ téměř jistě, tj. s pravděpodobností jedna. Pak pro všechny ${ displaystyle lambda v mathbb {R}}$,

${ displaystyle mathbb {E} doleva [e ^ { lambda X} doprava] leq exp { Big (} lambda eta + { frac { lambda ^ {2} (ba) ^ { 2}} {8}} { Big)}.}$

Všimněte si, že níže uvedený důkaz je založen na předpokladu, že náhodná proměnná ${ displaystyle X}$ má nulové očekávání (tj. za předpokladu, že ${ displaystyle eta = 0}$), proto ${ displaystyle a}$ a ${ displaystyle b}$ v lemmatu musí vyhovovat ${ displaystyle a leq 0 leq b}$. Pro libovolnou náhodnou proměnnou, která tento předpoklad nedodržuje, můžeme definovat ${ displaystyle { tilde {X}} triangleq X- eta}$, které se řídí předpoklady a použijí důkaz na ${ displaystyle { tilde {X}}}$.

Stručný důkaz lemmatu

Od té doby ${ displaystyle e ^ { lambda x}}$ je konvexní funkce ${ displaystyle x}$, my máme

${ displaystyle e ^ { lambda x} leq { frac {bx} {ba}} e ^ { lambda a} + { frac {xa} {ba}} e ^ { lambda b} qquad vše a leq x leq b}$

Tak, ${ displaystyle mathbb {E} doleva [e ^ { lambda X} doprava] leq { frac {b- mathbb {E} [X]} {ba}} e ^ { lambda a} + { frac { mathbb {E} [X] -a} {ba}} e ^ { lambda b}.}$

Nechat ${ displaystyle h = lambda (b-a)}$, ${ displaystyle p = { frac {-a} {b-a}}}$ a ${ displaystyle L (h) = - hp + ln (1-p + pe ^ {h})}$

Pak, ${ displaystyle { frac {b- mathbb {E} [X]} {ba}} e ^ { lambda a} + { frac { mathbb {E} [X] -a} {ba}} e ^ { lambda b} = e ^ {L (h)}}$ od té doby ${ displaystyle mathbb {E} [X] = 0}$

Užívání derivátu ${ displaystyle L (h)}$,

${ displaystyle L (0) = L ^ {'} (0) = 0 { text {and}} L ^ {' '} (h) leq { frac {1} {4}}}$ pro všechny h.

Taylorovou expanzí,

${ displaystyle L (h) leq { frac {1} {8}} h ^ {2} = { frac {1} {8}} lambda ^ {2} (b-a) ^ {2}}$

Proto, ${ displaystyle mathbb {E} doleva [e ^ { lambda X} doprava] leq e ^ {{ frac {1} {8}} lambda ^ {2} (ba) ^ {2}} }$

(Níže uvedený důkaz je stejný důkaz s větším vysvětlením.)

Podrobnější důkaz

Nejprve si všimněte, že pokud jeden z ${ displaystyle a}$ nebo ${ displaystyle b}$ je tedy nula ${ displaystyle textstyle mathbb {P} doleva (X = 0 doprava) = 1}$ a následuje nerovnost. Pokud jsou oba nenulové, pak ${ displaystyle a}$ musí být záporné a ${ displaystyle b}$ musí být pozitivní.

Dále si to připomeňte ${ displaystyle e ^ {sx}}$ je konvexní funkce na skutečné lince:

${ displaystyle forall x in [a, b]: qquad e ^ {sx} leq { frac {bx} {ba}} e ^ {sa} + { frac {xa} {ba}} e ^ {sb}.}$

Přihlašování ${ displaystyle mathbb {E}}$ na obě strany výše uvedené nerovnosti nám dává:

${ displaystyle { begin {aligned} mathbb {E} left [e ^ {sX} right] & leq { frac {b- mathbb {E} [X]} {ba}} e ^ { sa} + { frac { mathbb {E} [X] -a} {ba}} e ^ {sb} & = { frac {b} {ba}} e ^ {sa} + { frac {-a} {ba}} e ^ {sb} && mathbb {E} (X) = 0 & = (1- theta) e ^ {sa} + theta e ^ {sb} && theta = - { frac {a} {ba}}> 0 & = e ^ {sa} left (1- theta + theta e ^ {s (ba)} right) & = left (1- theta + theta e ^ {s (ba)} vpravo) e ^ {- s theta (ba)} konec {zarovnáno}}}$

Nechat ${ displaystyle u = s (b-a)}$ a definovat:

${ displaystyle { begin {cases} varphi: mathbb {R} to mathbb {R} varphi (u) = - theta u + log left (1- theta + theta e ^ {u} right) end {cases}}}$

${ displaystyle varphi}$ je dobře definováno na ${ displaystyle mathbb {R}}$, abychom to viděli, vypočítáme:

${ displaystyle { begin {zarovnáno} 1- theta + theta e ^ {u} & = theta left ({ frac {1} { theta}} - 1 + e ^ {u} right) & = theta left (- { frac {b} {a}} + e ^ {u} right) &> 0 && theta> 0, quad { frac {b} {a} } <0 end {zarovnáno}}}$

Definice ${ displaystyle varphi}$ naznačuje

${ displaystyle mathbb {E} doleva [e ^ {sX} doprava] leq e ^ { varphi (u)}.}$

Podle Taylorova věta, pro každý skutečný ${ displaystyle u}$ existuje a ${ displaystyle v}$ mezi ${ displaystyle 0}$ a ${ displaystyle u}$ takhle

${ displaystyle varphi (u) = varphi (0) + u varphi '(0) + { tfrac {1} {2}} u ^ {2} varphi' '(v).}$

Všimněte si, že:

${ displaystyle { begin {aligned} varphi (0) & = 0 varphi '(0) & = - theta + left. { frac { theta e ^ {u}} {1- theta + theta e ^ {u}}} doprava | _ {u = 0} & = 0 [6pt] varphi '' (v) & = { frac { theta e ^ {v} left (1- theta + theta e ^ {v} right) - theta ^ {2} e ^ {2v}} { left (1- theta + theta e ^ {v} right) ^ {2}}} [6pt] & = { frac { theta e ^ {v}} {1- theta + theta e ^ {v}}} vlevo (1 - { frac { theta e ^ {v}} {1- theta + theta e ^ {v}}} right) [6pt] & = t (1-t) && t = { frac { theta e ^ {v }} {1- theta + theta e ^ {v}}} & leq { tfrac {1} {4}} && t> 0 end {zarovnáno}}}$

Proto,

${ displaystyle varphi (u) leq 0 + u cdot 0 + { tfrac {1} {2}} u ^ {2} cdot { tfrac {1} {4}} = { tfrac {1 } {8}} u ^ {2} = { tfrac {1} {8}} s ^ {2} (ba) ^ {2}.}$

Z toho vyplývá

${ displaystyle mathbb {E} vlevo [e ^ {sX} vpravo] leq exp vlevo ({ tfrac {1} {8}} s ^ {2} (ba) ^ {2} vpravo ).}$

Viz také

• Hoeffdingova nerovnost
• Bennettova nerovnost

Poznámky

Tento pravděpodobnost související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.