Reliable operation of every day use computing system, from simple coffee machines to complex flight controller system in an aircraft, is necessary to save time, money, and in some cases lives. System testing can check for the presence of unwanted execution but cannot guarantee the absence of such. Probabilistic model checking techniques have demonstrated significant potential in verifying performance and reliability of various systems whose execution are defined with likelihood. However, its inability to scale limits its applicability in practice. This thesis presents a new model checker, STAMINA, with efficient and scalable model truncation for probabilistic verification. STAMINA uses a novel model reduction technique generating a finite state representations of large systems that are amenable to existing probabilistic model checking techniques. The proposed method is evaluated on several benchmark examples. Comparisons with another state-of-art tool demonstrates both accuracy and efficiency of the presented method.

No description available.

Markov chains have been widely used to the credit risk measurement in the last years. Using these chains we can model movements and distribution of clients within rating grades. However, various types of markov chains could be used. The goal of the theses is to present these types together with their advan- tages and disadvantages. We focus our attention primarily on various parameter estimation methods and hypotheses testing about the parameters. The theses should help the reader with a decision, which model of a markov chain and which method of estimation should be used for him observed data. We focus our attention primarily on the following models: a discrete-time markov chain, a continuous-time markov chain (we estimate based on continuous- time observations even discrete-time observations), moreover we present an even- tuality of using semi-markov chains and semiparametric multiplicative hazard model applied on transition intensities. We illustrate the presented methods on simulation experiments and simu- lation studies in the concluding part. Keywords: credit risk, markov chain, estimates in markov chains, probability of default 1

