Markov Diakritoy

ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΕΙΡΑΙΑ – ΤΜΗΜΑ ∆Ι∆ΑΚΤΙΚΗΣ ΤΗΣ ΤΕΧΝΟΛΟΓΙΑΣ ΚΑΙ ΨΗΦΙΑΚΩΝ ΣΥΣΤΗΜΑΤΩΝ

ΣΥΣΤΗΜΑΤΑ ΑΝΑΜΟΝΗΣ - ΠΡΟΣΟΜΟΙΩΣΗ ΕΠ. ΚΑΘ. Π. ∆ΕΜΕΣΤΙΧΑΣ ΕΝΟΤΗΤΑ ΣΥΣΤΗΜΑΤΑ ΑΝΑΜΟΝΗΣ 5 (ΣΑ5): ΜΑΡΚΟΒΙΑΝΕΣ ΑΛΥΣΙ∆ΕΣ ∆ΙΑΚΡΙΤΟΥ ΧΡΟΝΟΥ

Ακαδηµαϊκό Έτος 2004 - 2005 Συστήµατα Αναµονής – Προσοµοίωση: Ενότητα ΣΑ5

1

ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΕΙΡΑΙΑ – ΤΜΗΜΑ ∆Ι∆ΑΚΤΙΚΗΣ ΤΗΣ ΤΕΧΝΟΛΟΓΙΑΣ ΚΑΙ ΨΗΦΙΑΚΩΝ ΣΥΣΤΗΜΑΤΩΝ

Πίνακας Περιεχοµένων 1.

ΕΙΣΑΓΩΓΗ ........................................................................................................................ 3

2.

ΟΡΙΣΜΟΣ ΜΑ∆Χ ............................................................................................................. 3

3.

∆Ε∆ΟΜΕΝΑ ΚΑΙ ΖΗΤΟΥΜΕΝΑ ΣΕ ΜΑ∆Χ ....................................................................... 3

4.

ΜΕΘΟ∆ΟΛΟΓΙΑ ΑΝΑΛΥΣΗΣ ΜΙΑΣ ΜΑ∆Χ ..................................................................... 4

5.

ΠΑΡΑ∆ΕΙΓΜΑ ................................................................................................................... 4

6.

ΣΥΝΟΨΗ ........................................................................................................................... 5

7.

ΒΙΒΛΙΟΓΡΑΦΙΑ ................................................................................................................. 6

Συστήµατα Αναµονής – Προσοµοίωση: Ενότητα ΣΑ5

2

ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΕΙΡΑΙΑ – ΤΜΗΜΑ ∆Ι∆ΑΚΤΙΚΗΣ ΤΗΣ ΤΕΧΝΟΛΟΓΙΑΣ ΚΑΙ ΨΗΦΙΑΚΩΝ ΣΥΣΤΗΜΑΤΩΝ

1. ΕΙΣΑΓΩΓΗ Στην ενότητα αυτή µελετάµε Μαρκοβιανές Αλυσίδες ∆ιακριτού Χρόνου (ΜΑ∆Χ). Επιπλέον πληροφορίες σχετικά µε το περιεχόµενο της ενότητας µπορούν να βρεθούν στα [1,2,3,4,5,6]. 2. ΟΡΙΣΜΟΣ ΜΑ∆Χ Οι ΜΑ∆Χ έχουν διακριτό χώρο κατάστασης. Μια ΜΑ∆Χ είναι ένα σύνολο τυχαίων µεταβλητών, X n , όπου n = 0, 1, 2, … . Η τιµή της τυχαίας µεταβλητής, X n , της διαδικασίας Markov δείχνει την κατάσταση του συστήµατος στη συγκεκριµένη χρονική στιγµή n . Η βασική ιδιότητα των διαδικασιών Markov, στην περίπτωση αλυσίδων διακριτού χρόνου, µπορεί να εκφρασθεί ως εξής: P[X n +1 = j X n = in ,..., X 1 = i1 ] = P[X n +1 = j X n = in ]

