Automi di Markov

Gli automi di Markov ( o automi markoviani ) sono processi stocastici {x(t)} con spazio degli stati X che rispettano la proprietà di Markov in base alla quale sono privi di memoria ( memoryless ).

Sono privi di memoria perché l'automa conosce soltanto lo stato attuale, non memorizza alcuna informazione sulla sequenza passata degli eventi.

I processi di Markov

La proprietà di Markov ( memoryless ) si basa su due condizioni:

• No State Memory
  L'automa non conosce la sequenza di eventi passata.
• No State Age Memory
  L'automa non conosce quante volte è passato per uno stato.

  Nota. Quest'ultima condizione implica che la probabilità si basa su variabili aleatorie a distribuzione esponenziale.

La probabilità della transizione dallo stato x_i=x(τ) allo stato x_j=x(τ+dτ) è

In pratica, la probabilità P di passare dallo stato x_i allo stato x_i=x(τ+dτ) è una probabilità condizionata P(x_j|x(τ)=x_i) al fatto che l'automa si trovi attualmente (τ) nello stato x_i.

Per stimare la probabilità di transizione da uno stato all'altro, l'automa considera soltanto lo stato corrente.

Non sono prese in considerazione altre informazioni per il calcolo della probabilità.

L'automa conosce soltanto lo stato corrente in cui si trova.

Gli stati passati sono irrilevanti per prevedere il futuro.

Esempio. Se in una situazione ciclica l'automa ripassa molte volte nello stato x_i, la probabilità di passare allo stato x_j da x_i è sempre la stessa perché l'automa non memorizza quante volte passa in uno stato (no state age memory). Anche se il cammino si è dimostrato fallimentare in passato. L'automa non considera la traiettoria, ossia la sequenza degli stati assunti in passato dall'automa prima di arrivare allo stato x_i nell'intervallo [τ₀,τ], dove τ₀ è l'istante iniziale e τ l'istante attuale. L'automa elabora soltanto lo stato corrente.

Processi Semi Markoviani

I processi sono detti semi-markoviani quando rispettano soltanto alcune condizioni della proprietà di Markov.

Esempio

Un automa semi-markoviano non ha le informazioni sugli eventi passati ma memorizza quante volte passa in ogni stato.

In questo caso, l'automa rispetta soltanto la condizione no state memory.

Non rispetta la condizione no age state memory.

Tipi di processi di Markov

I processi markoviani possono essere

• Processi con spazio di stato X continuo
• Processi con spazio di stato X discreto ( catene di Markov )

E così via.