Ricerca distribuzione stazionaria
Buonasera,
mi sono appena avvicinato allo studio della catena di Markov ma a livello pratico non so veramente come lavorare su questi concetti.
A lezione abbiamo visto la seguente definizione:
sia $P$ un matrici di dimensioni $k*k$ che rappresenta le probabilità di transizione, allora $pi$ è detta una distribuzione stazionaria per $P$ se accade che $pi*P = pi$.
Subito dopo ci è stato lasciato questo esercizio(lascio l'immagine perchè è necessaria):
Ci si immagini di muoversi sulla griglia come un re vagante su una scacchiera, determinare allora la distribuzione stazionaria di un re libero di muoversi sulla scacchiera.
Ora mi trovo in difficoltà perchè onestamente non ho veramente idea su come partire e come fare a trovare sia la matrice $P$ sia $pi$ per poter, immagino ,applicare l'unica definizione che abbiamo visto.
Qualcuno potrebbe aiutarmi a capire come procedere e quali passaggi eseguire?
Grazie
mi sono appena avvicinato allo studio della catena di Markov ma a livello pratico non so veramente come lavorare su questi concetti.
A lezione abbiamo visto la seguente definizione:
sia $P$ un matrici di dimensioni $k*k$ che rappresenta le probabilità di transizione, allora $pi$ è detta una distribuzione stazionaria per $P$ se accade che $pi*P = pi$.
Subito dopo ci è stato lasciato questo esercizio(lascio l'immagine perchè è necessaria):
Ci si immagini di muoversi sulla griglia come un re vagante su una scacchiera, determinare allora la distribuzione stazionaria di un re libero di muoversi sulla scacchiera.
Ora mi trovo in difficoltà perchè onestamente non ho veramente idea su come partire e come fare a trovare sia la matrice $P$ sia $pi$ per poter, immagino ,applicare l'unica definizione che abbiamo visto.
Qualcuno potrebbe aiutarmi a capire come procedere e quali passaggi eseguire?
Grazie
Risposte
Quali sono gli stati? Quali sono le probabilità di transizione?
(Questo è un caso speciale dove trovare $\pi$ è una cosa che si fa in due righe. Ma forse lo scopo di questo esercizio è portarti alla scoperta di questo fatto.)
Hai provato a simulare i movimenti di questo re per vedere cosa succede?
(Questo è un caso speciale dove trovare $\pi$ è una cosa che si fa in due righe. Ma forse lo scopo di questo esercizio è portarti alla scoperta di questo fatto.)
Hai provato a simulare i movimenti di questo re per vedere cosa succede?
Allora anche qui mi trovo in difficoltà: a livello teorico so cosa siano gli stati e le probabilità di transizione, ma alle 2 domande non so risponderti.
Ad esempio la probabilità di transizione è
$p_(i,j)=P(X_(t+1)=j | X_t=i )$
Ma qui non capisco come applicarla questa definizione.
Per quanto riguarda le simulazioni del Re, ho ragionato cosi:
Quando sono agli estremi della scacchiera, ho sempre dei movimenti in meno perché mi manca una striscia della scacchiera, mentre invece quando sono lontano dai bordi il re puó muoversi liberamente.
Ad esempio la probabilità di transizione è
$p_(i,j)=P(X_(t+1)=j | X_t=i )$
Ma qui non capisco come applicarla questa definizione.
Per quanto riguarda le simulazioni del Re, ho ragionato cosi:
Quando sono agli estremi della scacchiera, ho sempre dei movimenti in meno perché mi manca una striscia della scacchiera, mentre invece quando sono lontano dai bordi il re puó muoversi liberamente.
"ghira":
Quali sono gli stati? Quali sono le probabilità di transizione?
(Questo è un caso speciale dove trovare $\pi$ è una cosa che si fa in due righe. Ma forse lo scopo di questo esercizio è portarti alla scoperta di questo fatto.)
Hai provato a simulare i movimenti di questo re per vedere cosa succede?
So che probabilmente come è scritto questo è un esempio stupido da 2 minuti, ma vorrei capire il modus operandi che ci sta dietro e comprendere come approcciare questo tipo di esercizi... non solo imparando la definizione
Grazie
"GuidoFretti":
Allora anche qui mi trovo in difficoltà: a livello teorico so cosa siano gli stati e le probabilità di transizione, ma alle 2 domande non so risponderti.
Quando sono agli estremi della scacchiera, ho sempre dei movimenti in meno perché mi manca una striscia della scacchiera, mentre invece quando sono lontano dai bordi il re puó muoversi liberamente.
Puoi essere molto più preciso? Hai provato a scrivere un programma per simulare i movimenti del re? O almeno ad usare un re degli scacchi, una scacchiera, e un dado ad 8 facce per vedere cosa succede? (Un programma sarebbe molto più veloce.)
"GuidoFretti":
a livello teorico so cosa siano gli stati e le probabilità di transizione, ma alle 2 domande non so risponderti.
Non so cosa dirti. In teoria cosa sono gli stati e le probabilità?
Qui cosa potrebbero essere gli stati? Ci sono _delle_ probabilità qui? Magari sono le probabilità di transizione. Fra cosa? Magari questo ti aiuta a riconoscere gli stati.
"ghira":
[quote="GuidoFretti"]Allora anche qui mi trovo in difficoltà: a livello teorico so cosa siano gli stati e le probabilità di transizione, ma alle 2 domande non so risponderti.
Quando sono agli estremi della scacchiera, ho sempre dei movimenti in meno perché mi manca una striscia della scacchiera, mentre invece quando sono lontano dai bordi il re puó muoversi liberamente.
Puoi essere molto più preciso? Hai provato a scrivere un programma per simulare i movimenti del re? O almeno ad usare un re degli scacchi, una scacchiera, e un dado ad 8 facce per vedere cosa succede? (Un programma sarebbe molto più veloce.)[/quote]
Allora le competenze per scrivere un programma attualmente non le ho, poiché non è nemmeno previsto nel corso.
Si ho provato a simulare i movimenti del Re con una scacchiera, ma onestamente non riesco a capire cosa mi porti ció, nel senso che: se mi trovo fuori dagli estremi della scacchiera posso scegliere di muovere il Re in 8 posizione differenti facendo una mossa. Se invece sono ai bordi(esclusi i 4 angoli), per ogni mossa ho 5 possibilità di scelta sulla nuova posizione in cui mettere il Re. Infine se sono ai 4 angoli, allora per ogni mossa ho solo 3 possibilità di scelta per la nuova posizione del Re
Qui capisco che con questa descrizione ci sia un nesso con le definizioni di probabilità di transizione... perché a seconda di dove mi trovo ho una condizionamento sul poter scegliere la successiva posizione...ma non sono in grado di capire come definirla e per questo ho chiesto aiuto qui...
"ghira":
[quote="GuidoFretti"]a livello teorico so cosa siano gli stati e le probabilità di transizione, ma alle 2 domande non so risponderti.
Non so cosa dirti. In teoria cosa sono gli stati e le probabilità?
Qui cosa potrebbero essere gli stati? Ci sono _delle_ probabilità qui? Magari sono le probabilità di transizione. Fra cosa? Magari questo ti aiuta a riconoscere gli stati.[/quote]
Le definizioni di probabilità di transizione l'ho data sopra e qui mi verrebbe da dire che la probabilità di transizione in questo esempio è la probabilità che il re si trovi in posizione $j$ al tempo $t+1$ sapendo che era in posizione $i$ al tempo $t$
Lo spazio degli stati sono i valori che assume la variabile aleatoria al variare di $t$, quindi qui sarebbero tutte le posizioni che può assumere il Re, ovvero lo spazio degli stati qui,per me, sono le $64$ caselle.
"GuidoFretti":
Lo spazio degli stati sono i valori che assume la variabile aleatoria al variare di $t$, quindi qui sarebbero tutte le posizioni che può assumere il Re, ovvero lo spazio degli stati qui,per me, sono le $64$ caselle.
Benone.
Se il re è in una data posizione adesso, dove può essere dopo la prossima mossa? Quali sono le probabilità delle possibili posizioni dopo la prossima mossa? Stiamo supponendo che le mosse disponibili abbiano tutte la stessa probabilità altrimenti non possiamo fare molto.
Allora onestamente non sono per nulla sicuro di quello che sto scrivendo, ma ci provo:
So che il mio spazio degli stati è $64$ e ogni mossa ha la stessa probabilità cioè $1/64$ perché non c'è nessuna mossa privilegiata rispetto ad altre (spero di aver detto giusto).
Ora però mi confondo: dal disegno mi verrebbe da dire che devo fare una distinzione a seconda di dove mi trovo nella scacchiera per dire quale è la probabilità di andare in una posizione successiva... è corretto oppure mi sto solo confondendo?
So che il mio spazio degli stati è $64$ e ogni mossa ha la stessa probabilità cioè $1/64$ perché non c'è nessuna mossa privilegiata rispetto ad altre (spero di aver detto giusto).
Ora però mi confondo: dal disegno mi verrebbe da dire che devo fare una distinzione a seconda di dove mi trovo nella scacchiera per dire quale è la probabilità di andare in una posizione successiva... è corretto oppure mi sto solo confondendo?
"GuidoFretti":
So che il mio spazio degli stati è $64$ e ogni mossa ha la stessa probabilità cioè $1/64$ perché non c'è nessuna mossa privilegiata rispetto ad altre (spero di aver detto giusto).
Ma che dici? Se il re è in alto a sinistra può trovarsi ovunque dopo la prossima mossa? Non è vero. Hai detto in una delle tue altre risposte cosa succede. Insomma.
Ok allora la situazione è come avevo immaginato all'inizio, ma non so come gestirla e mi spiego:
Ho capito il funzionamento della scacchiera, ma sapendo che ho $64$ stati non so ad esempio come "mettere in probabilità" il fatto che se sono nell'angolo in alto posso fare solo $3$ possibile mosse... ovvero trovare la probabilità di transizione
Nel mio tentativo (probabilmente errato) ho pensato che la probabilità di andare in un'altra posizione è $3/64$ ed essendo $4$ angoli allora ho $4*3/64$.
Poi rimanendo sul bordo ho $5$ possibilità per ogni mossa e quindi escludendo gli angoli già trattati avrei $28*5/64$ che però è $>1$ e quindi già qui capisco che non ha senso!
Però non so come realizzare a livello di calcoli questa situazione che in realtà a livello di simulazione ho capito.
Ho capito il funzionamento della scacchiera, ma sapendo che ho $64$ stati non so ad esempio come "mettere in probabilità" il fatto che se sono nell'angolo in alto posso fare solo $3$ possibile mosse... ovvero trovare la probabilità di transizione
Nel mio tentativo (probabilmente errato) ho pensato che la probabilità di andare in un'altra posizione è $3/64$ ed essendo $4$ angoli allora ho $4*3/64$.
Poi rimanendo sul bordo ho $5$ possibilità per ogni mossa e quindi escludendo gli angoli già trattati avrei $28*5/64$ che però è $>1$ e quindi già qui capisco che non ha senso!
Però non so come realizzare a livello di calcoli questa situazione che in realtà a livello di simulazione ho capito.
"GuidoFretti":
Nel mio tentativo (probabilmente errato) ho pensato che la probabilità di andare in un'altra posizione è $3/64$
Quale sarebbe la probabilità di andare nella stessa posizione?
"GuidoFretti":
ed essendo $4$ angoli allora ho $4*3/64$.
Cosa?
Premessa: non so niente delle catene di Markov 
Spunto: ci sono tre tipi di caselle, quelle di centro, quelle di bordo, quelle d'angolo. Tre tipi, tre stati?
Quelle di centro possono andare in 8 caselle diverse, quelle di bordo in 5 e quelle d'angolo in 3.
Quelle d'angolo hanno due possibilità su tre di andare in una casella di bordo e una probabilità su tre di andare in una casella centrale.
Quelle di bordo sono $24$ e quindi hanno $120$ destinazioni possibili; per $16$ di queste ci sono $2/5$ di probabilità di andare ancora sul bordo e $3/5$ su quelle centrali mentre per le restanti $8$ le probabilità sono $1/5, 2/5, 2/5$ di finire all'angolo, al bordo e al centro.
Stesso ragionamento (ma più lungo) per le caselle centrali ma non ho voglia di farlo
È solo uno spunto
Cordialmente, Alex
Spunto: ci sono tre tipi di caselle, quelle di centro, quelle di bordo, quelle d'angolo. Tre tipi, tre stati?
Quelle di centro possono andare in 8 caselle diverse, quelle di bordo in 5 e quelle d'angolo in 3.
Quelle d'angolo hanno due possibilità su tre di andare in una casella di bordo e una probabilità su tre di andare in una casella centrale.
Quelle di bordo sono $24$ e quindi hanno $120$ destinazioni possibili; per $16$ di queste ci sono $2/5$ di probabilità di andare ancora sul bordo e $3/5$ su quelle centrali mentre per le restanti $8$ le probabilità sono $1/5, 2/5, 2/5$ di finire all'angolo, al bordo e al centro.
Stesso ragionamento (ma più lungo) per le caselle centrali ma non ho voglia di farlo
È solo uno spunto
Cordialmente, Alex
"axpgn":
Spunto: ci sono tre tipi di caselle, quelle di centro, quelle di bordo, quelle d'angolo. Tre tipi, tre stati?
Direi più semplicemente 64 caselle, 64 stati.
Volendo dividere le caselle in tipi, direi che ce ne sono 10. Per alcuni scopi potrebbe essere utile dividere le caselle così ma in questo problema vogliamo rispondere a "Nel lungo andare, con che probabilità il re si trova sulla casella C3?" e altre 63 domande simili.
Io direi che possiamo fermarci a tre. Si fa prima. 
"axpgn":
Premessa: non so niente delle catene di Markov
Spunto: ci sono tre tipi di caselle, quelle di centro, quelle di bordo, quelle d'angolo. Tre tipi, tre stati?
Quelle di centro possono andare in 8 caselle diverse, quelle di bordo in 5 e quelle d'angolo in 3.
Quelle d'angolo hanno due possibilità su tre di andare in una casella di bordo e una probabilità su tre di andare in una casella centrale.
Quelle di bordo sono $24$ e quindi hanno $120$ destinazioni possibili; per $16$ di queste ci sono $2/5$ di probabilità di andare ancora sul bordo e $3/5$ su quelle centrali mentre per le restanti $8$ le probabilità sono $1/5, 2/5, 2/5$ di finire all'angolo, al bordo e al centro.
Stesso ragionamento (ma più lungo) per le caselle centrali ma non ho voglia di farlo
È solo uno spunto
Cordialmente, Alex
Grazie per lo spunto, almeno ho capito come ragionare e provo a vedere cosa riesco ad ottenere: noto con piacere che però abbiamo fatto la medesima distinzione dei possibili spostamenti del Re
"ghira":
[quote="axpgn"]
Spunto: ci sono tre tipi di caselle, quelle di centro, quelle di bordo, quelle d'angolo. Tre tipi, tre stati?
Direi più semplicemente 64 caselle, 64 stati.
Volendo dividere le caselle in tipi, direi che ce ne sono 10. Per alcuni scopi potrebbe essere utile dividere le caselle così ma in questo problema vogliamo rispondere a "Nel lungo andare, con che probabilità il re si trova sulla casella C3?" e altre 63 domande simili.[/quote]
Ok ho compreso che cosi sto allungando la strada, ma ora non riesco a capire come fare nel modo più semplice che continui a citare...
Quale ragionamento c'è alla base e come dovrei andare avanti per trovare $P$?
Grazie
@GuidoFretti
Sì, beh, come dice ghira, se vuoi determinare la probabilità di andare da una ben precisa casella ad un'altra non basta quella suddivisione ma devi costruire una tabella $64 xx 64$ e calcolare gli "infiniti" percorsi: non finisci più
(almeno credo )
Comunque l'idea era di quella di darti un'idea (anche perché io ne so veramente poco)
Sì, beh, come dice ghira, se vuoi determinare la probabilità di andare da una ben precisa casella ad un'altra non basta quella suddivisione ma devi costruire una tabella $64 xx 64$ e calcolare gli "infiniti" percorsi: non finisci più
(almeno credo )Comunque l'idea era di quella di darti un'idea
(anche perché io ne so veramente poco)
Si io ho bisogno di trovare la probabilità generale $p_(i,j)$ di andare dalla posizione $i$ a quella $j$.
Ma come a livello grafico ho capito cosa può fare il Re, qui non sto capendo come trovare queste maledette $p_(i,j)$.
Anche perché finito qui dovrei costruire $P$ e calcolare $πP=π$ perché il mio scopo è trovare il vettore $π$.
Mi viene allorché il dubbio se io possa farlo solo con un calcolatore
Ma come a livello grafico ho capito cosa può fare il Re, qui non sto capendo come trovare queste maledette $p_(i,j)$.
Anche perché finito qui dovrei costruire $P$ e calcolare $πP=π$ perché il mio scopo è trovare il vettore $π$.
Mi viene allorché il dubbio se io possa farlo solo con un calcolatore
"GuidoFretti":
Anche perché finito qui dovrei costruire $P$ e calcolare $πP=π$ perché il mio scopo è trovare il vettore $π$.
Mi viene allorché il dubbio se io possa farlo solo con un calcolatore
Non è necessario costruire $P$. "determinare allora la distribuzione stazionaria". Vogliamo solo $\pi$.
Si può fare solo con una calcolatrice tascabile, te lo giuro.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo