Lancio di una moneta

[jas123]

Salve a tutti.
C'è un quesito, all'apparenza piuttosto semplice, che mi sta dando qualche problema:
qual è la probabilità di fare almeno 10 teste consecutive lanciando una moneta 2048 volte?

Vi ringrazio in anticipo (qui sotto metto in spoiler il mio approccio, che purtroppo credo sia infruttuoso)

Testo nascosto, fai click qui per vederlo

ho immaginato di scrivere la serie di 2048 teste e croci come una parola di 2048 lettere T e C, in tutto esistono $ 2^2048 $ parole di questo tipo, poi ho immaginato di prendere un "blocco" di 10 T e far variare tutte le altre ottenendo $ 2^2038 $ possibili parole, poi però il gruppo di 10 T può cambiare posizione in 2039 punti e quindi ottengo $ 2039*2^2038 $ possibili parole. Tuttavia questo risultato è sbagliato perché ci sono delle ovvie ripetizioni e non so come "aggiustare il tiro".

[ghira]

Che tipo di soluzione stai cercando?

Puoi farlo numericamente con una catena di Markov. Gli stati sono i numeri da $0$ a $10$ per il numero di teste consecutive. Cominci nello stato $0$ con probabilità 1. Ad ogni lancio passi dallo stato $i$ allo stato $i+1$ o allo stato $0$, tranne nel caso $i=10$ dove passi sempre allo stato $10$.

O potresti definire $f(n)$ la probabilità di vedere almeno 10 teste in $n$ lanci.

$f(n)=0$ per $n<10$, ovviamente. $f(10)=\frac{1}{2^{10}}$.

Per $n>10$, $f(n)=f(n-1)+(1-f(n-11))\frac{1}{2^{11}}$ e scrivi un programma per calcolare $f(2048)$.

Magari ci sono modi migliori o più furbi.

Ecco due programmi per farlo nei due modi che ho indicato:

Formula ricorsiva:

Codice:

#!/usr/bin/perl

for $i (0..2048) {
   if ($i<10) {
      $f[$i]=0;
      } elsif ($i==10) {
         $f[$i]=1/1024;
         } else {
            $f[$i]=$f[$i-1]+(1-$f[$i-11])/2048;
         }
      }   
   
print $f[2048]."\n";

e

Catena di Markov:

Codice:

#!/usr/bin/perl

$p[0][0]=1;
$old=0;
$new=1;

for (1..2048) {
   $p[0][$new]=0;
      for $i (1..9) {
         $p[$i][$new]=$p[$i-1][$old]/2;
         }
      for $i (0..9) {
         $p[0][$new]+=$p[$i][$old]/2;
         }
      $p[10][$new]=$p[10][$old]+$p[9][$old]/2;
   $old=1-$old;
   $new=1-$old;
   }

print $p[10][$old]."\n";

Entrambi dicono:

0.632571761339798

Ed ecco una simulazione:

Codice:

#!/usr/bin/perl

$n=0;
$s=0;


while (1) {
   $t=0;
   for (1..2048) {
      if (rand()<0.5) {
      $t++;
                if ($t>=10) {
                last;
                }
      } else {
      $t=0;
      }
   }
   if ($t>=10) {
   $s++;
   }
   $n++;
   $p=$s/$n;
   print "$p \n";
   }


Se la faccio andare per un po' dice 0.632qualcosa o 0.633qualcosa. Abbastanza vicino, direi.

[jas123]

Non so che sia una catena di Markov, ma mi piacerebbe qualche spiegazione in più, sono curioso.
Come hai fatto ad ottenere quella forma ricorsiva?
In ogni caso vado a cercare qualcosa sulla catena di Markov perché mi hai incuriosito.
(Comunque io non so assolutamente nulla di programmazione, quindi non saprei nemmeno dove runnare i tuoi programmi, però mi piacerebbe imparare, sai da dove potrei cominciare?)

[ghira]

Non so che sia una catena di Markov, ma mi piacerebbe qualche spiegazione in più, sono curioso.

Le catene di Markov si trovano in molti libri/corsi sulla probabilità. Potrebbero essere la mia cosa preferita in tutta la matematica.

In realtà il programma per la catena di Markov non dovrebbe fare 2048 iterazioni. Se lo fai con la matrice di transizione, la elevi al quadrato ripetutamente ottenendo il risultato di 2048 iterazioni della catena con 11 moltiplicazioni.

Come hai fatto ad ottenere quella forma ricorsiva?

I valori di $f(n)$ per $n$ da $0$ a $10$ sono abbastanza chiari, spero.

Se $n$ è maggiore di 10...

Dopo $n-1$ lanci o avevi o non avevi già visto 10 teste di fila. Quindi..

$f(n)=f(n-1)+\Pr(\text{10 teste di fila per la prima volta al lancio }n)$

Per vedere 10 teste di fila per la prima volta al lancio $n$ devi avere $n-11$ lanci senza 10 teste di fila, che
succede con probabilità $1-f(n-11)$, poi una croce, poi 10 teste.

