Metastability of reversible finite state Markov processes

We prove the metastable behavior of reversible Markov processes on finite state spaces under minimal conditions on the jump rates. To illustrate the result we deduce the metastable behavior of the Ising model with a small magnetic field at very low temperature.     

Explicit error bounds for lazy reversible Markov chain Monte Carlo

We prove explicit, i.e., non-asymptotic, error bounds for Markov Chain Monte Carlo methods, such as the Metropolis algorithm. The problem is to compute the expectation (or integral) of f$f$ with respect to a measure π$\pi$ which can be given by a density ?$?$ with respect to another measure. A straight simulation of the desired distribution by a random number generator is in general not possible. Thus it is reasonable to use Markov chain sampling with a burn-in. We study such an algorithm and extend the analysis of Lovasz and Simonovits [L. Lovász, M. Simonovits, Random walks in a convex body and an improved volume algorithm, Random Structures Algorithms 4 (4) (1993) 359–412] to obtain an explicit error bound.     

层次模型Markov链的观测与统计

对于连续时间的层次模型M arkov链,所有的转移速率都可以由最底层状态的逗留时间和击中时间分布惟一决定,因而整个M arkov链的统计性质由它们的统计所决定.并给出了相应的算法和数例.     

Computing the nearest diagonally dominant matrix

We solve the problem of minimizing the distance from a given matrix to the set of symmetric and diagonally dominant matrices. First, we characterize the projection onto the cone of diagonally dominant matrices with positive diagonal, and then we apply Dykstra's alternating projection algorithm on this cone and on the subspace of symmetric matrices to obtain the solution. We discuss implementation details and present encouraging preliminary numerical results. Copyright © 1999 John Wiley & Sons, Ltd.     

On Markov chain Monte Carlo Algorithms for Computing Conditional Expectations Based on Sufficient Statistics

Much work has focused on developing exact tests for the analysis of discrete data using log linear or logistic regression models. A parametric model is tested for a dataset by conditioning on the value of a sufficient statistic and determining the probability of obtaining another dataset as extreme or more extreme relative to the general model, where extremeness is determined by the value of a test statistic such as the chi-square or the log-likelihood ratio. Exact determination of these probabilities can be infeasible for high dimensional problems, and asymptotic approximations to them are often inaccurate when there are small data entries and/or there are many nuisance parameters. In these cases Monte Carlo methods can be used to estimate exact probabilities by randomly generating datasets (tables) that match the sufficient statistic of the original table. However, naive Monte Carlo methods produce tables that are usually far from matching the sufficient statistic. The Markov chain Monte Carlo method used in this work (the regression/attraction approach) uses attraction to concentrate the distribution around the set of tables that match the sufficient statistic, and uses regression to take advantage of information in tables that “almost” match. It is also more general than others in that it does not require the sufficient statistic to be linear, and it can be adapted to problems involving continuous variables. The method is applied to several high dimensional settings including four-way tables with a model of no four-way interaction, and a table of continuous data based on beta distributions. It is powerful enough to deal with the difficult problem of four-way tables and flexible enough to handle continuous data with a nonlinear sufficient statistic.     

确定星形分枝Markov链离子通道的转移速率

给出了Markov链中某状态集的生存时间和死亡时间的分布(均是混合指数分布),以及其分布的各阶导数与转移速率之间的约束关系.利用它们证明了:对于星形分枝Markov链离子通道,其全部转移速率能够通过中心状态及其相邻状态的生存时间和死亡时间的分布唯一确定,给出了相应的算法,并例证该算法的正确性和有效性.     

Large Deviations for the Markov Binomial Distribution

Considering the Markov binomial distribution, we study large deviations for the Poisson approximation. Apart from the standard choice of parameters, we use the approach where the parameter of approximation depends on the argument of the approximated distribution function.     

An improved customer lifetime value model based on Markov chain

Firms are increasingly looking to provide a satisfactory prediction of customer lifetime value (CLV), a determining metric to target future profitable customers and to optimize marketing resources. One of the major challenges associated with the measurement of CLV is the choice of the appropriate model for predicting customer value because of the large number of models proposed in the literature. Earlier models to forecast CLV are relatively unsuccessful, whereas simple models often provide results which are equivalent or even better than sophisticated ones. To predict CLV, Rust et al. (2011) proposed a framework model that performs better than simple managerial heuristic models, but its implementation excludes cases where customer's profit is negative and does not handle lost‐for‐good situations. In this paper, we propose a modified model that handles both negative and positive profits based on Markov chain model (MCM), hence offering a greater flexibility by covering always‐a‐share and lost‐for‐good situations. The proposed model is compared with the Pareto/Negative Binomial Distribution (Pareto/NBD), the Beta Geometric/Negative Binomial Distribution (BG/NBD), the MCM, and the Rust et al. (2011) models. Based on customer credit card transactions provided by the North African retail bank, an empirical study shows that the proposed model has better forecasting performance than competing models. Copyright © 2014 John Wiley & Sons, Ltd.     

