Hoeffding ulighed

I sandsynlighedsteori er Hoeffdings ulighed en ulighed i koncentration vedrørende summen af uafhængige og afgrænsede tilfældige variabler . Det stammer fra den finske matematiker og statistiker Wassily Hoeffding . Der er en mere generel version af denne ulighed, der vedrører en sum af stigninger i martingaler , igen begrænsede stigninger: denne mere generelle version er undertiden kendt under navnet Azuma-Hoeffding ulighed .

Stater

Hoeffding ulighed - Lad være en sekvens af uafhængige reelle tilfældige variabler, der tilfredsstiller, for to sekvenser af reelle tal, således at $\ (X_ {k}) _ {{1 \ leq k \ leq n}} \$ $\ (a_ {k}) _ {{1 \ leq k \ leq n}}, \$ $\ (b_ {k}) _ {{1 \ leq k \ leq n}} \$ $\ a_ {k} <b_ {k}, \$

\ forall k, \ qquad {\ mathbb {P}} (a_ {k} \ leq X_ {k} \ leq b_ {k}) = 1.

Vi udgør

S_ {n} = X_ {1} + X_ {2} + \ prikker + X_ {n}.

Så for alt $\ t> 0, \$

{\ begin {array} {rl} {\ mathbb {P}} \ left (S_ {n} - {\ mathbb {E}} [S_ {n}] \ geq t \ right) & \ leq \ exp \ left (- {\ frac {2 \, t ^ {2}} {\ sum _ {{i = 1}} ^ {n} (b_ {i} -a_ {i}) ^ {2}}} \ højre) , \\ {\ mathbb {P}} \ left (S_ {n} - {\ mathbb {E}} [S_ {n}] \ leq -t \ right) & \ leq \ exp \ left (- {\ frac {2 \, t ^ {2}} {\ sum _ {{i = 1}} ^ {n} (b_ {i} -a_ {i}) ^ {2}}} \ højre), \\ {\ mathbb {P}} \ left (\ left | S_ {n} - {\ mathbb {E}} [S_ {n}] \ right | \ geq t \ right) & \ leq 2 \ exp \ left (- {\ frac {2 \, t ^ {2}} {\ sum _ {{i = 1}} ^ {n} (b_ {i} -a_ {i}) ^ {2}}} \ højre). \ end { matrix}}

Hvis binomialet

Antag at

{\ mathbb {P}} (X_ {k} = 1) = 1 - {\ mathbb {P}} (X_ {k} = 0) = p.

Derefter følger binomialfordelingen af parametrene n og p . Den Bienayme-Chebyshev ulighed og Hoeffding ulighed henholdsvis giver $\ S_ {n} \$ ${\ displaystyle \ forall x> 0}$

{\ begin {array} {rl} {\ mathbb {P}} \ left (\ left | S_ {n} - {\ mathbb {E}} [S_ {n}] \ right | \ geq x {\ sqrt { n}} \ højre) & \ leq {\ frac {p (1-p)} {x ^ {2}}}, \\ {\ mathbb {P}} \ venstre (\ venstre | S_ {n} - { \ mathbb {E}} [S_ {n}] \ right | \ geq x {\ sqrt {n}} \ right) & \ leq 2 \ exp \ left (-2 \, x ^ {2} \ right). \ end {array}}

Vi ser, at Hoeffding-uligheden i dette tilfælde (og det er ret repræsentativ for den generelle situation) er meget mere præcis for tilstrækkelig stor. $\ x \$

Demonstration

Indledende ulighed

Beviset bruger følgende forslag:

Proposition - Lad være en afgrænset og centreret reel tilfældig variabel (verificering ). Lad to reelle tal være sådan, og sådan, at derefter for alle reelle tal $\ Y \$ $\ {\ mathbb {E}} [Y] = 0 \$ $\ c, \, d \$ $\ c <d \$ $\ {\ mathbb {P}} (c \ leq Y \ leq d) = 1. \$ $\ s> 0, \$

{\ mathbb {E}} \ left [e ^ {{sY}} \ right] \ leq \ exp \ left (s ^ {2} (dc) ^ {2} / 8 \ right).

