Le contrôle de l'information émise par un système a vu son utilité grandir avec la multiplication des systèmes communicants. Ce contrôle peut être réalisé par exemple pour révéler une information du système, ou au contraire pour en dissimuler une. Le diagnostic notamment cherche à déterminer, grâce à l'observation du système, si une faute a eu lieu au sein de celui-ci. Dans cette thèse, nous établissons des bases formelles à l'analyse des problèmes du diagnostic pour des modèles stochastiques. Nous étudions ensuite ces problèmes dans plusieurs cadres (fini/infini, passif/actif). / The control of the information given by a system has seen increasing importance recently with the multiplication of communicating systems. This control can be used in order to disclose an information of the system, or, oppositely, to hide one. Diagnosis for instance tries to determine from the observation produced by the system whether a fault occurred within it or not. In this PhD, we establish formal foundations to the analysis of the diagnosis problems for stochastic models. We then study these problems in multiple framework (finite/infinite, passive/active).

Nesta dissertação de mestrado, vamos apresentar uma prova para os grandes desvios para variáveis aleatórias independentes e identicamente distribuídas com todos os momentos finitos e para a medida empírica de cadeias de Markov com espaço de estados finito e tempo discreto. Além disso, abordaremos os teoremas de Sanov e Gärtner-Ellis. / In this master thesis it is presented a proof of the large deviations for independent and identically distributed random variables with all finite moments and for the empirical measure of Markov chains with finite state space and with discrete time. Moreover, we address the theorems of Sanov and of Gartner-Ellis.

Grande parte do sucesso do Google provêm do algoritmo Page Rank, que avalia quantitativamente a importância de cada página na web. Esta ordenação é obtida através do vetor estacionário de uma matriz estocástica específica, utilizando o Método das Potências. A velocidade de convergência deste método será avaliada em detalhe, já que se trata de uma resposta imediata da pesquisa do usuário. Afim de entender as diferentes situações que o modelo pode enfrentar, diversas simulações são apresentadas neste trabalho. Em particular, estamos interessados nos fatores que influenciam a velocidade de convergência. Para tanto, o número de páginas total e de cada conjunto fechado, bem como o número de conjuntos fechados e de nós pendentes foram estudados. / Great part of Google\'s success comes from the Page Rank algorithm, wich quantitatively evaluates the importance of each page on the web. This sort is achieved through a specific stochastic matrix stationary vector, using the Power Method. The convergency speed of this method will be evaluated in details, since this is a imediate response for the user search. In order to understand the diferent situations the model can confront, several simulations are shown in this work. In particular, we are interested in the factors which influences the convergency speed. For that, the total and inside each closed set number of pages and also the closed sets and dangling nodes numbers were studied.

Uma forma de se reduzir o custo (em termos tanto de área de chip quanto de consumo de energia) de algoritmos de processamento de sinais é empregar aritmética de ponto fixo, usando o menor número de bits possível para se representar as variáveis e coeficientes necessários. Com isso, consegue-se reduzir a complexidade do hardware, levando a economias de energia e de área de chip em circuitos dedicados. A escolha do nível de quantização a que cada variável deve ser submetida depende de se conhecer o efeito da quantização de cada variável nas saídas do sistema, o que pode ser conseguido através de simulações (em geral lentas) ou por métodos analíticos. Este documento propõe avanços a uma nova metodologia de análise de algoritmos para processamento digital de sinais implementados em aritmética de ponto fixo, usando modelos baseados em cadeias de Markov. As contribuições desta dissertação são as seguintes: Filtros IIR de primeira e de segunda ordem são analisados via cadeia de Markov, pressupondo que a entrada possui uma função densidade de probabilidade conhecida. O modelo é desenvolvido de forma geral, de forma que pode ser considerada uma função de densidade de probabilidade qualquer. A saída dos filtros é usada para definir os estados da cadeia. O modelo via cadeia de Markov para o coeficiente do algoritmo LMS unidimensional é estendido para entrada correlacionada. Nesse caso, os estados passam a ser descritos em termos do coeficiente e do da entrada anterior. Um exemplo assumido função de densidade de probabilidade de entrada gaussiana para o filtro adaptativo é apresentado. / The implementation cost of signal processing algorithms may be reduced by using fixed-point arithmetic with the smallest possible word-length for each variable or parameter. This allows the designer to reduce hardware complexity, leading to economy of energy and chip area in dedicated circuits. The choice of word-length depends on the determination of the effect at the output of the quantization of each variable, which may be obtained through simulations (generally slow) or through analytical methods. This document proposes new advances to a new analysis method for digital signal processing algorithms implemented in fixed-point arithmetic, based on Markov chain models. Our contributions are the following: A Markov chain model is used to study first and second order IIR filters for an known input density probability function. The model is general and can be applied for any probability function. We use the output of the filters to define the states of the Markov chain. The unidimensional LMS Markov chain model is extended to correlated input. The states are defined by a pair considering the coefficient and the previous input and an example assuming Gaussian-distributed input is presented.

