Măsoară inegalitatea de concentrare

În teoria probabilităților , măsurile inegalităților de concentrare oferă estimări ale abaterii unei variabile aleatoare de la o anumită valoare (de obicei de la așteptările ei matematice ). Legea numerelor mari a teoriei clasice a probabilității afirmă că sumele variabilelor aleatoare independente, supuse unor condiții destul de slabe, cu o probabilitate mare se dovedesc a fi apropiate de așteptările lor matematice. Asemenea sume sunt exemple principale de variabile aleatoare care sunt concentrate în jurul valorilor lor medii .

Inegalitatea lui Markov

Să fie o variabilă aleatoare, aproape sigur nenegativă. Apoi, pentru orice constantă

.

Observați următoarea expresie pentru inegalitatea lui Markov: dacă  este o funcție nenegativă strict crescătoare, atunci

.

Inegalitatea lui Cebyshev

Inegalitatea Chebyshev necesită ca variabila aleatoare să îndeplinească următoarele condiții:

Apoi pentru orice constantă

,

sau, echivalent,

,

unde  este abaterea standard a variabilei aleatoare .

Inegalitatea Chebyshev poate fi considerată ca un caz special al inegalității generalizate de Markov aplicată variabilei aleatoare c .

Inegalitatea Vysochansky-Petunin

Inegalitatea gaussiană

Granițele lui Cernov

Cazul principal al limitei Cernovului [1] :63–65 necesită existența unei funcții generatoare definite ca . Pe baza inegalității Markov, pentru fiecare

,

si pentru fiecare

.

Limitele Chernoff sunt diferite pentru diferite distribuții și valori diferite ale parametrului .

Limite pentru sumele variabilelor aleatoare independente

Fie  variabile aleatoare independente astfel încât pentru tot i:

aproape probabil .

Fie - suma lor, - așteptarea matematică și  - varianța

, , .

Este adesea interesant să se estimeze diferența dintre sumă și așteptările sale matematice. Se pot folosi mai multe inegalități.

1. Inegalitatea lui Hoefding afirmă că

.

2. O variabilă aleatoare  este un caz special de martingale și . Prin urmare, se poate folosi inegalitatea lui Azuma , care oferă o estimare puțin mai slabă

.

Aici devine posibil să se ia în considerare orice martingale , inclusiv supermartingale și submartingale .

3. Funcția de însumare  este un caz special al unei funcții de variabile. Această funcție se modifică într-un mod limitat: dacă variabila se modifică, atunci și valoarea se modifică cu cel mult . Prin urmare, se poate folosi inegalitatea lui McDiarmid și va oferi o estimare similară

.

Aceasta este o altă generalizare a inegalității lui Hoefding, deoarece aici este posibil să se lucreze nu numai cu funcția de însumare, ci și cu alte funcții dacă acestea se modifică într-un mod limitat.

4. Inegalitatea lui Bennett oferă o oarecare îmbunătățire față de inegalitatea lui Höfding atunci când varianțele termenilor sunt mici în comparație cu „limitele aproape probabil” ale acestora C .

Unde

5. Prima dintre inegalitățile lui Bernstein afirmă că

.

La fel ca inegalitatea lui Höfding, pentru care această estimare este o generalizare, prima inegalitate a lui Bernstein ia în considerare aproape sigur variabile aleatoare mărginite. Mai mult, permite obținerea unei estimări mai precise, cu condiția ca variabilele aleatoare să aibă varianțe limitate.

6. Limitele Chernoff au o formă deosebit de simplă pentru suma mărimilor independente, deoarece

].

De exemplu, [2] lasă variabilele aleatoare să satisfacă inegalitatea pentru , apoi pentru coada inferioară avem inegalitatea

.

Dacă satisface inegalitatea , atunci pentru coada superioară avem inegalitatea

.

Dacă sunt independente și egal distribuite și  este varianța lui , atunci forma tipică a inegalității Chernoff este următoarea:

.

7. Limite similare pot fi găsite în secțiunea: Distribuție Rademacher (Margini pe sume)

Inegalitate Efron-Stein

Inegalitatea Efron-Stein (inegalitatea de influență sau estimatorul MG al varianței) estimează varianța unei funcții generale de variabile aleatoare.

Fie , să fie independent, a și să aibă aceeași distribuție pentru toate .

Pune Atunci

.

Inegalitatea Dvoretsky-Kiefer-Wolfowitz

Inegalitatea Dvoretsky-Kiefer-Wolfowitz estimează diferența dintre funcțiile de distribuție actuale și empirice .

Fie pentru un număr natural dat variabile aleatoare cu  valori reale independente și distribuite identic cu funcția de distribuție . Să notăm funcția de distribuție empirică corespunzătoare , definită prin formula

Astfel,  este probabilitatea unui eveniment ca o singură variabilă aleatoare să fie mai mică decât , și  este numărul mediu de valori din eșantion , ale cărui realizări sunt mai mici de .

Atunci următoarele estimări unilaterale și bilaterale sunt adevărate:

Note

  1. Mitzenmacher, Michael. Probabilitate și calcul: algoritmi aleatoriu și analiză probabilistică  / Mitzenmacher, Michael, Upfal, Eli. - Cambridge University Press, 2005. - ISBN 0-521-83540-2 . Arhivat pe 16 aprilie 2021 la Wayback Machine
  2. Chung, Fan; Lu, Linyuan Vechi și noi inegalități de concentrare . Grafice și rețele complexe . Societatea Americană de Matematică (2010). Preluat la 14 august 2018. Arhivat din original la 15 aprilie 2021.

Link -uri