6.2 Catene di Markov

In questa sezione studiamo i processi di Markov \((X_t)_{t \in \mathcal{T}}\) a tempi discreti, in particolare poniamo \[\mathcal{T} = \cur{0,1,2,\ldots, n} \subseteq \mathbb{N}\] e stati discreti (spesso finiti). Per semplificare molti risultati aggiungeremo anche l’ipotesi che siano processi omogenei. In particolare le probabilità di transizione tra \(k\) e \(k+1 \in \mathcal{T}\) dipendono solo dagli stati \(x\), \(y \in E\), e non da \(k\): \[ P(X_{k+1} = y | X_k = x) = P(X_{1} = y| X_0=x).\] La terminologia più precisa per tali processi è di catene di Markov omogenee (homogeneous Markov chains in inglese) ma spesso omettiamo per brevità il termine omogenee e scriviamo solo catene di Markov .

Remark. L’insieme dei tempi \(\mathcal{T}\) non deve necessariamente essere della forma \(\cur{0,1, \ldots, n}\), ma basta che sia un qualsiasi “intervallo” discreto \(\cur{m, m+1, m+2, \ldots, m+n} \subseteq \mathbb{Z}\) costituito da tempi equispaziati. Spesso è comodo considerare anche infiniti tempi e porre direttamente \(\mathcal{T} = \mathbb{N}\) o anche \(\mathcal{T} = \mathbb{Z}\).

Le probabilità di transizione \[ Q_{x \to y} = P(X_1 = y | X_0=x)\] al variare di \(x\), \(y \in E\) sono spesso raccolte in una matrice quadrata, con tante righe e colonne quanti gli stati (eventualmente infinite), \(Q \in \mathbb{R}^{E \times E}\), detta matrice di transizione associata alla catena di Markov \(X\).

Esempio 6.2 Lo stato di una macchina – che può essere accesa, ON, oppure spenta, OFF – è rappresentato tramite una catena di Markov sull’insieme degli stati \(E = \cur{\text{OFF}, \text{ON}}\) con probabilità di transizione \[ P(X_1 = \text{ON} | X_0 = \text{OFF}) = 10\%,\]

\[ P(X_1 = \text{OFF} | X_0 = \text{ON}) =70\%.\] Poiché \[ P(X_1 = \text{OFF} | X_0 = \text{OFF}) = 1- P(X_1 = \text{ON} | X_0 = \text{OFF}) = 90\%,\] e \[ P(X_1 = \text{ON} | X_0 = \text{ON}) = 1- P(X_1 = \text{OFF} | X_0 = \text{ON}) = 30\%,\] possiamo definire la matrice di transizione (ordinando gli stati nell’ordine \(\text{OFF}\), \(\text{ON}\)) come \[\bra{ \begin{array}{cc} Q_{\text{OFF} \to \text{OFF}} & Q_{\text{OFF} \to \text{ON}} \\ Q_{\text{ON} \to \text{OFF}} & Q_{\text{ON} \to \text{ON}} \end{array}} = \bra{ \begin{array}{cc} 0.9 & 0.1 \\ 0.7 & 0.3 \end{array}}. \tag{6.2}\]

Remark. Come si può osservare anche nell’Esempio 6.2, la somma delle probabilità in ciascuna riga della matrice di transizione vale \(1\), questo perché, per ogni \(x\in E\), le probabilità \[ (Q_{x \to y})_{y \in E} = ( P(X_1 = y| X_0 = x))_{y \in E}\] sono la densità discreta della variabile \(X_1\) rispetto all’informazione \(X_0=x\).

In generale, una qualsiasi matrice \(Q\) con entrate a valori in \([0,1]\) e tale che la somma sulle righe sia costante e uguale ad \(1\) è detta matrice stocastica. Le matrici di transizione delle catene di Markov sono tutte matrici stocastiche.

Se anche la somma sulle colonne è uguale ad \(1\) è detta matrice bistocastica (vedremo l’utilità di questo concetto più avanti).

