1. casa
  2. Domanda e risposta
  3. Una catena di Markov è uguale a una macchina a stati finiti?

Una catena di Markov è uguale a una macchina a stati finiti?

2011-02-02 12 views

risposta

45

Le catene Markov possono essere rappresentate da macchine a stati finiti. L'idea è che una catena di Markov descrive un processo in cui la transizione verso uno stato al tempo t + 1 dipende solo dallo stato al tempo t. La cosa principale da tenere a mente è che le transizioni in una catena di Markov sono probabilistiche piuttosto che deterministiche, il che significa che non si può sempre dire con certezza perfetta cosa succederà al tempo t + 1.

Gli articoli di Wikipedia su Finite-state machines hanno una sottosezione su Finite Markov-chain processes, mi consiglia di leggerlo per ulteriori informazioni. Inoltre, l'articolo di Wikipedia su Markov chains ha una breve frase che descrive l'uso di macchine a stati finiti nel rappresentare una catena di Markov. Che afferma:

Una macchina a stati finiti può essere utilizzata come una rappresentazione di una catena di Markov. Assumendo una sequenza di indipendente e segnali di ingresso identicamente distribuite (ad esempio, i simboli da un binario alfabeto scelto da lanci di moneta), se la macchina è in stato y al tempo n, allora la probabilità che si muove a stato x alla volta n + 1 dipende solo da lo stato corrente.

fonte

2011-02-02 21:56:55

+1

In realtà, quello che stai rivendicando su una catena Markov non è corretto al 100%. Quello a cui si fa riferimento qui è il "processo Markov del primo ordine". Per un processo Markov di secondo ordine, lo stato successivo dipenderà dagli stati degli ultimi 2 tempi temporali, ...... Una macchina a stati è un caso speciale di una catena di Markov; poiché una catena di Markov è di natura stocastica. Una macchina statale, per quanto ne so, è deterministica. –

+3

Non qualificato, il termine catena Markov indica un processo stocastico a tempo discreto con la proprietà Markov, il che significa che non dipende da stati passati. Il poster originale non chiedeva informazioni sui processi Markov di ordine superiore, quindi non sono così rilevanti. La macchina a stati finiti è generalmente un termine per tutti gli automi finiti, che può essere di natura deterministica o non deterministica. –

19

Mentre una catena di Markov è una macchina a stati finiti, si distingue per le sue transizioni stocastiche, cioè casuali, e descritte dalle probabilità.

fonte

2011-02-02 21:56:19

+2

Grazie per questo, esattamente quello che stavo cercando. –

+2

Posso dire, automi a stati finiti stocastici? –

15

I due sono simili, ma le altre spiegazioni qui sono leggermente errate. Solo le catene FINITE di Markov possono essere rappresentate da un FSM. Le catene di Markov consentono uno spazio di stato infinito. Come è stato sottolineato, le transizioni di una catena di Markov sono descritte dalle probabilità, ma è anche importante ricordare che le probabilità di transizione possono dipendere solo dallo stato corrente. Senza questa restrizione, sarebbe chiamato un "processo stocastico a tempo discreto".

fonte

2011-08-05 16:55:58

+1

(+1) Buoni punti chiari da fare. Grazie –

0

Se si lascia da parte i dettagli di lavoro interni, la macchina a stati finiti è come un valore normale, mentre la catena di markov è come una variabile casuale (aggiunge probabilità sopra al valore normale). Quindi la risposta alla domanda originale è no, non sono la stessa cosa. In senso probabilistico, la catena di Markov è un'estensione della macchina a stati finiti.

fonte

2013-12-11 11:59:24 liang

Problemi correlati

 Problemi correlati