-
.
Simulare un Random Walk e trovare una convergenza
Talvolta capita di avere processi in cui delle risorse devono essere trasferite da una locazione ad un'altra e ad un certo punto viene raggiunto un punto di convergenza: ovvero il processo pur continuando a spostare risorse, in ogni locazione avremo sempre lo stesso numero di elementi.
Proviamo a spiegare con un esempio e immaginiamoci un arzillo kostaki pronto a portare al pascolo le sue 100 mucche.
Queste mucche però vanno portate in 4 campi diversi (A,B,C,D), il primo giorno le 100 mucche vengono tutte portate nel campo A, il secondo giorno vengono tutte portate nel campo B, il terzo giorno vengono tutte portate nel campo C e infine dal campo C metà vengono portate nel campo D e l'altra metà ritorna nel campo A e ricomincia il giro.
Le mucche nel campo D passano successivamente al campo A e ricominciano pure loro il giro.
Ricordiamoci però che nonno kost deve rifornire i vari campi del cibo per le mucche e chiaramente con questi ritmi rischiamo che non arrivi sano alla pensione.
Infatti per i primi tre giorni non avrà problemi: le 100 mucche passeranno per A, poi per B e infine per C.
Dal quarto giorno comincia a succedere qualcosa che potrebbe cominciare a mostrargli qualche problema: metà mucche dovranno andare in D e l'altra metà in A.
Arrivando al 25 in C cominceremo ad avere un numero dispari da dividere in due e qui il nostro contadino preferito sarà sempre più in difficoltà nel gestire questi calcoli matematici.
Possiamo provare ad elaborare una strategia per aiutare nonno kost nella sua missione.
1) Rappresentazione Concettuale del Grafo
Per prima cosa dobbiamo rappresentare il grafo che rappresenta i nodi A,B,C,D e le relazioni tra essi (In questo post trovate qualche informazione sui grafi).
2) Matrice di Adiacenza del Grafo
Trovate un post a riguardo Qui .
In questo caso è:CODICE[0 1 0 0]
[0 0 1 0]
[1 0 0 1]
[1 0 0 0]
3) Calcolo della matrice dei gradi
La matrice dei gradi è una matrice diagonale in cui nella diagonale inserisce la somma degli elementi della rispettiva riga della matrice di Adiacenza ACODICE[1 0 0 0]
[0 1 0 0]
[0 0 2 0]
[0 0 0 1]
4) Calcolo della matrice Stocastica
La matrice stocastica viene creata facendo la divisione fra gli elementi della matrice di adiacenza per il grado della riga e poi facciamo la matrice traspostaCODICE[ 0 0 0.5 1 ]
[ 1 0 0 0 ]
[ 0 1 0 0 ]
[ 0 0 0.5 0 ]
5) Iterazione di Vettore
Ora finalmente abbiamo la nostra matrice stocastica e dobbiamo immaginare di moltiplicarla per un vettore.
Questo vettore iniziale sarà [100 0 0 0], ovvero immaginiamoci di partire dal fatto che al primo giro le 100 mucche andranno immediatamente al campo A.
Ora non ci resta che aggiornarlo fino a quando non raggiungo una convergenza.
Con Convergenza si intende un punto in cui moltiplicando il vettore x per la matrice stocastica ottengo lo stesso identico vettore x e quindi continuando a ripetere l'operazione otterrò sempre lo stesso risultato.
Ho deciso di arrotondare i valori a un numero intero per far capire a kostaki come rifornire di cibo i vari campi tarandole su mucche intere e non divise in tanti pezzi.
Il risultato è il seguente:
Come potete notare, dopo 52 ripetizioni sembro raggiungere la convergenza, ovvero dal 52° giorno in poi kost potrà contare su un numero fisso di mucche in ogni campo, pur continuando i loro spostamenti e non dovrà più diventare matto nel capire quanto cibo rifornire i vari campi.
Se nonno kost è ancora più furbo può partire direttamente dal numero di mucche già ben disposto nei vari campi, così potrà stare tranquillo fin dal primo giorno e non dal 52°.
Ma questo metodo funziona sempre?
Purtroppo no.
Non tutte le matrici stocastiche portano ad una convergenza.
Il Teorema di Perron Frobenius può venire in nostro aiuto per comprendere se l'iterazione di vettore può fare al caso nostro: nel caso delle matrici stocastiche contengono tutti valori maggiori o uguali a zero e il grafo deve essere irriducibile, ovvero composto da un unica componente connessa.
Inoltre il suo autovalore maggiore sarà 1 e deve essere unico, ovvero non devono esistere altri autovalori maggiori o uguali a 1.
Nell'esempio riportato la matrice è irriducibile poiché tutti i nodi sono connessi tra di loro e da ogni nodo posso raggiungerne un altro direttamente o indirettamente.
Per quanto riguarda gli autovalori possiamo calcolarli direttamente con il calcolatore online di YouMath .
I risultati che ottengo sono i seguenti:
Come potete vedere: anche la condizione di avere un autovalore uguale a 1 e senza avere altri autovalori identici è rispettata, pertanto è possibile avere una convergenza.
E se avessi avuto solo 3 campi in cui tutte le mucche vengono sempre trasferite da un campo all'altro?
- le 100 mucche vanno in A
- le 100 mucche si spostano da A in B
- le 100 mucche si spostano da B in C
- le 100 mucche si spostano da C ad A
- Si ricomincia fino alla convergenza.
In questo caso la matrice di Adiacenza sarebbe stata:CODICE[ 0 1 0]
[ 0 0 1]
[ 1 0 0]
Mentre la matrice dei Gradi:CODICE[ 1 0 0]
[ 0 1 0]
[ 0 0 1]
Infine la matrice stocastica che corrisponde alla matrice A trasposta (ovvero invertite righe e colonne):CODICE[ 0 0 1]
[ 1 0 0]
[ 0 1 0]
La matrice stocastica è ancora connessa.
Tuttavia non potrà mai esserci una convergenza, perché non esisterà mai una sequenza di transizioni che faranno avere lo stesso numero di mucche tra una transizione e l'altra.
Ringrazio nonno kost per essere stato prestato contro la sua volontà in questo post
, ma almeno così sono sicuro di poter riuscire almeno un minimo a suscitare il suo interesse
. -
.
Un luogo dove qualcuno ancora pensa a te, quello è il luogo che puoi chiamare casa...
- Group
- Member
- Posts
- 235
- Status
Anonymous
caspita, con questo mi hai spiazzato.
Praticamente la funzione che ogni giorno sposta gli elementi del vettore è una funzione lineare che corrisponde alla matrice stocastica trasposta. Poi magicamente la sequenza converge all'autovettore della matrice.
C'è da dire che (come hai fatto notare tu) la convergenza non c'è sempre, autovalori a parte, se nonno kost avesse deciso di utilizzare radici o logaritmi non avrebbe funzionato niente
Non ho mai studiato questa roba.. -
.
- Group
- ForumFree Staff
- Posts
- 109,420
- Location
- Slayer's Flag
- Status
- Anonymous
io non ci sono nemmeno andato vicinoCITAZIONERingrazio nonno kost per essere stato prestato contro la sua volontà in questo post , ma almeno così sono sicuro di poter riuscire almeno un minimo a suscitare il suo interesse
io leggo tutto quello che scrivi, e tutto mi interessa, il problema è la comprensione quindi vi sono delle situazioni in cui si puòarrivare ad una configurazione stabile o comunque ripetitiva, ed altre, apparentemente simili, che invece non possiedono una "isola di stabilità" e matematicamente non solo le si può distinguere, ma si può anche calcolare, per le prime,quale sia la convergenza e quindi volendo si può giungervi direttamente risparmiandosi di andare in giro con branchi di mucche a caso 
e non si devono nemmeno tagliare le mucche 
. -
.
Un luogo dove qualcuno ancora pensa a te, quello è il luogo che puoi chiamare casa...
- Group
- Member
- Posts
- 235
- Status
- Anonymous
io non ci sono nemmeno andato vicinoCITAZIONERingrazio nonno kost per essere stato prestato contro la sua volontà in questo post , ma almeno così sono sicuro di poter riuscire almeno un minimo a suscitare il suo interesse
io leggo tutto quello che scrivi, e tutto mi interessa, il problema è la comprensione quindi vi sono delle situazioni in cui si puòarrivare ad una configurazione stabile o comunque ripetitiva, ed altre, apparentemente simili, che invece non possiedono una "isola di stabilità" e matematicamente non solo le si può distinguere, ma si può anche calcolare, per le prime,quale sia la convergenza e quindi volendo si può giungervi direttamente risparmiandosi di andare in giro con branchi di mucche a caso e non si devono nemmeno tagliare le mucche
esatto.
Simulare un Random Walk e trovare una convergenza |
Web