Esercizio - mediana randomizzata, parametri e probabilità di fallimento

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 → (algoritmo e analisi); per il confronto con le code esponenziali Limiti di Chernoff e di HoeffdingMarkov applicato a e^(tX) dà code esponenziali. Per somme di Bernoulli indipendenti con media μ: P(X ≥ (1+δ)μ) ≤ [e^δ/(1+δ)^(1+δ)]^μ ≤ e^(-δ²μ/3) per 0<δ≤1, P(X ≤ (1-δ)μ) ≤ e^(-δ²μ/2), P(X ≥ R) ≤ 2^(-R) se R ≥ 6μ. Hoeffding per X_i in [a_i,b_i]: P(|S-E[S]| ≥ t) ≤ 2exp(-2t²/Σ(b_i-a_i)²). Applicazioni: n ≥ ln(2/δ)/(2ε²) campioni per stimare una probabilità, amplificazione BPP con k = O(log 1/ε) ripetizioni, bilanciamento di insiemi con scarto √(4m ln n).Limiti di Chernoff e di Hoeffding →.

Testo. Si esegue l'algoritmo della mediana per campionamento su $n=10^6+1$ numeri distinti: campione di $m=\lceil n^{3/4}\rceil$ elementi con reinserimento, $d$ e $u$ ai ranghi $m/2\mp\sqrt n$ del campione, $C=\{x:d\le x\le u\}$, si ricomincia se la mediana non è in $C$ o se $|C|>4m$.

1. Calcolare $m$, $\sqrt n$, il numero atteso di elementi in $C$ e il costo di un giro in confronti.
2. Dimostrare che la probabilità che $d$ sia sopra la mediana è al più $\frac14n^{-1/4}$ e calcolare il limite per l'intero fallimento.
3. Rifare il limite con Hoeffding al posto di Chebyshev.
4. Confrontare con una simulazione.

Soluzione

1. Parametri. $n^{3/4}=10^{4{,}5}=31622{,}8$, quindi $m=31623$; $\sqrt n=1000{,}0005\approx1000$ (la mediana ha rango $k=500001$). I due estremi distano $2\sqrt n=2000$ ranghi nel campione di $m$ elementi, cioè una frazione $\frac{2000}{m}$ dell'insieme: $|C|\approx n\cdot\frac{2\sqrt n}{m}=2n^{3/4}\approx63246\approx2m$, ben sotto il limite $4m=126492$. Un giro costa:

• ordinare il campione: $O(m\log m)$, circa $31623\cdot15\approx4{,}7\times10^5$ operazioni;
• confrontare ogni elemento con $d$ e con $u$: $2n=2\,000\,002$ confronti;
• ordinare $C$: $O(|C|\log|C|)$, circa $63246\cdot16\approx10^6$.

In totale circa $2\times10^6+1{,}5\times10^6=3{,}5\times10^6$ confronti, contro $n\log_2n\approx2\times10^7$ dell'ordinamento diretto. Asintoticamente domina $2n$, perché i due ordinamenti costano $O(n^{3/4}\log n)=o(n)$; per $n=10^6$ però pesano ancora quasi quanto il passaggio sull'input.

2. Limite di Chebyshev. Sia $Y$ il numero di elementi del campione che sono $\le$ mediana: $Y\sim\mathrm{Bin}(m,q)$ con $q=\frac{k}{n}\ge\frac12$. Se $d>$ mediana, meno di $m/2-\sqrt n$ campioni sono $\le$ mediana, cioè $Y<m/2-\sqrt n\le E[Y]-\sqrt n$. Con $\mathrm{Var}(Y)=mq(1-q)\le\frac m4$ e Chebyshev: $$P\big(Y\le E[Y]-\sqrt n\big)\le\frac{m/4}{n}=\frac{n^{3/4}}{4n}=\frac14n^{-1/4}=\frac14\cdot0{,}0316=0.0079.$$ Gli altri tre eventi cattivi (la mediana sopra $u$, $u$ oltre il rango $k+2m$, $d$ sotto $k-2m$) hanno la stessa limitazione, quindi $$P(\text{giro fallito})\le4\cdot0{,}0079=n^{-1/4}=0.0316.$$ In media si fanno meno di $\frac1{1-0{,}0316}=1{,}033$ giri.

3. Limite di Hoeffding. $Y$ è somma di $m$ indicatori indipendenti: $P(Y\le E[Y]-\sqrt n)\le e^{-2(\sqrt n)^2/m}=e^{-2n/m}=e^{-2n^{1/4}}=e^{-63{,}2}=3{,}4\times10^{-28}$. Per i quattro eventi $\le1{,}4\times10^{-27}$: la probabilità di fallimento passa da $3\times10^{-2}$ a $10^{-27}$: il limite di Chebyshev è molto prudente.

4. Simulazione. Su $300$ esecuzioni con $n=10^6+1$: $0$ giri falliti, $|C|$ medio $63161$ (da $59184$ a $66657$, previsto $\approx2m=63246$), quindi il costo di un giro resta quello stimato al punto 1.

Risultato. $m=31623$, $|C|\approx63246$, costo $2n+O(n^{3/4}\log n)$, circa $3{,}5\times10^6$ confronti; fallimento $\le n^{-1/4}=0{,}0316$ (Chebyshev), $\le1{,}4\times10^{-27}$ (Hoeffding).

Verifica.

import math
import numpy as np

n = 10**6 + 1
m = math.ceil(n**0.75); r = math.isqrt(n); k = (n + 1) // 2
print(m, r, n**-0.25, 4 * math.exp(-2 * n / m))     # 31623 1000 0.0316 1.4e-27

rng = np.random.default_rng(1)
a = np.arange(n)                                     # i numeri sono 0..n-1, la mediana e' n // 2
falliti, dim = 0, []
for _ in range(300):
    R = np.sort(rng.integers(0, n, size=m))          # campione con reinserimento (valori = ranghi)
    d, u = R[m // 2 - r - 1], R[m // 2 + r]
    sotto, sopra = (a < d).sum(), (a > u).sum()
    C = ((a >= d) & (a <= u)).sum(); dim.append(C)
    falliti += not (sotto < k and sopra < k and C <= 4 * m)
print(falliti, np.mean(dim))                         # 0 ~63200