Sparse Markov Chains for Sequence Data

Finite memory sources and variable‐length Markov chains have recently gained popularity in data compression and mining, in particular, for applications in bioinformatics and language modelling. Here, we consider denser data compression and prediction with a family of sparse Bayesian predictive models for Markov chains in finite state spaces. Our approach lumps transition probabilities into classes composed of invariant probabilities, such that the resulting models need not have a hierarchical structure as in context tree‐based approaches. This can lead to a substantially higher rate of data compression, and such non‐hierarchical sparse models can be motivated for instance by data dependence structures existing in the bioinformatics context. We describe a Bayesian inference algorithm for learning sparse Markov models through clustering of transition probabilities. Experiments with DNA sequence and protein data show that our approach is competitive in both prediction and classification when compared with several alternative methods on the basis of variable memory length.     

Central Limit Theorem approximations for the number of runs in Markov-dependent binary sequences

We consider Markov-dependent binary sequences and study various types of success runs (overlapping, non-overlapping, exact, etc.) by examining additive functionals based on state visits and transitions in an appropriate Markov chain. We establish a multivariate Central Limit Theorem for the number of these types of runs and obtain its covariance matrix by means of the recurrent potential matrix of the Markov chain. Explicit expressions for the covariance matrix are given in the Bernoulli and a simple Markov-dependent case by expressing the recurrent potential matrix in terms of the stationary distribution and the mean transition times in the chain. We also obtain a multivariate Central Limit Theorem for the joint number of non-overlapping runs of various sizes and give its covariance matrix in explicit form for Markov dependent trials.     

A latent Markov model for detecting patterns of criminal activity

Summary.  The paper investigates the problem of determining patterns of criminal behaviour from official criminal histories, concentrating on the variety and type of offending convictions. The analysis is carried out on the basis of a multivariate latent Markov model which allows for discrete covariates affecting the initial and the transition probabilities of the latent process. We also show some simplifications which reduce the number of parameters substantially; we include a Rasch-like parameterization of the conditional distribution of the response variables given the latent process and a constraint of partial homogeneity of the latent Markov chain. For the maximum likelihood estimation of the model we outline an EM algorithm based on recursions known in the hidden Markov literature, which make the estimation feasible also when the number of time occasions is large. Through this model, we analyse the conviction histories of a cohort of offenders who were born in England and Wales in 1953. The final model identifies five latent classes and specifies common transition probabilities for males and females between 5-year age periods, but with different initial probabilities.     

A copula-based partition Markov procedure

The number of parameters needed to specify a discrete multivariate Markov chain grows exponentially with the order and dimension of the chain, and when the size of the database is not large enough, it is not possibly a consistent estimation. In this paper, we introduce a strategy to estimate a multivariate process with an order greater than the order achieved using standard procedures. The new strategy consists in obtaining a partition of the state space which is constructed from a combination of the partitions corresponding to the marginal processes and the partitions corresponding to the multivariate Markov chain.     

Bivariate Semi-Markov Process for Counterparty Credit Risk

We consider the problem of constructing an appropriate multivariate model to study counterparty credit risk in the credit rating migration problem. For this financial problem different multivariate Markov chain models were proposed. However, the Markovian assumption may be inappropriate for the study of the dynamics of credit ratings, which typically show non Markovian-like behavior. In this article, we develop a semi-Markov approach to study the counterparty credit risk by defining a new multivariate semi-Markov chain model. Methods are given for computing the transition probabilities, reliability functions and the price of a risky Credit Default Swap.     

A Novel Estimation Approach for Mixture Transition Distribution Model in High-Order Markov Chains

A transformation is proposed to convert the nonlinear constraints of the parameters in the mixture transition distribution (MTD) model into box-constraints. The proposed transformation removes the difficulties associated with the maximum likelihood estimation (MLE) process in the MTD modeling so that the MLEs of the parameters can be easily obtained via a hybrid algorithm from the evolutionary algorithms and/or quasi-Newton algorithms for global optimization. Simulation studies are conducted to demonstrate MTD modeling by the proposed novel approach through a global search algorithm in R environment. Finally, the proposed approach is used for the MTD modelings of three real data sets.     

Number of occurrences in two-state Markov chains,with an application in linguistics

Let N_n be the number of occurrences in n trials of an event governed by a two-state Markov chain (of first order or second order). We obtain the distribution of N_n and apply it to a problem involving literary text.     

Flexible Latent‐State Modelling of Old Faithful's Eruption Inter‐Arrival Times in 2009

This paper is concerned with the analysis of a time series comprising the eruption inter‐arrival times of the Old Faithful geyser in 2009. The series is much longer than other well‐documented ones and thus gives a more comprehensive insight into the dynamics of the geyser. Basic hidden Markov models with gamma state‐dependent distributions and several extensions are implemented. In order to better capture the stochastic dynamics exhibited by Old Faithful, the different non‐standard models under consideration seek to increase the flexibility of the basic models in various ways: (i) by allowing non‐geometric distributions for the times spent in the different states; (ii) by increasing the memory of the underlying Markov chain, with or without assuming additional structure implied by mixture transition distribution models; and (iii) by incorporating feedback from the observation process on the latent process. In each case it is shown how the likelihood can be formulated as a matrix product which can be conveniently maximized numerically.     