La restauration statistique non-supervisée de signaux admet d'innombrables applications dans les domaines les plus divers comme économie, santé, traitement du signal, ... Un des problèmes de base, qui est au coeur de cette thèse, est d'estimer une séquence cachée (Xn)1:N à partir d'une séquence observée (Yn)1:N. Ces séquences sont considérées comme réalisations, respectivement, des processus (Xn)1:N et (Yn)1:N. Plusieurs techniques ont été développées pour résoudre ce problème. Le modèle parmi le plus répandu pour le traiter est le modèle dit "modèle de Markov caché" (MMC). Plusieurs extensions de ces modèles ont été proposées depuis 2000. Dans les modèles de Markov couples (MMCouples), le couple (X, Y) est markovien, ce qui implique que p(x|y) est également markovienne (alors que p(x) ne l'est plus nécessairement), ce qui permet les mêmes traitements que dans les MMC. Plus récemment (2002) les MMCouples ont été étendus aux "modèles de Markov triplet" (MMT), dans lesquels on introduit un processus auxiliaire U et suppose que le triplet T = (X, U, Y) est markovien. Là encore il est possible, dans un cadre plus général que celui des MMCouples, d'effectuer des traitements avec une complexité raisonnable. L'objectif de cette thèse est de proposer des nouvelles modélisations faisant partie des MMT et d'étudier leur pertinence et leur intérêt. Nous proposons deux types de nouveautés: (i) Lorsque la chaîne cachée est discrète et lorsque le couple (X, Y) n'est pas stationnaire, avec un nombre fini de "sauts" aléatoires dans les paramètres, l'utilisation récente des MMT dans lesquels les sauts sont modélisés par un processus discret U a donné des résultats très convaincants (Lanchantin, 2006). Notre première idée est d'utiliser cette démarche avec un processus U continu, qui modéliserait des non-stationnarités "continues" de(X, Y). Nous proposons des chaînes et des champs triplets et présentons quelques expériences. Les résultats obtenus dans la modélisation de la non-stationnarité continue semblent moins intéressants que dans le cas discret. Cependant, les nouveaux modèles peuvent présenter d'autres intérêts; en particulier, ils semblent plus efficaces que les modèles "chaînes de Markov cachées" classiques lorsque le bruit est corrélé; (ii) Soit un MMT T = (X, U, Y) tel que X et Y sont continu et U est discret fini. Nous sommes en présence du problème de filtrage, ou du lissage, avec des sauts aléatoires. Dans les modélisations classiques le couple caché (X, U) est markovien mais le couple (U, Y) ne l'est pas, ce qui est à l'origine de l'impossibilité des calculs exacts avec une complexité linéaire en temps. Il est alors nécessaire de faire appel à diverses méthodes approximatives, dont celles utilisant le filtrage particulaire sont parmi les plus utilisées. Dans des modèles MMT récents le couple caché (X, U) n'est pas nécessairement markovien, mais le couple (U, Y) l'est, ce qui permet des traitements exacts avec une complexité raisonnable (Pieczynski 2009). Notre deuxième idée est d'étendre ces derniers modèles aux triplets T = (X, U, Y) dans lesquels les couples (U, Y) sont "partiellement" de Markov. Un tel couple (U, Y) n'est pas de Markov mais U est de Markov conditionnellement àY. Nous obtenons un modèle T = (X, U, Y) plus général, qui n'est plus de Markov, dans lequel le filtrage et le lissage exacts sont possibles avec une complexité linéaire en temps. Quelques premières simulations montrent l'intérêt des nouvelles modélisations en lissage en présence des sauts. / Statistical unsupervised restoration of signal can be applied in many fields such as economy, health, signal processing, meteorology, finance, biology, reliability, transportation, environment, ... the main problem treated in this thesis is to estimate a hidden sequence (Xn)1:N based on an observed sequence (Yn)1:N. In Probabilistic treatment of the problem in these sequences are considered as accomplishments of respectively, process (Xn)1:N and (Yn)1:N. Several techniques based on statistical methods have been developed to solve this problem. The most common model known for this kind of problems is the “hidden Markov model”. In this model we assume that the hidden process X is Markovian and laws p(y|x) of Y are conditional on X are sufficiently simple so that the law p(x|y) is also Markovian, this property is necessary for treatment. Many Extensions of these models have been proposed since 2000. In Markov models couples (MMCouples), more general than the MMC, the pair (X,Y) is Markovian), implying that p(x|y) is also Markovian (when p(x) is not necessarily markovian), which allows the same treatment as in MMC. More recently (2002), were extended to MMCouples are extended to Markov models Triplet (MMT), in which we introduce an auxiliary process U and suppose that the triple T=(X,U,Y) is Markovian. It’s again possible, in a general case of MMCouples, to perform treatments with a reasonable complexity. The objective of this thesis is to propose new modeling of MMT and to investigate their relevance and interest. We offer two types of innovations: (i) When the hidden system is discrete and when the couple (X,Y) is not stationary with a finite number of random “jumps” in parameters, the recent use of MMT where the jumps are modelized by a discrete process U has been very convincing (Lanchantin, 2006). Our first idea is to use this approach with a continuous process U, which models non-steady "continuous" of (X,Y). We propose chains and triplet fields and present some experiments. The results obtained in the modeling of non-stationarity still seem less interesting that in the discrete case. However, new models may have other interests, in particular, they seem more efficient than “classic hidden Markov” when the noise is correlated; (ii) Considering an MMT T=(X,U,Y) such that X and Y are continuous and U is discrete finite. We are dealing with a problem of filtering, or smoothing, with random jumps. In classic modelling the hidden pair (X,U) is Markovian, but the pair (U,Y) is not, what is the cause of the impossibility of Exact calculations with time linear complexity. It is then necessary to use various approximate methods, including methods using particle filtering which are the most common. In recent models MMT the hidden pair (X,U) is not necessarily Markovian, but the pair (U,Y) is Markovian, which allows accurate treatment with a reasonable complexity (Pieczynski 2009). Our second idea is to extend these models to triplets T=(X,U,Y) where the pairs (U,Y) are "partially" Markovian. Such a pair (U,Y) is not Markovian but U is conditionally Markovian on Y. We have in result a model with general model T=(X,U,Y) , which is no more Markovian, wherein the filtering and smoothing are accurate possible with time linear complexity. Some preliminary Simulations show the importance of new smoothing models with of jumps.

