Esercizi e complementi

1. Il problema del collezionista.
Una popolazione contiene $n$ elementi distinti, tutti in ugual proporzione, (ad es. figurine per una collezione). Si fanno estrazioni con rimpiazzo. Un campione di dimensione $d$ in generale conterrà meno di $d$ elementi distinti a causa delle ripetizioni (i doppioni). Sia $V_t$ la var.al. ``numero di estrazioni necessarie per avere $t$ elementi distinti"; i valori possibili per $V_t$ sono $t, t+1,..$. Si vuole calcolare la media di $V_t$.
Soluzione.
Diciamo che un'estrazione ha successo se risulta nell'aggiunta di un nuovo elemento nel campione. Poniamo poi $X_k = V_{k+1} - V_k$ ; allora $(X_k - 1)$ è il numero di estrazioni con insuccesso tra il $k$-mo successo e il $(k+1)$-mo successo. Durante tutte queste estrazioni la popolazione contiene $(n-k)$ elementi che non sono entrati nel campione, per cui $(X_k - 1)$ è il numero di insuccessi che precedono il primo successo in prove ripetute di Bernoulli con $p = \frac{n-k}{n}$. $X_k$ prende il valore $s+1$ con probabilità $(1-p)^s p$ per cui, facendo i calcoli, si ottiene $E[X_k] = \frac{1}{p} = \frac{n-k}{n}$. Si noti ora che $V_t = 1 + X_1 +..+ X_{t-1}$, per cui

$$E[V_t] = n \,( \frac{1}{n} + \frac{1}{n-1} + ..+ \frac{1}{n-t... ...t+1/2}^{n+1/2} \frac{1}{x} dx = n \log \frac{n+1/2}{n-t+1/2}\,.$$

In particolare $E[V_n] \simeq n \log n$ e (assumendo $n$ pari) $E[V_{n/2}] \simeq n \log 2$. Si osservi come il numero atteso di prove per completare la collezione sia in generale assai più grande del doppio del numero atteso di prove per completare metà collezione.
2. Varianza di somme.
Supponiamo che $n$ var.al. $X_i$ abbiano varianza finita, allora per la varianza della loro somma si ha la formula generale

$$(*) \hspace{.4cm} {\rm Var} (X_1 + X_2 +..+ X_n) = \sum_i {\rm Var}(X_i) + \sum_{i \neq j} {\rm Cov}(X_i, X_j)\,.$$

3. Problema dei matches
Facciamo riferimento a 2 di 1.4 . Sia $S = S_N$ la var.al. ``numero di matches", si chiedono la media e la varianza di $S$.
Soluzione.
Sia $X_i$ la var.al. che vale 1 (con probab. $1/N$) se all'i-mo posto c'è match e 0 altrimenti. Abbiamo

$$E[X_i] = 1/N,\; S = \sum_{i=1}^N X_i ,\; E[S] = 1,\;{\rm Var}(X_i) = (N-1)/N^2 \,.$$

Calcoliamo le covarianze. Per $i \neq j$ la var.al $X_i X_j$ prende solo valori 0 e 1, quest'ultimo con prob. $\frac{1}{N (N-1)}$. Pertanto si ha

$${\rm Cov}(X_i, X_j) = E[X_i X_j] - E[X_i] E[X_j] = \frac{1}{N (N-1)} - \frac{1}{N^2}\,.$$

Applicando la formula (*) si ottiene

$${\rm Var}(S) = N \frac{N-1}{N^2} + N (N-1) \frac{1}{N^2(N-1)} = 1 \,.$$

4. Polinomi di Bernstein
Diamo ora una interessante applicazione dei metodi probabilistici alla teoria dell'approssimazione.
Sia $f$ una funzione reale continua su $[0,1]$, per $n \in {\bf N},\; x \in [0,1]$; l'$n$-mo polinomio di Bernstein della $f$ è definito da

$$B_n^f(x) = \sum_{k=0}^n f(\frac{k}{n}) {n\choose k} x^k (1-x)^{n-k}.$$

Faremo vedere che $B_n^f$ converge uniformemente a $f$; dando così una dimostrazione del teorema di Weierstrass: ``I polinomi sono densi nello spazio delle funzioni continue". Si ha

$$\vert B_n^f(x) - f(x)\vert = \vert\sum_{k=0}^n [f(\frac{k}{n})-f(x)] {n\choose k} x^k (1-x)^{n-k}\vert \leq$$

$$\leq \sum_{k=0}^n \vert f(\frac{k}{n})-f(x)\vert {n\choose k} x^k (1-x)^{n-k}$$

Poichè $f$ è uniformemente continua, fissato $\epsilon > 0$ esiste un $\delta > 0$ tale che: $\vert u-v\vert \leq \delta \Rightarrow \vert f(u)-f(v)\vert < \epsilon/2$; sia poi $\vert\vert f\vert\vert = M$. Si ha

$$\vert B_n^f(x) - f(x)\vert \leq \sum_{\vert\frac{k}{n}-x\vert... ...2M\sum_{\vert k-nx\vert> n \delta}{n\choose k} x^k (1-x)^{n-k}.$$

Se si interpreta $x$ come la probabilità parametro di una var.al. $S_n$ binomiale (avente media $\mu = n x$), allora l'ultima somma eguaglia

$$p\,\{\,\vert S_n -\mu \vert > n\delta \,\}\,.$$

Questa quantità, usando la disuguaglianza di Chebyshev, si maggiora con

$$\frac{{\rm Var}(S_n)}{n^2\delta^2} = \frac{nx(1-x)}{n^2\delta^2}\,.$$

Otteniamo dunque

$$\vert B_n^f(x) - f(x)\vert < \epsilon/2 + \frac{M}{2n\delta^2},$$

e quindi $\vert\vert B_n^f - f\vert\vert < \epsilon$ per $n$ sufficientemente grande.