Sensitivity to perturbation of the stationary distribution of an ergodic markov chain

see the original item page
in the repository's web site and access all digital files if the item*

2007 (EN)
Ευαισθησία στη διαταραχή της στάσιμης κατανομής μιας εργοδικής μαρκοβιανής αλυσίδας
Sensitivity to perturbation of the stationary distribution of an ergodic markov chain

Κωνσταντινίδου, Ελένη Ανδρέα

Είναι γνωστό ότι όλη η επαρκής πληροφορία που χρειαζόμαστε για τη μελέτη κάθεομογενούς και πεπερασμένης εργοδικής (αδιαχώριστης) ΜΑ, εμπεριέχεται σε ένανμοναδικό μη αρνητικό στοχαστικό πίνακα P , που ονομάζεται πίνακας μετάβασης της ΜΑ και έχει ως στοιχεία του, τις πιθανότητες μετάβασης, σε ένα βήμα, όλων των καταστάσεων{ } 1,2,.., i S n ∈ = της ΜΑ.Κάθε τέτοια ΜΑ έχει μοναδική στάσιμη κατανομή T w, η οποίαείναι ένα διάνυσμα γραμμή που έχει ως στοιχεία της τα {1,2,..,n} δηλαδή τιςπιθανότητες η ΜΑ να βρεθεί ασυμπτωτικά σε κάθε μία από τις καταστάσεις i .Προκαλώντας μία μικρή διαταραχή E στον πίνακα μετάβασης P της ΜΑ,προκύπτει ένας νέος πίνακας μετάβασης ο οποίος προφανώς εκπροσωπεί μία νέα ΜΑ(διαταραγμένη της αρχικής) για την οποία θεωρούμε ότι έχει τις ίδιες ιδιότητες με τηναρχική. Το ζητούμενο είναι να μελετήσουμε τη στάσιμη κατανομή της διαταραγμένης ΜΑκαι πιο συγκεκριμένα να ελέγξουμε αν τελικά μπορεί αυτή να συμπίπτει με την στάσιμηκατανομή της αρχικής ΜΑ. Αυτή ακριβώς είναι και η έννοια της ευαισθησίας της στάσιμηςκατανομής σε διαταραχές του πίνακα μετάβασης μιας εργοδικής ΜΑ, η οποία αποτελεί καιτο κεντρικό θέμα της παρούσας εργασίας. Αν μετά από μία μικρή διαταραχή του πίνακαμετάβασης P , η στάσιμη κατανομή δεν επηρεαστεί, τότε τη χαρακτηρίζουμε ως μηευαίσθητη .Ουσιαστικά η μελέτη της ευαισθησίας της T ισοδυναμεί με την αναζήτηση άνωφραγμάτων ενός κλάσματος, το οποίο ορίστηκε με μαθηματικό τρόπο [Funderlic - Meyer,1986; Seneta, 2006] να μετράει ακριβώς αυτή τη σχετική επιρροή της διαταραχής E τουπίνακα μετάβασης P πάνω στη στάσιμη κατανομή T της εργοδικής ΜΑ. Ένα από τασημαντικότερα φράγματα που βρέθηκαν φέρει το όνομα “condition number κ(C) ” τηςεργοδικής ΜΑ C και υπολογίζεται μέσω ενός συγκεκριμένου τύπου γενικευμένουαντιστρόφου του πίνακα A=I−P, ο οποίος ονομάζεται “Group Inverse A# =(I−P)# ” τηςΜΑ και έπαιξε πολύ σημαντικό ρόλο γενικά στη μελέτη των εργοδικών ΜΑ [κεφάλαιο 2]. Ουπολογισμός του A# μερικές φορές αποδείχθηκε δύσκολος και έτσι ξεκίνησε η αναζήτησηνέων πιο εύχρηστων φραγμάτων. Ένα αρκετά ικανοποιητικό φράγμα εντοπίστηκε απότους [Funderlic - Meyer, 1986] από το οποίο προέκυψε το συμπέρασμα ότι «μία εργοδικήΜΑ, η οποία έχει τουλάχιστον μία κατάσταση που είναι προσιτή με μεγάλη πιθανότητα8από κάθε άλλη (“ισχυρά προσιτή”-“strongly accessible”) , θα έχει T μη ευαίσθητη σεμικρές διαταραχές του P ». Το θεώρημα αυτό βελτίωσε πολύ αργότερα ο [Seneta, 2006]βρίσκοντας ένα ακόμα πιο ικανοποιητικό φράγμα για την ευαισθησία της T wαπό αυτότων Funderlic – Meyer.
It is known that all the sufficient information we need to examine everyhomogeneous and finite ergodic (irreducible) Markov Chain, is included in a unique nonnegativestochastic matrix P , which is known as transition matrix of Markov Chain and itselements denote one-step transition probabilities s of all the situations iΈS={1,2,..,n} of theMarkov Chain. Every Markov Chain with this structure has a unique row vector stationarydistribution T w, whose elements wi ΝiΈS= {1,2,..,n} denote the asymptotic probability ofany i situation of the Markov Chain.If we cause a small perturbation E in the transition matrix P of the Markov Chain,then a new transition matrix will arise, that obviously denotes a new Markov Chain(perturbed of the first one) for which we make the assumption that has the same structurewith our initial Markov Chain. The question is to examine the stationary distribution of theperturbed Markov Chain and more specifically to examine if finally this one can beequalized with the stationary distribution of the initial Markov Chain. This is the meaning ofthe sense of sensitivity to perturbation of the stationary distribution of an ergodic MarkovChain, which constitutes the fundamental subject of the presence paper. If after a smallperturbation in the transition matrix P , the stationary distribution is not affected then wedefine it as an insensitive stationary distribution.Virtually the study on sensitivity of the stationary distribution T wis mathematicallyequal with the search of an upper bound of a fraction that was defined by [Funderlic -Meyer, 1986; Seneta, 2006] and it measures exactly this relative effect on stationarydistribution T wof the perturbation E to transition matrix P . One of the most importantbounds that has been found is called gcondition number ƒΘ(C) h of the ergodic MarkovChain and it is calculated from a specific type of general inverse of matrix A=I−P, whichcalled gGroup Inverse A# =(I−P)# h. Group Inverse was shown to play a central role onthe study of ergodic Markov Chains [chapter 2]. However sometimes the calculation of A#is very difficult, so several authors started searches for more useful bounds. An alsosuccessful bound was proved by [Funderlic - Meyer, 1986] from which had followed theconclusion that gan ergodic Markov Chain that has at least one state that is accessiblewith strong probability from every other state (strongly accessible state), has stationar10distribution T winsensitive in small perturbations of transition matrix P h. This theorem wasimproved some years later by [Seneta, 2006], who was found an even better bound forthe sensitivity of the stationary distribution than Funderlic and Meyer's one.

Postgraduate Thesis / Μεταπτυχιακή Εργασία

"Group inverse" γενικευμένος αντίστροφος
Sensitivity of stationary distribution
Strongly accessible state
"Condition number"
Ευαισθησία της στάσιμης κατανομής
Condition number
Ισχυρά προσιτή κατάσταση
Perturbation of transition matrix
Διαταραχή του πίνακα μετάβασης

Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης (EL)
Aristotle University of Thessaloniki (EN)



Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης, Σχολή Θετικών Επιστημών, Τμήμα Μαθηματικών

This record is part of 'IKEE', the Institutional Repository of Aristotle University of Thessaloniki's Library and Information Centre found at Unless otherwise stated above, the record metadata were created by and belong to Aristotle University of Thessaloniki Library, Greece and are made available to the public under Creative Commons Attribution-ShareAlike 4.0 International license ( Unless otherwise stated in the record, the content and copyright of files and fulltext documents belong to their respective authors. Out-of-copyright content that was digitized, converted, processed, modified, etc by AUTh Library, is made available to the public under Creative Commons Attribution-ShareAlike 4.0 International license ( You are kindly requested to make a reference to AUTh Library and the URL of the record containing the resource whenever you make use of this material.

*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)