Teorema della scimmia instancabile

Secondo il teorema uno scimpanzé come questo, premendo i tasti della tastiera per un tempo sufficientemente lungo, arriverà quasi sicuramente a comporre qualsiasi opera conservata nella Biblioteca nazionale di Francia

Il teorema della scimmia instancabile o teorema delle scimmie infinite afferma che una scimmia che prema a caso i tasti di una tastiera per un tempo infinitamente lungo quasi certamente riuscirà a comporre qualsiasi testo prefissato. Come esempio i francofoni prendono i volumi della Biblioteca nazionale di Francia e gli anglosassoni le opere di William Shakespeare e, per quanto riguarda l'Italia, la Divina Commedia. Il teorema può essere considerato un caso particolare del secondo lemma di Borel-Cantelli.

Questa formulazione del problema è stata data da Émile Borel. La (o le) "scimmie" che battono a macchina rappresentano soltanto un meccanismo per produrre una sequenza infinita di caratteri casuali. Nella letteratura matematica il risultato è noto anche come paradosso di Borel.

Aspetti matematici

Data una tastiera di $m$ tasti e un testo da riprodurre di $k$ battute, la probabilità di non effettuarlo in $n$ tentativi (indipendenti) è $\left(1-{\frac {1}{m^{k}}}\right)^{n}$ e il limite $n\longrightarrow +\infty$ porta tutta l'espressione a $0$ perciò la probabilità di riprodurre un testo fissato se si prova all'infinito è $1$.

Per una trattazione rigorosa in termini probabilistici, si veda la dimostrazione formale riportata più sotto.

Richard Dawkins ha osservato, nel suo L'orologiaio cieco (1986, capitolo III), che al ritmo di una lettera al secondo il tempo trascorso dalla nascita dell'Universo ad oggi non sarebbe stato (quasi sicuramente) sufficiente alla scimmia per terminare il proprio lavoro. In particolare ha verificato, con un programma che genera casualmente lettere dell'alfabeto, che la probabilità per una scimmia di scrivere soltanto le prime 28 battute di una frase di Shakespeare è appena di $\left({\frac {1}{27}}\right)^{28}$, ossia 1 su 10.000 milioni di milioni di milioni di milioni di milioni di milioni. Per avere un riferimento basti pensare che le probabilità di vincere al SuperEnalotto sono di 1 su 622 milioni.

In caso di multiverso o di tempo infinito il teorema sarebbe invece una spiegazione adeguata per la perfezione delle leggi naturali adatte allo sviluppo della vita intelligente (principio antropico forte).

Paradosso di Borel: enunciato e dimostrazione formale

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 ${\bigl (}X_{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={\bigl (}x_{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 ${\bigl (}Y_{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}]$

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

Sia ${\bigl (}Z_{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 ${\bigl (}Z_{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 ${\bigl (}Z_{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}}={\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 ${\biggl (}1-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.$

Nella letteratura

L'idea di produrre tutti i possibili testi combinando casualmente le lettere dell'alfabeto è già presente ne I viaggi di Gulliver di Jonathan Swift, come uno dei progetti degli accademici di Lagado, nell'isola di Laputa. Jorge Luis Borges, nel saggio La Biblioteca Total (apparso sulla rivista Sur nel 1939), attribuisce questo "teorema" ad Huxley (non specifica però se Aldous o Thomas Henry), ed in seguito lo inserisce (senza però citarlo) all'interno della struttura del suo racconto La Biblioteca di Babele (1941, raccolto in Finzioni). Douglas Adams nella Guida galattica per gli autostoppisti fra gli eventi osservati da Arthur Dent durante la propulsione ad improbabilità infinita cita «un'incredibile moltitudine di scimmie che vogliono parlarci di una sceneggiatura dell'Amleto che avrebbero appena finito di scrivere».

Un altro testo più recente che si ispira ad una variante di questo "teorema" è il romanzo giallo An Infinite Number of Monkeys di Les Roberts.. Il caso è citato anche da Sciascia nel suo "Candido".

Nel fumetto Animal Man (n. 25 Gli enigmi della scimmia) di Grant Morrison è presente una scimmia che, dopo aver scritto a macchina le opere complete di William Shakespeare, sta scrivendo proprio la storia che stiamo leggendo e che permetterà al protagonista del fumetto stesso, Animal Man, di uscire dal limbo dei supereroi dimenticati.

Nella musica

La sonata in sol minore K. 30 di Domenico Scarlatti è conosciuta come Fuga del gatto in quanto caratterizzata da un insolito intervallo di note tale per cui nel XIX secolo nacque l'aneddoto che il tema musicale fosse stato ispirato dalle note suonate casualmente sulla tastiera dal gatto del compositore napoletano.

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.

Voci correlate

• I nove miliardi di nomi di Dio

Altri progetti

Altri progetti

• Wikiquote

• Wikiquote contiene citazioni sulla teorema della scimmia instancabile

Collegamenti esterni

• Una bibliografia con citazioni, su angelfire.com.