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 ${\displaystyle {\bigl (}\Omega ,{\mathcal {A}},P{\bigr )}}$ uno spazio di probabilità. Si può definire una successione ${\displaystyle {\bigl (}X_{i}{\bigr )}_{i>0}}$ di variabili aleatorie stocasticamente indipendenti e identicamente distribuite tali che per ogni ${\displaystyle i>0}$ si ha

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

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

Dimostrazione

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

${\displaystyle B_{0}=\{X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{h}=x_{h}\}}$

${\displaystyle B_{1}=\{X_{h+1}=x_{1},X_{h+2}=x_{2},\ldots ,X_{2h}=x_{h}\}}$

${\displaystyle \ldots }$

${\displaystyle 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 ${\displaystyle {\bigl (}Y_{i}{\bigr )}_{i>0}}$ indipendenti tali che

${\displaystyle Y_{0}=[X_{1},X_{2},\ldots ,X_{h}]}$

${\displaystyle Y_{1}=[X_{h+1},X_{h+2},\ldots ,X_{2h}]}$

${\displaystyle \ldots }$

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

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

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

Osservazione 1

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

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

Osservazione 2

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

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

Osservazione 3

${\displaystyle 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

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

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

${\displaystyle 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

${\displaystyle 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 ${\displaystyle 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

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

Per l'indipendenza della successione ${\displaystyle {\bigl (}Z_{i}{\bigr )}_{i>0}}$ si ha che ${\displaystyle 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 ${\displaystyle \prod _{I=0}^{n}P{\begin{Bmatrix}Z_{i}=0\end{Bmatrix}}={\biggl (}1-p^{\sum _{i=1}^{h}x_{i}}(1-p)^{h-\sum _{i=1}^{h}x_{i}}{\biggr )}^{n}.}$

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

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

Osservazione 5

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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.}$

Bibliografia

• Paolo Baldi, Calcolo delle Probabilità e Statistica - Seconda Edizione, Milano, McGraw-Hill, 1998, ISBN 88-386-0737-0.
• Paolo Baldi, Calcolo delle Probabilità, Milano, McGraw-Hill, 2007, ISBN 978-88-386-6365-9.
• Francesca Biagini, Massimo Campanino, Elementi di Probabilità e Statistica, Milano, Springer, 2006, ISBN 88-470-0330-X.

Collegamenti esterni

• Borel, paradosso di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.