Η βασική ιδιότητα µιας διαδικασίας Markov είναι ότι η κατάσταση τη χρονική στιγµή n + 1 εξαρτάται µόνο από την κατάσταση τη χρονική στιγµή n , και όχι από τις καταστάσεις στις προηγούµενες χρονικές στιγµές. Λόγω της βασικής ιδιότητας των διαδικασιών Markov, η κατανοµή του χρόνου παραµονής σε µια κατάσταση χαρακτηρίζεται από έλλειψη µνήµης. Για διακριτό χρόνο η µόνη κατανοµή που έχει την ιδιότητα αυτή είναι η γεωµετρική. 3. ∆Ε∆ΟΜΕΝΑ ΚΑΙ ΖΗΤΟΥΜΕΝΑ ΣΕ ΜΑ∆Χ Μια ΜΑ∆Χ δίνεται υπό τη µορφή κατευθυντικού γράφου G (V , E ) και ενός πίνακα πιθανοτήτων µετάβασης Pˆ . Οι κόµβοι του γράφου, V , είναι οι δυνατές καταστάσεις της ΜΑ∆Χ. Οι ακµές δίνουν τις δυνατές µεταβάσεις µεταξύ των καταστάσεων. Κάθε ακµή ( i , j )∈ E σηµαίνει ότι είναι δυνατή η µετάβαση, σε ένα βήµα, από την κατάσταση i στην j . Μετάβαση σε ένα βήµα σηµαίνει ότι αν µια ΜΑ∆Χ βρεθεί, κάποια στιγµή, στην κατάσταση i , τότε είναι πιθανόν την επόµενη χρονική στιγµή να βρεθεί στην κατάσταση j . Το πόσο πιθανές είναι οι µεταβάσεις καθορίζεται από τον πίνακα πιθανοτήτων µετάβασης Pˆ . Οι διαστάσεις του πίνακα είναι V × V ( V είναι το πλήθος των

καταστάσεων). Κάθε στοιχείο του πίνακα, pij , λέγεται πιθανότητα µετάβασης, και καθορίζει το πόσο πιθανή είναι η µετάβαση σε ένα βήµα από την κατάσταση i στην j . Γενικά, ισχύει ∑ pij = 1, ∀ i ∈ V . j∈V

Το ζητούµενο όταν αναλύουµε µια ΜΑ∆Χ είναι ένα διάνυσµα πιθανοτήτων πˆ = [ π 1 , ... , π V ], το οποίο ονοµάζεται στατική κατανοµή πιθανότητας, ή κατανοµή µόνιµης κατάστασης (steady state distribution), ή κατανοµή κατάστασης ισορροπίας (equilibrium state distribution). Η κάθε πιθανότητα π i (∀ i ∈ V ) εκφράζει το πόσο

Συστήµατα Αναµονής – Προσοµοίωση: Ενότητα ΣΑ5

3

ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΕΙΡΑΙΑ – ΤΜΗΜΑ ∆Ι∆ΑΚΤΙΚΗΣ ΤΗΣ ΤΕΧΝΟΛΟΓΙΑΣ ΚΑΙ ΨΗΦΙΑΚΩΝ ΣΥΣΤΗΜΑΤΩΝ

πιθανή είναι η κάθε κατάσταση i , ή µε άλλα λόγια, το ποσοστό του χρόνου που η ΜΑ∆Χ θα βρίσκεται στην κατάσταση i . Ισχύει η σχέση M i = (1/ π i ), όπου M i είναι ο µέσος χρόνος επανάληψης (mean recurrence time) της κατάστασης i . 4. ΜΕΘΟ∆ΟΛΟΓΙΑ ΑΝΑΛΥΣΗΣ ΜΙΑΣ ΜΑ∆Χ

Το διάνυσµα πιθανοτήτων πˆ δίνεται από το σύστηµα εξισώσεων:

πˆ = πˆ Pˆ

(1α)

∑π

(2)

i∈V

i

=1

Το σύστηµα πˆ = πˆ Pˆ αναλυτικότερα γράφεται:

[ π 1 , ... , π V ] = [ π 1 , ... , π V

⎡ p11 ⎢p ] ⎢ 21 ⎢ . ⎢ ⎣ pV 1

p12

...

p 22

...

.

... ...

pV 2

p1V ⎤ p 2V ⎥⎥ . ⎥ ⎥ pVV ⎦

(1β)

Το σύστηµα (1β) µπορεί επίσης να γραφεί:

πi=

∑π j∈V

j

⋅ p ji

∀ i ∈V

(1γ)

