Capitolo 2 - Modelli di sistemi: processi stocastici
I processi stocastici costituiscono una classe di modelli di sistemi che permette lo studio e l’analisi dei sistemi. In questo capitolo introduciamo i processi stocastici Markoviani per la loro applicazione all’analisi delle prestazioni di sistemi. In particolare, richiamiamo brevemente la definizione e classificazione dei processi stocastici che costituiscono la base dei modelli di sistemi che tratteremo in seguito.
2.1 Processi stocastici
Un processo stocastico (p.s.) è definito come una famiglia di variabili casuali X = {X(t) | t∈T} definite su uno spazio di probabilità Ω, ed indiciate dal parametro t, dove t varia in un insieme indice T.
L’indice t è usualmente detto tempo. Ogni variabile casuale (v.c.) X(t) assume valori, detti stati della v.c., in un insieme E detto spazio degli stati del processo stocastico. Poiché ogni v.c. è definita come una funzione da uno spazio campione S all’insieme dei reali, un processo stocastico è un insieme di funzioni {X(t,s) | t∈T, s∈S}. Fissato un particolare valore dell’indice t=t0 la funzione X(t 0,s), che indichiamo con X(t0), è una v.c. sullo spazio campione S. Fissato un particolare punto dello spazio s0∈S la funzione X(t,s 0) è una realizzazione del processo stocastico. Al variare di s e t si ha una famiglia di v.c., ovvero il processo stocastico.
I processi stocastici possono essere classificati in base alle seguenti caratteristiche:
• spazio degli stati E
• indice tempo
• tipo di dipendenza stocastica fra le v.c..
• Lo spazio degli stati E può essere discreto o continuo. Nel primo caso il processo stocastico a spazio discreto è anche detto catena e lo spazio E è spesso indicato come l’insieme degli interi non negativi. Nel secondo caso l’insieme dei valori assunti dalle v.c. non è finito o numerabile e il processo stocastico è a spazio continuo.
• L’indice tempo a sua volta può essere discreto o continuo. Un processo stocastico a tempo discreto è anche detto sequenza stocastica ed è denotato come {Xn | n ∈ T } dove l’insieme T è finito o numerabile. In questo caso i cambiamenti di stato si osservano soltanto a determinati istanti, finiti o numerabili. Al contrario, se i cambiamenti di stato avvengono in un qualsiasi istante in un insieme finito o infinito di intervalli reali, allora si ha un processo a tempo continuo, denotato come {X(t) | t∈T}.
Esempio. Il numero di pazienti ricoverati in un ospedale in funzione del tempo, osservati alle ore 8 di ogni giorno, è un processo stocastico, in cui lo spazio degli stati E è discreto (un sottoinsieme finito dei naturali) e il tempo è discreto. La temperatura misurata in una stanza in funzione del tempo, osservata ad ogni istante, è un processo stocastico, con spazio degli stati E continuo e tempo continuo.
Esempio. Consideriamo un sistema di elaborazione rappresentato come una singola risorsa a cui arrivano dall’esterno job a tempi casuali e che, dopo un possibile tempo di attesa, vengono elaborati ed infine lasciano il sistema. Se indichiamo con Nk il numero di job presenti nel sistema all’istante di arrivo del k-simo job al sistema, allora {Nk | k=1,2,...} è un p.s. a spazio discreto E=N={0,1,2,...} e tempo discreto T={1,2,...}. Se invece consideriamo il numero X(t) di job presenti nel sistema al tempo t, il p.s. {X(t) | t ∈ T } è a spazio discreto E=N e tempo continuo T=R0+={t | 0 ≤t≤ ∞ }. Infine se indichiamo con W k il tempo di attesa del k-simo job nel sistema prima di ricevere servizio e con Y(t) il tempo di servizio cumulativo di tutti i job presenti nel sistema al tempo t, allora il p.s. {Wk | k=1,2,...} è a spazio continuo E=R0+ e a tempo discreto T={1,2,...}, mentre il p.s. {Y(t) | t ∈ T } è sia a spazio continuo E=R0+ che tempo continuo T=R0+.
• La dipendenza stocastica fra variabili casuali X(t) per diversi valori di t (o Xn per diversi valori di n, nel caso di tempo discreto) caratterizza un processo stocastico e talora semplifica la sua descrizione. La funzione che descrive le dipendenze stocastiche fra le v.c. di un p.s. è la funzione di distribuzione di probabilità congiunta per le v.c. X=[X(t1),X(t2),...,X(tn)], denotata come
FX (x;t) = Prob{ X(t1)≤x1 ; X(t2)≤x2 ;...; X(tn)≤xn}
al variare di n e di x=[x1,x2,...,xn] e t=[t1,t2,...,tn], con xi∈E, ti∈T, 1≤i≤n, n≥1, e t1<t2<...<tn. La descrizione completa di un processo in termini di funzione di distribuzione congiunta è data da FX (x;t), ∀x, ∀t, ∀n. Per molti processi di interesse pratico, sfruttando particolari proprietà è però possibile definire una descrizione del processo molto più semplice.
Introduciamo ora una classificazione dei processi stocastici in base al tipo di dipendenza stocastica fra le v.c. che lo compongono.
Un processo stocastico è stazionario in senso stretto se la funzione di distribuzione FX (x;t) è invariante rispetto ad uno spostamento sull’asse del tempo T, ovvero se per ogni costante t
FX (x;t+τ) =FX (x;t) dove t+τ=[t1+τ,t2+τ,...,tn+τ], e per ogni x, t ed n.
Un processo stocastico è stazionario in senso largo se i primi due momenti della distribuzione sono indipendenti dalla posizione sull’asse T, ovvero se la media E[X(t)]
e la varianza Var[X(t)] sono costanti rispetto al tempo t∈T e se E[X(t1), X(t2)]
dipende solo da |t1-t2| e non dai singoli valori t1, t2∈T. In tal caso la funzione di autocovarianza Cov[X(t1),X(t2)]=E[(X(t1)-E[X(t1)]) (X(t2)-E[Xt2)])] può essere espressa come funzione della sola differenza |t1-t2| ed è una funzione pari.
Un processo stocastico è indipendente se la funzione di distribuzione congiunta è fattorizzabile nelle singole funzioni di distribuzione marginali:
FX( x ; t ) = ∏
i=1 n
FXi(xi ; ti ) =∏
i=1 n
Prob{X(ti ) ≤ xi }
Un processo stocastico a tempo discreto {Xn | n=1,2,...} è di rinnovamento se le v.c. X1, X2,... sono indipendenti, identicamente distribuite (i.i.d.) e a valori non negativi. In altre parole, un processo stocastico di rinnovamento si ripete probabilisticamente, ovvero è possibile identificare una sequenza di punti detti di rigenerazione, a partire dai quali il processo si comporta, in termini probabilistici, sempre nello stesso modo. Il tempo fra due punti di rigenerazione è detto ciclo di rigenerazione.
Un processo stocastico a tempo discreto {Xn | n ∈ T } è di Markov se la probabilità di stato al tempo n+1 dipende soltanto dallo stato al tempo attuale, n, e non dalla storia precedente, ovvero se per ogni n>0 e per ogni valore degli stati j, i0, i1,..., in ∈ E si ha:
Prob {Xn+1 = j | X0 = i0 ; X1 = i1 ;...; Xn = in} = Prob {Xn+1 = j | Xn = in} (2.1).
In un processo stocastico Markoviano la dipendenza stocastica fra le variabili casuali è quindi limitata nel tempo ad un passo. Lo stato corrente raccoglie in sè tutta la storia passata.
Un p.s. a tempo continuo {X(t) | t ∈ T } è di Markov se per ogni sequenza di valori t0<t1<...<tn<t la distribuzione di probabilità di X(t) condizionata a X(t0), X(t1),..., X(tn) dipende soltanto dallo stato X(tn), per ogni n>0 e per ogni valore degli stati j, i0, i1,..., in ∈ E:
Prob {X(t)=j | X(t0) = i0; X(t1) = i1;...;X(tn) = in} = Prob {X(t)=j | X(tn) = in} (2.2).
Dalla definizione di processo Markoviano si può ricavare un vincolo sulla
tempo discreto il tempo di permanenza in uno stato è un v.c. geometrica, mentre per un processo di Markov a tempo continuo è un v.c. esponenziale. Questo vincolo deriva dalla proprietà di assenza di memoria indotta sulla v.c. dal processo Markoviano.
Come è noto le uniche distribuzioni che godono della proprietà di assenza di memoria sono, rispettivamente, la geometrica fra le distribuzioni discrete e l’esponenziale fra le continue.
Se si assume che la distribuzione di probabilità di permanenza in uno stato non sia geometrica (per tempo discreto) o esponenziale (per tempo continuo), ma generale, allora si ha un processo stocastico di semi-Markov. In questo caso le transizioni fra stati del processo avvengono ad istanti di tempo distribuiti arbitrariamente. Se consideriamo il p.s. ai soli istanti in cui avvengono le transizioni fra stati, allora ritroviamo un p.s. di Markov, detto immerso (embedded).
Un p.s. di Markov a spazio discreto E è anche detta catena di Markov.
Una catena di Markov è di nascita-morte (birth-death) se le uniche transizioni possibili che il processo può effettuare sono soltanto fra stati vicini. Indicando lo spazio degli stati E come l’insieme di numeri naturali, nel caso di tempo discreto, se lo stato Xn=i allora lo stato al tempo successivo può soltanto essere Xn+1∈{i-1, i, i+1},
∀i∈E. La particolare struttura di tali processi rende particolarmente semplice la loro analisi.
Un random walk è un processo stocastico {Xn | n=1,2,...} che può essere pensato come la rappresentazione del movimento di una particella nello spazio, identificandone la sua posizione al tempo n, n>0. Tale posizione dipende dalla posizione precedente e da una v.c. indipendente dallo stato del processo e con distribuzione arbitraria. Formalmente un p.s. random walk è definito come {Xn | n≥0}
con X0=0 e
Xn= Y1+ Y2+ ... + Yn n>0
e dove Yi, i>0, è una sequenza di v.c. indipendenti e con identica distribuzione (i.i.d.).
Il p.s. random walk è discreto (o continuo) se le v.c.Yi, i>0, sono discrete (o continue).
In un p.s. random walk discreto la probabilità di transizione fra due stati i e j dipende soltanto dalla loro differenza (j-i). Ad esempio il numero di teste osservate in una sequenza indipendente di lanci di moneta è un p.s. random walk discreto.
2.2 Processo di Poisson
Il processo stocastico di Poisson riveste un ruolo fondamentale nella definizione e soluzione di modelli stocastici. Esso può essere definito in diversi modi equivalenti.
Indichiamo con N(t), t≥0, il numero di eventi osservati in un intervallo di tempo [0,t].
SISTEMA
arrivi partenze
Fig. 2.1 - Sistema aperto -
Ad esempio, consideriamo un sistema aperto, rappresentato in Fig. 2.1, a cui arrivano dall’esterno dei job (o utenti) i quali, dopo aver speso un certo tempo nel sistema, lo lasciano. Rappresentiamo l’evoluzione nel tempo di tale sistema con la v.c. N(t) che indica il numero di arrivi osservati al sistema nell’intervallo [0,t]. Tale processo è anche detto processo d’arrivo. Inoltre sia Xi la v.c. che indica il tempo che intercorre fra l’arrivo dell’(i-1)-esimo job e l’arrivo dell’i-esimo job al sistema, per i>1, mentre X1 indica il tempo di arrivo del primo job. Se le v.c. Xi, i>0, sono i.i.d., allora il processo stocastico {N(t) | t≥0} è di rinnovamento.
Inoltre se le v.c. Xi, i>0, sono i.i.d. con distribuzione esponenziale di parametro λ, allora il processo stocastico {N(t) | t≥0} è di Poisson.
Il parametro λ rappresenta il tasso di arrivo al sistema. Il processo è omogeneo se λ non varia nel tempo. La v.c. N(t) ha quindi distribuzione di probabilità di Poisson con parametro λt , ovvero :
Prob { N(t) = i } = e -λ t i!
(λt)i
i ≥ 0 E[N(t)] = Var[N(t)] = λt (2.3).
In modo equivalente il processo di Poisson può essere definito come il p.s. {N(t), t≥0} che indica il numero di eventi osservati in un intervallo di tempo [0,t], per cui N(0)=0, e che soddisfa le seguenti condizioni:
1) il numero di eventi in intervalli disgiunti sono stocasticamente indipendenti;
2) il numero di eventi in un intervallo di tempo dipende solo dalla sua lunghezza e non dall’istante iniziale;
3) per un valore sufficientemente piccolo di t e per una costante positiva λ si ha:
Prob { un evento in un intervallo di ampiezza t } = λt + o(t) Prob { nessun evento in un intervallo di ampiezza t } = o(t) Prob { più di un evento in un intervallo di ampiezza t } = o(t)
dove o(t) è una funzione di ordine inferiore a t , ovvero lim t→∞ [o(t)/t] = 0.
Si può dimostrare che il processo di Poisson è l’unico che soddisfa le condizioni 1-2-3 [FEL 66, KLE 75, TRI 82]. Dalla proprietà 2 deriva che
Prob { k eventi nell'intervallo (s,s+t) } = e- λ t k!
(λt)k
k>0
Nel caso di processo di Poisson come processo di arrivo al sistema di Fig. 2.1, l’evento considerato è l’arrivo al sistema di un job. In questo caso se il tempo di interarrivo è esponenziale allora il processo di arrivo è di Poisson. Viceversa, se il processo di arrivo è di Poisson allora il tempo di interarrivo è necessariamente esponenziale.
Infatti, se indichiamo con X la v.c. tempo di interarrivo con distribuzione cumulativa A(t)=Prob{X≤t} allora possiamo scrivere, per la proprietà 2, che
A(t) = 1-Prob{N(t)=0 } = 1- e-λt , t>0
ovvero esponenziale di parametro λ. Quindi il tempo di interarrivo di un processo di arrivo di Poisson è esponenziale.
Il processo di Poisson è spesso utilizzato per definire modelli di sistemi fisici e organici, oltre che di sistemi di calcolo e di comunicazione. Tale applicazione dipende anche alla seguente proprietà di tale processo: la somma di un grande numero di processi di rinnovamento indipendenti e stazionari, ognuna con distribuzione del tempo di rinnovamento arbitraria, tende ad un processo di Poisson. Questo importante risultato permette di approssimare processi naturali e artificiali formati da un elevato numero di individui o componenti, con un processo di Poisson.
Il processo di Poisson gode inoltre delle seguenti proprietà che riguardano la composizione e la decomposizione di processi.
Composizione di processi di Poisson. La sovrapposizione o composizione di n processi di Poisson indipendenti rispettivamente di parametro λ1, λ2 , ..., λn è anch’esso un processo di Poisson di parametro λ1+λ2 +…+λn.
Esempio. Ad un sistema di elaborazione provengono due flussi di arrivo di programmi rappresentabili con due processi di Poisson indipendenti, rispettivamente di parametro, ovvero con tasso di arrivo, λ1 e λ2. Il processo di arrivo complessivo è anch’esso di Poisson e il tasso totale di arrivo è λ1+λ2.
Decomposizione di processi di Poisson. Dato un processo di Poisson {N(t) | t≥0} di parametro λ, assumiamo che sia decomposto in n processi, selezionando ogni uscita del processo secondo una distribuzione di probabilità di Bernoulli ad n uscite, con
probabilità pi, 1≤i≤n. Allora gli n processi di uscita {Ni(t) | t≥0} sono indipendenti e sono anch’essi processi di Poisson rispettivamente con parametro λpi, 1≤i≤n.
Esempio. Supponiamo che il numero di transazioni in arrivo ad un sistema di basi di dati sia rappresentabile da un processo di Poisson di parametro λ.
Assumiamo che il sistema sia composto da n archivi e che ogni transazione in arrivo richieda l’archivio i con probabilità pi, 1≤i≤n. Sotto l’ipotesi di indipendenza fra le transazioni anche il processo di arrivo al singolo archivio i è un processo di Poisson di parametro λpi, 1≤i≤n.
2.3 Processi di Markov
Introduciamo la classe di processi stocastici di Markov considerando lo spazio degli stati discreto (e quindi catene di Markov) ed il tempo discreto o continuo nelle due seguenti sezioni.
2.3.1 Catene di Markov a tempo discreto
Abbiamo definito un processo stocastico a tempo discreto {Xn | n ∈ T} di Markov se la probabilità di stato al tempo n+1 dipende soltanto dallo stato corrente, n, e non dall’evoluzione precedente del processo, come espresso dalla formula (2.1).
Assumiamo, senza perdita di generalità, che T sia l’insieme dei naturali N. Se anche lo spazio degli stati E è discreto allora {Xn | n ∈N} è una catena di Markov a tempo discreto, e Xn=j indica che il processo si trova nello stato j al tempo n, n∈N, j∈E.
Nella formula (2.1) la probabilità condizionata al membro destro Prob {Xn+1 = j | Xn = i}
è detta probabilità di transizione al tempo n dallo stato i allo stato j, i,j∈E, n≥0.
Una catena di Markov si dice omogenea se le probabilità di transizione sono indipendenti dal tempo n. Si definisce la probabilità di transizione dallo stato i allo stato j come:
pij = Prob {Xn+1 = j | Xn= i} (2.4)
∀i,j∈E, ∀n≥0. Tali probabilità costituiscono gli elementi della matrice delle probabilità di transizione P= [pij], che, di conseguenza, soddisfa le seguenti proprietà:
pij∈[0,1] e Σj pij =1, ∀i,j∈E. Da ora in poi consideriamo soltanto catene di Markov omogenee.
Una catena di Markov può essere analizzata sia in un tempo finito (analisi transiente) sia a lungo termine (analisi stazionaria).
Analisi transiente
Denotiamo con pij(m) = Prob {Xn+m = j | Xn = i} la probabilità di transizione dallo stato i allo stato j in m passi, ∀i,j∈E, ∀m>0. Considerando un qualsiasi stato k∈E, la transizione dallo stato i allo stato j in m passi può essere vista come composizione della transizione dallo stato i allo stato k in m-1 passi seguita dalla transizione dallo stato k allo stato j in un passo. Per la definizione di processo Markoviano i due eventi sono indipendenti e si può scrivere:
pij(m) = Σk∈E pik (m-1) pkj m > 1 (2.5).
Tale formula è nota come equazione di Chapman-Kolmogorov per il calcolo della probabilità in m passi. In forma matriciale dalla formula (2.5) segue immediatamente che la matrice delle probabilità di transizione in m passi P(m) è calcolabile come P(m) = P(m-1) P da cui, per l’omogeneità della catena P(m)=Pm.
Sia πj(n)= Prob{Xn= j} la probabilità di osservare lo stato j al tempo n, ∀j∈E,
∀n>0. In forma compatta indichiamo con π(n) = [π0(n) π1(n) π2(n) ...] il vettore delle probabilità di stato al tempo n. Se la distribuzione di probabilità di stato del processo al tempo iniziale π(0) è nota, allora la distribuzione di probabilità di stato al tempo n>0 è calcolabile come
π (n) = π (0) P(n) ovvero
π (n) = π (0) Pn (2.6).
Il comportamento transiente del processo è descritto dal vettore π(n) che può essere quindi calcolato dalla probabilità di stato iniziale e dalla matrice di transizione P. Tale soluzione è facilmente calcolabile solo in casi particolari, ad esempio per catene di Markov con spazio E finito e/o per particolari strutture della matrice P.
L’analisi del comportamento del processo di Markov per n che tende ad infinito richiede l’identificazione degli stati che il processo visita infinite volte. Per questo scopo introduciamo una breve classificazione degli stati di una catena di Markov.
Classificazione degli stati
Una catena di Markov può essere rappresentata dal diagramma di transizione fra
stati. Esso è un grafo orientato con archi etichettati, i cui nodi rappresentano gli stati del processo e in cui esiste un arco (i,j), con etichetta pij se e solo se la probabilità di transizione pij>0. La Fig. 2.2 mostra un esempio di catena di Markov finita con spazio E={1,2,3,4,5,6} e matrice di transizione P e il relativo diagramma degli stati.
Una catena di Markov è detta irriducibile se ogni stato può essere raggiunto da ogni altro stato in un tempo finito, ovvero se per ogni i,j∈E esiste un m>0 tale che pij(m)>0. Un sottoinsieme di stati E' di E è chiuso se non esiste alcuna transizione da E' al suo complemento E-E'. Una catena di Markov con spazio E che contiene sottoinsiemi chiusi è riducibile. Se E'={i} sottoinsieme chiuso di E è formato da un solo stato i, questo si dice stato assorbente. In questo caso pii=1. Uno stato i∈E è ricorrente se il processo, iniziando nello stato i, torna allo stato i con certezza (con probabilità 1). Uno stato i è ricorrente non-nullo (o ricorrente positivo) se il tempo medio di ricorrenza in i è finito, mentre è ricorrente nullo se il tempo medio di ricorrenza in i è infinito. Uno stato i è transiente se vi è probabilità non nulla di non ritorno allo stato i.
Per uno stato ricorrente i si definisce il periodo γi come il massimo comun divisore dell’insieme degli interi m per cui pii(m)>0. Uno stato ricorrente è aperiodico se γi=1 ed è periodico se γi>1.
Una catena di Markov è ergodica se è irriducibile e formata da stati aperiodici e ricorrenti non nulli.
Esempio. In Fig. 2.2 il sottoinsieme E'={1,2,3} è chiuso, gli stati 1, 2 e 3 sono ricorrenti periodici di periodo 3. Gli stati 4 e 5 sono transienti e lo stato 6 è assorbente.
Per catene di Markov irriducibili si può dimostrare [FEL 66] che tutti gli stati sono o transienti o ricorrenti nulli o ricorrrenti non-nulli e, se periodici, hanno tutti lo stesso periodo.
1 2 4
3 P =
0 0 0 0 0.5 0.5 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0.7 0 0.3 5
6
Fig. 2.2 - Esempio di diagramma fra gli stati di una catena di Markov a tempo discreto con matrice delle probabilità di transizione P -
Analisi stazionaria
La descrizione del processo stocastico in condizioni asintotiche, per il tempo n che tende ad infinito, si esprime in termini di distribuzione di probabilità di stato. Sia πj = limn→∞ πj (n) = Prob{X= j} la probabilità di osservare lo stato j in condizioni di equilibrio, ∀j∈E. In forma compatta indichiamo con π = [ π0 π1 π2 ...] il vettore delle probabilità stazionarie di stato.
Riportiamo, senza dimostrazione, un importante teorema della teoria delle catene di Markov.
Teorema [KLE 75]
La distribuzione di probabilità stazionaria π di una catena di Markov omogenea, irriducibile e aperiodica esiste sempre ed è indipendente dallo stato iniziale. Inoltre
• se gli stati sono transienti o ricorrenti nulli πj= 0, ∀j∈E, e non esiste distribuzione stazionaria;
• se gli stati sono ricorrenti non-nulli πj > 0, ∀j∈E, e la distribuzione stazionaria π è l’unica soluzione non negativa del sistema lineare
π = π P (2.7)
con la condizione di normalizzazione Σj πj =1.
In altre parole π è l’autovettore sinistro associato all’autovalore dominante di P, uguale ad 1, poiché la matrice P è stocastica.
Se una catena di Markov è finita e irriducibile allora tutti gli stati sono ricorrenti non nulli e la distribuzione stazionaria di stato si calcola risolvendo il sistema (2.7).
L’analisi stazionaria di una catena di Markov omogenea irriducibile e aperiodica richiede quindi semplicemente la soluzione di un sistema lineare la cui dimensione è pari alla cardinalità dello spazio degli stati E. Questo sistema lineare è risolvibile esattamente soltanto per catene di Markov finite o per particolari strutture della matrice P. Un altro approccio risolutivo, spesso applicato per catene aperte, si basa sul metodo di trasformazione della funzione di probabilità in funzione generatrice.
Ricordiamo inoltre che, per la proprietà di assenza di memoria della catena di Markov, possiamo anche analizzare il tempo di permanenza in ogni stato del processo.
La v.c. t i che denota il tempo in cui la catena rimane nello stato i∈E durante una sola visita (ovvero con continuità) è distribuita geometricamente con parametro pii, probabilità di transizione dallo stato i ad i stesso. La probabilità di un tempo di visita di n passi (n>0) è Prob{ti =n}= (1-pii ) piin-1, e il numero medio di passi spesi nello stato i sono E[ti] = 1/(1-pii).
2.3.2 Catene di Markov a tempo continuo
In un processo stocastico di Markov a tempo continuo {X(t) | t∈T} lo stato futuro dipende soltanto dallo stato corrente e non dall’evoluzione precedente del processo, come espresso dalla formula (2.2). Assumiamo, senza perdita di generalità che T sia l’insieme dei reali non negativi R0+. Se anche lo spazio degli stati E è discreto allora {X(t) | t ≥ 0} è una catena di Markov a tempo discreto, e X(t) = j indica che il processo si trova nello stato j al tempo t≥0, j∈E. Se indichiamo il tempo t=tn+s, con s>0, allora possiamo riscrivere la formula (2.2) come segue
Prob {X(tn+s)=j | X(t0)=i0; X(t1)=i1;...; X(tn)=in} = Prob {X(tn+s)=j | X(tn)=in per ogni n>0, per ogni j,i0,i1,...,in∈E e per ogni t0<t1<...tn<tn+s.
Una catena di Markov a tempo continuo è omogenea se la probabilità condizionata al membro destro è indipendente dall’istante iniziale tn, ma dipende soltanto da s;
definiamo la probabilità di transizione dallo stato i allo stato j in un intervallo di ampiezza s come segue:
pij(s) = Prob {X(tn+s) = j | X(tn) = i} (2.8)
∀i,j∈E, ∀tn≥0. Tali probabilità costituiscono gli elementi della matrice delle probabilità di transizione P(s) = [pij(s)] che gode delle stesse proprietà osservate nel caso discreto: pij(s)∈[0,1] e Σj pij(s) =1, ∀i,j∈E. Consideriamo soltanto catene di Markov omogenee.
Analogamente alle catene di Markov a tempo discreto, si può ricavare l’equazione di Chapman-Kolmogorov per le catene di Markov omogenee a tempo continuo:
pij(s+t) = Σk∈E pik (s) pkj (t) s,t >0 (2.9) e, in forma matriciale P(s+t)=P(s)P(t) e si pone per definizione P(0)=I, matrice identità.
Poiché l’uso diretto dell’equazione (2.9) per determinare la soluzione transiente è complesso, si derivano altre equazioni ottenute considerando condizioni limite, ovvero differenziando.
Mentre nel caso di catene a tempo discreto si fa riferimento alla matrice di probabilità di transizione relativa ad un passo (discreto), nel caso di catene a tempo continuo dalla matrice di transizione P(s), definita in funzione dell’intervallo di ampiezza s>0, si definisce una matrice Q delle velocità infinitesimali di transizione fra gli stati. Tale matrice Q = [qij], i,j∈E, è anche detta generatore infinitesimale del processo o
Q = lim s P(s) - I
s→0 (2.10)
dove
qii = lim s pii(s) -1
s→0 q
ij = lim s pij(s)
s→0 i≠j ∀i,j∈E
Gli elementi della matrice Q possono essere interpretati, rispettivamente, qii come la velocità complessiva di uscita dallo stato i, quando il processo è nello stato i, e qij come la velocità con cui il processo si sposta dallo stato i allo stato j, partendo dallo stato i.
Dalla condizione di normalizzazione sulle probabilità, Σj pij(s)=1, deriva la condizione sulle righe di Q: Σj qij=0, ∀i,j∈E. Si noti che gli elementi di Q sono velocità di transizione e non probabilità, e quindi possono assumere valori maggiori di uno.
Una catena di Markov a tempo continuo può essere rappresentata dal diagramma di transizione fra stati, grafo orientato con archi etichettati, i cui nodi rappresentano gli stati del processo e in cui esiste un arco (i,j), i≠j, con etichetta qij se e solo se la velocità di transizione qij>0, i,j∈E. Si noti che in tal caso nel grafo non sono rappresentati gli archi corrispondenti agli elementi diagonali, qii, i∈E.
Dalla definizione di matrice Q, con alcuni passaggi si possono ricavare le seguenti equazioni differenziali:
dt d P(t)
= P(t) Q
dt d P(t)
= Q P(t) .
Imponendo la condizione iniziale P(0)=I, si ricava la soluzione P(t) = e Q t t>0 (2.11) dove la matrice potenza è definita come:
eQ t = I + Q t + Q2 (t2 / 2!) + Q3 (t3 / 3!) + ... . Analisi transiente
Sia πi(t)= Prob{X(t) = i} la probabilità di osservare lo stato j al tempo t, ∀i∈E,
∀t>0, e, in forma vettoriale π(t) = [ π0(t) π1(t) π2(t) ...]. Il comportamento transiente
può essere ricavato dalla distribuzione di probabilità di stato del processo al tempo iniziale, π(0), e dalla matrice di probabilità di transizione P(t) tramite l’equazione:
π(t) = π(0) P(t), t>0, dove P(t) è definita dall’equazione (2.11).
Analisi stazionaria
Per definizione della matrice Q, per un piccolo intervallo dt>0, possiamo scrivere πi(t + dt) = πi(t) [1-Σj≠ i qij dt ] + Σj≠ i qji dt +o(dt )
da cui, poiché qii=-Σj≠ i qij e considerando il limite per dt che tende a 0, si ricava
dt d πi(t)
= ∑
j ∈ S
πj(t) qji
e, in forma matriciale
dt d π (t)
= π (t) Q (2.12).
Sia πj = limt→∞ πj(t) = Prob{X= j} la probabilità di osservare lo stato j in condizioni stazionarie, ∀j∈E, e in forma vettoriale π = [ π0 π1 π2 ...].
La classificazione degli stati di una catena di Markov a tempo continuo è identica a quella introdotta per le catene a tempo discreto. In particolare una c. di M. a tempo continuo è irriducibile se ogni stato può essere raggiunto da ogni altro stato. In tal caso vale il seguente teorema:
Teorema. Per una catena di Markov a tempo continuo omogenea, irriducibile ed aperiodica esiste sempre la probabilità stazionaria di stato πj = limt→∞ πj(t), j∈E, ed è indipendente dallo stato iniziale.
La soluzione stazionaria si ottiene allora imponendo dπ(t) / dt =0 da cui, dalla equazione (2.12) deriva
π Q = 0 (2.13)
che, insieme alla condizione di normalizzazione Σi πi =1, determina univocamente la soluzione.
Si noti che anche in questo caso la soluzione stazionaria della catena di Markov è espressa in termini di soluzione di un sistema lineare omogeneo la cui dimensione è
pari alla cardinalità dello spazio degli stati E. In particolare tale sistema è infinito se lo spazio E è infinito.
Il sistema di equazioni (2.13) è detto anche sistema di equazioni di bilanciamento globale in quanto la singola equazione relativa allo stato i può essere riscritta come:
πi Σj≠ i qij = Σj≠ i πj qji (2.14).
Tale equazione si può interpretare come bilanciamento fra il flusso totale uscente dallo stato i (membro sinistro) e il flusso totale entrante in i e proveniente da tutti gli altri stati j≠i (membro destro). Il termine globale è utilizzato per distinguere questo sistema dal cosiddetto sistema di equazioni di bilanciamento locale che il processo Markoviano soddisfa soltanto sotto particolari condizioni. Una catena di Markov soddisfa il bilanciamento locale se sono uguali il flusso di probabilità da uno stato i ad uno stato j e viceversa, ovvero se per ogni i,j∈E
πi qij = πj qji (2.15).
Sommando le equazioni (2.15) per j≠i si ottengono le equazioni (2.14); quindi se un processo soddisfa le equazioni di bilanciamento locale allora soddisfa anche le equazioni di bilanciamento globale, mentre il contrario non è necessariamente vero. Il bilanciamento locale è strettamente legato al concetto di processo di Markov reversibile di cui si può trovare una estesa trattazione in [KEL 79].
2.4 Processi di nascita-morte
Vediamo ora una classe particolare di processi di Markov per la quale è possibile calcolare molto semplicemente la soluzione e che trova ampia applicazione nei modelli basilari di teoria delle code. In una catena di Markov di nascita-morte (birth- death), con spazio degli stati E=N, le uniche transizioni fra stati ammesse sono dallo stato i agli stati i-1, i, i+1, ∀i∈E. Se lo stato è interpretato come la dimensione di una popolazione, una transizione da i ad i+1 rappresenta una nascita ed una transizione da i ad i-1 rappresenta una morte.
µ1 µ
2 µ
k µ
k+1
λ 0 λ
1 λ
k-1 λ
k
0 1 2 ... k-1 k k+1 ...
Fig. 2.3 - Diagramma degli stati di un processo di nascita e morte -
Consideriamo un processo di nascita-morte a tempo continuo. In tal caso definiamo la matrice Q = [qij] delle velocità di transizione fra stati i,j∈E, come:
q i i+1 = λi i≥0 q i i-1 = µi i≥1 q 0 0 = -λ0
q i i = - (λi + µ i ) i≥1
q i j = 0 per | i - j | > 1
dove λi e µi denotano, rispettivamente, il tasso di nascita e di morte quando il processo è nello stato i. Il processo è omogeneo perché questi tassi dipendono solo dallo stato e non dal tempo. La matrice Q ha struttura tridiagonale. La Fig. 2.3 mostra il diagramma di transizione fra stati del processo.
Il sistema di equazioni (2.12) relativo alla distribuzione di probabilità di stato π(t) al tempo t>0 per un processo di nascita e morte assume la forma seguente:
dt d π (t)
= µ1 π1(t) - λ π (t)
0 0
0
dt d πk(t)
= λk-1 πk-1(t) + µk+1 πk+1(t) - (λk+ µk) πk(t) k>0
Questo sistema di equazioni descrive il comportamento del processo in funzione del tempo e può essere risolto assumendo una distribuzione di probabilità di stato iniziale.
Se il processo di nascita e morte è irriducibile la probabilità stazionaria di stato π si ottiene dalla soluzione del sistema di equazioni di bilanciamento globale (2.13) che può essere riscritto come:
λk-1πk-1 + µk+1πk+1 = (λk+ µk) πk k > 0 µ1π1 = λ0π0
Questo sistema può essere facilmente risolto ad esempio per sostituzione. Infatti dalla prima equazione si ricava
π1 = π0 µ1 λ0
e per sostituzione, dalla seconda equazione
π2 = π1 µ2 λ1
= π0 µ2 µ1 λ1 λ0
e, per sostituzioni successive, dall’equazione k-sima πk = πk-1
µk λk-1
= π0 ∏
i = 0 k-1
µi+1 λi
k > 0 (2.16).
Infine, sfruttando la condizione di normalizzazione sulle probabilità, Σi πi =1, si ottiene
π0 =
1 + ∑
k = 1
∞ ∏
i = 0 k-1
µi+1 λi 1
(2.17).
La soluzione stazionaria del processo di nascita e morte a tempo continuo espresso dalle formule (2.16) e (2.17) può essere applicata soltanto se il processo è ergodico. In altre parole i tassi di nascita e di morte devono garantire che vi sia una probabilità non nulla di sistema vuoto, π0 > 0.
Condizione di stazionarietà
Una condizione necessaria e sufficiente perché il processo di nascita e morte sia ergodico (irriducibile, aperiodico, ricorrente non nullo) [KLE 75] è che esista un k0>0 tale che ∀k > k0 sia λk < µ k.
Processo di pura nascita
Considerando il particolare processo di nascita e morte in cui i tassi di morte sono nulli (µ k=0, k>0), definiamo un processo di pura nascita. Assumiamo inoltre che il tasso di nascita sia costante, indipendente dallo stato: λk = λ, k≥0. Il diagramma degli stati è mostrato in Fig. 2.4. Il sistema (2.12) relativo delle probabilità di stato π(t) al tempo t diventa
λ λ
0 1 2
λ
k-1 k k+1
λ
... ...
Fig. 2.4 - Diagramma degli stati di un processo di pura nascita -
dt d πk(t)
= - λ πk(t) + λ πk-1(t) k≥1
dt d π0(t)
= - λ π0(t) Assumendo la condizione iniziale di sistema vuoto, π0(0) = 1, πk(0) = 0, ∀k≠0, si ricava facilmente la soluzione transiente:
πk(t) = k!
(λt) k
e- λ t k ≥ 0, t ≥ 0
che riconosciamo, in accordo alla formula (2.3), come la distribuzione di Poisson di parametro λt, di media e varianza λt. Si noti che il processo di pura nascita non soddisfa la condizione di stazionarietà, infatti tutti gli stati sono transienti, e quindi non esiste la soluzione stazionaria.
Nel prossimo capitolo introduciamo un particolare processo di nascita e morte con il quale è possibile rappresentare un modello basilare di code: il sistema M/M/1 ed alcune sue varianti.
