6.3 Processi di Markov a salti

I processi di Markov \((X_t)_{t \in \mathcal{T}}\) a tempi continui \[\mathcal{T} = [0,T]\] e a stati discreti sono detti a salti, perché le traiettorie “saltano” da uno stato all’altro – anche se la struttura dei tempi permetterebbe un passaggio continuo da uno stato all’altro, l’insieme degli stati non lo permette.

Come per le catene di Markov, ci limitiamo a considerare il caso di processi omogenei, ossia tali che, per ogni \(t \in [0,T]\), \(\delta t>0\) tale che \(t+\delta t \in [0,T]\), si abbia \[ P(X_{t+\delta t} = y | X_t = x) = P(X_{\delta t} = y| X_0 = x).\] In analogia con quanto accade per le catene di Markov, per descrivere completamente la legge di un processo di Markov a salti, è sufficiente indicare la densità marginale al tempo iniziale \((P(X_0 = x))_{x\in E}\) e una opportuna matrice che permetta di determinare le probabilità di transizione da uno stato all’altro. Nel caso dei processi di Markov a salti, essa è la matrice delle intensità di salto, definita come \[ \begin{split} L_{xy} & =\frac{d}{dt}\Bigr|_{\substack{t=0}} P(X_{t} =y| X_0 =x) \\ & = \lim_{\delta t \to 0}\frac{ P(X_{\delta t} = y | X_0 =x) - P(X_{0} = y | X_0 =x)}{\delta t},\end{split}\] dove si suppone che il limite esista (finito) per ogni coppia di stati \(x\), \(y \in E\).

Remark. La matrice \(L\) si ottiene come derivata della matrice (stocastica) delle intensità di salto. Pertanto, anche se \(L\) non è una matrice stocastica, essa eredita da questa alcune proprietà: dati \(x\), \(y \in E\),

• se \(x\neq y\), vale \(P(X_{0} = y | X_0 =x) = 0\) e quindi \[ L_{xy} =\frac{d}{dt} P(X_{t} =y| X_0 =x) = \lim_{\delta t \to 0}\frac{ P(X_{\delta t} = y | X_0 =x)}{\delta t} \ge 0\] è una quantità non-negativa (eventualmente nulla), ma non necessariamente minore di \(1\)
• se invece \(x=y\), allora \(P(X_0 = y| X_0 = x) = 1\) e quindi \[ L_{xy} =\frac{d}{dt} P(X_{t} =y| X_0 =x) = \lim_{\delta t \to 0}\frac{ P(X_{\delta t} = y | X_0 =x) -1}{\delta t} \le 0.\] Infine, la condizione che la somma su ciascuna riga valga \(1\) si traduce in \[ \sum_{y \in E} L_{xy} = \frac{d}{dt} \sum_{y \in E} P(X_{t} =y| X_0 =x) = \frac{d}{dt} 1 = 0,\] ossia la somma su ciascuna riga vale \(0\), o equivalentemente, isolando il termine nella somma in cui \(y=x\), \[ L_{xx} = - \sum_{y \neq x} L_{xy}.\]

Esempio 6.8 Lo stato di una macchina può essere spento (Off), in attesa (Standby) o acceso (On) e lo si modellizza tramite un processo di Markov a salti su \(E = \cur{\text{Off}, \text{Standby}, \text{On}}\), con matrice delle intensità di salto \[L = \bra{ \begin{array}{ccc} * & 5 & 10 \\ 1 & * & 3 \\ 0 & 4 & * \end{array}},\tag{6.5}\] dove non abbiamo neppure indicato le entrate sulla diagonale (che si ricavano imponendo la somma sulle righe nulla, quindi ad esempio nella prima riga vale \(-15\)).

