Esercizio - Stima degli elementi distinti con il k-esimo minimo

Teoria: Algoritmi di streaming - campionamento di riserva e conteggio degli elementi distintiModello a flusso (un passaggio, memoria molto minore di n); campionamento di riserva (reservoir sampling) con dimostrazione per induzione; contatore di Morris (stima non distorta 2^X-1, varianza n(n-1)/2); elementi distinti: idea di Flajolet-Martin e stima del k-esimo minimo (k-1)/v_k; Count-Min sketch con garanzia (epsilon, delta) e dimensionamento w=e/epsilon, d=ln(1/delta).Algoritmi di streaming - campionamento di riserva e conteggio degli elementi distinti → (elementi distinti, $k$-esimo minimo), 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 →.

Testo. Un flusso contiene $d$ valori distinti (con ripetizioni). Una funzione hash casuale manda ogni valore in un punto uniforme e indipendente di $(0,1)$ e l'algoritmo tiene i $k$ valori hash distinti più piccoli; con $v_k$ il $k$-esimo, la stima è $\hat d=\frac{k-1}{v_k}$.

1. Dimostrare che il minimo $V_1$ di $d$ punti uniformi ha $P(V_1>t)=(1-t)^d$ e $E[V_1]=\frac1{d+1}$. Verificare numericamente con $d=50$.
2. Con $d=3$ e $k=2$ dimostrare a mano che $E\bigl[\frac1{V_2}\bigr]=3=\frac d{k-1}$, cioè che $\hat d$ è non distorto.
3. Perché $k=1$ ($\hat d=\frac1{V_1}-1$) è una cattiva stima? Dare i quantili per $d=50$.
4. Quale $k$ garantisce uno scarto relativo $\approx5\%$? Quanta memoria serve rispetto a un insieme esatto di $10^5$ identificatori da $8$ byte?
5. Con $d=10^5$ stimare con una simulazione la probabilità di essere entro il $10\%$ e il $5\%$ del valore vero per $k=100$ e $k=402$.

Soluzione

1. Minimo. Il minimo supera $t$ se tutti i $d$ punti superano $t$: $P(V_1>t)=(1-t)^d$ per $t\in[0,1]$. Allora $$E[V_1]=\int_0^1P(V_1>t)\,dt=\int_0^1(1-t)^d\,dt=\frac1{d+1}.$$ Per $d=50$: $\frac1{51}=0{,}01961$; la simulazione ($200\,000$ prove) dà $0{,}01965$. Intuizione: $d$ punti dividono $(0,1)$ in $d+1$ intervalli, in media di lunghezza $\frac1{d+1}$, e il minimo è il primo.

2. Non distorsione per $d=3$, $k=2$. $V_2$ è il secondo più piccolo di $3$ punti. Densità: si sceglie quale dei $3$ punti sta in $v$ ($3$ modi), quale dei restanti $2$ sta sotto ($2$ modi) e l'altro sta sopra: $f(v)=3\cdot2\cdot v\,(1-v)=6v(1-v)$ (controllo: $\int_0^16v(1-v)dv=6(\frac12-\frac13)=1$). Quindi $$E\Bigl[\frac1{V_2}\Bigr]=\int_0^1\frac1v\,6v(1-v)\,dv=6\int_0^1(1-v)\,dv=3=\frac d{k-1},$$ e $E[\hat d]=(k-1)\cdot3=3=d$. Simulazione ($10^5$ prove): media di $1/V_2$ pari a $3{,}015$.

3. Il caso $k=1$. La densità di $V_1$ vicino a $0$ vale $d$, quindi $E[1/V_1]=\int\frac1vd(1-v)^{d-1}dv=\infty$: la media non esiste, la varianza non esiste, e una singola stima può essere enorme. Per $d=50$ i percentili $5\%$, $50\%$, $95\%$ di $\frac1{V_1}-1$ valgono $16{,}2$, $71{,}3$, $977{,}7$ (vero: $50$): l'errore va da un fattore $3$ in meno a un fattore $20$ in più. Con $k\ge3$ la media esiste e lo scarto relativo è circa $\frac1{\sqrt{k-2}}$.

4. Scelta di $k$. Si vuole $\frac1{\sqrt{k-2}}\le0{,}05\iff k-2\ge400$, cioè $\boxed{k=402}$. Memoria: $402$ valori hash da $8$ byte $=3216$ byte, indipendenti da $d$, contro $10^5\cdot8=800\,000$ byte per l'insieme esatto: $250$ volte meno. Per Chebyshev, con $k=\lceil2/\varepsilon^2\rceil+2$ lo scarto relativo è $\approx\varepsilon/\sqrt2$ e la stima è entro $\varepsilon d$ con probabilità $\ge\frac12$; per una confidenza più alta si usa la mediana di copie indipendenti.

5. Simulazione ($d=10^5$, $2000$ prove).

Gli scarti $0{,}1020$ e $0{,}0500$ coincidono con la formula ($0{,}1010$ e $0{,}0500$). Con $k=402$ la frazione entro $5\%$ è $\approx68\%$, il valore di una gaussiana a una deviazione standard: lo scarto relativo $\frac1{\sqrt{k-2}}$ è proprio la deviazione standard di $\hat d/d$, non un limite sul caso peggiore.

Codice di verifica

import numpy as np

rng = np.random.default_rng(13)

d = 50
minimi = rng.random((200_000, d)).min(axis=1)
print(minimi.mean(), 1 / (d + 1), np.percentile(1 / minimi - 1, [5, 50, 95]))

v2 = np.sort(rng.random((100_000, 3)), axis=1)[:, 1]      # secondo più piccolo di 3 punti
print((1 / v2).mean())                                     # vicino a 3

D = 10 ** 5
for k in (100, 402):
    stime = np.array([(k - 1) / np.partition(rng.random(D), k - 1)[k - 1] for _ in range(2000)])
    print(k, stime.mean(), stime.std() / D, np.mean(abs(stime - D) <= 0.1 * D), np.mean(abs(stime - D) <= 0.05 * D))

Risultato: 0.01965 0.01961 [16.2 71.3 977.7], poi 3.015, poi le due righe della tabella: 100 100221.9 0.1020 0.6835 0.369 e 402 99760.2 0.0500 0.956 0.6875.