The system availability process indicates whether or not the interconnection of components is operating as intended at each time instant. It is shown that a 2-states system availability process that results from a transformation of a Markov chain is not a Markov chain. The probabilistic characterization of the system availability process is given.

Orientadores: Nancy Lopes Garcia, Alexsandro Giacomo Grimbert Gallo / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-24T12:54:22Z (GMT). No. of bitstreams: 1 Carvalho_WalterAugustoFonsecade_D.pdf: 1034671 bytes, checksum: 25dd72305f343655bedfde62a785a259 (MD5) Previous issue date: 2014 / Resumo: Esta tese é dedicada ao estudo dos processos de renovação binários obtidos como agregação de estados a partir de processos Markovianos com alfabeto finito. Na primeira parte, utilizamos uma abordagem matricial para obter condições sob as quais o processo agregado pertence a cada uma das seguintes classes: (1) Markoviano de ordem finita, (2) processo de ordem infinita com probabilidades de transição contínuas, (3) processo Gibbsiano. A segunda parte trata da distância d entre processos de renovação binários. Obtivemos condições sob as quais esta distância pode ser atingida entre tais processos / Abstract: This thesis is devoted to the study of binary renewal processes obtained as aggregation of states from Markov processes with finite alphabet. In the rst part, we use a matrix approach to obtain conditions under which the aggregated process belongs to each of the following classes: (1) Markov of finite order, (2) process of infinite order with continuous transition probabilities, (3) Gibbsian process. The second part deals with the distance d between binary renewal processes. We obtain conditions under which this distance can be achieved between these processes / Doutorado / Estatistica / Doutor em Estatística

No description available.

Το θέμα της παρούσας μεταπτυχιακής διπλωματικής εργασίας είναι η εφαρμογή της θεωρίας των Σχεδόν Πλήρως Αναλυόμενων Στοχαστικών Συστημάτων (Nearly Completely Decomposable) σε μία σειρά προβλημάτων στα οποία παραδοσιακές προσεγγίσεις αποδεικνύονται ερμηνευτικά στείρες και υπολογιστικά κοστοβόρες. Στο πρώτο μέρος της διπλωματικής αφού κάνουμε μία διαισθητικού τύπου παρουσίαση της ιδέας της decomposability και συνοψίσουμε τα απαραίτητα στοιχεία του θεωρητικού υποβάθρου που χρησιμοποιούμε στα πλαίσια της εργασίας, παραθέτουμε τονπυρήνα της θεωρίας της decomposability, όπως αυτή θεμελιώνεται μαθηματικά από τον Courtois στην κλασική του μονογραφία. Τέλος, παραθέτουμε και μία υλοποίηση του KMS αλγορίθμου Συσσωμάτωσης/Αποσυσσωμάτωσης, για τη λύση NCD συστημάτων. Το δεύτερο μέρος του συγγράμματος, είναι αφιερωμένο στην εφαρμογή της NCD σε δύο ενδιαφέροντα προβλήματα εκτίμησης απόδοσης υπολογιστικών συστημάτων. Συγκεκριμένα, μελετούμε μία ιδιότυπη ουρά που εξυπηρετεί πελάτες διαφορετικών κλάσεων, με τις ανά κλάση αφίξεις να χαρακτηρίζονται από εναλλαγές μεταξύ περιόδων ηρεμίας και κινητικότητας και την εξυπηρέτηση να γίνεται σε δέσμες πελατών της ίδιας κλάσης. Το κίνητρο για τη μελέτη αυτής της ουράς εντοπίζεται στη bursty φύση της μεταγωγής πακέτων στα σύγχρονα δίκτυα αλλά και στους reassembly buffers των multicluster πολυεπεξεργαστικών συστημάτων. Η ανάλυση της ουράς με παραδοσιακές τεχνικές οδηγεί αναπόφευκτα σε μαρκοβιανή αλυσίδα πολύ μεγάλου χώρου κατάστασης. Εμείς, ξεκινάμε από το πλήρες στοχαστικό μητρώο και αφού διαμερίσουμε κατάλληλα το χώρο καταστάσεων, αποδεικνύουμε ικανές συνθήκες υπό τις οποίες το αρχικό σύστημα είναι δυνατόν να αναλυθεί σε πολλαπλά επίπεδα υποσυστημάτων, η αυτόνομη ανάλυση των οποίων δίνει μία πολύ καλή προσέγγιση της στάσιμης κατανομής του αρχικού συστήματος. Επίσης, παραθέτουμε και αποδεικνύουμε μία ικανή συνθήκη για μηδενικό σφάλμα προσέγγισης και την ερμηνεύουμε σε όρους προδιαγραφών του προβλήματος. Τέλος, θεωρούμε μία ειδική συμμετρική εκδοχή για την οποία καταφέρνουμε να δώσουμε μία κλειστή έκφραση της κατανομής πληρότητας της ουράς συναρτήσει της λύσης των υποσυστημάτων. Για να δείξουμε την απλοποίηση της ανάλυσης που επιφέρει η χρήση του NCD μοντέλου θεωρούμε ένα σενάριο για το οποίο προχωρούμε την ανάλυση σε βάθος και καταφέρνουμε να εξάγουμε χρήσιμες μετρικές στις οποίες, σε αντίθετη περίπτωση, θα ήταν ιδιαίτερα επίπονο να καταλήξει κανείς. Συγκεκριμένα, υπολογίζουμε την πιθανότητα blocking και δείχνουμε πως αυτή μειώνεται σχεδόν εκθετικά με το μέγεθος της ουράς. Βλέπουμε τελικά πως η εκμετάλλευση της NCD ιδιότητας από τη μία διευκολύνει την ανάλυση και από την άλλη παρέχει ανεκτίμητη διαίσθηση σχετικά με τη μεταβατική συμπεριφορά του συστήματος προς την κατάσταση στατιστικής ισορροπίας. Το δεύτερο μέρος της διπλωματικής κλείνει με τη μελέτη κριτηρίων υπό τα οποία, πολυεπεξεργαστικά συστήματα που χωρίζονται σε ομάδες ισχυρά αλληλεπιδρώντων επεξεργαστών, μπορούν να αναλυθούν με χρήση της θεωρίας NCD. Είναι γνωστό πως στα δίκτυα ουρών αναμονής συγκρίσιμων ρυθμών εξυπηρέτησης, η NCD του μητρώου πιθανοτήτων δρομολόγησης συνεπάγεται την NCD του δικτύου. Εμείς, θεωρούμε μία ειδική περίπτωση τέτοιων συστημάτων για την οποία δείχνουμε ένα, εύκολο να ελεγχθεί, κριτήριο για NCD. Τέλος, εξετάζουμε βαθύτερα το σφάλμα της προσέγγισης, και χρησιμοποιώντας ένα πρόσφατο αποτέλεσμα της θεωρίας των σχεδόν ασύζευκτων μαρκοβιανών αλυσίδων δίνουμε έναν επιπλέον ποιοτικό περιορισμό που πρέπει να ικανοποιούν τα εν λόγω συστήματα για να πάρει κανείς ικανοποιητική προσέγγιση από την ανάλυσή τους σε ανεξάρτητα block. Στο τρίτο μέρος της παρούσας εργασίας, εξετάζουμε την εφαρμογή της NCD στο πρόβλημα της κατάταξης ιστοσελίδων. Η πρόσφατη έρευνα έχει σχολιάσει την ειδική δομή του στοχαστικού μητρώου που προκύπτει από το γράφο του διαδικτύου· συγκεκριμένα, οι τοπολογικές ιδιότητες της αυτοoργάνωσης του Ιστού φαίνεται να παράγουν ένα στοχαστικό μητρώο με NCD δομή. Εμείς, αφού παραθέσουμε μία σύνοψη των μαθηματικών πίσω από τον αλγόριθμο PageRank, σχολιάζουμε και δικαιολογούμε διαισθητικά την NCD δομή του Ιστού αλλά και τη φύση των υποσυστημάτων. Τέλος, προτείνουμε έναν νέο αλγόριθμο κατάταξης με το όνομα NCDawareRank, o οποίος εκμεταλλεύεται την NCD ιδιότητα για να πετύχει ποιοτικότερο και ταχύτερο ranking. Μάλιστα, δίνουμε δύο εκδοχές του αλγορίθμου, μία σειριακή και μία παράλληλη, η οποία εκμεταλλεύεται την NCD του Ιστού και υπολογιστικά. Τα οφέλη που υπόσχεται ο NCDawareRank τα επιβεβαιώνουμε και πειραματικά εκτελώντας μία σειρά από πειράματα τόσο σε τεχνητά όσο και σε πραγματικά δεδομένα, αντιπαραβάλλοντας τα αποτελέσματα μας με αυτά του αλγορίθμου PageRank. O NCDawareRank φαίνεται μάλιστα να δίνει λύση σε ένα γνωστό πρόβλημα του PageRank: αυτό της μεροληψίας εναντίον νεοεισερχομένων σελίδων. Άλλο ένα, τέλος, παράπλευρο όφελος του αλγορίθμου NCDawareRank είναι αυτό της Levelwise κατάταξης, η οποία εκτός της σημασίας που έχει αφεαυτής, μπορεί να υποδείξει εξυπνότερο crawling ή ακόμα και αποδοτικότερα σχήματα ευρετηριοποίησης του Ιστού. Στο τέταρτο και τελευταίο μέρος της διπλωματικής εφαρμόζουμε την NCD στην εύρεση των στοχαστικά ευσταθών καταστάσεων μίας κατηγορίας εξελικτικών παιγνίων στα οποία εμφανίζονται πολυεπίπεδες στρατηγικές δυναμικές. Αφού παραθέσουμε κάποιες πρόσφατες παρατηρήσεις από τη βιβλιογραφία της οικονομετρίας σχετικά με την αξιοποίηση της NCD στην προσεγγιστική ανάλυσή τους, αποδεικνύουμε συνθήκες υπό τις οποίες είναι δυνατόν να πετύχει κανείς ακριβή ανάλυση. / The purpose of this master’s thesis is the application of the theory of Nearly Completelely Decomposable stochastic systems to a number of interesting problems for which tra- ditional techniques turn out to be both intuitively unappealing and computationally in- tractable. In the first part of this work, after introducing, the concept of decomposability in an intuitive way and summarizing the essential elements of the theoretical background that is necessary to follow the rest of the text, we present the fundamental mathematical principles of NCD as established by Courtois in his classic monograph. Finally, we give an implementation of the KMS iterative aggregation/disaggregation algorithm which is commonly used for the solution of NCD systems. The second part of the dissertation is devoted to the application of NCD to two inter- esting problems of Computer Systems Performance Evaluation. Specifically, we study an uncommon discrete time queue that serves customers from different classes, with the ar- rivals of each class characterized by alternating busy and idle periods. The service is done in batches of customers of the same class. The motivation behind the study of this queue, lies in the bursty nature of packet switching, as well as in the modern reassembly buffers of multicluster multiprocessor systems. The traditional analysis techniques of this queue inevitably lead to Markov chains with very large state space. We begin with the complete stochastic matrix and after careful partitioning of the state space, we give sufficient condi- tions under which the original system can be analysed through multi level decomposition into subsystems, the autonomous analysis of which results in a very good approximation to the stationary distribution of the original system. Furthermore, we present and prove a sufficient condition for an error-free approximation and we give an interpretation of this condition in terms of the specifications of the problem. Finally, we consider a special sym- metric version of the problem, for which we manage to derive a closed-form expression for the queue’s occupancy distribution as a function of the steady state probabilities of the subsystems. To demonstrate the simplification of the analysis brought by the NCD model, we con- sider a scenario in which we proceed to an in depth analysis and we manage to extract useful metrics the derivation of which, would be considerably harder without exploiting 13 Abstract 14 NCD. Specifically, we calculate the blocking probability and we show that it decreases almost exponentially with the size of the queue. From our analysis, it is clear that the exploitation of the NCD model increases significantly our ability to understand the dy- namics of our system and to interpret aspects of its transient behaviour towards statistical equilibrium. The second part of this work ends with the study of criteria under which multipro- cessing systems, that can be divided into groups of strongly interacting processors, can be analysed using the theory of NCD. It is known that in queueing networks with servers of comparable service rates, the NCD of the routing probability matrix implies the NCD of the network. We consider a special case of such systems and we derive an easy to check criterion for NCD. Finally, we look deeper into the error analysis of this approach, and using a recent result from the theory of nearly uncoupled Markov chains, we give an addi- tional qualitative constrain to be met by these systems in order to get a good approximation of their analysis into independent blocks. In the third part of this paper, we examine the application of NCD to the problem of ranking websites. Recent research has commented on the special structure of the stochastic matrix which corresponds to the web-graph. In particular, the topological properties of the Web seems to produce a NCD stochastic matrix. Here, after presenting briefly the mathe- matical basis of PageRank, we give a linear algebraic as well as an intuitive justification of the NCD Web structure and we discuss the nature of the subsystems. Finally, we propose a new ranking algorithm named NCDawareRank, which exploits NCD in order to achieve a fairer and faster ranking. Indeed, we give two versions of the algorithm, one serial and one parallel, in which we take advantage of the computational benefits of NCD as well. The advantages of NCDawareRank are then confirmed experimentally through a series of tests on both, artificial and real data. NCDawareRank seems to solve a known problem of PageRank: the bias against new websites. Finally, another side benefit of our algorithm is that it makes it easy to extract a level-wise ranking, which besides its importance in itself, may indicate smarter crawling or even more sophisticated and efficient indexing schemes of the Web. Finally, in the fourth part of this work we apply NCD to the problem of finding the stochastically stable states of a class of evolutionary games which involve multilevel strategic dynamics. After presenting some interesting recent results coming from the lit- erature of econometrics, we give conditions under which it is possible to get the exact stochastically stable states through the use of NCD.