Lancio di una moneta
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)
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)
Risposte
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:
e
Catena di Markov:
Entrambi dicono:
0.632571761339798
Ed ecco una simulazione:
Se la faccio andare per un po' dice 0.632qualcosa o 0.633qualcosa. Abbastanza vicino, direi.
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:
#!/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:
#!/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:
#!/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.
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?)
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?)
"jas123":
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.
"jas123":
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.
"jas123":
(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.
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}} \]
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}} \]
@ghira
Innanzitutto ti ringrazio per la risposta estremamente esaustiva.
è un problema che mi sono posto io quindi le tue risposte sono considerate più che corrette.
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.
Innanzitutto ti ringrazio per la risposta estremamente esaustiva.
"ghira":
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.
"ghira":
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.
@3m0o
Ok tutto abbastanza chiaro tranne una cosa, come fai a dire questo?
Ok tutto abbastanza chiaro tranne una cosa, come fai a dire questo?
"3m0o":
Che è la funzione generatrice della successione
\[ a_n = 2a_{n-1} - a_{n-10} \]
"jas123":
@ghira
ho studiato un po' le catene di Markov e da quello che ho capito in questo caso sarebbe una cosa del genere:
Sì.
"jas123":
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?
"jas123":[/quote]
@3m0o
Ok tutto abbastanza chiaro tranne una cosa, come fai a dire questo?
[quote="3m0o"]Che è la funzione generatrice della successione
\[ a_n = 2a_{n-1} - a_{n-10} \]
Perché lo sapevo.
"3m0o":
\[ 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} \]
\[ a_n = 2a_{n-1} - a_{n-11} \]
Oppure se vuoi capirlo a partire dalla serie. Dovrebbe esserci un metodo a partire direttamente dalla funzione generatrice, ma attualmente non lo trovo onestamente.
Però puoi sempre fare delle osservazioni e delle ipotesi, e poi cercare di dimostrare le tue ipotesi.
Ad esempio a partire da
\[ \sum_{k=0}^{\infty} (x+\ldots+x^{10})^k \]
è facile verificare che \(a_0=1\) e \(a_n=2^{n-1} \) con \( 1 \leq n \leq 10 \), basta osservare il triangolo di tartaglia che appare e sapere che la somma dell'\(n\)-esima riga del triangolo di tartaglia è appunto \(2^{n-1} \).
Ad esempio per ottenere il coefficiente di \(x^6 \) è somma dei coefficienti di \(x^6 \) presenti nelle espansioni \( (x+\ldots+x^{10})^k \) con \(1 \leq k \leq 6 \).
- Per il coefficiente di \(x^{11} \), lo ottieni come somma dei coefficienti di \(x^{11} \) presenti nelle espansioni \( (x+\ldots+x^{10})^k \) con \(2 \leq k \leq 11 \). E noti che sono i primi 10 termini della \(10\)-ima riga del triangolo di tartaglia ma l'ultimo \(1\) non è presente quindi ottieni \(a_{11} = 2^{10} - 1 = 2 \cdot a_{10} - a_{0} \)
- Per il coefficiente di \(x^{12} \), lo ottieni come somma dei coefficienti di \(x^{12} \) presenti nelle espansioni \( (x+\ldots+x^{10})^k \) con \(3 \leq k \leq 12 \). E noti che sono i primi 10 termini della \(11\)-ima riga del triangolo di tartaglia più un 9. Ma \(9 = 11 - 2 \) quindi diventa la somma dei primi 11 termini della \(11\)-ima riga triangolo di tartaglia meno l'ultimo 1. E quindi \(a_{12} = 2^{11} -2 - 1 = 2 \cdot (2^{10} - 1)- a_{1}= 2 a_{11} - a_{1} \)
- Per il coefficiente di \(x^{13} \), lo ottieni come somma dei coefficienti di \(x^{13} \) presenti nelle espansioni \( (x+\ldots+x^{10})^k \) con \(4 \leq k \leq 13 \). E noti che sono i primi 10 termini della \(12\)-ima riga del triangolo di tartaglia più un 63 e più un 8. Ma \(8 = 12 - 4 \) e \(63=66-3 \) quindi diventa la somma dei primi 12 termini della \(12\)-ima riga triangolo di tartaglia meno l'ultimo 1. E quindi \(a_{13} = 2^{12} -3- 4 - 1 = 2 \cdot (2^{11} - 3)- a_{2}= 2 a_{12} - a_{2} \)
Quindi ipotizzi che sia vero per ogni \(n > 10 \) e provi a dimostrarlo come sopra.
Oppure ancora dimostri che per ogni \( n > 10 \) è vero che
\[ a_{n} = \sum_{k=n-10}^{n-1} a_k \]
Abbiamo che il coefficiente \(a_{n} \) è presente in questa serie
\[ \sum_{k=0}^{\infty} (x+\ldots+x^{10})^k \]
ora siccome con \(n > 10 \) il termine \(k=0 \) non da alcuna contribuzione pertanto il coefficiente \(a_{n} \) in questa serie è il medesimo.
\[ \sum_{k=1}^{\infty} (x+\ldots+x^{10})^k \]
Mettendo in evidenza un \( (x+\ldots+x^{10}) \) otteniamo
\[ (x+\ldots+x^{10}) \cdot \sum_{k=1}^{\infty} (x+\ldots+x^{10})^{k-1}= (x+\ldots+x^{10}) \cdot \sum_{k=0}^{\infty} (x+\ldots+x^{10})^{k}\]
E quindi
\[ a_{n} = \sum_{k=n-10}^{n-1} a_k \]
Dopo di che ti basta osservare che
\[ a_{n} = \sum_{k=n-10}^{n-1} a_k = a_{n-1} + \sum_{k=n-10}^{n-2} a_k =a_{n-1} + \left( \sum_{k=n-11}^{n-2} a_k \right) - a_{n-11} = 2a_{n-1} - a_{n-11} \]
"ghira":
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?
ho un'idea ma i calcoli sono spaventosi:
ogni punto sulla scacchiera rappresenta una sotato: A1 è il primo, A2 il secondo e così via, la distribuzione iniziale di probabilità è (1,0,..,0) e la matrice stocastica sarà una 64x64 (quindi un bel casino).
Da qui con il metodo delle catene di Markov si calcola la probabilità che il cavallo si trovi in A1 al tempo k e poi non resta che calcolare il valore atteso di k, cosa che non so se si possa fare analiticamente, forse c'è bisogno per forza di un calcolatore.
Oppure un altro metodo potrebbe essere quello con la matrice di adiacenza: calcoli facilmente il numero di passeggiate chiuse da A1 in A1 di lunghezza k e altrettanto facilmente il numero totale di passeggiate possibili che partono da A1 di lunghezza k. Il rapporto tra queste due quantità dà la probabilità che il cavallo si trovi in A1al tempo k. In ogni caso resta il problema del calcolo del valore atteso.
Si fa in due righe. La seconda riga è "$=168$"! E la prima non è troppo orribile.
allora, l'idea può essere quella di cercare la distribuzione stazionaria, quindi un vettore che risolva l'equazione
$ v*Ms=v $ ($ Ms $ è la matrice stocastica definita come nei miei tentativi precedenti) e una volta risolto il sistema il primo elemento del vettore $ v $ elevato alla meno 1 ci darà il risultato cercato. Però i calcoli sono comunque più di una riga...
$ v*Ms=v $ ($ Ms $ è la matrice stocastica definita come nei miei tentativi precedenti) e una volta risolto il sistema il primo elemento del vettore $ v $ elevato alla meno 1 ci darà il risultato cercato. Però i calcoli sono comunque più di una riga...
"jas123":
allora, l'idea può essere quella di cercare la distribuzione stazionaria, quindi un vettore che risolva l'equazione
$ v*Ms=v $ ($ Ms $ è la matrice stocastica definita come nei miei tentativi precedenti) e una volta risolto il sistema il primo elemento del vettore $ v $ elevato alla meno 1 ci darà il risultato cercato. Però i calcoli sono comunque più di una riga...
In generale sì ma quando si tratta di un cammino casuale su un grafo, come in questo caso... tutte le connessioni fra le "caselle" sono bidirezionali e la probabilità di stare in un nodo particolare nel grafo nella distribuzione stazionaria è proporzionale al suo numero di uscite. (Lo so che qui sono stato molto sintetico. Ma è un caso importante che quasi sicuramente trovi discusso in più o meno qualsiasi libro/corso.)
Il tempo medio fra le visite è il reciproco della probabilità. Quindi per a1 e un cavallo, facciamo
$T=frac{4\times 2 + 8\times 3 + 20\times 4 + 16\times 6 + 16 \times 8}{2}=168$ se ho contato bene le caselle con i vari numeri di uscite.
Questo funziona per i pezzi degli scacchi (a parte il pedone) ma non, per esempio, per il generale d'oro o il generale d'argento nello shogi. (Le loro mosse sono tali che non è come muoversi su un grafo non-orientato.)
Fare un calcolo simile per il re, la torre, la donna o l'alfiere a questo punto è facilissimo. (Nel caso dell'alfiere ci sono solo 32 caselle raggiungibili, però.)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo