Esercizio - Hoeffding per una somma di variabili con ampiezze diverse

Teoria: 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 → (teorema di Hoeffding) e 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 → (confronto con Chebyshev).

Testo. Un server riceve $100$ richieste indipendenti. Il tempo di servizio delle prime $60$ è uniforme su $[0,1]$ secondo, quello delle altre $40$ è uniforme su $[0,2]$ secondi. $S$ è il tempo totale.

1. Calcolare $E[S]$, $\mathrm{Var}(S)$ e la costante $c=\sum(b_i-a_i)^2$ di Hoeffding.
2. Limitare $P(S\ge E[S]+t)$ per $t=15,20,25$ con Hoeffding e con Chebyshev.
3. Da quale $t$ in poi Hoeffding è migliore? Quale $t$ garantisce probabilità $\le10^{-3}$ con Hoeffding?
4. Controllare con una simulazione. Si può usare Chernoff nella forma per variabili 0-1?

Soluzione

1. Momenti. Per $U\sim\mathrm{Unif}[0,\ell]$: media $\frac\ell2$, varianza $\frac{\ell^2}{12}$. $$E[S]=60\cdot\tfrac12+40\cdot1=70,\qquad\mathrm{Var}(S)=60\cdot\tfrac1{12}+40\cdot\tfrac4{12}=5+13{,}33=18{,}33\quad(\sigma=4{,}28).$$ Le ampiezze sono $b_i-a_i=1$ (60 volte) e $2$ (40 volte): $c=60\cdot1+40\cdot4=220$.

2. Limiti.

• Hoeffding: $P(S-70\ge t)\le e^{-2t^2/220}$.
• Chebyshev: $P(S-70\ge t)\le P(|S-70|\ge t)\le\frac{18{,}33}{t^2}$.

3. Incrocio. Hoeffding batte Chebyshev quando $e^{-2t^2/220}<\frac{18{,}33}{t^2}$, cioè per $t>17{,}65$ (circa $4{,}1\sigma$): oltre quella soglia l'esponenziale cala più in fretta di $1/t^2$. Per $t$ piccolo (pochi $\sigma$) Chebyshev è meglio, perché Hoeffding ignora la varianza vera e usa solo le ampiezze. Per la probabilità $10^{-3}$: $e^{-2t^2/220}\le10^{-3}\iff t\ge\sqrt{110\ln1000}=27{,}6$, quindi $t=28$: con probabilità $\ge99{,}9\%$ il tempo totale è sotto $98$ secondi.

4. Controllo. Su $4\times10^5$ simulazioni: media $69{,}996$, varianza $18{,}35$ (teoria $70$ e $18{,}33$ ✓); $P(S\ge85)$ osservata $1{,}8\times10^{-4}$, entro i limiti (a $t=25$ nessuna prova). I limiti restano molto larghi: l'esponente di Hoeffding è $\frac{2t^2}{c}=\frac{t^2}{6\mathrm{Var}}$, tre volte più piccolo dell'esponente gaussiano $\frac{t^2}{2\mathrm{Var}}$ (qui $c=12\,\mathrm{Var}$). La forma di Chernoff dimostrata nella nota vale per variabili in $\{0,1\}$ e qui non si applica direttamente: le variabili sono continue. Hoeffding invece ammette variabili limitate qualsiasi, anche con ampiezze diverse.

Risultato. $E[S]=70$, $\mathrm{Var}(S)=18{,}33$, $c=220$; $P(S\ge95)\le0{,}00341$ (Hoeffding) contro $0{,}0293$ (Chebyshev); soglia di incrocio $t=17{,}65$.

Verifica.

import math
import numpy as np

c = 60 * 1 + 40 * 4; mu = 60 * 0.5 + 40 * 1.0; var = 60 / 12 + 40 * 4 / 12
for t in (15, 20, 25):
    print(t, math.exp(-2 * t * t / c), var / t**2)
rng = np.random.default_rng(5)
S = rng.random((400000, 60)).sum(1) + (2 * rng.random((400000, 40))).sum(1)
print(S.mean(), S.var(), [(S - mu >= t).mean() for t in (15, 20, 25)])
print(math.sqrt(c * math.log(1000) / 2))                 # 27.6