Esercizio - Chebyshev non si può migliorare e le due forme del secondo momento

Teoria: Momenti e deviazioni - Markov, Chebyshev e mediana randomizzataVar(ΣX_i) = ΣVar + 2ΣCov, e basta l'indipendenza a coppie perché la varianza si sommi. Chebyshev dà code polinomiali (collezionista: P(T ≥ nH_n + cn) ≤ π²/(6c²)); il metodo del secondo momento dà P(X=0) ≤ Var(X)/E[X]². Algoritmo della mediana: campione di n^(3/4) elementi, due estremi d e u a ±√n, ordinamento dei soli elementi tra d e u; fallisce con probabilità ≤ n^(-1/4) ed è Las Vegas con 2n + o(n) confronti.Momenti e deviazioni - Markov, Chebyshev e mediana randomizzata → (Chebyshev e metodo del secondo momento), Disuguaglianze di Markov, Chebyshev e JensenMarkov: per X ≥ 0, P(X ≥ a) ≤ E[X]/a; Chebyshev: P(|X − μ| ≥ ε) ≤ Var(X)/ε²; Jensen: per φ convessa, φ(E[X]) ≤ E[φ(X)]. Stimano probabilità e medie conoscendo solo media e varianza.Disuguaglianze di Markov, Chebyshev e Jensen →.

Testo (domande da orale).

1. Costruire una variabile $X$ con $E[X]=0$, $\mathrm{Var}(X)=1$ e $P(|X|\ge3)=\frac19$, cioè con Chebyshev raggiunto con uguaglianza. Generalizzare a ogni $k>1$.
2. Dimostrare che per ogni $X\ge0$ con $E[X]>0$ vale $P(X>0)\ge\frac{E[X]^2}{E[X^2]}$.
3. Trovare una $X$ per cui questo limite è un'uguaglianza e una per cui $P(X=0)\le\frac{\mathrm{Var}(X)}{E[X]^2}$ è inutile ma la forma $\frac{E[X]^2}{E[X^2]}$ è esatta.

Soluzione

1. Chebyshev è stretto. Per Chebyshev $P(|X-\mu|\ge k\sigma)\le\frac1{k^2}$. Si cerca una legge che non spreca nulla: tutta la massa fuori dall'intervallo deve stare esattamente sul bordo $\pm k\sigma$, e il resto sul centro. Con $\sigma=1$, $\mu=0$, $k=3$: $$P(X=3)=P(X=-3)=\tfrac1{18},\qquad P(X=0)=1-\tfrac19=\tfrac89.$$ Controllo: $E[X]=0$ per simmetria; $E[X^2]=9\cdot\frac1{18}+9\cdot\frac1{18}=1=\mathrm{Var}(X)$; $P(|X|\ge3)=\frac1{18}+\frac1{18}=\frac19=\frac1{k^2}$ ✓. Per ogni $k>1$: $X=\pm k$ con probabilità $\frac1{2k^2}$ ciascuno e $X=0$ con probabilità $1-\frac1{k^2}$; allora $\mathrm{Var}(X)=2k^2\cdot\frac1{2k^2}=1$ e $P(|X|\ge k)=\frac1{k^2}$. Chebyshev non si può migliorare se si conoscono solo media e varianza: nessuna costante più piccola di $\frac1{k^2}$ vale per tutte le leggi.

2. Forma di Cauchy-Schwarz. $X\ge0$ implica $X=X\cdot\mathbf 1_{\{X>0\}}$. Per Cauchy-Schwarz, $E[UV]^2\le E[U^2]E[V^2]$ con $U=X$ e $V=\mathbf 1_{\{X>0\}}$: $$E[X]^2=E\big[X\,\mathbf 1_{\{X>0\}}\big]^2\le E[X^2]\,E\big[\mathbf 1_{\{X>0\}}^2\big]=E[X^2]\,P(X>0).$$ Dividendo per $E[X^2]>0$ si ottiene la tesi. $\blacksquare$ (Anche $E[X]>0$ è usata: se $E[X]=0$ il limite è banale.)

3. Uguaglianza. In Cauchy-Schwarz si ha uguaglianza quando $U$ e $V$ sono proporzionali, cioè $X$ è costante dove è positiva. Esempio: $X=100$ con probabilità $\frac1{100}$ e $X=0$ altrimenti. Allora $$E[X]=1,\quad E[X^2]=10000\cdot\frac1{100}=100,\quad\mathrm{Var}(X)=99.$$ La forma Chebyshev dà $P(X=0)\le\frac{\mathrm{Var}}{E^2}=99$: inutile (maggiore di $1$). La forma del secondo momento dà $P(X>0)\ge\frac{1}{100}=0{,}01$, che è esattamente $P(X>0)$. Al contrario per $X$ con valori diversi tra loro (per esempio $X\in\{1,2\}$ con $0$) il limite è solo approssimato.

Risultato. Esempio di Chebyshev esatto: $\pm3$ con probabilità $\frac1{18}$, $0$ con $\frac89$; $P(X>0)\ge\frac{E[X]^2}{E[X^2]}$ con uguaglianza per $X$ costante sul suo supporto.

Verifica.

from fractions import Fraction as F

k = 3
dist = {-k: F(1, 2 * k * k), k: F(1, 2 * k * k), 0: 1 - F(1, k * k)}
E = sum(x * p for x, p in dist.items()); V = sum(x * x * p for x, p in dist.items()) - E**2
print(E, V, sum(p for x, p in dist.items() if abs(x) >= k))      # 0 1 1/9

Y = {100: F(1, 100), 0: F(99, 100)}
E = sum(x * p for x, p in Y.items()); E2 = sum(x * x * p for x, p in Y.items())
print(E, E2 - E**2, E**2 / E2, sum(p for x, p in Y.items() if x > 0))   # 1 99 1/100 1/100