Paradosso di Borel
# Paradosso di Borel

Nella teoria delle probabilità il paradosso di Borel afferma che è sempre possibile comporre una qualsiasi opera letteraria (ad esempio la Divina Commedia) digitando casualmente le lettere di una tastiera. Da qui deriva anche il nome di paradosso della scimmia in quanto si immagina che una scimmia possa scrivere un testo di senso compiuto digitando casualmente le lettere di una tastiera.

Il paradosso di Borel può essere modellato da una successione di variabili aleatorie che assumono, con una certa probabilità prefissata, i valori zero o uno. Se ipotizziamo che le lettere dell'alfabeto siano rappresentate tramite il sistema binario (ossia sequenze di zero e uno) è possibile scrivere ugualmente una qualsiasi opera letteraria. Il paradosso di Borel afferma che, data una sequenza di bit prefissata, la probabilità che si realizzi è uno e quindi è un evento quasi certo.

L'apparente paradosso viene chiarito calcolando il tempo medio di uscita di una stringa, che oltre ad essere estremamente lungo, cresce in base alla sequenza di caratteri ripetuti all'interno della stringa stessa.

## Enunciato

Sia ${\bigl\Omega ,{\mathcal {A}},P{\bigr )}$ uno spazio di probabilità. Si può definire una successione ${\biglX_{i}{\bigr )}_{i>0}$ di variabili aleatorie stocasticamente indipendenti e identicamente distribuite tali che per ogni $i>0$ si ha

    $X_{i}={\begin{cases}1,&{\mbox{con probabilità }}p,\\0,&{\mbox{con probabilità }}1-p,\end{cases}}$

con $p\in (0,1)$. Fissato un vettore di $h$ caratteri $S={\biglx_{1},x_{2},\ldots ,x_{h}{\bigr )}\in \{0,1\}^{h}$ si definisce $A_{n}=\{X_{n+1}=x_{1},X_{n+2}=x_{2},\ldots ,X_{n+h}=x_{h}\}$ l'evento che $(X_{n},X_{n+1},\ldots ,X_{n+h})=S$, ossia al tempo $n+h$ la stringa sia stata composta. Si dimostra che $P{\begin{Bmatrix}\bigcup _{n>0}A_{n}\end{Bmatrix}}=1$.

## Dimostrazione

Per ogni $i>0$ si può definire una partizione di eventi indipendenti tali che

    $B_{0}=\{X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{h}=x_{h}\}$
    $B_{1}=\{X_{h+1}=x_{1},X_{h+2}=x_{2},\ldots ,X_{2h}=x_{h}\}$
    $\ldots$
    $B_{i}=\{X_{ih+1}=x_{1},X_{ih+2}=x_{2},\ldots ,X_{(i+1)h}=x_{h}\}.$

Allo stesso modo si può definire una successione di variabili aleatorie ${\biglY_{i}{\bigr )}_{i>0}$ indipendenti tali che

    $Y_{0}=[X_{1},X_{2},\ldots ,X_{h}]$
    $Y_{1}=[X_{h+1},X_{h+2},\ldots ,X_{2h}]$
    $\ldots$
    $Y_{i}=[X_{ih+1},X_{ih+2},\ldots ,X_{(i+1)h}]$

${\biglY_{i}{\bigr )}_{i>0}$ è stocasticamente indipendente in quanto lo è anche ${\biglX_{i}{\bigr )}_{i>0}$ e $Y_{i}\cap Y_{j}=\varnothing ,$ per ogni $i,j>0$ con $i\neq j.$

Sia ${\biglZ_{i}{\bigr )}_{i>0}$ una successione di variabili aleatorie tali che $Z_{i}=\mathrm {I} _{B_{i}},$ per ogni $i>0,$ dove $\mathrm {I} _{B_{i}}$ è la funzione indicatrice di $B_{i}$. Dato che i $B_{i}$appartengono a una partizione di eventi indipendenti e gli $Z_{i}$ possono essere visti come $g\circ Y_{i}$, ne segue che ${\biglZ_{i}{\bigr )}_{i>0}$ è una successione di variabili aleatorie indipendenti.

### Osservazione 1

    $\bigcup _{i=0}^{\infty }B_{i}\subseteq \bigcup _{n=0}^{\infty }A_{n}.$

Considerando che l'unione degli eventi $B_{i}$ è sottoinsieme dell'unione degli eventi $A_{n}$, se si prova che $P{\begin{Bmatrix}\bigcup _{i=0}^{\infty }B_{i}\end{Bmatrix}}=1$, allora anche $P{\begin{Bmatrix}\bigcup _{n=0}^{\infty }A_{n}\end{Bmatrix}}=1.$

### Osservazione 2

    $P\{Z_{i}=1\}=P\{B_{i}\}.$

