Home » Intelligenza Artificiale » 📋 URL
Servono per modellare i processi stocastici, ovvero delle variabili aleatorie che evolvono nel tempo.
X_0,\,X_1,\,X_2,\,\dots(\text{ogni }X_i \text{ è lo stato di un sistema ad un tempo e spazio discreti})La proprietà di Markov diche che se X_n è il presente. Vogliamo conoscere X_{n+1} data tutta la storia di ciò che è successo in passato, ovvero
P(X_{n+j}\mid X_n=i,\,X_{n-1}=i_{n-2}=i_{n-2},\,\dots,\,X_0=i_0)Vogliamo riuscire ad approssimare tutti gli infiniti termini X_{n-k}=i_{i-k} con un numero finito di quantità. Un sistema che rispetta la proprietà di Markov è un sistema nel quale l’intero insieme di informazioni necessarie per descriverlo è contenuto interamente negli ultimi stati del sistema. In particolare, nel caso in cui consideriamo soltanto l’ultimo stato del sistema a contenere tutte le informazioni, avremo a che fare con un processo di Markov del primo ordine, se invece consideriamo gli ultimi due stati del sistema parliamo di un processo di Markov del secondo ordine. Avremo dunque che per trovare X_{n+1} ci basterà sapere
P(X_{x+1}\mid X_{n}=i)\text{ oppure }P(X_{x+1}\mid X_{n}=i,\,X_{n-1}=i_{n-1})A parole: il passato e il futuro sono condizionalmente indipendenti dato il presente.
Consideriamo un sistema di Markov del primo ordine. Dal punto di vista grafico possiamo indicare tali probabilità tramite le frecce, indicandone il valore numerico sopra di esse.
Possiamo scrivere tali probabilità tramite una matrice di elementi q_{i,j}
Q=[q_{i,j}]=\begin{bmatrix}
1/3 & 2/3 & 0 & 0\\
1/2 & 0 & 1/2 & 0\\
0 & 0 & 0 & 1\\
1/2 & 0 & 1/4 & 1/4
\end{bmatrix}Dove ogni riga sommi a uno, per la definizione di probabilità (ma avremmo potuto scegliere anche la convenzione che ogni colonna sommi a uno—non importa quale convenzione si scelga, l’importante è mantenerla).
Supponiamo che al tempo n, X_n ha una distribuzione \vec{s} (che è un vettore, ovvero una matrice 1\times M). Vogliamo conoscere
\begin{aligned}
P(X_{n+1}\mid X_n=j)&=\sum_i P(X_{n+1}=j\mid X_{n}=i)P(X_n=i)\\[10pt]
&=\sum_i
s_i \, q_{i,j} \text{ è l'i-esimo elemento di $\vec{s}Q$}\\
&\text{dove $\vec{s}$ è di grandezza }1\times M \text{ e } Q \text{ di M}\times M\end{aligned}Si avrà:
- \vec{s}Q è la distribuzione al tempo n+1
- \vec{s}Q^2 è la distribuzione al tempo n+2
- \vec{s}Q^3 è la distribuzione al tempo n+3
- \dots
La matrice Q rende dunque possibile sapere tutti gli stati futuri al tempo n+m, dove m è l’esponente a cui eleviamo Q
Al primo grado avremo
P(X_{n+1}\mid X_n=i)=[q_{i,j}]Al secondo grado invece
\begin{aligned}
P(X_{n+2}\mid X_n=i)&=\sum_k P(X_{n+1}=j\mid X_{n+1}=k,\,\cancel{X_{n}=i})P(X_{n+1}\mid X_n=1)\\[10pt]
&=\sum_k q_{ik} q_{kj}\text{ è la }\\
&=\dots\\
&=P(X_{n+m}=j\mid X_{n}=i)=((i,\,j)\text{-esimo elemento di $Q^m$} )
\end{aligned}Per la proprietà di Markov abbiamo detto però che vogliamo tenere soltanto l’ultimo stato del sistema, dunque X_n=i è già inutili visto che conosciamo X_{n+1}.
Distribuzione stazionaria
Una distribuzione \vec{s} si dice stazionaria per una catena se \vec{s}Q=\vec{s} (cfr. autovettori, autovalori).
Catena irriducibile
Una catena si dice irriducibile se si riesce ad arrivare da ogni punto della catena a ogni altro punto della catena—in un numero finito di movimenti.
Stati ricorrenti
Uno stato (della catena) viene chiamato ricorrente se la catena tornerà in tale punto con probabilità unitaria. Altrimenti dichiamo che uno stato è transitorio.
Nota bene: se uno stato è ricorrente, allora verrà visitato infinite volte.
Stati assorbenti
Se da uno stato è impossibile uscire chiamiamo tale stato assorbente.
Il collegamento con i processi bayesiani
Se hai appunti con questo argomento scrivi a giacomo.dandria@esercizistem.com.