Oggi voglio discutere di un problema molto interessante che ho trovato leggendo il post “A Discrete Approach to the Sum Over One Problem”, scritto dal fisico Matthew Lewis sul suo blog.
Si tratta di un problema che, come ho scoperto, è stato proposto anche come uno dei problemi della settimana da Harvard. La formulazione del problema è la seguente:
Si estrae un numero reale casuale, distribuito uniformemente nell’intervallo ([0,1]). Successivamente, si estraggono altri numeri casuali indipendenti, anch’essi uniformemente distribuiti tra 0 e 1, e li si somma progressivamente al totale accumulato. Il procedimento continua fino a quando la somma cumulativa supera il valore 1; a quel punto il gioco termina.
Da questa semplice regola emergono due domande naturali:
- In media, quanti numeri casuali è necessario estrarre affinché la somma superi 1?
- Al momento in cui il gioco si arresta, qual è il valore medio della somma totale ottenuta?
Clicca qui per la soluzione
Di seguito presento la soluzione nel continuo, visto che nel discreto ci ha già pensato Matthew. Questa soluzione è la stessa riportata nelle solutions di Harvard.
1. Numero medio di estrazioni per superare 1
Per determinare quanti numeri casuali è necessario estrarre, in media, affinché la loro somma superi 1, si sfrutta il seguente teorema:
Teorema: Dati $n$ numeri casuali indipendenti tra 0 e 1, la probabilità $P_n(s)$ che la loro somma non ecceda $s$ è $$ P_n(s) = \frac{s^n}{n!}, \quad \text{per tutti } s \le 1 $$
Questo teorema si dimostra utilizzando il principio di induzione:
- Per $n = 1$ e $s \le 1$ il risultato è banale: essendo uniforme la distribuzione, la probabilità che la somma (cioè il numero estratto) non superi $s$ coincide con $s$, come previsto dal teorema.
- Assumiamo ora che il teorema sia vero per un certo $n$.
- Verifichiamo che allora valga anche per $n+1$: $$ P_{n+1}(s) = \frac{s^{,n+1}}{(n+1)!} $$
Sia $x$ l’$(n+1)$-esimo numero estratto, tale che la somma totale non superi $s$ ($s \le 1$).
La probabilità che i primi $n$ numeri abbiano somma non superiore a $(s - x)$ sarà, per ipotesi induttiva:
$$
P_n(s-x) = \frac{(s-x)^n}{n!}
$$
Integrando questa probabilità su tutti i possibili valori di $x$ da $0$ a $s$, otteniamo: $$ P_{n+1}(s) = \int_0^s \frac{(s-x)^n}{n!} , dx = \frac{s^{,n+1}}{(n+1)!} $$
E così si conclude la dimostrazione del teorema.
Probabilità che occorrano esattamente $n$ estrazioni
La probabilità che esattamente $n$ estrazioni siano necessarie per superare 1 si calcola considerando:
La probabilità che in $(n-1)$ estrazioni non si superi 1: $$ P_{n-1}(1) = \frac{1}{(n-1)!} $$
La probabilità che con l’$n$-esima estrazione si superi 1, sottraendo la probabilità che la somma non superi 1 neanche con l’$n$-esima estrazione: $$ P_n(1) = \frac{1}{n!} $$
Pertanto, la probabilità totale è: $$ P_n = \frac{1}{(n-1)!} - \frac{1}{n!} $$
Valore medio del numero di estrazioni
Il valore medio $ \mathbb{E}[N] $ si calcola come:
$$ \mathbb{E}[N] = \sum_{n=2}^{\infty} n \left( \frac{1}{(n-1)!} - \frac{1}{n!} \right) $$
$$ = \sum_{n=2}^{\infty} n \left( \frac{n! - (n-1)!}{n! (n-1)!} \right) $$
$$ = \sum_{n=2}^{\infty} n \cdot \frac{n-1}{n!} $$
$$ = \sum_{n=2}^{\infty} \frac{n-1}{(n-1)!} $$
$$ = \sum_{n=2}^{\infty} \frac{1}{(n-2)!} $$
$$ = \sum_{n=0}^{\infty} \frac{1}{n!} = e $$
Quindi, il numero medio di estrazioni necessarie per superare 1 è $e \approx 2.718$.
Valore medio della somma finale
Per trovare il valore medio della somma $\overline{s}$ con cui si supera 1, osserviamo che il valore medio di una variabile uniforme su $[0,1]$ è $1/2$.
Pertanto, il valore medio della somma finale è:
$$
\overline{s} = \frac{1}{2} \cdot e = \frac{e}{2}
$$