Esercizio - Contatore di Morris - distribuzione esatta, varianza e numero di contatori

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 → (contatore di Morris), 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 → (Chebyshev).

Testo. Il contatore di Morris tiene un intero $X$, inizialmente $0$; a ogni evento incrementa $X$ con probabilità $2^{-X}$; la stima è $\tilde n=2^X-1$.

1. Calcolare la distribuzione esatta di $X$ dopo $n=3$ e $n=4$ eventi. Verificare $E[\tilde n]=n$ e $\text{Var}(\tilde n)=\frac{n(n-1)}2$.
2. Dimostrare entrambe le formule per ogni $n$.
3. Con $n=1000$ la deviazione standard è circa $707$. Quanti contatori indipendenti, mediati, servono perché l'errore relativo sia $\le10\%$ con probabilità $\ge90\%$ (Chebyshev)? Verificare con una simulazione.
4. Variante con base $1+a$: incremento con probabilità $(1+a)^{-X}$, stima $\frac{(1+a)^X-1}a$, $\text{Var}=\frac{a\,n(n-1)}2$. Che $a$ garantisce, con un solo contatore, errore $\le10\%$ con probabilità $\ge90\%$? Quanti bit servono per contare fino a $10^6$, contro il conteggio esatto?

Soluzione

1. Distribuzioni esatte. Se $X=x$ l'incremento ha probabilità $2^{-x}$. Dopo $1$ evento $X=1$ con probabilità $1$ (da $X=0$ si incrementa con probabilità $2^0=1$).

• $n=2$: da $X=1$: $X=2$ con $\frac12$, $X=1$ con $\frac12$.
• $n=3$: da $X=1$ (peso $\frac12$): sale a $2$ con $\frac12$ e resta con $\frac12$; da $X=2$ (peso $\frac12$): sale a $3$ con $\frac14$ e resta con $\frac34$. Quindi $P(X=1)=\frac14$, $P(X=2)=\frac14+\frac38=\frac58$, $P(X=3)=\frac18$. Stime $2^X-1=1,3,7$: $E=\frac14+\frac{15}8+\frac78=3$; $E[\tilde n^2]=\frac14+\frac{45}8+\frac{49}8=12$, $\text{Var}=12-9=3=\frac{3\cdot2}2$.
• $n=4$: $P(X=1)=\frac18$, $P(X=2)=\frac{19}{32}$, $P(X=3)=\frac{17}{64}$, $P(X=4)=\frac1{64}$ (si ottengono dalla distribuzione di $n=3$: $X=1$ resta con $\frac12$, $X=2$ viene da $\frac14\cdot\frac12+\frac58\cdot\frac34=\frac{19}{32}$, ecc.). Stime $1,3,7,15$: $E=\frac18+\frac{57}{32}+\frac{119}{64}+\frac{15}{64}=4$; $\text{Var}=\frac{n(n-1)}2=6$ (verificato con frazioni esatte per $n=1,\dots,30$).

2. Dimostrazione. Sia $Z_n=2^{X_n}$. Dato $X_n=x$: $$E[Z_{n+1}\mid X_n=x]=2^{x+1}\cdot2^{-x}+2^x(1-2^{-x})=2+2^x-1=Z_n+1,$$ $$E[Z_{n+1}^2\mid X_n=x]=4^{x+1}\cdot2^{-x}+4^x(1-2^{-x})=4\cdot2^x+4^x-2^x=Z_n^2+3Z_n.$$ Quindi $E[Z_{n+1}]=E[Z_n]+1$ e, con $Z_0=1$, $E[Z_n]=n+1$: $E[\tilde n]=n$. Inoltre $E[Z_{n+1}^2]=E[Z_n^2]+3(n+1)$, da cui $E[Z_n^2]=1+3\sum_{i=1}^ni=1+\frac{3n(n+1)}2$ e $\text{Var}(Z_n)=1+\frac{3n(n+1)}2-(n+1)^2=\frac{n^2-n}2$. Controllo con $n=3$: $1+18-16=3$ ✓.

3. Numero di contatori. La media di $s$ contatori indipendenti ha varianza $\frac{n(n-1)}{2s}$. Chebyshev: $$P(|\bar n-n|\ge0{,}1n)\le\frac{n(n-1)/(2s)}{0{,}01n^2}<\frac1{0{,}02s}\le0{,}1\iff s\ge\boxed{500}.$$ Simulazione ($n=1000$). Un solo contatore ($5000$ prove): media $989$, deviazione standard $679$ (teoria $707$; la media ha errore standard $\approx10$). Media di $500$ contatori ($100$ prove): media $1001{,}8$, deviazione standard $30{,}9$ (teoria $31{,}6$), e l'errore supera il $10\%$ in $1$ prova su $100$: ben sotto il $10\%$ massimo garantito da Chebyshev, che è un limite largo.

4. Base $1+a$. Per un solo contatore, Chebyshev: $P(|\tilde n-n|\ge\varepsilon n)\le\frac{a\,n(n-1)/2}{\varepsilon^2n^2}<\frac a{2\varepsilon^2}$. Si impone $\le\delta$: $a=2\varepsilon^2\delta=2\cdot0{,}01\cdot0{,}1=\boxed{0{,}002}$. Il contatore arriva a $X\approx\log_{1+a}(a\,n)$: per $n=10^6$, $\frac{\ln(0{,}002\cdot10^6)}{\ln1{,}002}=\frac{7{,}60}{0{,}001998}=3804$, cioè $\lceil\log_23804\rceil=12$ bit, contro $\lceil\log_210^6\rceil=20$ bit del conteggio esatto. Simulazione per $n=1000$, $a=0{,}002$ ($3000$ prove): media $1000{,}8$, deviazione standard $32{,}1$ (teoria $31{,}6$) e l'errore supera il $10\%$ nello $0{,}13\%$ dei casi. Con $a=1$ ($\varepsilon$ non controllato) servono $\log_2\log_2n$ bit: $\approx5$ bit per $n=10^9$, ma con deviazione standard $\approx0{,}7n$.

Codice di verifica

import random
from fractions import Fraction
from statistics import mean, pstdev

def distribuzione(n):
    d = {0: Fraction(1)}
    for _ in range(n):
        nuovo = {}
        for x, p in d.items():
            q = Fraction(1, 2 ** x)                           # probabilità di incremento
            nuovo[x + 1] = nuovo.get(x + 1, 0) + p * q
            nuovo[x] = nuovo.get(x, 0) + p * (1 - q)
        d = nuovo
    return d

for n in (3, 4):
    d = distribuzione(n)
    m = sum(p * (2 ** x - 1) for x, p in d.items())
    v = sum(p * (2 ** x - 1) ** 2 for x, p in d.items()) - m * m
    print(n, {x: str(p) for x, p in sorted(d.items()) if p}, m, v)

def morris(n, a=1.0):
    X = 0
    for _ in range(n):
        if random.random() < (1 + a) ** -X:
            X += 1
    return ((1 + a) ** X - 1) / a

random.seed(2)
uno = [morris(1000) for _ in range(5000)]
print(mean(uno), pstdev(uno))
m500 = [mean(morris(1000) for _ in range(500)) for _ in range(100)]
print(mean(m500), pstdev(m500), mean(abs(v - 1000) > 100 for v in m500))
v = [morris(1000, 0.002) for _ in range(3000)]
print(mean(v), pstdev(v), mean(abs(x - 1000) > 100 for x in v))

Risultato: per $n=3$ e $n=4$ le distribuzioni del punto 1 con media 3 e varianza 3, poi media 4 e varianza 6; poi tre righe di simulazione: 989.39 678.68 (un contatore), 1001.77 30.88 0.01 (media di $500$ contatori) e 1000.76 32.07 0.00133 (base $1{,}002$), cioè media, deviazione standard e frazione di errori oltre il $10\%$ citate nei punti 3 e 4.