Birth-Death Processes and Exponential Functions

Slide1ΣΥΣΤΗΜΑΤΑ ΑΝΑΜΟΝΗΣ ΣΥΣΤΗΜΑΤΑ  ΑΝΑΜΟΝΗΣ   Διαδικασίες Γεννήσεων – Θανάτων (Birth-Death Processes) 2 - 4 -2012

Slide2ΣΥΣΤΗΜΑΤΑ ΑΝΑΜΟΝΗΣ ΣΥΣΤΗΜΑΤΑ  ΑΝΑΜΟΝΗΣ ΕΠΑΝΑΛΗΨΗ: Η εκθετική κατανομή • Μια τ.μ.  Χ  ακολουθεί εκθετική κατανομή με παράμετρο  λ όταν: • F χ (t) = 1-exp(- λ t), f Χ (t) =  λ  exp(- λ t) • E( Χ ) =   1/ λ,  var( Χ ) =  1/λ 2 • Ιδιότητα έλλειψης μνήμης – P[ X >t+s/ X >t]=P[ X >s] • Κατανομή ελαχίστου μεταξύ ανεξάρτητων τ.μ. εκθετικά κατανεμημένων – Χ 1 : με παράμετρο  λ 1 – Χ 2 : με παράμετρο  λ 2 – Χ= min{ Χ 1 ,Χ 1 }  είναι εκθετικά κατανεμημένη με παράμετρο λ  =   (λ 1 +λ 1 )

Slide3ΣΥΣΤΗΜΑΤΑ ΑΝΑΜΟΝΗΣ ΣΥΣΤΗΜΑΤΑ  ΑΝΑΜΟΝΗΣ • ΕΠΑΝΑΛΗΨΗ: Στοχαστικές διαδικασίες • Ανεξάρτητες διαδικασίες • Στάσιμες διαδικασίες • Διαδικασίες  Markov • P[X(t n+1 )=x n+1 /X(t n )=x n ,X(t n-1 )=x n-1 ,…,X(t 1 )=X 1 ]= =P[X(t n+1 )=X n+1 /X(t n )=x n ] • Εργοδικότητα • Διαδικασίες Γεννήσεων-Θανάτων: αποτελούν μια κλάση των διαδικασιών  Markov , με την επιπλέον ιδιαίτερη συνθήκη ότι μεταβάσεις επιτρέπονται μόνο ανάμεσα σε γειτονικές καταστάσεις • Διαδικασία απαρίθμησης γεγονότων • Ανεξάρτητες αυξήσεις – Στάσιμες αυξήσεις

Slide4ΣΥΣΤΗΜΑΤΑ ΑΝΑΜΟΝΗΣ ΣΥΣΤΗΜΑΤΑ  ΑΝΑΜΟΝΗΣ ΕΠΑΝΑΛΗΨΗ: Η κατανομή  Poisson : • k   αφίξεις σε διάστημα  Τ  με πιθανότητα • P k  (T) = e  – λ T  ( λΤ) k  / k ! • E T ( k ) =  λ T • Var T  ( k ) =  λΤ • Μέσος ρυθμός αφίξεων :  λ  πελάτες/ sec Η κατανομή  Poisson  σαν όριο της Διωνυμικής Κατανομής : • Χωρίζω το διάστημα  Τ  σε  Ν  υποδιαστήματα. Σε κάθε υποδίαστημα θεωρώ  N  ανεξάρτητες   δοκιμές  Bernoulli  με πιθανότητα επιτυχίας  p T = N x  ΔΤ ,  p =  λ   ΔΤ  =  λΤ/Ν • Η πιθανότητα  k   επιτυχιών σε  N   δοκιμές είναι P k  (T) = P k  (N)  =  N !/ ( K !( N-k )! )  x ( λΤ /N )  k   x (1-   λΤ /N )  N-k • Στο όριο   Ν    ∞, ΔΤ    0,  :  P k  (T)     e  – λ T  ( λΤ) k  / k !  