Il problema che ora affrontiamo è se la matrice delle intensità di salto sia sufficiente a determinare la legge dell’intero processo (supponendo anche di conoscere la densità marginale al tempo \(0\)). La risposta è affermativa, e l’osservazione principale per dedurre risultati analoghi al caso delle catene di Markov è che i tempi continui \(\mathcal{T} = [0,T]\) possono essere ottenuti come un limite di tempi discreti \[ \mathcal{T}^\delta = \cur{0, \delta, 2\delta, \ldots, \lfloor T/ \delta \rfloor \delta },\] dove \(\lfloor T/\delta \rfloor\) indica il più grande numero naturale minore di \(T/\delta\). Se si considera il processo ristretto a tali tempi discreti, ossia si pone \[ X^\delta_k := X_{k \delta},\] esso è una catena di Markov con matrice di transizione \[ P^\delta_{xy} = P(X_{\delta} = y| X_0 = x) = Id + L \delta + O(\delta^2) \approx Id + L \delta.\] Indicando con \(\pi_{t}(x) = P(X_t = x)\) il vettore (riga) della densità discreta marginale al tempo \(t\), si ha per i tempi della forma \(t = h \delta\), \[ \pi_t = \pi_0 ( P^{\delta})^h \approx \pi_0 \bra{ Id + \frac{t L}{h}}^h,\] avendo scritto \(\delta = t/h\). Ora, fissato \(t \in [0,T]\) si possono trovare \(h \to \infty\) in modo che \(\delta \to 0\) e quindi, ricordando il limite notevole (che vale anche per le matrici) \[ \lim_{h \to \infty} \bra{Id + \frac{A}{h}}^h = \exp\bra{A}, \] si trova che \[ \pi_t = \pi_0 \exp\bra{ t L}.\] Pertanto, le densità delle marginali sono determinate dalla matrice \(L\) e dalla densità al tempo iniziale.

Esempio 6.9 Si consideri un processo di Markov a salti con matrice \(L\) come in (6.5). Supponendo che \(X_0 = \text{Off}\), possiamo determinare le densità marginali calcolando tramite R l’esponenziale di matrice (per fare questo è necessario caricare la libreria Matrix e usare la funzione expm())

# rappresentiamo lo stato iniziale come
# un vettore riga

dens_0 <- matrix(c(1, 0, 0), nrow = 1)

# definiamo la matrice delle intensità
# di salto

L <- matrix(c(-15, 5, 10, 1, -4, 3, 0, 4,
  -4), nrow = 3, byrow = TRUE)

# carichiamo la libreria Matrix

library("Matrix")

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

dens_01 <- dens_0 %*% expm(0.1 * L)
# per calcolare la densità al tempo 0.3
# possiamo ulteriormente moltiplicare
# la densità al tempo 0.1 per
# l'esponenziale exp(0.2 L)
dens_03 <- dens_01 %*% expm(0.2 * L)
dens_04 <- dens_03 %*% expm(0.1 * L)

# al solito per rappresentarle in un
# singolo grafico costruiamo una
# matrice a partire dalle densità
# (ciascuna densità è una riga). È
# necessario convertire in una matrice
# perché la libreria Matrix usa un
# altro oggetto per le matrici -- e il
# comando barplot non lo riconosce
# correttamente

dens_matrice <- as.matrix(rbind(dens_0, dens_01,
  dens_03, dens_04))

# Plottiamo il diagramma a barre

alternative <- c("Off", "Standby", "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_{0.1}", "X_{0.3}", "X_{0.4}"), cex = 0.8)

Figura 6.4: Grafico a barre della densità marginale del processo a salti ai tempi \(0\) (Off), \(0.1\), \(0.3\) e \(0.4\).

Remark. L’analoga dell’equazione ricorsiva (6.4) nel caso di processi di Markov a salti, è l’equazione differenziale ottenuta derivando la formula sopra: \[ \frac\tag{6.6} L (#eq:master-continua) \] Tale equazione lineare è detta anche equazione di Kolmogorov (in inglese Kolmogorov forward oppure master equation).

deltat <- 0.01
t <- seq(0, 0.5, by = deltat)
Q <- as.matrix(expm(deltat * L))

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)
lines(t, dens_matrice[, 3], col = miei_colori[3],
  type = "l", lwd = 3)



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

Figura 6.5: grafico delle densità marginali in funzione del tempo \(t \in [0,0.5]\) partendo dallo stato \(X_0 = \text{Off}\).

Con lo stesso argomento di approssimazione dei tempi continui tramite tempi discreti, possiamo considerare la probabilità di osservare un cammino che visiti nell’ordine gli stati \(x_0 \to x_1 \to \ldots \to x_n\). Trattandosi però di tempi continui, dobbiamo specificare i tempi di permanenza in ciascuno stato \(t_1, \ldots, t_n\), in modo che il processo “salti” al tempo \(t_1\) dallo stato \(x_0\) verso \(x_1\), al tempo \(t_1+t_2\) da \(x_1\) verso \(x_2\), e così via. Fissato \(\delta\) tale che \(t_1 = \delta h_1\), \(t_2 = \delta h_2\) ecc., si trova l’approssimazione \[ \begin{split} P( X^\delta = (x_0 \to x_1 \to \ldots \to x_n) ) \approx & P(X_0 = x_0) (1+ \frac{ t_1 L_{x_{0} x_{0}}}{h_1} )^{h_1} ( \delta L_{x_0 x_1})\cdot \\ & \cdot (1+ \frac{ t_2 L_{x_{1} x_{1}}}{h_2} )^{h_2} ( \delta L_{x_1 x_2})\cdot \ldots\\ & \cdot (1+ \frac{ t_n L_{x_{n-1} x_{n-1}}}{h_n} )^{h_n} ( \delta L_{x_{n-1} x_n}). \end{split} \] Al tendere di \(\delta\) a zero si trova che la probabilità tende a zero: tuttavia dividendo per \(\delta^n\) si ottiene una “densità” non nulla, data dall’espressione \[ P(X_0 = x_0) \prod_{k=1}^n \exp\bra{t_k L_{x_{k-1} x_{k-1}}} \prod_{k=1}^n L_{x_{k-1} x_k}.\] L’intepretazione rigorosa si ottiene introducendo le variabili aleatorie \(T_1\), \(T_2\), …, \(T_n\) che indicando appunto il tempo di permanenza del processo in ciascuno degli stati visitati \(x_0\), \(x_1\), …, \(x_{n-1}\). Inoltre, i tempi di salto sono dati dalle somme \(S_1 = T_1\), \(S_2 = T_1+T_2\), …, \(S_n = T_1+T_2+\ldots+T_n\). Con questa notazione, abbiamo ottenuto che \[ \begin{split} p(T_1 = t_1, X_{S_1} & = x_1, T_2 = t_2, X_{S_2} = x_2 \ldots, T_n = t_n, X_{S_n} = x_n) \\ & = P(X_0 = x_0) \prod_{k=1}^n \exp\bra{t_k L_{x_{k-1} x_{k-1}}} L_{x_{k-1} x_k},\end{split} \tag{6.7}\] dove la notazione “\(p\)” per la densità di probabilità si riferisce solo alle variabili continue \(T_1\), \(T_2\), …, \(T_n\), mentre le variabili \(X_{S_1}\), \(X_{S_2}\), …, \(X_{S_n}\) sono ovviamente discrete (questo è un caso in cui la densità congiunta non è né discreta né continua). La formula sopra contiene molti prodotti, il che suggerisce che vi siano variabili indipendenti. In effetti, si può anche riscrivere in questo modo, separando le variabili continue da quelle discrete: \[ P(X_{S_1} = x_1, X_{S_2} = x_2 \ldots, X_{S_n} = x_n) = P(X_0 =x_0) \prod_{k=1}^n \frac{ L_{x_{k-1} x_k}}{-L_{x_{k-1} x_{k-1}}},\] e \[ \begin{split} & p(T_1 = t_1, T_2 = t_2, \ldots, T_n = t_n| X_{S_1}= x_1, \ldots X_{S_n} = x_n) \\ & = P(X_0 = x_0) \prod_{k=1}^n (-L_{x_{k-1}x_{k-1}}) \exp\bra{t_k L_{x_{k-1} x_{k-1}}}.\end{split}\] In termini più intuitivi, la prima equazione mostra che le variabili \(X_0\), \(X_{S_1}\), …, \(X_{S_n}\) che indicano gli stati visitati dal processo sono una catena di Markov (a tempi discreti) con probabilità di transizione (per \(x\neq y\)) \[ Q_{xy} = \frac{L_{xy}}{-L_{xx}},\] mentre, supponendo noti gli stati visitati, i tempi di permanenza \(T_1\), \(T_2\), …, \(T_n\) sono variabili aleatorie indipendenti tra loro, e ciascuna \(T_k\) ha densità continua esponenziale di parametro \(-L_{x_{k-1}x_{k-1}}\).

Remark. Le formule trovate permettono una descrizione alternativa di un processo di Markov a salti (ad esempio utile per simularli). Una traiettoria del processo si ottiene a partire da una traiettoria della catena di Markov con matrice di transizione \(Q\) e successivamente campionando i tempi di permanenza indipendenti con densità esponenziale dei parametri opportuni.

6.3.1 Esercizi

Esercizio 6.2 Si consideri una matrice di intensità di salto (sull’insieme degli stati \(E = \cur{1,2,3}\)) \[ L = \bra{ \begin{array}{lll} * & 2 & 0 \\ 0 & * & 3 \\ 1 & 0 & * \end{array}}.\] Supponendo che al tempo iniziale sia \(X_0 = 1\), calcolare le densità delle marginali al tempo \(t=1\) (usare eventualmente comandi R per semplificare i calcoli) e rappresentare graficamente tale densità. Si faccia lo stesso (numericamente e graficamente) per tutti i tempi \(t \in [0,1]\).