Appunti di Telecommunication Networks

Processi Stocastici

Alo stato di partenza del processo (ci troviamo sicuramente sullo di partenza con valore1).Con questa procedura possiamo studiare il modo in cui il processo si evolve durante lafase transitoria e quindi siamo in grado di caratterizzare il processo in un regimetransitorio.

Teorema (soluzione a regime stazionario): se la catena di Markov è omogenea a statiricorrenti ed aperiodici e risulta indipendente dalla configurazione iniziale dello stato,allora la soluzione a regime stazionario esiste ed è data da , dove .(n)= = limA AP A An→∞14 CAPITOLO 2. PROCESSI STOCASTICI

Dim:Si dimostra a partire da e facendo tendere(n) (n−1) → ∞.=A A P nPerciò, in uno stato di regime otteniamo:(n) (n−1){A } {A }lim = = =A P APn→∞C.V.D.N.B: nella risoluzione del sistema dobbiamo verificare il vincolo P = 1.a iiES:Vogliamo trovare la soluzione a regime stazionario, ovvero con=A AP= [a ].A , a , a1 2 3  14=a a1 2  2=a 13 1 

23= +a a a  2 1 3 84 2 ⇒ =a 214 34 12 23= + +a a a a3 1 2 3  13  =a  3 23 + + = 1a a a 1 2 3

Per validare la soluzione si fissa una configurazione iniziale del vettore di stato, ad esempio (0) = [1, 0, 0], e si applica iterativamente la relazione:

(n) = A(n-1)

fino a che il processo non si stabilizza quando raggiunge lo stato di regime stazionario.

Otteniamo quindi:

(1) = [0, 3, 1]

(2) = [4, 3, 1]

(3) = [2, 16, 8]

...

(36) = [13, 23, 232]

2.3. CATENE DI MARKOV ASSORBENTI

Possiamo inoltre verificare che modificando la configurazione iniziale (0) del vettore di stato, la configurazione a regime non cambia.

2.3 Catene di Markov assorbenti

Le catene di Markov assorbenti sono catene di Markov nelle quali lo spazio degli stati può essere suddiviso in:

- Stati transitori, che sono stati non permanenti che una volta visitati possono essere abbandonati e quindi possono essere visitati più volte.

- Stati assorbenti finali, che sono stati permanenti che una volta visitati non possono essere abbandonati e quindi non possono essere visitati più volte.

(o sono stati permanenti che una volta visitati non possono essere abbandonati.della rovina dei giocatori):

ES (problemaPer semplicità supponiamo il caso di due giocatori e Questi giocatoriA B.hanno rispettivamente una disponibilità di gioco di euro e di euro.k mAd ogni giocata (o round) ogni giocatore scommette euro. Perciò, la disponibilità di gioco complessiva di e ad ogni round sarà + =A B k mcostante.Al termine del round un giocatore vince la scommessa (guadagna euro) e1l’altro la perde (perde euro).1Il gioco termina quando uno dei due giocatori perde tutta la disponibilità digioco.Detta la disponibilità di gioco di al round verifichiamo che è(n)X A n, X AAuna catena di Markov assorbente e definiamo la matrice di transizione .PDefiniamo la v.a. che rappresenta il risultato all’n-esima giocata.Z nAllora può assumere i valori nel caso in cui il giocatore vinca o±1Z Anperda, ovvero:• se vincePr(Z

1) An• se perde−1) −Pr(Z = 1 p An

Consideriamo lo stato della disponibilità di gioco di [0, 1, +X ..., k m]A(dove si verifica se perde tutto e se vince tutto).

0 = +X A X k mA AN.B: chiaramente gli stati ed una vota raggiunti non

0 = +X X k mA Apossono essere abbandonati.

Abbiamo quindi dimostrato che si tratta di una catena di Markov assorben-te poiché oltre ad avere stati transitori (sono tutti gli stati intermedi finchéun giocatore non perde tutta la disponibilità di gioco) possiede degli statiassorbenti che non possono essere abbandonati.

16 CAPITOLO 2. PROCESSI STOCASTICI

Per calcolare la matrice di transizione valutiamo i suoi elementi per degliPstati particolari:

• (la probabilità di transitare da uno stato al suo successivo=p p ii,i+1è p).

• (la probabilità di transitare da uno stato al suo− 1 =p p q ii,i−1precedente è q).

• (la probabilità di restare nello stato

ij|i - 1.j| > Perciò, nei processi di nascita e morte sono possibili solamente le transizioni tra stati ad un passo che distano al massimo unità (ovvero ad ogni passo possiamo transitare in uno stato di arrivo che dista al massimo unità dallo stato di partenza i).

Quindi, considerando uno stato di partenza in un processo di nascita e morte sono possibili solamente le seguenti transizioni:

• Verso uno stato immediatamente successivo (ovvero verso uno stato aumentato di una unità rispetto a i),
• Verso uno stato immediatamente precedente (ovvero verso uno stato diminuito di una unità rispetto a i).
• Verso lo stato di partenza (ovvero permanenza in i).

Analisi

Fissiamo un intervallo temporale molto piccolo (δ) e supponiamo di aver osservato il processo all'istante t. Detto P(n,t) la probabilità con cui il sistema si trova nello stato i all'istante t.

probabilità con cui il processo raggiunge lo stato a(δ)n t, P mn,mpartire dallo stato in un tempo piccolo e considerando valide le seguenti relazioni:

n δcoefficiente di natalità• dove è il (o tasso di nascita).(δ) = +P λ δ O(δ), λn,n+1 n n coefficiente di mortalità• dove è il (o tasso di morte).(δ) = +P µ δ O(δ), µn,n−1 n n• derivato dalle precedenti relazioni.− −(δ) = 1 +P λ δ µ δ O(δ),n,n n n

Allora, detta la probabilità che il sistema si trovi nello stato all’istante(t + +P δ) n t δn(ovvero la probabilità che partendo da uno stato o all’istante si−+ 1, 1i i i t,raggiunga lo stato in un unico passo avremo che:

n δ)· · · − −(t + = (t) [λ + + (t) [µ + + (t) [1 +P δ) P δ O(δ)] P δ O(δ)] P

λ δ µ δ O(δ)]n n−1 n−1 n+1 n+1 n n n

Da tale relazione deriva che, dividendo entrambi i membri per δ:

−(t + (t)P δ) P O(δ)n n · · − ·= (t) + (t) (λ + ) (t) +λ P µ P µ Pn−1 n−1 n+1 n+1 n n nδ δ

E considerando il limite per allora per−→ ≥0, 0:

δ n−(t + (t)d P δ) Pn n · · − ·(t) = lim = (t) + (t) (λ + ) (t)P λ P µ P µ Pn n−1 n−1 n+1 n+1 n n ndt δδ→0 O(δ)

N.B: abbiamo tenuto conto che lim = 0.δδ→0

Abbiamo quindi ottenuto il seguente sistema di equazioni differenziali che caratterizza il modo in cui varia nel tempo:

(t)P n se d · − ·(t) = (t) (t) = 0P µ P λ P n 0 1 1 0 0dt sed · · − ·(t) = (t) + (t) (λ + ) (t) 0P λ P µ P µ P n

>n n−1 n−1 n+1 n+1 n n n dt

Studiamo adesso il comportamento a regime stazionario. Supponendo possibile un regime stazionario (per allora poiché essendo a regime nond→ ∞), ∀n(t) = 0t P ndt variano nel tempo e quindi possiamo scrivere Di conseguenza otteniamo ∀n.(t) = P Pn ni l seguente sistema di equazioni:

 · ·=λ P µ P

 0 0 1 1· · ·(λ + ) = +µ P λ P µ Pn n n n−1 n−1 n+1 n+1



Diagramma di stato

Consideriamo il diagramma di stato associato al processo di nascita e morte: 18 CAPITOLO 2. PROCESSI STOCASTICI

Immaginando di isolare lo stato da tutto il sistema mediante un’ipotetica superficie n equilibrio locale sferica (tratteggiata in rosso) possiamo definire la relazione di dove il primo membro rappresenta l’intensità· · ·(λ + ) = +µ P λ P µ Pn n n n−1 n−1 n+1 n+1 di flusso con cui si