Considerando che $Z_{i}=\mathrm {I} _{B_{i}}$e la probabilità di una funzione indicatrice corrisponde alla probabilità dell'evento stesso, si può dire che $P\{Z_{i}=1\}=P\{B_{i}\}$. Analogamente $P\{Z_{i}=0\}$ equivale a calcolare la probabilità dell'evento complementare, ossia $P\{\neg B_{i}\}=1-P\{B_{i}\}$.

### Osservazione 3

    $P\{Z_{i}=1\}=p^{\sum _{i=1}^{h}x_{i}}(1-p)^{h-\sum _{i=1}^{h}x_{i}}.$

In base all'osservazione 2 si può dire che

    $P\{Z_{i}=1\}=P\{B_{i}\}.$

Dato che tutti i $B_{i}$ appartengono ad una partizione, per il criterio di indipendenza stocastica si può dire che

    $P\{B_{i}\}=P\{X_{ih+1}=x1,\ldots ,X_{(i+1)h=x_{h}}\}=P\{X_{ih+1}=x1\}\cdot \ldots \cdot P\{X_{(i+1)h}=x_{h}\}.$

Applicando l'enunciato si ha che

    $P\{X_{ih+1}=x1\}\cdot \ldots \cdot P\{X_{(i+1)h}=x_{h}\}=p^{\sum _{i=1}^{h}x_{i}}(1-p)^{h-\sum _{i=1}^{h}x_{i}}.$

Analogamente $P\{Z_{i}=0\}=1-P\{Z_{i}=1\}=1-p^{\sum _{i=1}^{h}x_{i}}(1-p)^{h-\sum _{i=1}^{h}x_{i}}.$

### Osservazione 4

    $\lim _{n\to \infty }P{\begin{Bmatrix}\bigcap _{i=0}^{n}Z_{i}=0\end{Bmatrix}}=0.$

Per l'indipendenza della successione ${\biglZ_{i}{\bigr )}_{i>0}$ si ha che $P{\begin{Bmatrix}\bigcap _{i=0}^{n}Z_{i}=0\end{Bmatrix}}=\prod _{i=0}^{n}P{\begin{Bmatrix}Z_{i}=0\end{Bmatrix}}.$

Per l'osservazione 3 si ha che $\prod _{I=0}^{n}P{\begin{Bmatrix}Z_{i}=0\end{Bmatrix}}={\biggl1-p^{\sum _{i=1}^{h}x_{i}}(1-p)^{h-\sum _{i=1}^{h}x_{i}}{\biggr )}^{n}.$

Passando al limite si ha che ${\biggl1-p^{\sum _{i=1}^{h}x_{i}}(1-p)^{h-\sum _{i=1}^{h}x_{i}}{\biggr )}^{n}\longrightarrow 0$, per $n\rightarrow \infty .$

Infatti, per $h$ fissato, $p^{\sum _{i=1}^{h}x_{i}}(1-p)^{h-\sum _{i=1}^{h}x_{i}}$può essere visto come una costante reale $0<c<1$ non dipendente da $n$. Pertanto $0<1-c<1\Longrightarrow (1-c)^{n}\rightarrow 0$ per $n\rightarrow \infty .$

### Osservazione 5

    $P{\begin{Bmatrix}\bigcap _{i=0}^{\infty }Z_{i}=0\end{Bmatrix}}=1-P{\begin{Bmatrix}\bigcup _{i=0}^{\infty }B_{i}\end{Bmatrix}}.$

Per le osservazioni 2 e 3 si ha che $P{\begin{Bmatrix}\bigcap _{i=0}^{\infty }Z_{i}=0\end{Bmatrix}}=P{\begin{Bmatrix}\bigcap _{i=0}^{\infty }\neg B_{i}\end{Bmatrix}}.$

Portando fuori l'operatore complementare si ha che $P{\begin{Bmatrix}\bigcap _{i=0}^{\infty }\neg B_{i}\end{Bmatrix}}=P{\begin{Bmatrix}\neg \bigcup _{i=0}^{\infty }B_{i}\end{Bmatrix}}=1-P{\begin{Bmatrix}\bigcup _{i=0}^{\infty }B_{i}\end{Bmatrix}}.$

### Conclusione

Per le osservazioni 4 e 5 si ha che $P{\begin{Bmatrix}\bigcap _{i=0}^{\infty }Z_{i}=0\end{Bmatrix}}=1-P{\begin{Bmatrix}\bigcup _{i=0}^{\infty }B_{i}\end{Bmatrix}}=0\Longrightarrow P{\begin{Bmatrix}\bigcup _{i=0}^{\infty }B_{i}\end{Bmatrix}}=1.$

Per l'osservazione 1 si può concludere e dimostrare la tesi, ossia $P{\begin{Bmatrix}\bigcup _{i=0}^{\infty }B_{i}\end{Bmatrix}}=1\Longrightarrow P{\begin{Bmatrix}\bigcup _{n=0}^{\infty }A_{n}\end{Bmatrix}}=1.$

