Thesis (Ph. D.)--University of Washington, 2000. / Vita. Includes bibliographical references (p. 109-112).

No description available.

Diss. (sammanfattning) Uppsala : Uppsala universitet, 2005. / Härtill 4 uppsatser.

Orientador: Simão Nicolau Stelmastchuk / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-17T21:13:11Z (GMT). No. of bitstreams: 1 Vieira_FranciscoZuiltonGoncalves_M.pdf: 2460011 bytes, checksum: bb34e809ab256fe3bb3b1bd74fc35eec (MD5) Previous issue date: 2011 / Resumo: Esta dissertação tem como tema o estudo das cadeias de Markov discretas com valores em um espaço de estados enumerável. Cadeias de Markov são processos estocásticos no seguinte sentido: dado o momento presente, o futuro não depende do passado, mas somente do momento presente. Nosso estudo é realizado sobre cadeias de Markov homogêneas (CMH) discretas. Inicialmente, introduzimos a definição e conceitos básicos das CMH discretas. Tais estudos nos conduzem ao conceito de topologia das matrizes de Transição associada as CMH. A topologia de tais cadeias é a ferramenta necessária para o estudo dos conjuntos recorrentes e transcientes, os quais são de grande importância nesta teoria. O estudo de estados estacionários e a propriedade forte de Markov também são abordados. Esta última propriedade serve para construção do conceito de estado recorrente. A partir deste último conceito trabalhamos com os conceitos de positivo e nulo recorrente. Por fim, estudamos o importante conceito de tempo absorção, o qual é entendido como o tempo que algum estado é absorvido a um conjunto recorrente / Abstract: This dissertation deals with the study of discrete Markov chains with values in a countable state space. Markov chains are processes stochastic in the following sense: given the present moment, the future does not depend on the past, but only in the present moment. Our study is conducted on homogeneous Markov chains (HMC) discrete. Initially, we introduced the definition and the basic concepts of discrete HMC. Such studies lead us to understand the concept of topology Transition matrices associated to HMC. The topology of these chains is a necessary tool for the study of the recurrent and transient sets, which are of great importance in this theory. The study of steady states and the strong Markov properties are also addressed. This latter property serves to build the concept of recurrent state. From this latter concept we work with the concepts of positive and null recurrent. Finally, we studied the important concept of absorption time, which is understood as the time that some state is absorbed to a set recurrent / Mestrado / Matematica / Mestre em Matemática

Accurate terrain models provide the chassis designer with a powerful tool to make informed design decisions early in the design process. During this stage, engineers are challenged with predicting vehicle loads through modeling and simulation. The accuracy of these simulation results depends not only on the fidelity of the model, but also on the excitation to the model. It is clear that the terrain is the main excitation to the vehicle [1]. The inputs to these models are often based directly on physical measurements (terrain profiles); therefore, the terrain measurements must be as accurate as possible. A collection of novel methods can be developed to aid in the study and application of 3D terrain measurements, which are dense and non-uniform, including efficient gridding, stochastic modeling, and compact characterization. Terrain measurements are not collected with uniform spacing, which is necessary for efficient data storage and simulation. Many techniques are developed to help effectively grid dense terrain point clouds in a curved regular grid (CRG) format, including center and random vehicle paths, sorted gridding methods, and software implementation. In addition, it is beneficial to characterize the terrain as a realization of an underlying stochastic process and to develop a mathematical model of that process. A method is developed to represent a continuous-state Markov chain as a collection of univariate distributions, to be applied to terrain road profiles. The resulting form is extremely customizable and significantly more compact than a discrete-state Markov chain, yet it still provides a viable alternative for stochastically modeling terrain. Many new simulation techniques take advantage of 3D gridded roads along with traditional 2D terrain profiles. A technique is developed to model and synthesize 3D terrain surfaces by applying a variety of 2D stochastic models to the topological components of terrain, which are also decomposed into frequency bandwidths and down-sampled. The quality of the synthetic surface is determined using many statistical tests, and the entire work is implemented into a powerful software suite. Engineers from many disciplines who work with terrain surfaces need to describe the overall physical characteristics compactly and consistently. A method is developed to characterize terrain surfaces with a few coefficients by performing a principal component analysis, via singular value decomposition (SVD), to the parameter sets that define a collection of surface models. / Master of Science

Integrated Vehicle Health Management (IVHM) systems use models and algorithmic techniques to process Condition-based Data (CBD) to offer prognostic information and actionable imperatives in support of Condition-based Maintenance (CBM) for the system. IVHM technology was first introduced by NASA to gather data, diagnose, detect, and predict faults, and support operational and post-maintenance activities in space vehicles. Eventually, it expanded to other vehicle types such as aircraft, ships, and land vehicles [1]. In recent years, the United States Army has been implementing a policy of CBM to transition from preventive to predictive maintenance [2]. One of the many challenges faced by the Army is the lack of accurate methods to assess ground vehicle reliability using modeling and/or simulation. This study aims at developing a Markov Chain-based algorithm that can detect anomalies and that is capable of accurately predicting the operational states of military ground vehicles. Several different Markov Chain Models (MCMs) have been developed and tested in their ability to predict the next state of a vehicle, given its current state (diagnostics and prognostics), and to examine how well a given model can detect unknown measurements (anomaly detection). A target of 90% Correct Classification (PCC) was established for all the vehicle performance data. The results suggest that it is possible to predict at a high level of accuracy the likely operational states of the military vehicles using MCMs. The anomaly detection test results revealed that MCMs can clearly distinguish a change in the performance data, that does not match the expected performance.

