Calcolo della probabilità di raggiungere lo stato in DTMC
-
06-11-2019 - |
Domanda
Considera un grafico altamente connesso di stati e transizioni in cui ogni transizione è contrassegnata con un peso (che rappresenta la probabilità di verificarsi) e il grafico soddisfa la proprietà discreta della catena di markov (DTMC): per ogni stato i pesi di transizione del deflusso sono reali (o semplicemente razionali, se questo fa la differenza) in [0,1] che somma a 1 e i pesi di transizione rimangono costanti nel tempo. Quindi una macchina a stato finito in cui il sistema si muove in modo probabilistico, fondamentalmente. Per esempio:
Dove $ a_ {0,1} + a_ {0,2} = 1 $, $ a_ {1,0} + a_ {1,3} = 1 $ eccetera.
Supponiamo di avviare il sistema nello stato dove $ x = 0 $; Qual è la probabilità che il sistema raggiunga lo stato dove $ x = 3 $, e qual è l'algoritmo per determinare quella probabilità? Dalla mia piccola conoscenza della probabilità, l'algoritmo richiede la somma delle probabilità di tutti i percorsi finiti che alla fine raggiungono $ x = 3 $; per esempio:
$ P [f (x = 3)] = a_ {0,1} CDOT a_ {1,3} + a_ {0,2} CDOT a_ {2,3} + a_ {0,1} CDOT a_ {1,0} CDOT a_ {0,1} CDOT a_ {1,3} + ldots $
Dal momento che è possibile che il sistema si avvicini a tempo indeterminato prima di raggiungere $ x = 3 $, questa equazione include una somma infinita di prodotti infiniti ed è oltre la mia capacità di risolvere. Come viene calcolato qualcosa di simile?
Nessuna soluzione corretta