Αλυσίδες Markov και θεωρία πινάκων

Abstract

Το θέμα της εργασίας αυτής βρίσκεται στη διασταύρωση δύο μεγάλων ερευνητικών τομέων: της εφαρμοσμένης πιθανότητας και της αριθμητικής ανάλυσης που παρουσιάζουν επίσης μεγάλο ενδιαφέρον για εφαρμογές. Το πρώτο κεφάλαιο περιέχει μία βασική περιγραφή των θεμελιωδών εννοιών που σχετίζονται με τις αλυσίδες Markov, καθώς είναι εμπλουτισμένο με παραδείγματα και γραφήματα για την καλύτερη κατανόησή τους. Το δεύτερο κεφάλαιο περιέχει μία συστηματική επεξεργασία των δομημένων πινάκων που απαιτούνται για την ανάλυση και την επίλυση στοχα- στικών προβλημάτων. Ορισμένες από τις κατηγορίες τέτοιων πινάκων που παρουσιάζονται αναλυτικά, είναι οι Κυκλικοί, οι 𝑧������-κυκλικοί, οι Toeplitz και οι Τριγωνικοί Toeplitz πίνακες. Επίσης, γίνεται αναφορά και σε ορισμένους αλγορίθμους, που χρησιμοποιούνται στην αντιμετώπιση σύνθετων υπολογιστικών προβλημάτων, που αφορούν τέτοιους πίνακες, καθώς και στο υπολογιστικό τους κόστος. Το τρίτο κεφάλαιο της εργασίας περιέχει δύο χαρακτηριστικά παραδείγματα εφαρμογής των εννοιών που παρουσιάζονται στα δύο προηγούμενα κεφάλαια. Γίνεται ανάλυση του επιτραπέζιου παιχνιδιού "Φιδάκι" το οποίο αποτελεί σύστημα αλυσίδας Markov. Έπειτα αναλύουμε ένα βασικό πρόβλημα της Θεωρίας Ουρών, "Το πρόβλημα της συντομότερης ουράς", με τη χρήση της Wiener-Hopf παραγοντοποίησης και άπειρων Toeplitz πινάκων.