The overall aim of this portfolio was to develop an understanding of how music fits socially, historically, and technically into the landscape of 21st century culture. The aims of the portfolio were to explore static harmony (resonance), statistically similar melodic sequences, electronic drones, rhythmic development (cycles), melodic development, and non-linear textures. A compositional process turned personal journey became the driving energy for these works, and one can see a clear development, as each piece is built on the findings of previous ones. The musical language became more sophisticated as a result of both these new techniques as well as interactions with other collaborators (including musicians, dancers, scientists, visual artists, and programmers). Each of the technical aims was developed throughout the creation of the portfolio. These are among the techniques which helped shape late 20th century music, with the goal of joining some of them together in new and aesthetically pleasing ways. Early on, there was a shift in the way they were applied, especially creating resonance, which was first done with acoustic instruments and then electronic drones. The repetition and rhythmic cycles also developed by using transition matrices from a Markov Chain process to create 'melody rhythms' (discussed more in Sequence). Pieces like Lost in Space and Smoke of Freedom were written by combining all of these techniques together in a fusion of static harmony, rhythmic cycles, and expressive melodies. I also had a social motivation when writing these works. For example, Wind Gust 42058 uses the trend of 'data is the new gold' by giving the audience a meaningful way to 'experience the data'. Also, Smoke of Freedom tells the story from the perspective of a man who is oppressed in China, not dissimilar from the four Hong Kong book sellers who were taken away by Chinese authorities for 'selling restricted books'. When this occurred in 2015, a lot of people were thinking of leaving the city in search of a more open society, and Smoke of Freedom follows the story of a man who does exactly that, leaving everything behind in search of a better life. The Answered Hymn is a unique piece in that it was performed at Westminster Abbey and St. Martin-in-the-Fields for special services celebrating the 500th anniversary of Lutheranism. The performances brought together 12 different choirs from around the world, each singing in their own language, and, in a 'Post-Brexit' United Kingdom, aimed to bring together themes of multi-nationalism and peace. The musical language developed during the course of this portfolio shows how musical technique can fit into and comment on the social, technological, and historical landscape of 21st century culture.

One of the newer and rapidly developing approaches in quantum computing is based on "quantum walks," which are quantum processes on discrete space that evolve in either discrete or continuous time and are characterized by mixing of components at each step. The idea emerged in analogy with the classical random walks and stochastic techniques, but these unitary processes are very different even as they have intriguing similarities. This thesis is concerned with study of discrete-time quantum walks. The original motivation from classical Markov chains required for discrete-time quantum walks that one adds an auxiliary Hilbert space, unrelated to the one in which the system evolves, in order to be able to mix components in that space and then take the evolution steps accordingly (based on the state in that space). This additional, "coin," space is very often an internal degree of freedom like spin. We have introduced a general framework for construction of discrete-time quantum walks in a close analogy with the classical random walks with memory that is rather different from the standard "coin" approach. In this method there is no need to bring in a different degree of freedom, while the full state of the system is still described in the direct product of spaces (of states). The state can be thought of as an arrow pointing from the previous to the current site in the evolution, representing the one-step memory. The next step is then controlled by a single local operator assigned to each site in the space, acting quite like a scattering operator. This allows us to probe and solve some problems of interest that have not had successful approaches with "coined" walks. We construct and solve a walk on the binary tree, a structure of great interest but until our result without an explicit discrete time quantum walk, due to difficulties in managing coin spaces necessary in the standard approach. Beyond algorithmic interests, the model based on memory allows one to explore effects of history on the quantum evolution and the subtle emergence of classical features as "memory" is explicitly kept for additional steps. We construct and solve a walk with an additional correlation step, finding interesting new features. On the other hand, the fact that the evolution is driven entirely by a local operator, not involving additional spaces, enables us to choose the Fourier transform as an operator completely controlling the evolution. This in turn allows us to combine the quantum walk approach with Fourier transform based techniques, something decidedly not possible in classical computational physics. We are developing a formalism for building networks manageable by walks constructed with this framework, based on the surprising efficiency of our framework in discovering internals of a simple network that we so far solved. Finally, in line with our expectation that the field of quantum walks can take cues from the rich history of development of the classical stochastic techniques, we establish starting points for the work on non-Abelian quantum walks, with a particular quantum walk analog of the classical "card shuffling," the walk on the permutation group. In summary, this thesis presents a new framework for construction of discrete time quantum walks, employing and exploring memoried nature of unitary evolution. It is applied to fully solving the problems of: A walk on the binary tree and exploration of the quantum-to-classical transition with increased correlation length (history). It is then used for simple network discovery, and to lay the groundwork for analysis of complex networks, based on combined power of efficient exploration of the Hilbert space (as a walk mixing components) and Fourier transformation (since we can choose this for the evolution operator). We hope to establish this as a general technique as its power would be unmatched by any approaches available in the classical computing. We also looked at the promising and challenging prospect of walks on non-Abelian structures by setting up the problem of "quantum card shuffling," a quantum walk on the permutation group. Relation to other work is thoroughly discussed throughout, along with examination of the context of our work and overviews of our current and future work. / Graduation date: 2012

We define a service factory to be a network of service-related-workstations, at which assigned workers process work-in-progress that flows through the workstations. Examples of service factory work include mail processing and sorting, check processing and telephoned order processing. Exogenous work may enter the factory at any workstation according to any time-of-day profile. Work-in-progress flows though the factory in discrete time according to Markovian routings. Workers, who in general are cross trained, may work part time or full time shifts, may start work only at designated shift starting times, and may change job assignments at midshift. In order to smooth the flow of work-in-progress through the service factory, work-in-progress may be temporarily inventoried (in buffers) at work stations. The objective is to schedule the workers (and correspondingly, the workflow) in a manner that minimizes labor costs subject to a variety of service-level, contractural and physical constraints. Motivated in part by analysis techniques of discrete time linear time-invariant (LTI) systems, an object-oriented linear programming (OOLP) model is developed. Using exogenous input work profiles typical of large U. S. mail processingfacilities, illustrative computational results are included.

This work analyzes the saving and consumption behavior of agents faced with the possibility of unemployment in a dynamic and stochastic life cycle model. The intertemporal optimization is based on Dynamic Programming with a backward recursion algorithm. The implemented uncertainty is not based on income shocks as it is done in traditional life cycle models but uses Markov probabilities where the probability for the next employment status of the agent depends on the current status. The utility function used is a CRRA function (constant relative risk aversion), combined with a CES function (constant elasticity of substitution) and has several consumption goods, a subsistence level, money and a bequest function. / Diese Arbeit modelliert das Spar- und Konsumverhalten von Individuen in Deutschland mit einem Lebenszyklusmodell. Dabei hat das Modell zwei Besonderheiten, erstens trifft die Möglichkeit arbeitslos zu werden nicht jeden Agenten des Models mit der gleichen Wahrscheinlichkeit, sondern wird von Bildungsabschluss und dem Beschäftigungsstatus des Agenten beeinflußt und zweitens weicht die verwendete Nutzenfunktion von den Standardnutzenfunktionen ab und implementiert Vererbung, Geld, verschiedene Güter und Subsistenzlevel. Der Optimierungsalgorithmus basiert auf Dynamischer Programmierung.

A Hidden Markov Model generates two basic stochastic processes, a Markov chain, which is hidden, and an observation sequence. The filtering process of a Hidden Markov Model is, roughly speaking, the sequence of conditional distributions of the hidden Markov chain that is obtained as new observations are received. It is well-known, that the filtering process itself, is also a Markov chain. A classical, theoretical problem is to find conditions which implies that the distributions of the filtering process converge towards a unique limit measure. This problem goes back to a paper of D Blackwell for the case when the Markov chain takes its values in a finite set and it goes back to a paper of H Kunita for the case when the state space of the Markov chain is a compact Hausdor space. Recently, due to work by F Kochmann, J Reeds, P Chigansky and R van Handel, a necessary and sucient condition for the convergence of the distributions of the filtering process has been found for the case when the state space is finite. This condition has since been generalised to the case when the state space is denumerable. In this paper we generalise some of the previous results on convergence in distribution to the case when the Markov chain and the observation sequence of a Hidden Markov Model take their values in complete, separable, metric spaces; it has though been necessary to assume that both the transition probability function of the Markov chain and the transition probability function that generates the observation sequence have densities.

Testing the reliability of an application usually requires a good usage model that accurately captures the likely sequences of inputs that the application will receive from the environment. The models being used in the literature are mostly based on Markov chains. They are used to generate test cases that are statistically close to what the applica-tion is expected to receive when in production. In this thesis, we propose a model for reli-ability testing that is created directly from the log file of a web application. Our proposed model is also based on Markov chains and has two components: one component, based on a modified tree, captures the most frequent behaviors, while the other component is another Markov chain that captures infrequent behaviors. The result is a statistically cor-rect model that shows clearly what most users do on the site. The thesis also presents an evaluation method for estimating the accuracy of vari-ous reliability-testing usage models. The method is based on comparison between ob-served users’ traces and traces inferred from the usage model. Our method gauges the accuracy of the reliability-testing usage model by calculating the sum of goodness-of-fit values of each traces and scaling the result between 0 and 1. Finally, we present an experimental study on the log of a real web site and discuss the way to use proposed usage model to generate test sequences, as well as strength and weakness of the model for reliability testing.