Stochastic monotonicity and comparability of Markov chains with block-monotone transition matrices and their applications to queueing systems

ABSTRACT

Motivated by various applications in queueing theory, this article is devoted to the stochastic monotonicity and comparability of Markov chains with block-monotone transition matrices. First, we introduce the notion of block-increasing convex order for probability vectors, and characterize the block-monotone matrices in the sense of the block-increasing order and block-increasing convex order. Second, we characterize the Markov chain with general transition matrix by martingale and provide a stochastic comparison of two block-monotone Markov chains under the two block-monotone orders. Third, the stochastic comparison results for the Markov chains corresponding to the discrete-time GI/G/1 queue with different service distributions under the two block-monotone orders are given, and the lower bound and upper bound of the Markov chain corresponding to the discrete-time GI/G/1 queue in the sense of the block-increasing convex order are found.     

Nonparametric Bayesian analysis for multi-site hidden Markov model

The hidden Markov model (HMM) provides an attractive framework for modeling long-term persistence in a variety of applications including pattern recognition. Unlike typical mixture models, hidden Markov states can represent the heterogeneity in data and it can be extended to a multivariate case using a hierarchical Bayesian approach. This article provides a nonparametric Bayesian modeling approach to the multi-site HMM by considering stick-breaking priors for each row of an infinite state transition matrix. This extension has many advantages over a parametric HMM. For example, it can provide more flexible information for identifying the structure of the HMM than parametric HMM analysis, such as the number of states in HMM. We exploit a simulation example and a real dataset to evaluate the proposed approach.     

An EM algorithm for estimation in the mixture transition distribution model

The mixture transition distribution (MTD) model was introduced by Raftery to face the need for parsimony in the modeling of high-order Markov chains in discrete time. The particularity of this model comes from the fact that the effect of each lag upon the present is considered separately and additively, so that the number of parameters required is drastically reduced. However, the efficiency for the MTD parameter estimations proposed up to date still remains problematic on account of the large number of constraints on the parameters. In this article, an iterative procedure, commonly known as expectation–maximization (EM) algorithm, is developed cooperating with the principle of maximum likelihood estimation (MLE) to estimate the MTD parameters. Some applications of modeling MTD show the proposed EM algorithm is easier to be used than the algorithm developed by Berchtold. Moreover, the EM estimations of parameters for high-order MTD models led on DNA sequences outperform the corresponding fully parametrized Markov chain in terms of Bayesian information criterion. A software implementation of our algorithm is available in the library seq++at http://stat.genopole.cnrs.fr/seqpp.     

Fully Bayesian Binary Markov Random Field Models: Prior Specification and Posterior Simulation

We propose a flexible prior model for the parameters of binary Markov random fields (MRF), defined on rectangular lattices and with maximal cliques defined from a template maximal clique. The prior model allows higher‐order interactions to be included. We also define a reversible jump Markov chain Monte Carlo algorithm to sample from the associated posterior distribution. The number of possible parameters for a higher‐order MRF becomes high, even for small template maximal cliques. We define a flexible parametric form where the parameters have interpretation as potentials for clique configurations, and limit the effective number of parameters by assigning apriori discrete probabilities for events where groups of parameter values are equal. To cope with the computationally intractable normalising constant of MRFs, we adopt a previously defined approximation of binary MRFs. We demonstrate the flexibility of our prior formulation with simulated and real data examples.     

Estimation with right‐censored observations under a semi‐Markov model

The semi‐Markov process often provides a better framework than the classical Markov process for the analysis of events with multiple states. The purpose of this paper is twofold. First, we show that in the presence of right censoring, when the right end‐point of the support of the censoring time is strictly less than the right end‐point of the support of the semi‐Markov kernel, the transition probability of the semi‐Markov process is nonidentifiable, and the estimators proposed in the literature are inconsistent in general. We derive the set of all attainable values for the transition probability based on the censored data, and we propose a nonparametric inference procedure for the transition probability using this set. Second, the conventional approach to constructing confidence bands is not applicable for the semi‐Markov kernel and the sojourn time distribution. We propose new perturbation resampling methods to construct these confidence bands. Different weights and transformations are explored in the construction. We use simulation to examine our proposals and illustrate them with hospitalization data from a recent cancer survivor study. The Canadian Journal of Statistics 41: 237–256; 2013 © 2013 Statistical Society of Canada     

Bayes Estimates of Markov Trends in Possibly Cointegrated Series

