ADRC - Probability Tools
1 Concentrare Variabili Aleatorie
La concentrazione di una variabile aleatoria \(X\) consiste nel trovare dei limiti (bounds) della seguente forma
\[Pr[ | X - \mathbb{E}[X] | > \epsilon] \leq \delta\]
Tipicamente poi vogliamo valori di \(\delta\) "molto bassi". In particolare se \(\delta = 1/n^{\alpha}\) con \(\alpha > 1\) costante possiamo dire che con alta probabilità \(X\) si trova al massimo distante \(\epsilon\) dalla media \(\mathbb[X]\).
Per ottenere risultati del genere esistono vari strumenti probabilistici. Tra questi troviami i seguenti tre:
- Disuguaglianza di Markov;
- Disuguaglianza di Chebyshev;
- Chernoff Bounds;
Andiamo quindi a descrivere ciascuno di questi strumenti in modo più dettagliato.
2 Disuguaglianza di Markov
Sia \(X\) una v.a. che assume solo valori non negativi. La disuguaglianza di Markov ci dice che
\[\forall a > 1: \,\, Pr[ X \geq a ] \leq \frac{\mathbb{E}[X]}{a}\]
Dimostrazione: Sia \(a > 0\), e definiamo la seguente v.a.
\[I_a := \begin{cases} 1 \,\,&,\,\, X \geq a \\ 0 \,\,&,\,\, \text{ altrimenti }\\ \end{cases}\]
Dato che \(X \geq 0\) troviamo che \(I_a \leq X/a\). Inoltre, per come abbiamo definito \(I_a\) troviamo
\[\mathbb{E}[I_a] = Pr[I_a = 1] = Pr[ X \geq a]\]
e quindi,
\[Pr[X \geq a] = \mathbb{E}[I_a] = \leq \frac{\mathbb{E}[X]}{a}\]
\[\tag*{$\blacksquare$}\]
2.1 Esempio
Supponiamo di voler dare un bound alla probabilità di ottenere più di \(3/4n\) teste in \(n\) lanci di una moneta equilibrata. A tale fine definiamo le seguenti v.a. v.a.
\[\forall i \in \{1, 2, \ldots, n\}: \,\,\, X_i := \begin{cases} 1 \,\,&,\,\, \text{l' } i \text{ -esimo lancio è testa} \\ 0 \,\,&,\,\, \text{l' } i \text{ -esimo lancio è croce} \\ \end{cases}\]
Abbiamo quindi che \(X := \sum_{i = 1}^n X_i\) conta il numero di teste totali. La probabilità a cui siamo interessati può quindi essere limitata nel seguente modo
\[Pr\Big[ X \geq \frac{3n}{4}\Big] \leq \frac{\mathbb{E}[X]}{\frac{3n}{4}} = \frac{\frac{n}{2}}{\frac{3n}{4}} = \frac{2}{3}\]
Osservazione: Generalmente la disuguaglianza di Markov è troppo debole e non ci permette di otenere dei risultati con alta probabilità.
3 Disuguaglianza di Chebyshev
Sia \(X\) una v.a. La disuguaglianza di Chebyshev ci dice che
\[\forall a > 0: \,\, Pr[|X - \mathbb{E}[X]| \geq a] \leq \frac{Var[X]}{a^2}\]
Dimostrazione: Iniziamo osservando che
\[Pr[|X - \mathbb{E}[X]| \geq a] = Pr[(X - \mathbb{E}[X])^2 \geq a^2]\]
Dato poi che \((X -\mathbb{E}[X])^2\) è una v.a. a valori non negativi, possiamo applicare la disuguaglianza di Markov per ottenere
\[Pr[(X - \mathbb{E}[X])^2 \geq a^2] \leq \frac{\mathbb{E}[(X - \mathbb{E}[X])^2]}{a^2} = \frac{Var[X]}{a^2}\]
\[\tag*{$\blacksquare$}\]
Da quanto appena dimostrato segue che \(\forall t > 1:\)
- \(\displaystyle{Pr\Big[\big| X - \mathbb{E}[X]\big| \geq t \cdot Var[X]\Big] \leq \frac{1}{t^2}}\)
- \(\displaystyle{Pr\Big[\big| X - \mathbb{E}[X]\big| \geq t \cdot \mathbb{E}[X]\Big] \leq \frac{Var[X]}{t^2 \cdot \mathbb{E}[X]^2}}\)
3.1 Esempio
Riprendendo l'esempio visto prima, possiamo migliorare il bound ottenuto per la probabilità di ottenere più di \(3/4n\) teste da una moneta equilibrata nel seguente modo
\[\begin{split} Pr\Big[X \geq \frac{3n}{4}\Big] \leq Pr\Big[ \big|X - \frac{n}{2}\big| \geq \frac{n}{4}\Big] &\leq \frac{Var[X]}{(\frac{n}{4})^2} \\ &= \frac{n/4}{(n/4)^2} \\ &= \frac{4}{n} \\ \end{split}\]
Come possiam onotare questo upper bound è "migliore" di quello di 2/3 trovato tramite la disuguaglianza, dove per "migliore" si intende il fatto che il bound si avvicina di più rispetto al vero valore di probabilità dell'evento in questione.
4 Chernoff Bounds
I Chernoff bounds sono degli strumenti di concentrazione applicabili a v.a. che possono essere espresse come somme di v.a. indipendenti, con la stessa distribuzione, e a valori booleani.
Formalmente, siano \(X_1, X_2, \ldots, X_n\) v.a. i.i.d. e sia \(X := \sum_{i = 1}^n X_i\) e \(\mu = \mathbb{X}\). Allora valgono i seguenti risultati
- Additive Form:
- \(\forall 0 < \lambda < n - \mu\)
\[Pr\Big[X \leq \mu - \lambda\Big] \leq Exp\Big(-\frac{2 \lambda^2}{n}\Big)\]
- \(\forall 0 < \lambda < \mu\)
\[Pr\Big[X \leq \mu + \lambda\Big] \leq Exp\Big(-\frac{2 \lambda^2}{n}\Big)\]
- \(\forall 0 < \lambda < n - \mu\)
- Moltiplicative Form
- \(\forall 0 < \delta < 1\)
\[Pr\Big[ X \geq (1 + \delta) \mu) \Big] \leq Exp\Big(-\frac{\mu \delta^2}{3}\Big)\]
- \(\forall 0 < \delta < 1\)
\[Pr\Big[ X \geq (1 - \delta) \mu) \Big] \leq Exp\Big(-\frac{\mu \delta^2}{2}\Big)\]
- \(\forall \delta > 0\)
\[Pr\Big[X \geq (1 + \delta) \mu\Big] \leq \Bigg(\frac{e^{\delta}}{(1 + \delta)^{(1 + \delta)}}\Bigg)^{\mu}\]
- \(\forall 0 < \delta < 1\)