Grazie all’identità (6.1), la legge di una catena di Markov è determinata dalla legge marginale al tempo iniziale (diciamo \(0 \in \mathcal{T}\)) e dalla matrice di transizione. Infatti, vale \[\begin{equation} P(X_0 = x_0, X_1=x_1, \ldots X_n = x_n) = P(X_0 = x_0) \prod_{k=1}\tag{6.3}, (#eq:markov-chain-path) \end{equation}\] che permette di calcolare la probabilità di osservare che la catena \(X\) percorra un cammino, ossia una sequenza ordinata di stati \(\gamma = (x_0 \to x_1 \to \ldots \to x_n)\): \[ P(X = \gamma) = P(X_0 = x_0) Q_\gamma\] dove il “peso” del cammino \(\gamma\), è il prodotto delle probabilità di transizione \[ Q_\gamma = \prod_{k=1}^n Q_{x_{k-1}\to x_{k}}.\] Vediamo un esempio.

Esempio 6.3 Si consideri una catena di Markov come nell’Esempio 6.2, con matrice di transizione (6.2) e si supponga che valga \(X_0=\text{OFF}\). Allora la probabilità di osservare il cammino \[\text{OFF} \to \text{OFF} \to \text{OFF} \to \text{ON} \to \text{OFF} \to \text{ON}\] è data dal prodotto \[ 0.9 \cdot 0.9 \cdot 0.1\cdot 0.7\cdot 0.1 = 0.00567.\]

Remark. Per calcolare la probabilità di una qualsiasi affermazione \(A\) circa una catena di Markov \((X_n)_{n=0}^\infty\), è quindi sufficiente rappresentare \(A\) in termini di cammini (a partire dal tempo iniziale) e sommare le probabilità corrispondenti ottenute tramite la formula sopra, purché gli eventi relativi a cammini diversi siano a due a due incompatibili. Questo avviene anche se i cammini hanno lunghezze diverse, ma nessun cammino considerato si può ottenere come prolungamento di un altro.

Esempio 6.4 Si consideri una catena di Markov come nell’Esempio 6.2, con matrice di transizione (6.2) e \(X_0=\text{OFF}\). Allora la probabilità \[ P( \text{$X_2 =\text{OFF}$ oppure $X_3 = \text{ON}$ } ) = 0.916\] perché l’affermazione sopra equivale ad osservare uno dei seguenti cammini (a partire dal tempo \(0\) in \(\text{OFF}\)) \[ \begin{array} {|llll|l|} X_0 & X_1 & X_2 & X_3 & Q_\gamma\\ \hline \text{OFF} & \to \text{OFF} & \to \text{OFF}& & 0.9 \cdot 0.9 \\ \text{OFF} & \to \text{ON} &\to \text{OFF}& & 0.1\cdot 0.7\\ \text{OFF} & \to \text{OFF} &\to \text{ON} & \to \text{ON }& 0.9\cdot 0.1\cdot 0.3\\ \text{OFF} & \to \text{ON} & \to \text{ON} & \to \text{ON}& 0.1\cdot 0.3 \cdot 0.3\\ \hline \end{array}\]

Notiamo che gli eventi corrispondenti sono a due a due incompatibili perché nessuno dei quattro cammini si ottiene come prolungamento di un altro. Sommando i pesi dei cammini si ottiene la probabilità cercata.

L’osservazione sopra si giustifica considerando ad esempio la rappresentazione tramite diagrammi ad albero dei sistemi di alternative associati a ciascuna variabile \(X_n\) di una catena di Markov. Nella pratica, tuttavia, tale rappresentazione diventa troppo pesante, e si preferisce “comprimerla” introducendo un grafo pesato orientato i cui nodi corrispondono agli stati \(i \in E\), e l’arco da \(i\) ad \(j \in E\) è pesato con la probabilità di transizione \(Q_{ij}\) (se la probabilità è nulla non viene rappresentato). Il grafo associato permette facilmente di calcolare le probabilità \[ \prod_{k=1}^n Q_{x_{k-1} x_k}\] associate ad un cammino \(x_0 \to x_1 \to \ldots \to x_n\), ma non include la probabilità marginale al tempo \(0\) (necessaria per determinare completamente la probabilità del cammino).

Esempio 6.5 La rappresentazione grafica di una catena con matrice di transizione (6.2) è

Tornando al caso generale, le densità marginali di una catena di Markov si ottengono sommando la densità congiunta su tutti i possibili valori delle altre variabili. Pertanto si trova che \[ P(X_n = x_n) = \sum_{x_0, x_1, \ldots x_{n-1} \in E} P(X_0 = x_0)\prod_{k=1}^n Q_{x_{k-1}x_k}.\] Per quanto esplicita, la sommatoria sopra è estesa su un grande numero di valori. Usando direttamente la proprietà di Markov, è possibile ottenere un’equazione ricorsiva per la densità marginale al tempo \(n\): \[\begin{split} P(X_n = x_n) & = \sum_{x_{n-1} \in E} P(X_n = x_n | X_{n-1} = x_{n-1}) P(X_{n-1} = x_{n-1})\\ & = \sum_{x_{n-1} \in E} Q_{x_{n-1}x_{n}} P(X_{n-1} = x_{n-1}).\end{split}\] Se intepretiamo \(Q\) come una matrice in \(\R^{E \times E}\), allora una densità di probabilità \(P(X_n = \cdot)\) si può pensare come un vettore in \(\R^{E}\). In particolare, è utile pensarlo come vettore riga \[ \pi_n(x) = P(X_n = x)\] (ossia con tante colonne quante \(E\)), così la formula sopra diventa semplicemente un prodotto tra matrici: \[\tag{6.4}Q, (#eq:master-discreta)\] che iterando ci porta ad una versione compatta della formula esplicita sopra: \[ \pi_n = \pi_{n-1} Q = \pi_{n-2} Q^2 = \ldots = \pi_0 Q^n,\] dove le potenze \(Q^k\) sono intese nel senso del prodotto di matrici.

Esempio 6.6 In R il prodotto tra matrici (di dimensioni compatibili) si ottiene tramite il comando %*%. Possiamo quindi calcolare e rappresentare graficamente le densità marginali di una catena avente matrice di transizione (6.2) e marginale al tempo \(0\) uniforme sui due stati.

# rappresentiamo lo stato iniziale come
# un vettore riga

dens_0 <- matrix(c(1/2, 1/2), nrow = 1)

# definiamo la matrice di transizione

Q <- matrix(c(0.9, 0.1, 0.7, 0.3), nrow = 2,
  byrow = TRUE)

# otteniamo le densità marginali
# tramite prodotto vettore*matrice

dens_1 <- dens_0 %*% Q
dens_2 <- dens_1 %*% Q
dens_3 <- dens_2 %*% Q

# al solito per rappresentarle in un
# singolo grafico costruiamo una
# matrice a partire dalle densità
# (ciascuna densità è una riga)

dens_matrice <- rbind(dens_0, dens_1, dens_2,
  dens_3)

# Plottiamo il diagramma a barre

alternative <- c("Off", "On")
colori <- miei_colori[1:4]

barplot(dens_matrice, beside = TRUE, col = colori,
  names.arg = alternative, ylab = "probabilità",
  xlab = "stato")

# Aggiungiamo una legenda

legend("topright", fill = colori, legend = c("X_0",
  "X_1", "X_2", "X_3"), cex = 0.8)

Figura 6.2: Grafico a barre della densità marginale della catena ai tempi \(0\) (uniforme), \(1\), \(2\) e \(3\).

In alternativa, possiamo rappresentare come funzione del tempo le densità marginali, come segue:

t <- seq(0, 5, by = 1)

dens <- dens_0
dens_matrice <- dens_0

for (iter in 2:length(t)) {
  dens <- dens %*% Q
  dens_matrice <- rbind(dens_matrice, dens)
}

plot(t, dens_matrice[, 1], col = miei_colori[1],
  ylim = c(0, 1), ylab = "probabilità",
  type = "l", lwd = 3)
lines(t, dens_matrice[, 2], col = miei_colori[2],
  type = "l", lwd = 3)



legend("topright", fill = colori, legend = c("Off",
  "On"), cex = 0.8)

Figura 6.3: grafico delle densità marginali in funzione del tempo \(t = 0, 1, \ldots, 5\) partendo dalla densità uniforme al tempo \(0\).

Ovviamente le due curve sommano a \(1\) in ogni tempo, ma con più di due stati è comunque utile rappresentarle tutte.

6.2.1 Esercizi

Esempio 6.7 Si consideri la matrice \[ Q = \bra{ \begin{array}{lll} 0.1 & 0.3 & * \\ * & 0.5 & 0.4 \\ * & 0.1 & 0.9 \end{array}}.\] Completare la matrice affinchè sia la matrice di transizione di una catena di Markov sull’insieme degli stati \(E = \cur{1,2,3}\). Supponendo che al tempo iniziale \(X_0 = 2\), calcolare le densità delle marginali ai tempi \(t=1,2,3\) (usare eventualmente comandi R per semplificare i calcoli) e rappresentare graficamente tali densità. Calcolare la probabilità dell’evento “\(X_t \neq 3\) per ogni \(t =1,2,3\)”.