Stylized facts show that average growth rates of U.S. per capita consumption and income differ in recession and expansion periods. Because a linear combination of such series does not have to be a constant mean process, standard cointegration analysis between the variables to examine the permanent income hypothesis may not be valid. To model the changing growth rates in both series, we introduce a multivariate Markov trend model that accounts for different growth rates in consumption and income during expansions and recessions and across variables within both regimes. The deviations from the multivariate Markov trend are modeled by a vector autoregression (VAR) model. Bayes estimates of this model are obtained using Markov chain Monte Carlo methods. The empirical results suggest the existence of a cointegration relation between U.S. per capita disposable income and consumption, after correction for a multivariate Markov trend. This result is also obtained when per capita investment is added to the VAR.     

Hierarchical Bayesian Approach to a Multi-Site Hidden Markov Model

Multivariate data with a sequential or temporal structure occur in various fields of study. The hidden Markov model (HMM) provides an attractive framework for modeling long-term persistence in areas of pattern recognition through the extension of independent and identically distributed mixture models. Unlike in typical mixture models, the heterogeneity of data is represented by hidden Markov states. This article extends the HMM to a multi-site or multivariate case by taking a hierarchical Bayesian approach. This extension has many advantages over a single-site HMM. For example, it can provide more information for identifying the structure of the HMM than a single-site analysis. We evaluate the proposed approach by exploiting a spatial correlation that depends on the distance between sites.     

Efficient Bayesian Multivariate Surface Regression

Methods for choosing a fixed set of knot locations in additive spline models are fairly well established in the statistical literature. The curse of dimensionality makes it nontrivial to extend these methods to nonadditive surface models, especially when there are more than a couple of covariates. We propose a multivariate Gaussian surface regression model that combines both additive splines and interactive splines, and a highly efficient Markov chain Monte Carlo algorithm that updates all the knot locations jointly. We use shrinkage prior to avoid overfitting with different estimated shrinkage factors for the additive and surface part of the model, and also different shrinkage parameters for the different response variables. Simulated data and an application to firm leverage data show that the approach is computationally efficient, and that allowing for freely estimated knot locations can offer a substantial improvement in out‐of‐sample predictive performance.     

Multivariate Poisson hidden Markov models with a case study of modelling seismicity

While the literature on multivariate models for continuous data flourishes, there is a lack of models for multivariate counts. We aim to contribute to this framework by extending the well known class of univariate hidden Markov models to the multidimensional case, by introducing multivariate Poisson hidden Markov models. Each state of the extended model is associated with a different multivariate discrete distribution. We consider different distributions with Poisson marginals, starting from the multivariate Poisson distribution and then extending to copula based distributions to allow flexible dependence structures. An EM type algorithm is developed for maximum likelihood estimation. A real data application is presented to illustrate the usefulness of the proposed models. In particular, we apply the models to the occurrence of strong earthquakes (surface wave magnitude ≥5), in three seismogenic subregions in the broad region of the North Aegean Sea for the time period from 1 January 1981 to 31 December 2008. Earthquakes occurring in one subregion may trigger events in adjacent ones and hence the observed time series of events are cross‐correlated. It is evident from the results that the three subregions interact with each other at times differing by up to a few months. This migration of seismic activity is captured by the model as a transition to a state of higher seismicity.     

Alternative Markov Properties for Chain Graphs

Graphical Markov models use graphs to represent possible dependences among statistical variables. Lauritzen, Wermuth, and Frydenberg (LWF) introduced a Markov property for chain graphs (CG): graphs that can be used to represent both structural and associative dependences simultaneously and that include both undirected graphs (UG) and acyclic directed graphs (ADG) as special cases. Here an alternative Markov property (AMP) for CGs is introduced and shown to be the Markov property satisfied by a block-recursive linear system with multivariate normal errors. This model can be decomposed into a collection of conditional normal models, each of which combines the features of multivariate linear regression models and covariance selection models, facilitating the estimation of its parameters. In the general case, necessary and sufficient conditions are given for the equivalence of the LWF and AMP Markov properties of a CG, for the AMP Markov equivalence of two CGs, for the AMP Markov equivalence of a CG to some ADG or decomposable UG, and for other equivalences. For CGs, in some ways the AMP property is a more direct extension of the ADG Markov property than is the LWF property.     

Applying a Markov chain for the stock pricing of a novel forecasting model

In this article, a stock-forecasting model is developed to analyze a company's stock price variation related to the Taiwanese company HTC. The main difference to previous articles is that this study uses the data of the HTC in recent ten years to build a Markov transition matrix. Instead of trying to predict the stock price variation through the traditional approach to the HTC stock problem, we integrate two types of Markov chain that are used in different ways. One is a regular Markov chain, and the other is an absorbing Markov chain. Through a regular Markov chain, we can obtain important information such as what happens in the long run or whether the distribution of the states tends to stabilize over time in an efficient way. Next, we used an artificial variable technique to create an absorbing Markov chain. Thus, we used an absorbing Markov chain to provide information about the period between the increases before arriving at the decreasing state of the HTC stock. We provide investors with information on how long the HTC stock will keep increasing before its price begins to fall, which is extremely important information to them.