Από το παραπάνω σύστηµα παίρνουµε V εξισώσεις, οπότε σε συνδυασµό µε τη σχέση (2) έχουµε ένα σύστηµα V +1 εξισώσεων µε V αγνώστους. Αγνοούµε µια εξίσωση από αυτές που προκύπτουν από το σύστηµα (1β) (ή 1(γ)), οπότε σε συνδυασµό µε τη σχέση (2) έχουµε ένα σύστηµα V εξισώσεων µε V αγνώστους, το οποίο µπορεί να λυθεί µε αντικατάσταση. 5. ΠΑΡΑ∆ΕΙΓΜΑ

∆ίνεται η ΜΑ∆Χ του παρακάτω σχήµατος και ζητείται η στατική κατανοµή πιθανότητας. 3/4

11 1/4

00

1/4

1/4

3/4 1/4

22 1/2

Σχήµα 1. Παράδειγµα ΜΑ∆Χ

Έχουµε ότι

Συστήµατα Αναµονής – Προσοµοίωση: Ενότητα ΣΑ5

4

ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΕΙΡΑΙΑ – ΤΜΗΜΑ ∆Ι∆ΑΚΤΙΚΗΣ ΤΗΣ ΤΕΧΝΟΛΟΓΙΑΣ ΚΑΙ ΨΗΦΙΑΚΩΝ ΣΥΣΤΗΜΑΤΩΝ

⎡ 0 3 4 1 4⎤ ˆ P = ⎢⎢1 4 0 3 4⎥⎥ ⎢⎣1 4 1 4 1 2 ⎥⎦

Επίσης

πˆ = πˆ Pˆ ⇒ ⎡ 0 3 4 1 4⎤ [ π 1 , π 2 , π 3 ] = [ π 1 , π 2 , π 3 ] ⎢⎢1 4 0 3 4⎥⎥ ⎢⎣1 4 1 4 1 2 ⎥⎦

Πραγµατοποιώντας τον πολλαπλασιασµό πινάκων παίρνουµε το σύστηµα:

π 1 = (1/4) π 2 + (1/4) π 3

(1)

π 2 = (3/4) π 1 + (1/4) π 3

(2)

π 3 = (1/4) π 1 + (3/4) π 2 + (1/2) π 3

(3)

Επίσης έχουµε την ακόλουθη εξίσωση:

π1 + π 2 + π 3 = 1

(4)

Από τις (1), (2), (4), και λύνοντας το σύστηµα µε αντικατάσταση, παίρνουµε π 1 =1/5, π 2 =7/25, π 3 =13/25 6. ΣΥΝΟΨΗ

Στην ενότητα αυτή µελετήσαµε Μαρκοβιανές Αλυσίδες ∆ιακριτού Χρόνου.

Συστήµατα Αναµονής – Προσοµοίωση: Ενότητα ΣΑ5

5

ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΕΙΡΑΙΑ – ΤΜΗΜΑ ∆Ι∆ΑΚΤΙΚΗΣ ΤΗΣ ΤΕΧΝΟΛΟΓΙΑΣ ΚΑΙ ΨΗΦΙΑΚΩΝ ΣΥΣΤΗΜΑΤΩΝ

7. ΒΙΒΛΙΟΓΡΑΦΙΑ

[1]

Ν. Ασηµακόπουλος, «Ουρές αναµονής Πανεπιστήµιο Πειραιά, Πειραιάς, 2001

[2]

L.Kleinrock, “Queueing systems; volume 1: theory”, J. Wiley & Sons, New York, 1975

[3]

S.Haykin, “Communication systems”, J. Wiley & Sons, New York, 1983

[4]

R.Wolf, “Stochastic modelling and the theory of queues”, Prentice-Hall, Englewood Cliffs, NJ, 1989

[5]

Γ. Κοκολάκης, Ι. Σπηλιώτης, “Θεωρία πιθανοτήτων και εφαρµογές”, Εκδόσεις Συµεών, Αθήνα, 1987

[6]

R.Yates, D.Goodman, “Probability and stochastic processes: A friendly introduction for electrical and computer engineers”, J. Wiley & Sons, New York, 1999

Συστήµατα Αναµονής – Προσοµοίωση: Ενότητα ΣΑ5

–

Θεωρία

και

εφαρµογές»,

6