For det første kan vi antage $c <0$ og $d > 0$ . Faktisk, hvis , så er $Y$ en næsten-sikker positiv tilfældig variabel med nul forventning, er $Y$ $= 0$ næsten-sikkert, og propositionen er indlysende; begrundelsen er analog for Ved konveksitet af den funktion, vi har, for ${\ displaystyle c \ geq 0}$ ${\ displaystyle d \ leq 0.}$ ${\ displaystyle \ x \ mapsto e ^ {sx}, \}$ $\ c \ leq Y (\ omega) \ leq d, \$

e ^ {{sY (\ omega)}} \ leq {\ frac {dY (\ omega)} {dc}} \ e ^ {{sc}} \ + \ {\ frac {Y (\ omega) -c} {dc}} \ e ^ {{sd}}.

Gå videre til håb, da vi udleder det $\ {\ mathbb {P}} (c \ leq Y \ leq d) = 1, \$

{\ mathbb {E}} [e ^ {{sY}}] \ leq f (s) = {\ frac {d} {dc}} \ e ^ {{sc}} \ + \ {\ frac {-c } {dc}} \ e ^ {{sd}}.

Vi udgør

{\ begin {array} {rl} (dc) s & = u \\\ ln (f (s)) & = \ psi (u), \\ {\ frac {-c} {dc}} & = p , \ quad 1-p = {\ frac {d} {dc}}. \ end {array}}

Da $c <0$ og $d > 0$ , har vi derfor relevansen af notationen. Den følger det ${\ displaystyle p \ in [0,1]}$

\ psi (u) \, = \, - pu + \ ln \ left (1-p + pe ^ {{u}} \ højre).

Vi bemærker derefter, at derudover $\ \ psi (0) = \ psi ^ {{\ prime}} (0) = 0. \$

\ psi ^ {{\ prime \ prime}} (u) = {\ frac {\ left (1-p \ right) pe ^ {{u}}} {\ left (1-p + pe ^ {{u} } \ right) ^ {2}}} = {\ frac {\ alpha \ beta} {(\ alpha + \ beta) ^ {2}}} \ leq {\ frac 14}.

Derefter i kraft af Taylor-Lagrange-formlen i rækkefølge 1,

{\ displaystyle \ psi (u) = \ psi (0) + \ psi ^ {\ prime} (0) u + R_ {2} (u) \ leq {\ frac {u ^ {2}} {8}} .}

Bevis for Hoeffdings ulighed

Vi anvender derefter Markov-uligheden . Til dette udgør vi:

{\ begin {array} {rl} Y _ {{i}} & = X _ {{i}} - {\ mathbb {E}} [X _ {{i}}], \\ c _ {{i }} & = a _ {{i}} - {\ mathbb {E}} [X _ {{i}}], \ quad d _ {{i}} = b _ {{i}} - {\ mathbb {E}} [X _ {{i}}], \ end {array}}

og det bemærker vi

{\ begin {array} {rl} {\ mathbb {P}} (c_ {i} \ leq Y_ {i} \ leq d_ {i}) & = 1, \\ d _ {{i}} - c _ {{i}} & = b _ {{i}} - en _ {{i}}, \\ S _ {{n}} - {\ mathbb {E}} [S _ {{n}}] & = Y _ {{1}} + Y _ {{2}} + \ prikker + Y _ {{n}}. \ Afslut {array}}

For alt har vi derfor i kraft af en følge af Markovs ulighed af uafhængigheden af og derfor af og af det foregående forslag: $\ s> 0, \$ $\ X _ {{i}}, \$ $\ Y _ {{i}}, \$

{\ begin {array} {rl} {\ mathbb {P}} \ left (S_ {n} - {\ mathbb {E}} [S_ {n}] \ geq t \ right) & \ leq {\ mathbb { E}} \ venstre [e ^ {{s (S_ {n} - {\ mathbb {E}} [S_ {n}])}} \ højre] e ^ {{- st}} \\ & = {\ mathbb {E}} \ left [e ^ {{s (Y _ {{1}} + Y _ {{2}} + \ prikker + Y _ {{n}})}} \ højre] e ^ {{ - st}} \\ & = e ^ {{- st}} \ \ prod _ {{i = 1}} ^ {n} {\ mathbb {E}} \ left [e ^ {{sY _ {{i }}}} \ højre] \\ & \ leq \ exp \ left (-st + {\ frac {s ^ {2} \ \ sum _ {{i = 1}} ^ {n} (b_ {i} - a_ {i}) ^ {2}} 8} \ højre). \ Afslut {array}}

Uligheden gælder især for

s _ {{0}} = {\ frac {4t} {\ sum _ {{i = 1}} ^ {n} (b_ {i} -a_ {i}) ^ {2}}},

som realiserer minimumet af den højre bundet, hvilket viser den første ulighed. Den anden ulighed demonstreres ved at erstatte ved og ved i den foregående beregning ved at stille $\ Y _ {{i}} \$ $\ Y _ {{i}} ^ {{\ prime}} = {\ mathbb {E}} [X _ {{i}}] - X _ {{i}}, \$ $\ S _ {{n}} - {\ mathbb {E}} [S _ {{n}}] \$ $\ {\ mathbb {E}} [S _ {{n}}] - S _ {{n}}, \$

{\ begin {array} {rl} c _ {{i}} ^ {{\ prime}} & = {\ mathbb {E}} [X _ {{i}}] - b _ {{i}}, \\ d_ {{i}} ^ {{\ prime}} & = {\ mathbb {E}} [X _ {{i}}] - en _ {{i}}, \ end {array}}

og bemærker det

{\ begin {array} {rl} {\ mathbb {P}} (c_ {i} ^ {{\ prime}} \ leq Y_ {i} ^ {{\ prime}} \ leq d_ {i} ^ {{ \ prime}}) & = 1, \\ d _ {{i}} ^ {{\ prime}} - c _ {{i}} ^ {{\ prime}} & = b _ {{i}} - a _ {{i}}, \\ {\ mathbb {E}} [S _ {{n}}] - S _ {{n}} & = Y _ {{1}} ^ {{\ prime}} + Y _ {{2}} ^ {{\ prime}} + \ prikker + Y _ {{n}} ^ {{\ prime}}. \ End {array}}

Den tredje ulighed er en direkte konsekvens af de to første.

Erklæring "til enhver tid"

I sit papir fra 1963 gav Hoeffding en lidt mere generel erklæring om sin ulighed ved hjælp af Doobs ulighed . Mere præcist under de samme antagelser for alle $\ t> 0, \$

{\ displaystyle {\ begin {array} {rl} \ mathbb {P} \ left (\ exist m \ leq n, ~ S_ {m} - \ mathbb {E} [S_ {m}] \ geq t \ right) & \ leq \ exp \ left (- {\ frac {2 \, t ^ {2}} {\ sum _ {i = 1} ^ {n} (b_ {i} -a_ {i}) ^ {2} }} \ højre), \\\ mathbb {P} \ venstre (\ eksisterer m \ leq n, ~ S_ {m} - \ mathbb {E} [S_ {m}] \ leq -t \ højre) & \ leq \ exp \ left (- {\ frac {2 \, t ^ {2}} {\ sum _ {i = 1} ^ {n} (b_ {i} -a_ {i}) ^ {2}}} \ højre), \\\ mathbb {P} \ left (\ exist m \ leq n, ~ \ left | S_ {m} - \ mathbb {E} [S_ {m}] \ right | \ geq t \ right) & \ leq 2 \ exp \ left (- {\ frac {2 \, t ^ {2}} {\ sum _ {i = 1} ^ {n} (b_ {i} -a_ {i}) ^ {2} }} \ right). \ end {array}}}

Se også

Tilknyttede sider

Bibliografi

C. McDiarmid, om metoden med begrænsede forskelle. I Surveys in Combinatorics , London Math. Soc. Readings Noter 141, Cambridge Univ. Press, Cambridge 1989, 148–188.
W. Hoeffding, "Sandsynlighedsuligheder for summer af afgrænsede tilfældige variabler", J. Amer. Statistik. Assoc. 58, 13-30, 1963