Esercizio - Markov traslato e ribaltato sui punteggi di un esame (lezioni MIT)

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 → (Markov e Chebyshev); dimostrazioni in 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 →. Esempi tratti dalle videolezioni di Mathematics for Computer Science, MIT OpenCourseWare.

Testo. Il punteggio $R$ di uno studente scelto a caso sta in $[30,100]$ e $E[R]=75$.

1. Limitare $P(R\ge90)$ con Markov applicato a $R$ e poi a $R-30$. Quale limite è migliore? Trovare una distribuzione per cui il secondo è un'uguaglianza.
2. Limitare $P(R\le65)$. Perché Markov su $R$ non serve? Che cosa si fa?
3. Se il punteggio potesse scendere fino a $-30$ (penalità) con la stessa media, quanto varrebbe il limite per $P(R\ge90)$? Perché non si può applicare Markov a $R$ direttamente? Mostrare con $R=\pm1$ che cosa succede.
4. Sapendo anche che $\mathrm{Var}(R)=25$, limitare $P(R\le65)$ con Chebyshev.
5. $n$ persone lasciano il telefono all'ingresso e lo riprendono a caso; $N$ è il numero di persone che riprendono il proprio, con $E[N]=1$. Limitare $P(N=n)$ con Markov e confrontare con il valore vero quando i telefoni sono su un vassoio girevole ruotato a caso e quando sono restituiti con una permutazione uniforme.

Soluzione

1. Markov e traslazione. $R\ge0$, quindi Markov si applica: $P(R\ge90)\le\frac{75}{90}=\frac56=0{,}833$. Ma si sa di più: $R\ge30$. La variabile $R'=R-30$ è ancora $\ge0$, ha media $75-30=45$, e $\{R\ge90\}=\{R'\ge60\}$: $$P(R\ge90)=P(R'\ge60)\le\frac{45}{60}=\frac34=\mathbf{0{,}75}.$$ È migliore perché un limite superiore più piccolo dice di più. Markov è un'uguaglianza quando tutta la massa sta in $0$ e sulla soglia: per $R'$ si prende $R'=0$ (cioè $R=30$) con probabilità $\frac14$ e $R'=60$ ($R=90$) con probabilità $\frac34$. Allora $E[R]=30\cdot\frac14+90\cdot\frac34=7{,}5+67{,}5=75$ e $P(R\ge90)=\frac34$: con queste informazioni non si può dire di meglio.

2. Coda inferiore, variabile ribaltata. $P(R\le65)=1-P(R\ge66)$, e Markov dà solo $P(R\ge66)\le\frac{75}{66}>1$: nessuna informazione. Si usa il massimo $100$: $S=100-R\ge0$, $E[S]=100-75=25$, e $\{R\le65\}=\{S\ge35\}$: $$P(R\le65)=P(S\ge35)\le\frac{25}{35}=\frac57=\mathbf{0{,}714}.$$ Anche questo è stretto: $R=65$ con probabilità $\frac57$ e $R=100$ con probabilità $\frac27$ hanno media $\frac{325+200}{7}=75$.

3. Valori negativi. Con $R\in[-30,100]$ Markov su $R$ non è lecito: nella dimostrazione si scrive $E[R]\ge a\,P(R\ge a)$ trascurando il contributo dell'evento $\{R<a\}$, che deve essere $\ge0$; se $R$ può essere negativa quel contributo può essere negativo. Si trasla: $T=R+30\ge0$, $E[T]=105$, $\{R\ge90\}=\{T\ge120\}$, quindi $P(R\ge90)\le\frac{105}{120}=\frac78=\mathbf{0{,}875}$, più debole del punto 1 perché si sa meno sul minimo. Controesempio. $R=\pm1$ con probabilità $\frac12$: $E[R]=0$ e "Markov" darebbe $P(R\ge\frac12)\le\frac{0}{1/2}=0$, mentre $P(R\ge\frac12)=P(R=1)=\frac12$.

4. Chebyshev. La deviazione standard è $\sqrt{25}=5$ e $65$ è a $10=2\sigma$ sotto la media. La coda sinistra è contenuta nell'unione delle due code: $$P(R\le65)\le P(|R-75|\ge10)\le\frac{25}{10^2}=\frac14=\mathbf{0{,}25},$$ molto meglio di $\frac57$ perché si usa anche la varianza. Il limite è prudente: include anche la coda $R\ge85$ che non interessa.

5. Telefoni. $N\ge0$ e $E[N]=1$: $P(N=n)=P(N\ge n)\le\frac1n$.

• Vassoio girevole ruotato di una posizione uniforme in $\{0,\dots,n-1\}$: ognuno riprende il proprio telefono solo con rotazione $0$, e in quel caso tutti lo riprendono. Quindi $N=n$ con probabilità $\frac1n$ e $N=0$ altrimenti: $E[N]=1$ e $P(N=n)=\frac1n$, Markov è esatto.
• Permutazione uniforme: solo l'identità restituisce tutti i telefoni, $P(N=n)=\frac1{n!}$ (per $n=5$: $\frac1{120}$ contro il limite $\frac15$). La media è ancora $1$ (Linearità del valore atteso e variabili indicatriciLa linearità $E[X+Y]=E[X]+E[Y]$ vale sempre, anche senza indipendenza; con le variabili indicatrici ($E[I_A]=P(A)$) trasforma un conteggio in una somma di probabilità. Applicazioni: attesa del primo successo $1/p$, collezionista di figurine $nH_n$, punti fissi di una permutazione (media $1$), record (media $H_n$), inversioni ($n(n-1)/4$), attesa condizionata, identità di Wald $E[S_N]=E[N]E[X]$.Linearità del valore atteso e variabili indicatrici →) ma la distribuzione è molto più concentrata.

La media da sola non distingue le due situazioni: Markov deve valere per entrambe, quindi non può essere migliore di $\frac1n$.

Risultato. $P(R\ge90)\le\frac34$ (traslando), $P(R\le65)\le\frac57$ (ribaltando) e $\le\frac14$ con la varianza; con minimo $-30$: $\frac78$; telefoni: $\frac1n$, esatto per il vassoio, contro $\frac1{n!}$ per la permutazione.

Verifica.

from fractions import Fraction as F
from itertools import permutations

E = lambda d: sum(x * p for x, p in d.items())
d1 = {30: F(1, 4), 90: F(3, 4)}                    # rende stretto il limite 3/4
d2 = {65: F(5, 7), 100: F(2, 7)}                   # rende stretto il limite 5/7
print(E(d1), d1[90], E(d2), d2[65])                # 75 3/4 75 5/7
print(F(75, 90), F(45, 60), F(25, 35), F(105, 120), F(25, 100))
n = 5
vassoio = [sum((i + r) % n == i for i in range(n)) for r in range(n)]
perm = [sum(p[i] == i for i in range(n)) for p in permutations(range(n))]
print(F(sum(vassoio), n), F(vassoio.count(n), n), F(sum(perm), len(perm)), F(perm.count(n), len(perm)))

Risultato: 75 3/4 75 5/7, poi 5/6 3/4 5/7 7/8 1/4, poi 1 1/5 1 1/120.