Disuguaglianza di Hoeffding

Da Wikipedia, l'enciclopedia libera.

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 svuolge un ruolo importante nell'ambito della teoria della statistica non parametrica grazie alle poche assunzioni fatte sulle v.c.

[modifica] Teorema

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

$P(a_i \le X_i \le b_i)=1$ e $-\infin<a_i, b_i<+\infin$ per i=1,...,n

e sia S la loro somma

S = X i + ... + X n

e E[S] il valore atteso della somma S

allora

$P(S-E[S] \ge t) \le e^{-\frac{2 t^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 \ge \delta) \le e^{-\frac{2 n^2 \delta^2}{\sum (b_i-a_i)^2}}$ per t > 0

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

[modifica] 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] \ge 10) \le 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 puta 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 è inferiore o uguale a 37 (E[S] ≤ 47-10).

Si noti che non è stata fatte 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.

[modifica] Bibliografia

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

[modifica] 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

Estratto da "http://it.wikipedia.org../../../d/i/s/Disuguaglianza_di_Hoeffding_dc01.html"

Categorie: Statistica | Disuguaglianze