Re Artù e i dadi...
Propongo un quesito che mi ha subito affascinato sin dal primo istante, ma di cui non sono ahimé mai riuscito a ricavarci nulla.
Spero nel vostro aiuto.
Re Artù siede alla tavola rotonda con $N-1$ cavalieri. Essi giocano al seguente gioco:
Il re ha un dado e lo tira. Se esce:
1 o 2, allora il re deve passare il dado al cavaliere alla sua destra,
3 o 4, allora il re deve passare il dado al cavaliere alla sua sinistra,
5 o 6, allora il gioco si ferma.
Quando il cavaliere alla destra (o sinistra) del re riceve il dado, ripete la stessa identica cosa, e così via finché il gioco non si ferma.
Le due domande sono:
1) Qual è la probabilità che, una volta che il gioco si è fermato, il re abbia il dado?
2) Qual è il limite per $N \to infty$ di tale probabilità?
È bello tosto...
Spero nel vostro aiuto.
Re Artù siede alla tavola rotonda con $N-1$ cavalieri. Essi giocano al seguente gioco:
Il re ha un dado e lo tira. Se esce:
1 o 2, allora il re deve passare il dado al cavaliere alla sua destra,
3 o 4, allora il re deve passare il dado al cavaliere alla sua sinistra,
5 o 6, allora il gioco si ferma.
Quando il cavaliere alla destra (o sinistra) del re riceve il dado, ripete la stessa identica cosa, e così via finché il gioco non si ferma.
Le due domande sono:
1) Qual è la probabilità che, una volta che il gioco si è fermato, il re abbia il dado?
2) Qual è il limite per $N \to infty$ di tale probabilità?
È bello tosto...
Risposte
in una maniera piuttosto brutale, che tiene conto della ripetitività del gioco ma non della particolarità degli ultimi passaggi nell'ipotesi che si possa completare il giro, io ho ottenuto come risultato che non mi convince (dovrebbe essere forse la risposta al secondo quesito, anche se l'impostazione riguarda il primo...)
P=9/13
se conosci quale dovrebbe essere il risultato, faccelo sapere. in ogni caso, visto che ti ha tanto intrigato, dicci qual è stata la tua impostazione e dove hai incontrato difficoltà o che cosa ti ha fatto pensare che il procedimento non fosse corretto.
ciao.
P=9/13
se conosci quale dovrebbe essere il risultato, faccelo sapere. in ogni caso, visto che ti ha tanto intrigato, dicci qual è stata la tua impostazione e dove hai incontrato difficoltà o che cosa ti ha fatto pensare che il procedimento non fosse corretto.
ciao.
Dal testo del problema mi sembra una catena di Markov
Rispondo prima al secondo punto che mi sembra più immediato, se non mi sbaglio (dato che sono un po' arrugginito 
), la matrice di transizione della catena è bistocastica (cioè la somma delle probabilità sulle righe e colonne è 1) quindi la probabilità invariante è $1/(N-1)$, la catena poi è ergodica quindi anche la probabilità per $N \to \infty$ è $1/(N-1)$.
Per il primo punto ora provo a vedere
), la matrice di transizione della catena è bistocastica (cioè la somma delle probabilità sulle righe e colonne è 1) quindi la probabilità invariante è $1/(N-1)$, la catena poi è ergodica quindi anche la probabilità per $N \to \infty$ è $1/(N-1)$.Per il primo punto ora provo a vedere
la probabilità non può essere inferiore ad 1/3
però, confrontando quanto scritto da Sergio e da frodo4, sembrerebbero risultati simili (va solo aggiunto +1/3 alla formula di frodo4 ...)
dal calcolo diretto, ho ottenuto,
nei casi particolari di n=2 ed n=3 rispettivamente vengono fuori due serie geometriche, e rispettivamente le probabilità di 3/5 e 2/3 ...
questi risultati non confortano né il mio primo calcolo su cui io stessa avevo delle riserve, né il risultato di Sergio.
frodo4, provi a schematizzare la catena di Markov?
ciao.
però, confrontando quanto scritto da Sergio e da frodo4, sembrerebbero risultati simili (va solo aggiunto +1/3 alla formula di frodo4 ...)
dal calcolo diretto, ho ottenuto,
nei casi particolari di n=2 ed n=3 rispettivamente vengono fuori due serie geometriche, e rispettivamente le probabilità di 3/5 e 2/3 ...
questi risultati non confortano né il mio primo calcolo su cui io stessa avevo delle riserve, né il risultato di Sergio.
frodo4, provi a schematizzare la catena di Markov?
ciao.
No ragazzi, sono sicuro che il procedimento è molto più difficile di quello che sembri.
Io ero riuscito a risolvere la seconda parte del problema, quella per $N \to infty$, infatti era molto più semplice in quanto si evitavano i casi in cui il dado faceva "giri" completi ritornando al re (siamo in una tavola rotonda!). Infatti per $N to infty$ la tavola "non è più rotonda", ma è una catena infinita di cavalieri alla destra, rispettivamente sinistra del re.
Io non ho ancora fatto le catene di Markov, quindi non capisco mi spiace.
Risolviamo il caso per passi:
1) Il re ha 1/3 di probabilità di fermare il gioco al primo turno. Da qui è ovvio che la probabilità è maggiore di 1/3.
2) Al secondo turno, se il re passa il dado al cavaliere di destra, abbiamo che il cavaliere deve beccare 3 o 4 (per ripassarlo al re) e quindi prob. 1/3.
3) Al terzo turno, il re dovrebbe lanciare e ottenere 5 o 6 per fermare il gioco.
Quindi, in tre turni la probabilità è: $1/3 + 2*(1/3)^3$
Generalizzando si osserva che (prendiamo il primo turno come turno 0):
1) Ai turni dispari il re non può avere il dado.
2) Si può considerare soltanto un "lato" (cioè il fatto che il primo turno si vada a destra o a sinistra), poiché il gioco è totalmente simmetrico quindi si moltiplica per 2.
3) Se vista come una passeggiata aleatoria (spero sapete tutti cos'è), il problema può essere visto come:
- probabilità 1/3 in su,
- 1/3 in giù,
- 1/3 si ferma.
Noi vogliamo calcolare la probabilità dell'unione di tutte le $S_n$, la variabile aleatoria che indica "il livello a cui ci si trova", tali per cui $S_n = 0$, per la probabilità che in quel livello il gioco si fermi, quindi $1/3$ (eccetto al turno 0).
Cioè:
$1/3+ 1/3*P[ bigcup_{n=1}^{infty} \{S_n=0\}]$
Cioè, visto che abbiamo la $sigma$-additività di $P$:
$1/3 + 1/3*sum_{n=1}^{infty} P[S_n=0]$
Il problema è adesso calcolare $P[S_n = 0]$ per tutte le $n$.
Dal punto 1): $P[S_(2n-1)=0] = 0$, quindi il problema si riduce nel calcolare $P[S_(2n) = 0]$, cioè $P[S_2=0]$, ...
$S_n$ è la somma di tutte le variabili aleatorie che indicano al $k$-esimo passo cosa succede, per $k=1,..., n$. Cioè:
$S_n = sum_{k=1}^n X_k$,
$X_k$ è il k-esimo passo, o fermata.
Quindi $P[S_n = 0] = P[sum_{k=1}^n X_k=0]$.
Quindi:
$P[S_(2n)=0] = ((2n),(n)) (1/3)^(2n)$,
ovvero i modi possibili di ritornare in $0$ dopo $2n$ passaggi per la probabilità di questi.
Vedi wiki:
http://it.wikipedia.org/wiki/Passeggiata_aleatoria
In definitiva la probabilità è:
$1/3 + 1/3*sum_{n=1}^{infty} ((2n),(n)) (1/3)^(2n)$
Che se non sbaglio è poco meno di 0.5...
Adesso, il punto più difficile mi sembra l'1...che non riesco a fare..
Io ero riuscito a risolvere la seconda parte del problema, quella per $N \to infty$, infatti era molto più semplice in quanto si evitavano i casi in cui il dado faceva "giri" completi ritornando al re (siamo in una tavola rotonda!). Infatti per $N to infty$ la tavola "non è più rotonda", ma è una catena infinita di cavalieri alla destra, rispettivamente sinistra del re.
Io non ho ancora fatto le catene di Markov, quindi non capisco mi spiace.
Risolviamo il caso per passi:
1) Il re ha 1/3 di probabilità di fermare il gioco al primo turno. Da qui è ovvio che la probabilità è maggiore di 1/3.
2) Al secondo turno, se il re passa il dado al cavaliere di destra, abbiamo che il cavaliere deve beccare 3 o 4 (per ripassarlo al re) e quindi prob. 1/3.
3) Al terzo turno, il re dovrebbe lanciare e ottenere 5 o 6 per fermare il gioco.
Quindi, in tre turni la probabilità è: $1/3 + 2*(1/3)^3$
Generalizzando si osserva che (prendiamo il primo turno come turno 0):
1) Ai turni dispari il re non può avere il dado.
2) Si può considerare soltanto un "lato" (cioè il fatto che il primo turno si vada a destra o a sinistra), poiché il gioco è totalmente simmetrico quindi si moltiplica per 2.
3) Se vista come una passeggiata aleatoria (spero sapete tutti cos'è), il problema può essere visto come:
- probabilità 1/3 in su,
- 1/3 in giù,
- 1/3 si ferma.
Noi vogliamo calcolare la probabilità dell'unione di tutte le $S_n$, la variabile aleatoria che indica "il livello a cui ci si trova", tali per cui $S_n = 0$, per la probabilità che in quel livello il gioco si fermi, quindi $1/3$ (eccetto al turno 0).
Cioè:
$1/3+ 1/3*P[ bigcup_{n=1}^{infty} \{S_n=0\}]$
Cioè, visto che abbiamo la $sigma$-additività di $P$:
$1/3 + 1/3*sum_{n=1}^{infty} P[S_n=0]$
Il problema è adesso calcolare $P[S_n = 0]$ per tutte le $n$.
Dal punto 1): $P[S_(2n-1)=0] = 0$, quindi il problema si riduce nel calcolare $P[S_(2n) = 0]$, cioè $P[S_2=0]$, ...
$S_n$ è la somma di tutte le variabili aleatorie che indicano al $k$-esimo passo cosa succede, per $k=1,..., n$. Cioè:
$S_n = sum_{k=1}^n X_k$,
$X_k$ è il k-esimo passo, o fermata.
Quindi $P[S_n = 0] = P[sum_{k=1}^n X_k=0]$.
Quindi:
$P[S_(2n)=0] = ((2n),(n)) (1/3)^(2n)$,
ovvero i modi possibili di ritornare in $0$ dopo $2n$ passaggi per la probabilità di questi.
Vedi wiki:
http://it.wikipedia.org/wiki/Passeggiata_aleatoria
In definitiva la probabilità è:
$1/3 + 1/3*sum_{n=1}^{infty} ((2n),(n)) (1/3)^(2n)$
Che se non sbaglio è poco meno di 0.5...
Adesso, il punto più difficile mi sembra l'1...che non riesco a fare..
"adaBTTLS":
la probabilità non può essere inferiore ad 1/3
però, confrontando quanto scritto da Sergio e da frodo4, sembrerebbero risultati simili (va solo aggiunto +1/3 alla formula di frodo4 ...)
dal calcolo diretto, ho ottenuto,
nei casi particolari di n=2 ed n=3 rispettivamente vengono fuori due serie geometriche, e rispettivamente le probabilità di 3/5 e 2/3 ...
questi risultati non confortano né il mio primo calcolo su cui io stessa avevo delle riserve, né il risultato di Sergio.
frodo4, provi a schematizzare la catena di Markov?
ciao.
Io ho schematizzato la catena di Markov così
$((1/3,1/3,0,....,1/3),(1/3,1/3,1/3,....,0),(....,....,....,....,....),(1/3,0,....,1/3,1/3))$
Forse non sono riuscito a scriverla chiaramente, però dai calcoli che ho fatto mi risulta che sia bistocastica, da qui la probabilità per $N \to \infty$ = $1/(N-1)$, per il primo punto ancora sto vedendo.
Anch'io ho ragionato utilizzando le catene di Markov. Ho rappresentato il gioco con la matrice seguente, dove ho inserito lo stato zero come stato assorbente (cioè il re vince):
$((1,0,0,....,....,0),(1/3,1/3,1/3,....,....,0),(0,1/3,1/3,1/3,....,0),(....,....,....,....,....,....),(0,1/3,....,....,1/3,1/3))$
Ora se con $v_i=P[X_T=0|X_0=i]$ indichiamo la probabilità di essere assorbiti dallo stato zero partendo dallo stato "i" (cioè la probabilità di vincere partendo da uno degli "N" giocatori), avremo:
$v_0=1$
$v_1=P[X_T=0|X_0=1]$ applicando "l'analisi al primo passo" si ottiene:
$v_1=P[X_1=2|X_0=1]*P[X_T=0|X_1=2]+P[X_2=1|X_1=1]*P[X_T=0|X_1=1]+$
$P[X_T=0|X_1=0]*P[X_1=0|X_0=1]+P[X_T=0|X_1=N]*P[X_1=N|X_0=1]=1/3*v_2+1/3*0+1*1/3+1/3v_N$.
Con lo stesso metodo si ottiene:
$v_2=1/3v_1+1/3*v_3$
$v_3=1/3v_2+1/3*v_4$
$v_N=1/3v_(N-1)+1/3*v_1$.
Ora questo è un sistema con N eq. e N incognite....Però trovo un pò di difficoltà nella risoluzione. Sorry...
$((1,0,0,....,....,0),(1/3,1/3,1/3,....,....,0),(0,1/3,1/3,1/3,....,0),(....,....,....,....,....,....),(0,1/3,....,....,1/3,1/3))$
Ora se con $v_i=P[X_T=0|X_0=i]$ indichiamo la probabilità di essere assorbiti dallo stato zero partendo dallo stato "i" (cioè la probabilità di vincere partendo da uno degli "N" giocatori), avremo:
$v_0=1$
$v_1=P[X_T=0|X_0=1]$ applicando "l'analisi al primo passo" si ottiene:
$v_1=P[X_1=2|X_0=1]*P[X_T=0|X_1=2]+P[X_2=1|X_1=1]*P[X_T=0|X_1=1]+$
$P[X_T=0|X_1=0]*P[X_1=0|X_0=1]+P[X_T=0|X_1=N]*P[X_1=N|X_0=1]=1/3*v_2+1/3*0+1*1/3+1/3v_N$.
Con lo stesso metodo si ottiene:
$v_2=1/3v_1+1/3*v_3$
$v_3=1/3v_2+1/3*v_4$
$v_N=1/3v_(N-1)+1/3*v_1$.
Ora questo è un sistema con N eq. e N incognite....Però trovo un pò di difficoltà nella risoluzione. Sorry...
"Sergio":
Provate a guardare qui e poi qui.
E magari anche qui, giusto per completezza...
Mmm....due dei tre link non funzionano.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo