Equazioni di Kolmogorov — ingegnerismo.it

Le equazioni di Kolmogorov sono le equazioni differenziali che descrivono come evolvono nel tempo le probabilità di transizione di una catena di Markov a tempo continuo. Collegano il comportamento infinitesimale del processo, raccolto nel generatore infinitesimale $Q$ , con le probabilità a tempo finito $P(t)$ .

Questa voce usa la convenzione a righe:

P_{ij}(t)=\mathbb{P}(X_t=j\mid X_0=i),

quindi la riga $i$ di $P(t)$ contiene la distribuzione dello stato al tempo $t$ se il processo parte da $i$ . Con questa convenzione, una distribuzione iniziale riga $\alpha(0)$ evolve come:

\alpha(t)=\alpha(0)P(t).

Le equazioni di Kolmogorov sono la versione infinitesimale delle equazioni di Chapman-Kolmogorov: Chapman-Kolmogorov compone transizioni su intervalli finiti; Kolmogorov descrive la derivata istantanea di quella composizione.

Dati del problema

Sia $Q=(q_{ij})$ il generatore della catena. Per $i\ne j$ , $q_{ij}$ è il tasso istantaneo di salto da $i$ a $j$ ; gli elementi diagonali sono scelti in modo che ogni riga sommi a zero:

q_{ij}\ge0\quad(i\ne j), \qquad q_{ii}=-\sum_{j\ne i}q_{ij}, \qquad \sum_j q_{ij}=0.

La matrice $Q$ non è una matrice di probabilità: contiene tassi. La matrice $P(t)$ , invece, è stocastica per ogni $t\ge0$ e soddisfa:

P(0)=I, \qquad \sum_j P_{ij}(t)=1.

Nel caso omogeneo finito, la soluzione compatta è:

P(t)=e^{Qt}.

Le equazioni di Kolmogorov spiegano perché questa esponenziale di matrice è la transizione naturale: trasforma tassi infinitesimali in probabilità finite su un intervallo di durata $t$ .

Equazione forward

L’equazione forward, o equazione di Kolmogorov in avanti, è:

\dfrac{dP(t)}{dt}=P(t)Q.

In componenti:

\dfrac{dP_{ij}(t)}{dt} = \sum_k P_{ik}(t)q_{kj}.

La lettura è orientata allo stato finale $j$ . Per arrivare in $j$ al tempo $t+dt$ , il processo può trovarsi in uno stato intermedio $k$ al tempo $t$ e poi saltare istantaneamente da $k$ a $j$ con tasso $q_{kj}$ . La somma su $k$ raccoglie tutti i flussi probabilistici che entrano o escono dallo stato finale.

Se $\alpha(t)$ è una distribuzione riga sugli stati, la sua evoluzione soddisfa la master equation:

\dfrac{d\alpha(t)}{dt}=\alpha(t)Q.

Questa è spesso la forma più usata in affidabilità, teoria delle code, modelli epidemici e sistemi riparabili, perché descrive direttamente la probabilità di trovarsi in ciascuno stato al tempo $t$ .

Equazione backward

L’equazione backward, o equazione di Kolmogorov all’indietro, è:

\dfrac{dP(t)}{dt}=QP(t).

In componenti:

\dfrac{dP_{ij}(t)}{dt} = \sum_k q_{ik}P_{kj}(t).

Questa volta la lettura è orientata allo stato iniziale $i$ . Il processo parte da $i$ , può fare come primo salto infinitesimo verso uno stato $k$ con tasso $q_{ik}$ e poi, da $k$ , evolvere fino a $j$ nel tempo residuo. Per questo la somma agisce sulla prima transizione dopo la partenza.

Forward e backward non indicano simulare il processo avanti o indietro nel tempo. Sono due decomposizioni analitiche della stessa probabilità di transizione: una guarda l’ultimo salto verso la destinazione, l’altra il primo salto fuori dall’origine.

Derivazione dal semigruppo

La proprietà di Markov omogenea implica il semigruppo:

P(t+s)=P(t)P(s), \qquad P(0)=I.

Per intervalli piccoli, il generatore dà:

P(h)=I+hQ+o(h).

Usando $P(t+h)=P(t)P(h)$ si ottiene:

\dfrac{P(t+h)-P(t)}{h} = P(t)\dfrac{P(h)-I}{h} \longrightarrow P(t)Q.

Questa è l’equazione forward. Usando invece $P(t+h)=P(h)P(t)$ si ottiene:

\dfrac{P(t+h)-P(t)}{h} = \dfrac{P(h)-I}{h}P(t) \longrightarrow QP(t),

cioè l’equazione backward. Nel caso finito omogeneo entrambe hanno la stessa soluzione $P(t)=e^{Qt}$ .

Esempio a due stati

Consideriamo un sistema con due stati:

$0$ : funzionante;
$1$ : guasto.

Supponiamo che il guasto avvenga con tasso $\lambda$ e la riparazione con tasso $\mu$ . Il generatore è:

Q= \begin{pmatrix} -\lambda & \lambda\\ \mu & -\mu \end{pmatrix}.

Se $p_1(t)$ è la probabilità che il sistema sia guasto al tempo $t$ , partendo da funzionante, l’equazione forward porta a:

\dfrac{dp_1(t)}{dt} = \lambda\bigl(1-p_1(t)\bigr)-\mu p_1(t).

Il primo termine è il flusso probabilistico verso il guasto; il secondo è il flusso di uscita dal guasto per riparazione. Con $p_1(0)=0$ , la soluzione è:

p_1(t)= \dfrac{\lambda}{\lambda+\mu} \left(1-e^{-(\lambda+\mu)t}\right).

Il limite di lungo periodo è:

\lim_{t\to\infty}p_1(t) = \dfrac{\lambda}{\lambda+\mu}.

Questa quantità è l’indisponibilità stazionaria del sistema nel modello a due stati. L’esempio mostra il valore ingegneristico delle equazioni: i tassi di evento diventano probabilità transitorie e indicatori di disponibilità.

Convenzioni riga e colonna

Molti errori nascono dalla convenzione usata. In questa voce le distribuzioni sono vettori riga e il generatore agisce a destra:

\alpha'(t)=\alpha(t)Q.

Se invece si usano distribuzioni colonna $p(t)$ , la stessa evoluzione si scrive:

p'(t)=Q^T p(t).

Le due forme descrivono lo stesso processo, ma matrici, trasposte e ordine delle moltiplicazioni cambiano. Prima di applicare formule da testi diversi conviene verificare sempre se il libro usa vettori riga o vettori colonna.

Stati finiti, infiniti e generatori dipendenti dal tempo

Su spazi di stato finiti, se $Q$ è costante, la teoria è pulita: $P(t)=e^{Qt}$ , forward e backward sono entrambe soddisfatte e $P(t)$ resta una matrice stocastica. Su spazi numerabili infiniti servono condizioni aggiuntive, per esempio non esplosione del processo, controllo dei tassi e buona definizione del semigruppo.

Se il generatore dipende dal tempo, $Q(t)$ , la soluzione non è in generale $e^{Q(t)t}$ . L’ordine temporale dei generatori conta: matrici a tempi diversi possono non commutare. In questi casi si usano equazioni differenziali non autonome, prodotti ordinati nel tempo o integrazione numerica.

Le equazioni di Kolmogorov hanno anche versioni per processi markoviani a stato continuo. In quel contesto diventano equazioni differenziali alle derivate parziali; l’equazione forward è spesso collegata alla Fokker-Planck. La voce qui resta concentrata sul caso a stati discreti, che è quello delle catene di Markov a tempo continuo.

Uso ingegneristico

Le equazioni di Kolmogorov permettono di calcolare probabilità transitorie, disponibilità, occupazione di code, rischio di guasto entro una finestra temporale, probabilità di saturazione e comportamento di sistemi con riparazioni. Sono utili quando il regime stazionario non basta: avviamenti, missioni di durata finita, manutenzione programmata, stati degradati e fasi di emergenza sono problemi transitori.

In affidabilità, una distribuzione iniziale concentrata nello stato funzionante può essere propagata fino al tempo di missione. In teoria delle code, la probabilità di avere $n$ clienti al tempo $t$ può essere ottenuta risolvendo la master equation. In modelli epidemici o di rete, i tassi di transizione codificano contagi, recuperi, guasti, riparazioni o cambi di configurazione.

Errori comuni

Il primo errore è trattare $Q$ come una matrice di probabilità. Le sue righe sommano a zero, gli elementi diagonali sono negativi e gli elementi fuori diagonale sono tassi.

Il secondo errore è invertire forward e backward senza controllare la convenzione riga/colonna. La formula corretta dipende da quale lato agisce il generatore.

Il terzo errore è dimenticare la condizione iniziale $P(0)=I$ . Senza condizione iniziale, l’equazione differenziale non determina una transizione unica.

Il quarto errore è usare direttamente $e^{Qt}$ quando $Q$ dipende dal tempo o quando lo spazio di stato infinito richiede condizioni tecniche non verificate.

Il quinto errore è confondere probabilità transitorie e distribuzione stazionaria. Le equazioni di Kolmogorov descrivono l’intero andamento temporale; il limite di lungo periodo, quando esiste, è solo una parte dell’informazione.

Vedi anche: generatore infinitesimale, catena di Markov a tempo continuo, equazioni di Chapman-Kolmogorov, matrice esponenziale, distribuzione stazionaria e formulario di processi stocastici e affidabilità.