Problema della formica e del ragno
Moderatori: Gianfranco, Bruno
Questo forum è una sezione del PORTALE DI BASE CINQUE
Problema della formica e del ragno
Una formica e un ragno cieco sono ai vertici opposti di un cubo. La formica sta ferma mentre il ragno si muove a caso da un vertice all'altro lungo gli spigoli. Quante mosse deve fare in media il ragno per raggiungere la formica?
il panurgo
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"
Re: Problema della formica e del ragno
Per ora sono arrivato a disegnare questo:
https://it.wikipedia.org/wiki/Processo_markoviano
Putroppo però la pagina di Wikipedia su cui speravo di trovare qualcosa di utile è fuori dalla mia portata https://it.wikipedia.org/wiki/Processo_markoviano
Franco
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
Re: Problema della formica e del ragno
Pagine come quelle sembrano fatte apposta per far credere al mondo che le catene di Markov siano fuori portata di chiunque non abbia una Laurea in Matematica.
La realta è molto più semplice: abbiamo un processo, in questo caso con quattro stati, e abbiamo per ogni coppia di stati una frequenza di transizione (mi secca chiamarla probabilità...), frequenze raccolte in una matrice $\mathbf{T}$; rappresentiamo lo stato attuale del processo con un vettore $\mathbf{y}$, contenente le frequenze di occupazione di ciascuno stato.
Per ogni passo del processo $\mathbf{y}\left(r\right)=\mathbf{T}\,\mathbf{y}\left(r-1\right) $, il che significa che $\mathbf{y}\left(r\right)=\mathbf{T}^{\,r}\mathbf{y}\left(0\right) $.
Per trovere la potenza di una matrice quadrata bisogna diagonalizzarla, cioè trovare una matrice $\mathbf{S}$ tale che $\mathbf{T}=\mathbf{S}\,\mathbf{\Lambda}\,\mathbf{S}^{-1}$, dove $\mathbf{\Lambda}$ è una matrice diagonale: per una matrice diagonale, applicando $r$ volte la moltiplicazione di matrici, troviamo che $\mathbf{\Lambda}^r=\text{diag}\left\{\lambda_1^r,\ldots,\lambda_n^r\right\}$.
Da ciò ricaviamo $\mathbf{y}\left(r\right)=\mathbf{S}\,\mathbf{\Lambda}^r\,\mathbf{S}^{-1}\,\mathbf{y}\left(0\right) $
Tornando al nostro problema, il ragno è nel primo stato
$\displaystyle\mathbf{y}\left(0\right)=\left(\begin{array}{cC}1\\0\\0\\0\end{array}\right)$
e la matrice di transizione è
$\displaystyle\mathbf{T}=\left(\begin{array}{cC}0 & \frac13 & 0 & 0 \\ 1 & 0 & \frac23 & 0 \\ 0 & \frac23 & 0 & 0 \\ 0 & 0 & \frac13 & 1\end{array}\right)$
(nel tuo grafo manca la transizione dallo stato F allo stato F con frequenza $1$)
Scriviamo
e ci rivolgiamo all’ottimo WolframAlpha ottenendo in risposta
Lo stato F è diverso dagli altri perché il ragno rimane lì una volta raggiunta la formica (non la vuole mica mangiare: essendo cieco ha solo bisogno di qualcuno che gli legga À la recherche du temps perdu) cioè diciamo che è uno stato assorbente!
Questo significa che la frequenza che noi troviamo in $y_4\left(r\right)$ è una frequenza cumulativa: il ragno potrebbe essere arrivato in uno qualsiasi degli $r$ passi. D’altronde, visto che siamo interessati solo allo stato F, non importa che eseguiamo esplicitamente tutte le moltiplicazioni tra le varie matrici: ci basta osservare che, poiché il ragno parte dallo stato R
$\displaystyle \mathbf{S}^{-1}\,\mathbf{y}\left(0\right)=\left(\begin{array}{cC}\frac27\\1\\\frac{-9+3\sqrt7}{14}\\-\frac{9+3\sqrt7}{14}\end{array}\right)$
cioè ci serve solo la prima colonna della matrice $\mathbf{S}^{-1}$, e che, per avere il quarto elemento di $\mathbf{y}\left(r\right)$, basta moltiplicare a sinistra per la quarta riga di $\mathbf{S}$
$\displaystyle y_4\left(r\right)=\left(\begin{array}{cC} 1 & 1 & 1 & 1 \end{array}\right)\left(\begin{array}{ccccCCCC} \lambda_1^r&&&\\&1&&\\&&\lambda_3^r\\&&&\lambda_4^r\end{array}\right)\left(\begin{array}{cC}\frac27\\1\\\frac{-9+3\sqrt7}{14}\\-\frac{9+3\sqrt7}{14}\end{array}\right)$
Ho messo $1$ perché $\lambda_2=1$ e quindi $\lambda_2^r=1$ per qualsiasi valore di $r$:
La frequenza cumulativa di $r$ è
$\displaystyle F\left(r\right)=\frac27\lambda_1^r+1-\frac{9-3\sqrt7}{14}\lambda_3^r-\frac{9+3\sqrt7}{14}\lambda_4^r$
Se vogliamo la frequenza con cui il ragno arriva in F esattamente in $r$ passi la otteniamo per differenza
$\displaystyle f\left(r\right)=F\left(r\right)-F\left(r-1\right)= \frac27\left(\lambda_1^r-\lambda_1^{r-1}\right)+1-1-\frac{9-3\sqrt7}{14}\left(\lambda_3^r-\lambda_3^{r-1}\right)-\frac{9+3\sqrt7}{14}\left(\lambda_4^r-\lambda_4^{r-1}\right) $
cioè
$\displaystyle f\left(r\right)=-\frac27\left(1-\lambda_1\right)\lambda_1^{r-1}+\frac{9-3\sqrt7}{14}\left(1-\lambda_3\right)\lambda_3^{r-1}+\frac{9+3\sqrt7}{14}\left(1-\lambda_4\right)\lambda_4^{r-1}$
A questo punto facciamo appello al Principio di Indifferenza per assegnare la frequenza teste trovata come valore della probabilità per il ragno di arrivare in F esattamente in $r$ passi
$\displaystyle\text{Pr}\left(r\middle|\top\right)=f\left(r\right)$
dove $r$ equivale alla proposizione “Il ragno raggiunge F esattamente in $r$ passi” e $\top$ rappresenta l’universo del discorso.
L’expectation di $r$ vale
$\displaystyle \left\langle r\middle|\top\right\rangle=\sum_{r=0}^\infty r\,\text{Pr}\left(r\middle|\top\right)$
Per eseguire questo calcolo facciamo uso della Magia dell’Anello (delle Serie Formali):
$\displaystyle\sum_{r=0}^\infty r\,q^{r-1}=\sum_{r=0}^\infty \frac{d}{dq}q^r=\frac{d}{dq}\sum_{r=0}^\infty q^r=\frac{d}{dq}\frac1{1-q}=\frac1{\left(1-q\right)^2}$
Mutatis mutandis
$\begin{array}{lllC}\displaystyle\left\langle r\middle|\top\right\rangle&\displaystyle =&\displaystyle -\frac27\left(1-\lambda_1\right)\sum_{r=0}^\infty r\,\lambda_1^{r-1}+\frac{9-3\sqrt7}{14}\left(1-\lambda_3\right)\sum_{r=0}^\infty r\,\lambda_3^{r-1}+\frac{9+3\sqrt7}{14}\left(1-\lambda_4\right)\sum_{r=0}^\infty r\,\lambda_4^{r-1}\\\displaystyle &\displaystyle =&\displaystyle -\frac2{7\left(1-\lambda_1\right)}+\frac{9-3\sqrt7}{14\left(1-\lambda_3\right)}+\frac{9+3\sqrt7}{14\left(1-\lambda_4\right)}=-\frac2{7\left(1-0\right)}+\frac{9}{14}\left(\frac{3-\sqrt7}{3+\sqrt7}+\frac{3+\sqrt7}{3-\sqrt7}\right)=10\end{array}$
Volete provare con un ottaedro?
La realta è molto più semplice: abbiamo un processo, in questo caso con quattro stati, e abbiamo per ogni coppia di stati una frequenza di transizione (mi secca chiamarla probabilità...), frequenze raccolte in una matrice $\mathbf{T}$; rappresentiamo lo stato attuale del processo con un vettore $\mathbf{y}$, contenente le frequenze di occupazione di ciascuno stato.
Per ogni passo del processo $\mathbf{y}\left(r\right)=\mathbf{T}\,\mathbf{y}\left(r-1\right) $, il che significa che $\mathbf{y}\left(r\right)=\mathbf{T}^{\,r}\mathbf{y}\left(0\right) $.
Per trovere la potenza di una matrice quadrata bisogna diagonalizzarla, cioè trovare una matrice $\mathbf{S}$ tale che $\mathbf{T}=\mathbf{S}\,\mathbf{\Lambda}\,\mathbf{S}^{-1}$, dove $\mathbf{\Lambda}$ è una matrice diagonale: per una matrice diagonale, applicando $r$ volte la moltiplicazione di matrici, troviamo che $\mathbf{\Lambda}^r=\text{diag}\left\{\lambda_1^r,\ldots,\lambda_n^r\right\}$.
Da ciò ricaviamo $\mathbf{y}\left(r\right)=\mathbf{S}\,\mathbf{\Lambda}^r\,\mathbf{S}^{-1}\,\mathbf{y}\left(0\right) $
Tornando al nostro problema, il ragno è nel primo stato
$\displaystyle\mathbf{y}\left(0\right)=\left(\begin{array}{cC}1\\0\\0\\0\end{array}\right)$
e la matrice di transizione è
$\displaystyle\mathbf{T}=\left(\begin{array}{cC}0 & \frac13 & 0 & 0 \\ 1 & 0 & \frac23 & 0 \\ 0 & \frac23 & 0 & 0 \\ 0 & 0 & \frac13 & 1\end{array}\right)$
(nel tuo grafo manca la transizione dallo stato F allo stato F con frequenza $1$)
Scriviamo
Codice: Seleziona tutto
diagonalize {{0,1/3,0,0},{1,0,2/3,0},{0,2/3,0,0},{0,0,1/3,1}}
Lo stato F è diverso dagli altri perché il ragno rimane lì una volta raggiunta la formica (non la vuole mica mangiare: essendo cieco ha solo bisogno di qualcuno che gli legga À la recherche du temps perdu) cioè diciamo che è uno stato assorbente!
Questo significa che la frequenza che noi troviamo in $y_4\left(r\right)$ è una frequenza cumulativa: il ragno potrebbe essere arrivato in uno qualsiasi degli $r$ passi. D’altronde, visto che siamo interessati solo allo stato F, non importa che eseguiamo esplicitamente tutte le moltiplicazioni tra le varie matrici: ci basta osservare che, poiché il ragno parte dallo stato R
$\displaystyle \mathbf{S}^{-1}\,\mathbf{y}\left(0\right)=\left(\begin{array}{cC}\frac27\\1\\\frac{-9+3\sqrt7}{14}\\-\frac{9+3\sqrt7}{14}\end{array}\right)$
cioè ci serve solo la prima colonna della matrice $\mathbf{S}^{-1}$, e che, per avere il quarto elemento di $\mathbf{y}\left(r\right)$, basta moltiplicare a sinistra per la quarta riga di $\mathbf{S}$
$\displaystyle y_4\left(r\right)=\left(\begin{array}{cC} 1 & 1 & 1 & 1 \end{array}\right)\left(\begin{array}{ccccCCCC} \lambda_1^r&&&\\&1&&\\&&\lambda_3^r\\&&&\lambda_4^r\end{array}\right)\left(\begin{array}{cC}\frac27\\1\\\frac{-9+3\sqrt7}{14}\\-\frac{9+3\sqrt7}{14}\end{array}\right)$
Ho messo $1$ perché $\lambda_2=1$ e quindi $\lambda_2^r=1$ per qualsiasi valore di $r$:
La frequenza cumulativa di $r$ è
$\displaystyle F\left(r\right)=\frac27\lambda_1^r+1-\frac{9-3\sqrt7}{14}\lambda_3^r-\frac{9+3\sqrt7}{14}\lambda_4^r$
Se vogliamo la frequenza con cui il ragno arriva in F esattamente in $r$ passi la otteniamo per differenza
$\displaystyle f\left(r\right)=F\left(r\right)-F\left(r-1\right)= \frac27\left(\lambda_1^r-\lambda_1^{r-1}\right)+1-1-\frac{9-3\sqrt7}{14}\left(\lambda_3^r-\lambda_3^{r-1}\right)-\frac{9+3\sqrt7}{14}\left(\lambda_4^r-\lambda_4^{r-1}\right) $
cioè
$\displaystyle f\left(r\right)=-\frac27\left(1-\lambda_1\right)\lambda_1^{r-1}+\frac{9-3\sqrt7}{14}\left(1-\lambda_3\right)\lambda_3^{r-1}+\frac{9+3\sqrt7}{14}\left(1-\lambda_4\right)\lambda_4^{r-1}$
A questo punto facciamo appello al Principio di Indifferenza per assegnare la frequenza teste trovata come valore della probabilità per il ragno di arrivare in F esattamente in $r$ passi
$\displaystyle\text{Pr}\left(r\middle|\top\right)=f\left(r\right)$
dove $r$ equivale alla proposizione “Il ragno raggiunge F esattamente in $r$ passi” e $\top$ rappresenta l’universo del discorso.
L’expectation di $r$ vale
$\displaystyle \left\langle r\middle|\top\right\rangle=\sum_{r=0}^\infty r\,\text{Pr}\left(r\middle|\top\right)$
Per eseguire questo calcolo facciamo uso della Magia dell’Anello (delle Serie Formali):
$\displaystyle\sum_{r=0}^\infty r\,q^{r-1}=\sum_{r=0}^\infty \frac{d}{dq}q^r=\frac{d}{dq}\sum_{r=0}^\infty q^r=\frac{d}{dq}\frac1{1-q}=\frac1{\left(1-q\right)^2}$
Mutatis mutandis
$\begin{array}{lllC}\displaystyle\left\langle r\middle|\top\right\rangle&\displaystyle =&\displaystyle -\frac27\left(1-\lambda_1\right)\sum_{r=0}^\infty r\,\lambda_1^{r-1}+\frac{9-3\sqrt7}{14}\left(1-\lambda_3\right)\sum_{r=0}^\infty r\,\lambda_3^{r-1}+\frac{9+3\sqrt7}{14}\left(1-\lambda_4\right)\sum_{r=0}^\infty r\,\lambda_4^{r-1}\\\displaystyle &\displaystyle =&\displaystyle -\frac2{7\left(1-\lambda_1\right)}+\frac{9-3\sqrt7}{14\left(1-\lambda_3\right)}+\frac{9+3\sqrt7}{14\left(1-\lambda_4\right)}=-\frac2{7\left(1-0\right)}+\frac{9}{14}\left(\frac{3-\sqrt7}{3+\sqrt7}+\frac{3+\sqrt7}{3-\sqrt7}\right)=10\end{array}$
Volete provare con un ottaedro?
il panurgo
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"
Re: Problema della formica e del ragno
molto più semplice
Come sempre, il tuo post è impeccabile, ma è proprio vero che la semplicità è un conceto relativo!
Un abbraccio
Franco
Franco
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
Re: Problema della formica e del ragno
Beh, almeno il mio è scritto in itailiano...
il panurgo
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"
Re: Problema della formica e del ragno
Le cose si complicano. Vediamo cosa ne ha capito Decimal Basic, che parla un'altra lingua:
. .
Però, chi l'avrebbe detto!! Promette bene il ragazzo: anche lui concorda con il 10
( r$ è la matrice dei vertici, ciascuno con le sue 3 diramazioni pseudocasuali possibili. Per 100.000 volte il ragno parte dal vertice A per raggiungere l'opposto vertice F: dal conteggio degli spigoli totali percorsi viene tratta la media )
. .
Però, chi l'avrebbe detto!! Promette bene il ragazzo: anche lui concorda con il 10
( r$ è la matrice dei vertici, ciascuno con le sue 3 diramazioni pseudocasuali possibili. Per 100.000 volte il ragno parte dal vertice A per raggiungere l'opposto vertice F: dal conteggio degli spigoli totali percorsi viene tratta la media )
_________________
$\text { }$ciao ciao
E' la somma che fa il totale (Totò)
$\text { }$ciao ciao
E' la somma che fa il totale (Totò)
Re: Problema della formica e del ragno
In problemi di questo tipo mi pare decisamente più agevole operare direttamente sul valor medio del numero di segmenti percorsi dal ragno per arrivare all'agognata destinazione.
Se, come indicato da Panurgo, raggruppiamo gli stati possibili etichettandoli con la loro 'distanza' dalla formica, abbiamo quattro possibilità: $ 0,1,2,3 $; ad ognuno di questi corrisponderà un numero medio di transizioni, che possiamo indicare con $ M_0, M_1, M_2, M_3 $. Questi valori non sono indipendenti, ma legati da equazioni lineari che possiamo ricavare osservando che il ragno trovandosi in una posizione qualsivoglia (diversa da $0$), percorrerà un segmento, scelto a caso, per ritrovarsi in una nuova posizione con un dato $ M_i $:
$ M_0=0; M_1=1+1/3 M_0+2/3 M_2; M_2=1+2/3 M_1+1/3 M_3; M_3=1+M_2 $.
Sistema di primo grado che fornisce immediatamente: $ M_0=0; M_1=7; M_2=9; M_3=10 $.
Il solido platonico più complicato da 'risolvere' è il dodecaedro, che porta a:
$ M_0=0; M_1=19; M_2=27; M_3=32; M_4=34: M_5=35 $.
Potrebbe essere interessante vedere cosa cambia se il ragno, furbescamente, evita di uscire da un vertice utilizzando lo spigolo che ha percorso per arrivarci, scegliendo a caso fra i restamti.
Ciao e tanti auguri di Buon Natale a tutti.
Se, come indicato da Panurgo, raggruppiamo gli stati possibili etichettandoli con la loro 'distanza' dalla formica, abbiamo quattro possibilità: $ 0,1,2,3 $; ad ognuno di questi corrisponderà un numero medio di transizioni, che possiamo indicare con $ M_0, M_1, M_2, M_3 $. Questi valori non sono indipendenti, ma legati da equazioni lineari che possiamo ricavare osservando che il ragno trovandosi in una posizione qualsivoglia (diversa da $0$), percorrerà un segmento, scelto a caso, per ritrovarsi in una nuova posizione con un dato $ M_i $:
$ M_0=0; M_1=1+1/3 M_0+2/3 M_2; M_2=1+2/3 M_1+1/3 M_3; M_3=1+M_2 $.
Sistema di primo grado che fornisce immediatamente: $ M_0=0; M_1=7; M_2=9; M_3=10 $.
Il solido platonico più complicato da 'risolvere' è il dodecaedro, che porta a:
$ M_0=0; M_1=19; M_2=27; M_3=32; M_4=34: M_5=35 $.
Potrebbe essere interessante vedere cosa cambia se il ragno, furbescamente, evita di uscire da un vertice utilizzando lo spigolo che ha percorso per arrivarci, scegliendo a caso fra i restamti.
Ciao e tanti auguri di Buon Natale a tutti.