(Comunque io non so assolutamente nulla di programmazione, quindi non saprei nemmeno dove runnare i tuoi programmi, però mi piacerebbe imparare, sai da dove potrei cominciare?)

I miei programmi sono in Perl. Se hai Linux (o un altro Unix) o Macos, dovresti già averlo. https://www.perl.org/get.html dice dove trovarlo per Windows. Anche il mio Amiga ha il Perl.

Non ti sto necessariamente dicendo di imparare il Perl. Io lo uso per fare quasi tutto, ma il Python sembra molto popolare. Non credo che sia molto utile per me passare dal Perl al Python adesso.

Credo di aver usato https://it.wikipedia.org/wiki/Learning_Perl per imparare il Perl. La stessa casa editrice pubblica libri anche su altri linguaggi. Ormai ci sarà tanta roba anche sul web.

Se vuoi imparare a programmare magari ti conviene provare alcuni linguaggi per vedere come ti sembrano. I veri programmatori diranno che non importa che linguaggio usi. Magari hanno ragione. Ma trovo il C e il Java incomprensibili. Ho guardato il Python brevemente e non mi è venuta alcuna voglia di insistere. Col Perl mi trovo bene. Non mi dispiaceva il REXX (https://it.wikipedia.org/wiki/REXX ) ma siamo nel 2020.

In quale contesto hai trovato questo "quesito"? Se è una cosa che devi fare con carta / penna / calcolatrice durante un esame, chiaramente nessuna delle mie risposte è quella prevista. Se è un compito da fare a casa, le mie risposte mi sembrano almeno plausibili. Se io volessi sapere la risposta a quella domanda userei uno di quei programmi. E magari userei la simulazione come controllo. Ovviamente potrei aver commesso lo stesso errore più volte.

[3m0o]

Ti do un metodo alternativo. Procediamo con la probabilità dell'evento complementare. Allora cerchiamo di contare tutte le sequenze di lanci che non vanno bene. Ovvero che non contengono nessuna successione di 10 teste consecutive.
D'ora in poi denoto \(T\)=testa e \(C\)=croce. Nota che aggiungendo una croce alla fine per avere una parola di \(2049\) lettere che possono essere o \(T\) o \(C\) che termina con \(C\) allora possiamo sempre suddividere la nostra parola in blocchi formati da una di queste possibilità
1) \(C=x\)
2) \(TC=x^2\)
3) \(TTC=x^3\)
4) \(TTTC=x^4\)
\(\vdots\)
9) \(TTTTTTTTC=x^9\)
10) \(TTTTTTTTTC=x^{10}\)
Ad esempio con una sequenza più piccola di 15 lettere, ad esempio: \( CTCCTTCTTTCTCTT \), aggiungiamo una \(C\) finale per ottenere una parola di 16 lettere: \( CTCCTTCTTTCTCTTC \) e otteniamo dunque i blocchi
\( C\) // \( TC \) // \(C \) // \(TTC \) // \(TTTC \) // \( TC \) // \( TTC \)
Se li sostituiamo con le "\(x\)" corrispondenti otteniamo la moltiplicazione
\( x \cdot x^2 \cdot x \cdot x^3 \cdot x^4 \cdot x^2 \cdot x^3 = x^{16} \)

Nota che l'esponente della \(x\) corrisponde esattamente alla lunghezza della nostra sequenza, sempre! Perché aggiungere una \(C\) finale? Beh perché come nel nostro esempio la nostra sequenza potrebbe terminare con \(T\) e quindi in questo caso non saremmo in grado di dividere in blocchi come sopra la nostra sequenza.

Nota ora che tutte le parole che non contengono 10 \(T\) consecutive sono formate da una possibile combinazione di questi blocchi pertanto per trovare il numero totale di combinazioni possibili (quindi il modo di combinare questi blocchi) basta trovare il coefficiente di \( x^{2049} \) nel seguente polinomio
\[ P(x) = \sum_{n=0}^{\infty} (x+x^2+x^3+x^4+x^5+x^6+x^7+x^8 +x^9 +x^{10} )^k \]
Abbiamo che
\[ (x+x^2+x^3+x^4+x^5+x^6+x^7+x^8 +x^9 +x^{10} ) = \frac{1-x^{11}}{1-x} -1 = \frac{x(1-x^{10})}{1-x} \]
pertanto abbiamo che
\[ P(x)= \sum_{n=0}^{\infty} \left( \frac{x(1-x^{10})}{1-x} \right)^k = \frac{1}{1- \left(\frac{x(1-x^{10})}{1-x}\right)} = \frac{1-x}{x^{10} - 2x +1} \]
Che è la funzione generatrice della successione
\[ a_n = 2a_{n-1} - a_{n-10} \]
dove \( a_0=1 \) e \( a_k = 2^{k-1}\) con \( 1\leq k \leq 10 \).
Pertanto
\[ P(x)= \sum_{n=0}^{\infty} a_n x^n \]
e abbiamo che la probabilità che nessuna sequenza di 10 teste consecutive sia presente è data da
\[ \frac{a_{2049}}{2^{2048}} \]
pertanto la probabilità da te cercata è
\[ 1 - \frac{a_{2049}}{2^{2048}} \]

[jas123]

@ghira
Innanzitutto ti ringrazio per la risposta estremamente esaustiva.

In quale contesto hai trovato questo "quesito"? Se è una cosa che devi fare con carta / penna / calcolatrice durante un esame, chiaramente nessuna delle mie risposte è quella prevista.

è un problema che mi sono posto io quindi le tue risposte sono considerate più che corrette.

Le catene di Markov si trovano in molti libri/corsi sulla probabilità. Potrebbero essere la mia cosa preferita in tutta la matematica.

In realtà il programma per la catena di Markov non dovrebbe fare 2048 iterazioni. Se lo fai con la matrice di transizione, la elevi al quadrato ripetutamente ottenendo il risultato di 2048 iterazioni della catena con 11 moltiplicazioni.

ho studiato un po' le catene di Markov e da quello che ho capito in questo caso sarebbe una cosa del genere:
il vettore di distribuzione di probabilità nel caso richiesto sarebbe uguale al prodotto tra un vettore riga composto da un 1 e tutti 0 e la potenza 2048-esima della matrice stocastica di questo tipo :





da qui si può jordanizzare, ma si tratta di fare veramente una miriade di calcoli quindi alla fine probabilmente conviene fare come dici tu, cioè elevare al quadrato 11 volte, certo è che jordanizzando avremmo una formula generale.

devo dire che questo metodo è veramente interessante e versatile.

Poi in realtà anche dalla formula ricorsiva che hai scritto si potrebbe ricavare una formula generale, ma ci sarebbero da svolgere anche lì una miriade di calcoli.

[jas123]

@3m0o
Ok tutto abbastanza chiaro tranne una cosa, come fai a dire questo?

Che è la funzione generatrice della successione
\[ a_n = 2a_{n-1} - a_{n-10} \]

[ghira]

@ghira
ho studiato un po' le catene di Markov e da quello che ho capito in questo caso sarebbe una cosa del genere:

Sì.

devo dire che questo metodo è veramente interessante e versatile.

Trasformano molti problemi apparentemente interessanti e/o difficili in esercizi meccanici noiosi!

Per esempio, se un cavallo degli scacchi si muove a caso sulla scacchiera (sceglie una mossa a caso fra quelle disponibili ogni volta) e si trova adesso sulla casella a1, mediamente fra quante mosse sarà di nuovo su a1?

[3m0o]

@3m0o
Ok tutto abbastanza chiaro tranne una cosa, come fai a dire questo?

Che è la funzione generatrice della successione
\[ a_n = 2a_{n-1} - a_{n-10} \]

Perché lo sapevo.

\[ P(x)= \sum_{n=0}^{\infty} \left( \frac{x(1-x^{10})}{1-x} \right)^k = \frac{1}{1- \left(\frac{x(1-x^{10})}{1-x}\right)} = \frac{1-x}{x^{10} - 2x +1} \]
Che è la funzione generatrice della successione
\[ a_n = 2a_{n-1} - a_{n-10} \]
dove \( a_0=1 \) e \( a_k = 2^{k-1} \) con \( 1\leq k \leq 10 \).

Secondariamente ho fatto un typo
\( P(x)= \frac{1-x}{x^{11} - 2x +1} \)
quindi con \(n > 10 \)
\[ a_n = 2a_{n-1} - a_{n-11} \]
dove \( a_0=1 \) e \( a_k = 2^{k-1} \) con \( 1\leq k \leq 10 \).

Comunque puoi dimostrarlo chiamiamo \( a_n = 2a_{n-1} - a_{n-11} \) per \(n > 10 \) e \( a_0 = 1 \) e \( a_k = 2^{k-1} \) per \( 1 \leq k \leq 10 \), chiamiamo \(s\) la funzione generatrice di \((a_n)_{n \in \mathbb{N}} \), abbiamo allora che
\[ s(x) = \sum_{n=0}^{\infty} a_n x^n \]
\[ 2x s(x) = \sum_{n=1}^{\infty} 2a_{n-1} x^n \]
\[ x^{11} s(x) = \sum_{n=11}^{\infty} a_{n-11} x^n \]

Otteniamo dunque
\[ s(x) (1-2x+x^{11} ) = a_0 + \sum_{n=1}^{10} (a_n - 2a_{n-1})x^n + \sum_{n=1}^{10} (a_n - 2a_{n-1} + a_{n-11})x^n \]
usando le relazioni della successioni abbiamo dunque
\[ s(x) (1-2x+x^{11} )=1 + (a_1 - 2 a_0) x + \sum_{n=2}^{10} \underbrace{(a_n - 2a_{n-1})}_{=0}x^n + \sum_{n=11}^{\infty} \underbrace{(a_n - 2a_{n-1} + a_{n-11})}_{=0}x^n \]
dunque
\[ s(x) = \frac{1-x}{x^{11}-2x+1} \]

[Bokonon]

Nel caso possa interessare: https://www.maa.org/sites/default/files ... p0021g.pdf