Esercizio - varianza dei punti fissi di una permutazione e Chebyshev

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 → (varianza di una somma). Il valore atteso è in 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 →; il calcolo con $E[X(X-1)]$ e la distribuzione completa per $n=5$ sono in Esercizio - cappotti restituiti a caso e punti fissi di una permutazione.

Testo. Una permutazione $\pi$ di $\{1,\dots,n\}$ è scelta uniformemente a caso e $X$ è il numero dei suoi punti fissi, cioè degli indici con $\pi(i)=i$.

1. Calcolare $\mathrm{Var}(X)$ per $n\ge2$ con la formula della varianza di una somma.
2. Le indicatrici dei punti fissi sono indipendenti? Sono almeno indipendenti a coppie?
3. Limitare $P(X\ge4)$ con Markov e con Chebyshev.
4. Per $n=6$ calcolare il valore esatto di $P(X\ge4)$ e confrontarlo; confrontare anche con il limite $n\to\infty$.

Soluzione

1. Varianza. $X=\sum_{i=1}^nI_i$ con $I_i=\mathbf 1_{\{\pi(i)=i\}}$. Ogni $\pi(i)$ è uniforme su $n$ valori: $E[I_i]=\frac1n$, quindi $E[X]=1$ e $\mathrm{Var}(I_i)=\frac1n-\frac1{n^2}=\frac{n-1}{n^2}$. Per $i\ne j$, $I_iI_j=1$ se e solo se $\pi(i)=i$ e $\pi(j)=j$. Le permutazioni che fissano due indici sono $(n-2)!$ su $n!$: $E[I_iI_j]=\frac{(n-2)!}{n!}=\frac{1}{n(n-1)}$. Quindi $$\mathrm{Cov}(I_i,I_j)=\frac1{n(n-1)}-\frac1{n^2}=\frac{n-(n-1)}{n^2(n-1)}=\frac{1}{n^2(n-1)}.$$ Nella formula $\mathrm{Var}(X)=\sum_i\mathrm{Var}(I_i)+\sum_{i\ne j}\mathrm{Cov}(I_i,I_j)$ le coppie ordinate sono $n(n-1)$: $$\mathrm{Var}(X)=n\cdot\frac{n-1}{n^2}+n(n-1)\cdot\frac{1}{n^2(n-1)}=\frac{n-1}{n}+\frac1n=1.$$ $\mathrm{Var}(X)=1$ per ogni $n\ge2$, uguale a $E[X]=1$ (come una Poisson di parametro $1$).

2. La covarianza è $\frac1{n^2(n-1)}>0$, non nulla: le indicatrici non sono indipendenti, nemmeno a coppie (sapere che $i$ è fisso rende un po' più probabile che lo sia anche $j$). Per questo la somma delle varianze $n\cdot\frac{n-1}{n^2}\approx1-\frac1n$ non basta: il contributo delle covarianze, $\frac1n$, la porta a $1$.

3. Limiti. Markov ($X\ge0$, $E[X]=1$): $P(X\ge4)\le\frac14=0{,}25$. Chebyshev: $X\ge4$ implica $|X-1|\ge3$, quindi $P(X\ge4)\le\frac{\mathrm{Var}(X)}{3^2}=\frac19=0{,}111$.

4. Valore esatto per $n=6$. Quattro punti fissi: si scelgono i $\binom64=15$ indici fissi e gli altri due devono essere scambiati ($1$ modo: un derangement di $2$ elementi). Cinque punti fissi è impossibile (il sesto è forzato). Sei: $1$ modo. In tutto $16$ permutazioni su $720$: $$P(X\ge4)=\frac{16}{720}=\frac1{45}=0.0222.$$ Chebyshev ($0{,}111$) è circa $5$ volte più grande, Markov ($0{,}25$) circa $11$ volte. Per $n\to\infty$ il numero di punti fissi tende a una Poisson di parametro $1$ (Distribuzione di PoissonPoi(λ) conta eventi rari: P(X = k) = e^(−λ) λ^k / k! per k = 0, 1, 2, …, con media e varianza entrambe uguali a λ; approssima la binomiale Bin(n, p) quando n è grande e p piccolo, con λ = np.Distribuzione di Poisson →): $P(X\ge4)=1-e^{-1}\big(1+1+\frac12+\frac16\big)=0{,}0190$; con $n=7$ il valore esatto è $\frac{23}{1260}=0{,}0183$.

Risultato. $E[X]=\mathrm{Var}(X)=1$; $P(X\ge4)\le\frac14$ (Markov), $\le\frac19$ (Chebyshev), esatto $\frac1{45}$ per $n=6$.

Verifica.

from itertools import permutations
from fractions import Fraction as F

vals = [sum(i == p for i, p in enumerate(pm)) for pm in permutations(range(6))]
N = len(vals)
E = F(sum(vals), N); E2 = F(sum(v * v for v in vals), N)
print(E, E2 - E * E, F(sum(v >= 4 for v in vals), N))   # 1 1 1/45