Διακριτές semi-Markov διαδικασίες και εφαρμογές σε εμφανίσεις λέξεων

Abstract

In this thesis we study theoretical problems concerning discrete time semi-markov processes. Moreover we give results to probability problems on word occurrences under the semi-markov hypothesis. There is a big bibliography on relevant problems under the hypothesis of independence and the markovian hypothesis. In chapter 1 we study a discrete time semi-markov process z with finite state space. We define its backward recurrence time u and we study the markov chain (z,u). We introduce a new markov chain looking at the k-tuples of the states of (z,u). In chapter 2 we give ways of representing a word and study its structure. In chapter 3 we derive the probability of a word occurrence in a semi-markov sequence of letters. We obtain results for the mean and the variance of the number of word occurrences under certain conditions. In chapter 4 we give a recurrent relation for the distribution of the waiting time for the first occurrence of a word and the corresponding generating function. Finally we study the waiting time for the first occurrence of a word from a finite set of words of equal length k.

Στη διδακτορική αυτή διατριβή γίνεται αφ' ενός η μελέτη θεωρητικών θεμάτων που αφορούν στις ημιμαρκοβιανες διαδικασίες διακριτού χρόνου, αφ' ετέρου δίνονται αποτελέσματα σε προβλήματα πιθανοτήτων που σχετίζονται με εμφανίσεις λέξεων κάτω από την ημιμαρκοβιανη υπόθεση. Υπάρχει πλούσια βιβλιογραφία για ανάλογα προβλήματα κάτω από την υπόθεση της ανεξαρτησίας και κάτω από τη μαρκοβιανη υπόθεση. Στο κεφάλαιο 1 γίνεται μελέτη μιας ημιμαρκοβιανης διαδικασίας διακριτού χρόνου z με χώρο καταστάσεων ένα πεπερασμένο σύνολο. Ορίζεται η αντίστοιχη της διαδικασία αναδρομικού χρόνου u και meλεταται η μαρκοβιανη αλυσίδα (z, u). Κατασκευάζεται και μελετάται μια νέα μαρκοβιανη αλυσίδα (z, u) η οποία σχηματίζεται θεωρώντας τις k-αδες των καταστάσεων της (z,u). Στο κεφάλαιο 2 δίνονται τρόποι παράστασης μιας λέξης και μελετάται η δομή της. Στο κεφάλαιο 3 μελετάται η πιθανότητα εμφάνισης μιας λέξης στην ημιμαρκοβιανη αλυσίδα γραμμάτων. Υπολογίζεται η μέση τιμή και η διασπορά του αριθμού των επικαλυπτόμενων εμφανίσεων μιας λέξης κάτω από συγκεκριμένες συνθήκες. Στο κεφαλαίο 4 δίνεται αναδρομική σχέση για την κατανομή του χρόνου αναμονής για την πρώτη εμφάνιση μιας συγκεκριμένης λέξης στην ημιμαρκοβιανη αλυσίδα γραμμάτων και η αντίστοιχη γεννήτρια συνάρτηση. Τέλος μελετάται ο χρόνος αναμονής για την πρώτη εμφάνιση μιας οποιασδήποτε λέξης από ένα πεπερασμένο σύνολο λέξεων ίσου μήκους κ.