Problema della formica e del ragno

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
panurgo
Livello 9
Livello 9
Messaggi: 1521
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Problema della formica e del ragno

Messaggio da panurgo »

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"

franco
Livello 9
Livello 9
Messaggi: 1438
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Problema della formica e del ragno

Messaggio da franco »

Per ora sono arrivato a disegnare questo:
RF.png
RF.png (25.61 KiB) Visto 5217 volte
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

panurgo
Livello 9
Livello 9
Messaggi: 1521
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Problema della formica e del ragno

Messaggio da panurgo »

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,
MPI.004.02.png
MPI.004.02.png (8.85 KiB) Visto 5211 volte
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}}
e ci rivolgiamo all’ottimo WolframAlpha ottenendo in risposta
MPI.004.03.001.png
MPI.004.03.001.png (5.22 KiB) Visto 5211 volte
MPI.004.03.002.png
MPI.004.03.002.png (20.1 KiB) Visto 5211 volte
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"

franco
Livello 9
Livello 9
Messaggi: 1438
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Problema della formica e del ragno

Messaggio da franco »

panurgo ha scritto:
sab dic 14, 2019 3:55 pm
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:
...
:D :D :D :D
molto più semplice
:D :D :D :D

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

panurgo
Livello 9
Livello 9
Messaggi: 1521
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Problema della formica e del ragno

Messaggio da panurgo »

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"

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: Problema della formica e del ragno

Messaggio da Pasquale »

Le cose si complicano. Vediamo cosa ne ha capito Decimal Basic, che parla un'altra lingua:
.
ragno.JPG
ragno.JPG (43.08 KiB) Visto 5186 volte
.
Però, chi l'avrebbe detto!! Promette bene il ragazzo: anche lui concorda con il 10 :shock: :D

( 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 Immagine ciao
E' la somma che fa il totale (Totò)

gnugnu
Livello 4
Livello 4
Messaggi: 147
Iscritto il: dom set 07, 2014 2:00 pm

Re: Problema della formica e del ragno

Messaggio da gnugnu »

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.

Rispondi