Disuguaglianza di Hoeffding

La disuguaglianza di Hoeffding permette di indicare la probabilità massima che la somma di variabili casuali limitate e indipendenti superi di una determinata quantità la somma dei loro valori attesi. Questa disuguaglianza venne pubblicata da Wassily Hoeffding nel 1963 e svolge un ruolo importante nell'ambito della teoria della statistica non parametrica grazie alle poche assunzioni fatte sulle variabili casuali.

Teorema

Siano $X_{1},...,X_{n}$ n variabili casuali indipendenti ma limitate nei loro valori minimi e massimi per cui

$P(a_{i}\leq X_{i}\leq b_{i})=1$ e $-\infty <a_{i},b_{i}<+\infty$ per $i=1,...,n$

e sia S la loro somma

$S=X_{1}+...+X_{n}$

e E[S] il valore atteso della somma S

allora

$P(S-E[S]\geq t)\leq e^{-{\frac {2t^{2}}{\sum (b_{i}-a_{i})^{2}}}}$ per t > 0

Se ci s'interessa non alla somma ma alla media allora la disuguaglianza diventa

$P(M-\mu \geq \delta )\leq e^{-{\frac {2n^{2}\delta ^{2}}{\sum (b_{i}-a_{i})^{2}}}}$ per $\delta$ > 0

dove $M={\frac {1}{n}}S$ e $\mu ={\frac {1}{n}}E[S]$.

Esempio

Si pensi al lancio di n=10 dadi con sei facce e i numeri da a=1 a b=6, di cui si ignora però se sono truccati o meno e pertanto non si può assumere la variabile casuale uniforme e neanche una generica v.c. della quale si conosca media a varianza (nel caso di dadi "giusti" la media è pari a 3,5 e la varianza è uguale a 2,91667).

Grazie alla disuguaglianza di Hoeffding si può comunque affermare che la probabilità che la somma S di questi 10 dadi superi di t=10 la vera (e ignota) somma dei valori attesi (E[S]) è sicuramente non superiore a 45 %, in quanto

$P(S-E[S]\geq 10)\leq e^{-{\frac {2*10^{2}}{\sum (6-1)^{2}}}}=e^{-{\frac {200}{10*5^{2}}}}=e^{-{\frac {200}{250}}}=0,4493...$

Ciò vuol dire che se, poniamo il caso, la somma dei 10 dadi risulta essere S=47, allora con una confidenza superiore al 55% possiamo affermare che la media teorica dei dieci dadi è maggiore o uguale a 37 (E[S] ≥ 47-10).

Si noti che non è stata fatta né l'ipotesi che i dieci dadi siano stati truccati in modo uguale e tanto meno che i dadi non siano truccati. Nessuna ipotesi è stata fatta neanche sulla varianza delle dieci variabili casuali corrispondenti ai dieci dadi.

Facendo invece l'ipotesi che i dieci dadi siano tutti "giusti", allora avremmo potuto affermare che la probabilità che la somma dei dieci dadi dia 45 o più è pari a 4%, valore nettamente inferiore a quello massimo indicato dalla disuguaglianza di Hoeffding. Questa differenza si spiega per esempio con il fatto che le poche ipotesi fatte per la disuguaglianza permettono di fare affermazioni valide sia per dadi "giusti" che anche per dadi pesantemente truccati, comprendendo tra l'altro dadi truccati indicando su cinque facce il valore 1 e sulla sesta il valore 6, ignorando i valori intermedi.

Bibliografia

• Wassily Hoeffding, Probability inequalities for sums of bounded random variables, in Journal of the American Statistical Association, 1963.

Voci correlate

• disuguaglianza di Cebicev, la quale richiede la conoscenza della varianza, ma le variabili non sono necessariamente limitate
• disuguaglianza di Bernstein, la quale richiede la conoscenza della varianza, e la variabili sono limitate