Slide5ΣΥΣΤΗΜΑΤΑ ΑΝΑΜΟΝΗΣ ΣΥΣΤΗΜΑΤΑ  ΑΝΑΜΟΝΗΣ Ιδιότητες διαδικασίας  Poisson: • Οι χρόνοι μεταξύ διαδοχικών αφίξεων μιας διαδικασίας Poisson  με ρυθμό  λ , είναι τ.μ εκθετικά κατανεμημένες με μέση τιμή  1/λ • Υπέρθεση ανεξάρτητων διαδικασιών  Poisson   λ 1 , λ 2    διαδικασία  Poisson   λ = λ 1  + λ 2 • Διάσπαση διαδικασίας  Poisson   λ   με πείραμα  Bernoulli   p, q = 1-p      ανεξάρτητες διαδικασίες  Poisson λ 1   = p  λ λ 2  = q  λ

Slide6ΣΥΣΤΗΜΑΤΑ ΑΝΑΜΟΝΗΣ ΣΥΣΤΗΜΑΤΑ  ΑΝΑΜΟΝΗΣ Στοιχεία από Έννοιες Διαδικασιών  Markov • Συστήματα και Αλυσίδες  Markov  διακριτού και συνεχούς χρόνου • Πιθανότητες και γράφοι / διαγράμματα μετάβασης • Στατικές κατανομές και πιθανότητες καταστάσεων Birth-Death Processes • Παραδοχές: – Ανεξαρτησία γεννήσεων-θανάτων – Εξέλιξη βασισμένη στο παρόν  (Markov) • Σύστημα Διαφορικών εξισώσεων Διαφορών – Κατάσταση ισορροπίας  (steady state)

Slide7ΣΥΣΤΗΜΑΤΑ ΑΝΑΜΟΝΗΣ ΣΥΣΤΗΜΑΤΑ  ΑΝΑΜΟΝΗΣ Παραδοχές Διαδικασίας Γεννήσεων – Θανάτων – Την χρονική στιγμή  t  όταν το σύστημα καταλήγει σε πληθυσμό  n  > 0   μπορεί να έχουν προηγηθεί οι ακόλουθες μεταβάσεις από την χρονική στιγμή  t -ΔΤ , ΔΤ  0: • Μία άφιξη στο διάστημα  ΔΤ , με πιθανότητα  λ n-1 ΔΤ • Μια αναχώρηση, με πιθανότητα  μ n+1 ΔΤ • Τίποτα από τα δύο, με πιθανότητα  1- ( λ n + μ n ) ΔΤ – Η εξίσωση μετάβασης ( Kolmogorov)  προκύπτει από τον τύπο συνολικής πιθανότητας: P n ( t ) =  λ n-1 ΔΤ  P n-1 ( t- ΔΤ ) +  μ n+1 ΔΤ  P n + 1 ( t- ΔΤ ) + [1- ( λ n + μ n ) ΔΤ ]  P n ( t- ΔΤ )

Slide8ΣΥΣΤΗΜΑΤΑ ΑΝΑΜΟΝΗΣ ΣΥΣΤΗΜΑΤΑ  ΑΝΑΜΟΝΗΣ Στο όριο ,  ΔΤ      dt : [ P n ( t )  -  P n ( t - dt )]/ dt  =  λ n-1 P n-1 ( t ) +  μ n+1 P n + 1 ( t )  – ( λ n + μ n ) P n ( t ) ή d P n ( t )/ dt =  λ n-1 P n-1 ( t ) +  μ n+1 P n + 1 ( t )  – ( λ n + μ n ) P n ( t ) d P 0 ( t )/ dt =  μ 1 P 1 ( t )  –  λ 0 P 0 ( t ) και σε σταθερή κατάσταση  t     οο  ( αν υπάρχει) :   P n ( t ) =  P n      :  Εργοδικές Πιθανότητες ( λ n + μ n ) P n   =  λ n-1 P n-1  +  μ n+1 P n + 1    (εξισώσεις ισορροπίας) λ 0 P 0   =  μ 1 P 1 P 0  + P 1  + P 2  +… = 1