Esercizio - coppie di compleanni uguali e indipendenza a coppie

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 → (secondo momento, indipendenza a coppie). Il paradosso del compleanno è trattato in Palline e urne - compleanno, carico massimo e approssimazione di PoissonModello palline e urne (m palline, n urne, scelte indipendenti e uniformi): paradosso del compleanno con soglia sqrt(2 n ln 2), urne vuote attese n e^(-m/n), carico massimo ln n / ln ln n con dimostrazione (first moment e union bound), approssimazione di Poisson con il fattore e sqrt(m), potere delle due scelte (ln ln n / ln 2).Palline e urne - compleanno, carico massimo e approssimazione di Poisson →.

Testo. $n$ persone hanno compleanni indipendenti e uniformi su $d=365$ giorni. $M$ è il numero di coppie $\{i,j\}$ con lo stesso compleanno, $M=\sum_{i<j}A_{ij}$, $A_{ij}=\mathbf 1_{\{b_i=b_j\}}$.

1. Mostrare che gli eventi $A_{ij}$ sono indipendenti a coppie ma non a tre a tre.
2. Calcolare $E[M]$ e $\mathrm{Var}(M)$.
3. Per $n=23$ usare il metodo del secondo momento per limitare dal basso $P(M>0)$ e confrontare con il valore esatto.
4. Per $n=100$ limitare $P(M=0)$ con Chebyshev e confrontare con il valore esatto.

Soluzione

1. Indipendenza a coppie. $P(A_{ij})=\frac1d$ (dato $b_i$, il giorno $b_j$ coincide con probabilità $\frac1d$). Due coppie $\{i,j\}$ e $\{k,l\}$:

• se sono disgiunte, $A_{ij}$ e $A_{kl}$ dipendono da compleanni diversi: indipendenti;
• se hanno una persona in comune, per esempio $\{i,j\}$ e $\{i,k\}$: dato $b_i$, $b_j$ e $b_k$ sono indipendenti e ciascuno coincide con $b_i$ con probabilità $\frac1d$, quindi $P(A_{ij}\cap A_{ik})=\frac1{d^2}=P(A_{ij})P(A_{ik})$.

A tre a tre invece: $A_{ij},A_{jk},A_{ik}$ si verificano insieme se e solo se $b_i=b_j=b_k$, probabilità $\frac1{d^2}$, mentre il prodotto sarebbe $\frac1{d^3}$. Quindi non sono indipendenti insieme.

2. Media e varianza. Con $\binom n2$ coppie, $E[M]=\binom n2\frac1d$. Le covarianze sono nulle, quindi la varianza si somma e $\mathrm{Var}(A_{ij})=\frac1d\big(1-\frac1d\big)$: $$\mathrm{Var}(M)=\binom n2\frac1d\Big(1-\frac1d\Big).$$ (Controllo per enumerazione con $n=4$, $d=5$: $E[M]=\frac65$, $\mathrm{Var}(M)=\frac{24}{25}$ ✓.)

3. $n=23$. $\binom{23}2=253$: $E[M]=\frac{253}{365}=0{,}6932$, $\mathrm{Var}(M)=0{,}6932\cdot\frac{364}{365}=0{,}6913$, $E[M^2]=\mathrm{Var}(M)+E[M]^2=0{,}6913+0{,}4805=1{,}1717$. Il secondo momento dà $$P(M>0)\ge\frac{E[M]^2}{E[M^2]}=\frac{0{,}4805}{1{,}1717}=0.410.$$ Il valore esatto è $P(M>0)=1-\prod_{i=0}^{22}\frac{365-i}{365}=0{,}5073$. Il limite $0{,}41$ non è stretto ma dice già che con $23$ persone una coppia uguale è tutt'altro che improbabile. Il limite di Chebyshev per $P(M=0)$ ($\frac{\mathrm{Var}}{E^2}=1{,}44$) qui sarebbe inutile: il secondo momento nella forma $\frac{E^2}{E[M^2]}$ è migliore.

4. $n=100$. $\binom{100}2=4950$: $E[M]=\frac{4950}{365}=13{,}56$, $\mathrm{Var}(M)=13{,}56\cdot\frac{364}{365}=13{,}52$. Chebyshev: $$P(M=0)\le\frac{13{,}52}{13{,}56^2}=0{,}0735,$$ mentre il valore esatto è $\prod_{i=0}^{99}\frac{365-i}{365}=3{,}07\times10^{-7}$. Il limite è corretto ma molto largo: la probabilità vera decresce in modo esponenziale, e a pari quantità di informazione ($E$ e $\mathrm{Var}$) Chebyshev non può saperlo. Una simulazione di $20000$ gruppi da $100$ dà media $13{,}56$ e varianza $13{,}4$, d'accordo con le formule.

Risultato. $E[M]=\binom n2/365$, $\mathrm{Var}(M)=E[M](1-\frac1{365})$; per $n=23$: $P(M>0)\ge0{,}410$ (esatto $0{,}507$); per $n=100$: $P(M=0)\le0{,}0735$ (esatto $3{,}07\times10^{-7}$).

Verifica.

import math, random
from itertools import product
from fractions import Fraction as F

d = 365
for n in (23, 100):
    E = math.comb(n, 2) / d; V = E * (1 - 1 / d)
    p0 = math.prod((d - i) / d for i in range(n))
    print(n, E, V, E * E / (V + E * E), 1 - p0, V / E**2, p0)

# controllo di Var(M) per enumerazione: n = 4, d = 5
vals = [sum(t[i] == t[j] for i in range(4) for j in range(i + 1, 4)) for t in product(range(5), repeat=4)]
N = len(vals); Em = F(sum(vals), N)
print(Em, F(sum(v * v for v in vals), N) - Em**2)          # 6/5 24/25