Les modélisations par chaînes de Markov cachées permettent de résoudre un grand nombre de problèmes inverses se posant en traitement d’images ou de signaux. En particulier, le problème de segmentation figure parmi les problèmes où ces modèles ont été le plus sollicités. Selon ces modèles, la donnée observable est considérée comme une version bruitée de la segmentation recherchée qui peut être modélisée à travers une chaîne de Markov à états finis. Des techniques bayésiennes permettent ensuite d’estimer cette segmentation même dans le contexte non-supervisé grâce à des algorithmes qui permettent d’estimer les paramètres du modèle à partir de l’observation seule. Les chaînes de Markov cachées ont été ultérieurement généralisées aux chaînes de Markov couples et triplets, lesquelles offrent plus de possibilités de modélisation tout en présentant des complexités de calcul comparables, permettant ainsi de relever certains défis que les modélisations classiques ne supportent pas. Un lien intéressant a également été établi entre les modèles de Markov triplets et la théorie de l’évidence de Dempster-Shafer, ce qui confère à ces modèles la possibilité de mieux modéliser les données multi-senseurs. Ainsi, dans cette thèse, nous abordons trois difficultés qui posent problèmes aux modèles classiques : la non-stationnarité du processus caché et/ou du bruit, la corrélation du bruit et la multitude de sources de données. Dans ce cadre, nous proposons des modélisations originales fondées sur la très riche théorie des chaînes de Markov triplets. Dans un premier temps, nous introduisons les chaînes de Markov à bruit M-stationnaires qui tiennent compte de l’aspect hétérogène des distributions de bruit s’inspirant des chaînes de Markov cachées M-stationnaires. Les chaînes de Markov cachée ML-stationnaires, quant à elles, considèrent à la fois la loi a priori et les densités de bruit non-stationnaires. Dans un second temps, nous définissons deux types de chaînes de Markov couples non-stationnaires. Dans le cadre bayésien, nous introduisons les chaînes de Markov couples M-stationnaires puis les chaînes de Markov couples MM-stationnaires qui considèrent la donnée stationnaire par morceau. Dans le cadre évidentiel, nous définissons les chaînes de Markov couples évidentielles modélisant l’hétérogénéité du processus caché par une fonction de masse. Enfin, nous présentons les chaînes de Markov multi-senseurs non-stationnaires où la fusion de Dempster-Shafer est employée à la fois pour modéliser la non-stationnarité des données (à l’instar des chaînes de Markov évidentielles cachées) et pour fusionner les informations provenant des différents senseurs (comme dans les champs de Markov multi-senseurs). Pour chacune des modélisations proposées, nous décrivons les techniques de segmentation et d’estimation des paramètres associées. L’intérêt de chacune des modélisations par rapport aux modélisations classiques est ensuite démontré à travers des expériences menées sur des données synthétiques et réelles / Hidden Markov chains (HMCs) based approaches have been shown to be efficient to resolve a wide range of inverse problems occurring in image and signal processing. In particular, unsupervised segmentation of data is one of these problems where HMCs have been extensively applied. According to such models, the observed data are considered as a noised version of the requested segmentation that can be modeled through a finite Markov chain. Then, Bayesian techniques such as MPM can be applied to estimate this segmentation even in unsupervised way thanks to some algorithms that make it possible to estimate the model parameters from the only observed data. HMCs have then been generalized to pairwise Markov chains (PMCs) and triplet Markov chains (TMCs), which offer more modeling possibilities while showing comparable computational complexities, and thus, allow to consider some challenging situations that the conventional HMCs cannot support. An interesting link has also been established between the Dempster-Shafer theory of evidence and TMCs, which give to these latter the ability to handle multisensor data. Hence, in this thesis, we deal with three challenging difficulties that conventional HMCs cannot handle: nonstationarity of the a priori and/or noise distributions, noise correlation, multisensor information fusion. For this purpose, we propose some original models in accordance with the rich theory of TMCs. First, we introduce the M-stationary noise- HMC (also called jumping noise- HMC) that takes into account the nonstationary aspect of the noise distributions in an analogous manner with the switching-HMCs. Afterward, ML-stationary HMC consider nonstationarity of both the a priori and/or noise distributions. Second, we tackle the problem of non-stationary PMCs in two ways. In the Bayesian context, we define the M-stationary PMC and the MM-stationary PMC (also called switching PMCs) that partition the data into M stationary segments. In the evidential context, we propose the evidential PMC in which the realization of the hidden process is modeled through a mass function. Finally, we introduce the multisensor nonstationary HMCs in which the Dempster-Shafer fusion has been used on one hand, to model the data nonstationarity (as done in the hidden evidential Markov chains) and on the other hand, to fuse the information provided by the different sensors (as in the multisensor hidden Markov fields context). For each of the proposed models, we describe the associated segmentation and parameters estimation procedures. The interest of each model is also assessed, with respect to the former ones, through experiments conducted on synthetic and real data

Mathematical probability has a rich theory and powerful applications. Of particular note is the Markov chain Monte Carlo (MCMC) method for sampling from high dimensional distributions that may not admit a naive analysis. We develop the theory of the MCMC method from first principles and prove its relevance. We also define a Bayesian hierarchical model for generating data. By understanding how data are generated we may infer hidden structure about these models. We use a specific MCMC method called a Gibbs' sampler to discover topic distributions in a hierarchical Bayesian model called Topics Over Time. We propose an innovative use of this model to discover disease and treatment topics in a corpus of health insurance claims data. By representing individuals as mixtures of topics, we are able to consider their future costs on an individual level rather than as part of a large collective.

<p dir="ltr">This thesis presents probably approximately correct (PAC) bounds on estimates of the transition kernels of Controlled Markov chains (CMC’s). CMC’s are a natural choice for modelling various industrial and medical processes, and are also relevant to reinforcement learning (RL). Learning the transition dynamics of CMC’s in a sample efficient manner is an important question that is open. This thesis aims to close this gap in knowledge in literature.</p><p dir="ltr">In Chapter 2, we lay the groundwork for later chapters by introducing the relevant concepts and defining the requisite terms. The two subsequent chapters focus on non-parametric estimation. </p><p dir="ltr">In Chapter 3, we restrict ourselves to a finitely supported CMC with d states and k controls and produce a general theory for minimax sample complexity of estimating the transition matrices.</p><p dir="ltr">In Chapter 4 we demonstrate the applicability of this theory by using it to recover the sample complexities of various controlled Markov chains, as well as RL problems.</p><p dir="ltr">In Chapter 5 we move to a continuous state and action spaces with compact supports. We produce a robust, non-parametric test to find the best histogram based estimator of the transition density; effectively reducing the problem into one of model selection based on empricial processes.</p><p dir="ltr">Finally, in Chapter 6 we move to a parametric and Bayesian regime, and restrict ourselves to Markov chains. Under this setting we provide a PAC-Bayes bound for estimating model parameters under tempered posteriors.</p>

In the dissertation there is investigated a class of Markov chains defined by iterations of a function possessing a property of asymptotical homogeneity. Two problems are solved: 1) there are established rather general conditions under which the chain has unique stationary distribution; 2) for the chains evolving in a real line there are established conditions under which the stationary distribution of the chain is heavy-tailed. / Disertacijoje tirta Markovo grandinių klasė, kurios iteracijos nusakomos atsitiktinėmis asimptotiškai homogeninėmis funkcijomis, ir išspręsti du uždaviniai: 1) surastos bendros sąlygos, kurios garantuoja vienintelio stacionaraus skirstinio egzistavimą; 2) vienmatėms grandinėms surastos sąlygos, kurioms esant stacionarus skirstinys turi "sunkias" uodegas.

Disertacijoje tirta Markovo grandinių klasė, kurios iteracijos nusakomos atsitiktinėmis asimptotiškai homogeninėmis funkcijomis, ir išspręsti du uždaviniai: 1) surastos bendros sąlygos, kurios garantuoja vienintelio stacionaraus skirstinio egzistavimą; 1) vienmatėms grandinėms surastos sąlygos, kurioms esant stacionarus skirstinys turi "sunkias" uodegas. / In the dissertation there is investigated a class of Markov chains defined by iterations of a function possessing a property of asymptotical homogeneity. Two problems are solved: 1) there are established rather general conditions under which the chain has unique stationary distribution; 2) for the chains evolving in a real line there are established conditions under which the stationary distribution of the chain is heavy-tailed.

In this thesis, we use martingales to show that the dilation of a sequence of monotone convolutions $D_\frac{1}{b_n} (\mu_1 \triangleright \mu_2 \triangleright \cdots \triangleright \mu_n)$ is stable, where $\mu_j$ are probability distributions with the condition $\sum \limits_{n=1}^\infty \frac{1}{b_n} \text{var}(\mu_n) < \infty$. This proves a law of large numbers for monotonically independent random variables.