Laplace Expansions in Markov chain Monte Carlo Algorithms

Complex hierarchical models lead to a complicated likelihood and then, in a Bayesian analysis, to complicated posterior distributions. To obtain Bayes estimates such as the posterior mean or Bayesian confidence regions, it is therefore necessary to simulate the posterior distribution using a method such as an MCMC algorithm. These algorithms often get slower as the number of observations increases, especially when the latent variables are considered. To improve the convergence of the algorithm, we propose to decrease the number of parameters to simulate at each iteration by using a Laplace approximation on the nuisance parameters. We provide a theoretical study of the impact that such an approximation has on the target posterior distribution. We prove that the distance between the true target distribution and the approximation becomes of order O(N^?a) with a ∈ (0, 1), a close to 1, as the number of observations N increases. A simulation study illustrates the theoretical results. The approximated MCMC algorithm behaves extremely well on an example which is driven by a study on HIV patients.     

Linear programming with multiple choice constraints for single chain undiscounted Markov decision problems

This paper develops an efficient LP algorithm for solving single chain undiscounted Markov decision problems. The algorithm imposes, in the framework of the simplex method, the multiple choice constraints that exactly one basic variable be chosen from each Markov state. It is proved that the algorithm converges to an optimal solution in a finite number of steps.     

隐Markov模型的强马氏性

引入隐Markov模型强马氏性的概念,并进一步研究了隐Markov模型在强马氏性方面的一些性质.     

Nonparametric Density Estimation in Hidden Markov Models

Let { X n} be a Markov chain that is either f -mixing or satisfies the Poisson equation.In this note we obtain the convergence rate under L 1 -criterion for bounded functions of the X k 's. And in the hidden Markov model setup { (X n ,Y n ) }we study the kernel estimate of the density of the observed variables { Y n }when a 'stable' status is reached.     

Markov chain mixing time on cycles

Mixing time quantifies the convergence speed of a Markov chain to the stationary distribution. It is an important quantity related to the performance of MCMC sampling. It is known that the mixing time of a reversible chain can be significantly improved by lifting, resulting in an irreversible chain, while changing the topology of the chain. We supplement this result by showing that if the connectivity graph of a Markov chain is a cycle, then there is an Ω(n²) lower bound for the mixing time. This is the same order of magnitude that is known for reversible chains on the cycle.     

A multivariate Markov chain model for categorical data sequences and its applications in demand predictions

Markov models are commonly used in modelling many practicalsystems such as telecommunication systems, manufacturing systemsand inventory systems. In this paper we propose a multivariateMarkov chain model for modelling multiple categorical data sequences.We develop efficient estimation methods for the model parameters.We then apply the model and method to demand predictions fora soft-drink company in Hong Kong.     

Markov chains with almost exponential hitting times

If a Markov chain converges rapidly to stationarity, then the time until the first hit on a rarely-visited set of states is approximately exponentially distributed; moreover an explicit bound for the error in this approximation can be given. This complements results of Keilson.     

THE POINT PROCESS OF STATETRANSITIONS IN AREGULAR MARKOV CHAIN

1.IntroductionInreliabilitytheory,inordertocalculatethefailurefrequencyofarepairablesystem,Shily]firstintroducedandstudiedthetransitionfrequencybetweentwodisjointstatesetsforafiniteMarkovchainandavectorMarkovprocesswithfinitediscretestatespaceandobtainedageneralformulaoftransitionfrequency.Then,ontheconditionthatthegeneratormatrixofMarkovchainisuniformlybounded,Shi[8'9]againprovedthetransitionfrequencyformulaandobtainedthreeotherusefulformulas.Obviously,thepoint(orcalledcounting)processofsta…     

On additive functionals of Markov chains

Let{S _n } _n=0 ^∞ be a Harris-recurrent Markov chain on a measurable state space. We prove strong approximation results for the additive functionals . Research supported by the Hungarian National Foundation for Scientific Research, Grant No. 1905. Mathematical Institute of the Hungarian Academy of Sciences, Budapest, P.O.B. 127, H-1364, Hungary. Research supported by an NSERC Canada Grant, Carleton University. Department of Mathematics and Statistics, Carleton University, Ottawa, Canada K1S 5B6.