Continuous-time Markov chains (CTMC's) form a convenient mathematical framework for analyzing random systems across many different disciplines. A specific research problem that is often of interest is to try to predict maximum probability sequences of state transitions given initial or boundary conditions. This work shows how to solve this problem exactly through an efficient dynamic programming algorithm. We demonstrate our approach through two different applications - ranking mutational pathways of HIV virus based on their probabilities, and determining the most probable failure sequences in complex fault-tolerant engineering systems. Even though CTMC's have been used extensively to realistically model many types of complex processes, it is often a standard practice to eventually simplify the model in order to perform the state evolution analysis. As we show here, simplifying approaches can lead to inaccurate and often misleading solutions. Therefore we expect our algorithm to find a wide range of applications across different domains.

Consideremos uma sequência de lançamentos de moedas em que denotamos o resultado de cada lançamento por H, se der cara, ou por T, se der coroa. Formemos uma palavra apenas com H\'s e T\'s, por exemplo, HHHHH ou HTHTH. Quantas vezes arremessaremos uma mesma moeda ate que uma das duas palavras acima ocorrera? Por exemplo, dadas as sequências THTHHHHH e TTHTTHTHTH. O numero de vezes que arremessamos a moeda ate que HHHHH e HTHTH ocorreram pela primeira vez e oito e dez, respectivamente. Podemos generalizar a ideia acima para um numero finito de palavras em um alfabeto finito qualquer. Assim, o nosso principal objetivo dessa dissertação e encontrarmos a distribuição do tempo de espera ate que um membro de uma coleção finita de palavras seja observado em uma sequência de ensaios de Markov de letras de um alfabeto finito. Mais especificamente, as letras de um alfabeto finito são geradas por uma cadeia de Markov ate que uma das palavras de uma coleção finita ocorra. Além disso encontraremos a probabilidade de que determinada palavra ocorra antes das demais palavras pertencentes a um mesmo conjunto finito. Por ultimo encontraremos a função geradora de probabilidade do tempo de espera. / Consider a sequence of independent coin flips where we denote the result of any landing for H, if coming up head, or T, otherwise. Create patterns with H\'s and T\'s, for example, HHHHH or HTHTH. How many times do we have to land the same coin until one such two patterns happens? For example, let the sequences being THTHHHHH and TTHTTHTHTH. The number of times that we landed the coin until HHHHH and HTHTH happens it was eight and ten times respectively. We can generalize this idea for a finite number of patterns in any finite set. Then, the first of all interest of this dissertation is to find the distribution of the waiting time until a member of a finite colection of patterns is observed in a sequence of Markov chains of letters in from finite set. More specically the letters in a finite set are generated by Markov chain until one of the patterns in any finite set happens. Besides that, we will find the probability of a pattern happen before of all patterns in the same finite set. Finally we will find the generator function of probability of waiting time.

A contextualização de eventos próximos da realidade dos alunos aliada a utilização da informática como ferramenta auxiliar no aprendizado da probabilidade, pode ser um dos caminhos para a melhoria do ensino de Matemática. Assim, este trabalho buscou a modelagem matemática de eventos temporais do dia a dia dos alunos do ensino básico. A modelagem se baseou no conceito de Cadeias de Markov e teve o objetivo de auxiliar o professor dos ensinos fundamental e médio a introduzir o conceito de probabilidade. As aplicações das Cadeias de Markov também possibilitam apresentar aos alunos dos ensinos médio e fundamental como a Matemática pode resolver problemas do cotidiano. Para introduzir os conceitos de Cadeias de Markov foi necessário uma revisão teórica dos conceitos da teoria da probabilidade e os conceitos de Cadeias de Markov foram estudados em literatura em língua inglesa. Considerando o interesse e curiosidade demonstrado pelos alunos em experiência prévia com o material, as atividades mostraram-se muito eficientes. Espera-se que esse trabalho possa contribuir para a prática docente de outros professores. / The contextualization of events close to the reality of the students allied to the use of information technology as an auxiliary tool in the learning of probability, can be one of the ways to improve the teaching of Mathematics. Thus, this paper sought the mathematical modeling of temporal events from the daily of students of basic Education. The modeling was based on the concept of Markov Chains and aimed to help the middle and high school teachers to introduce the concept of probability. The applications of the Markov Chains also make it possible to present to the students of the middle and high school teachings how Mathematics can solve daily problems. To introduce the concepts of Markov Chains, a theoretical revision of the concepts of probability theory was necessary and the concepts of Markov Chains were studied in literature in English Language. Considering the interest and curiosity demonstrated by the students in previous experience with the material, the activities were very efficient. It is hoped that this paper may contribute to the teaching practice of other teachers.

Les chaînes de Markov constituent une famille de modèle statistique incontournable dans de nombreuses applications, dont le spectre s'étend de la compression de texte à l'analyse des séquences biologiques. Un problème récurrent dans leur mise en oeuvre face à des données réelles est la nécessité de compromettre l'ordre du modèle, qui conditionne la complexité des interactions modélisées, avec la quantité d'information fournies par les données, dont la limitation impacte négativement la qualité des estimations menées. Les arbres de contexte permettent une granularité fine dans l'établissement de ce compromis, en permettant de recourir à des longueurs de mémoire variables selon le contexte rencontré dans la séquence. Ils ont donné lieu à des outils populaires tant pour l'indexation des textes que pour leur compression (Context Tree Maximisation – CTM - et Context Tree Weighting - CTW). Nous proposons une extension de cette classe de modèles, en introduisant les arbres de contexte parcimonieux, obtenus par fusion de noeuds issus du même parent dans l'arbre. Ces fusions permettent une augmentation radicale de la granularité de la sélection de modèle, permettant ainsi de meilleurs compromis entre complexité du modèle et qualité de l'estimation, au prix d'une extension importante de la quantité de modèles mise en concurrence. Cependant, grâce à une approche bayésienne très similaire à celle employée dans CTM et CTW, nous avons pu concevoir une méthode de sélection de modèles optimisant de manière exacte le critère bayésien de sélection de modèles tout en bénéficiant d'une programmation dynamique. Il en résulte un algorithme atteignant la borne inférieure de la complexité du problème d'optimisation, et pratiquement tractable pour des alphabets de taille inférieure à 10 symboles. Diverses démonstrations de la performance atteinte par cette procédure sont fournies en dernière partie. / Markov chains, as a universal model accounting for finite memory, discrete valued processes, are omnipresent in applied statistics. Their applications range from text compression to the analysis of biological sequences. Their practical use with finite samples, however, systematically require to draw a compromise between the memory length of the model used, which conditions the complexity of the interactions the model may capture, and the amount of information carried by the data, whose limitation negatively impacts the quality of estimation. Context trees, as an extension of the model class of Markov chains, provide the modeller with a finer granularity in this model selection process, by allowing the memory length to vary across contexts. Several popular modelling methods are based on this class of models, in fields such as text indexation of text compression (Context Tree Maximization and Context Tree Weighting). We propose an extension of the models class of context trees, the Parcimonious context trees, which further allow the fusion of sibling nodes in the context tree. They provide the modeller with a yet finer granularity to perform the model selection task, at the cost of an increased computational cost for performing it. Thanks to a bayesian approach of this problem borrowed from compression techniques, we succeeded at desiging an algorithm that exactly optimizes the bayesian criterion, while it benefits from a dynamic programming scheme ensuring the minimisation of the computational complexity of the model selection task. This algorithm is able to perform in reasonable space and time on alphabets up to size 10, and has been applied on diverse datasets to establish the good performances achieved by this approach.