Markov Systems in a General State Space

In this article, we introduce and study Markov systems on general spaces (MSGS) as a first step of an entire theory on the subject. Also, all the concepts and basic results needed for this scope are given and analyzed. This could be thought of as an extension of the theory of a non homogeneous Markov system (NHMS) and that of a non homogeneous semi-Markov system on countable spaces, which has realized an interesting growth in the last thirty years. In addition, we study the asymptotic behaviour or ergodicity of Markov systems on general state spaces. The problem of asymptotic behaviour of Markov chains has been central for finite or countable spaces since the foundation of the subject. It has also been basic in the theory of NHMS and NHSMS. Two basic theorems are provided in answering the important problem of the asymptotic distribution of the population of the memberships of a Markov system that lives in the general space (X, ?(X)). Finally, we study the total variability from the invariant measure of the Markov system given that there exists an asymptotic behaviour. We prove a theorem which states that the total variation is finite. This problem is known also as the coupling problem.     

Statistical analysis of the number of self-overlapping leftmost repeats in an homogeneous stationary Markov chain on finite states

ABSTRACT

This article addresses the problem of repeats detection used in the comparison of significant repeats in sequences. The case of self-overlapping leftmost repeats for large sequences generated by an homogeneous stationary Markov chain has not been treated in the literature. In this work, we are interested by the approximation of the number of self-overlapping leftmost long enough repeats distribution in an homogeneous stationary Markov chain. Using the Chen–Stein method, we show that the number of self-overlapping leftmost long enough repeats distribution is approximated by the Poisson distribution. Moreover, we show that this approximation can be extended to the case where the sequences are generated by a m-order Markov chain.     

Exotic Properties of Non Homogeneous Markov and Semi-Markov Systems

In this article we study what we chose to call exotic properties of NHMS and NHSMS. The interplay between stochastic theory of NHMS and NHSMS and other branches of probability, stochastic processes and mathematics, we believe is a fascinating one apart from being important. In many cases the information needed for the evolution of a NHMS is a larger set than the history of the multidimensional process NHMS. In our world where an overflow of information exists almost in all problems, it is almost surely that this will be available. Here, we extend the definition of the NHMS in order to accomodate this case. In this respect we arrive at the defnition of the 𝒢-non homogeneous Markov system. We study the problem of change of measure in a 𝒢-non homogeneousMarkov system. It is proved that under certain conditions the NHMS retains the Markov property, while as expected the basic sequences of transition probabilities change and it is established how they do so. We also find the expected population structure of the NHMS under the new measure in close analytic form. We also define the 𝒢-non homogeneous semi-Markov system and we study the problem of change of measure in a 𝒢-non homogeneous semi-Markov system. It is proved that under certain conditions the NHSMS retains the semi-Markov property while as expected the basic sequences of transition probabilities change and it is established how they do so. We prove that if the input process of memberships is a non homogeneous Poisson process, then asymtotically and under certain easily met in practice conditions, the compensated population structure of the 𝒢-NHMS is a martingale. Finally we prove that the space of all random population structures, under easily met in practice conditions, is a Hilbert space.     

Fitting Gaussian Markov Random Fields to Gaussian Fields

This paper discusses the following task often encountered in building Bayesian spatial models: construct a homogeneous Gaussian Markov random field (GMRF) on a lattice with correlation properties either as present in some observed data, or consistent with prior knowledge. The Markov property is essential in designing computationally efficient Markov chain Monte Carlo algorithms to analyse such models. We argue that we can restate both tasks as that of fitting a GMRF to a prescribed stationary Gaussian field on a lattice when both local and global properties are important. We demonstrate that using the KullbackLeibler discrepancy often fails for this task, giving severely undesirable behaviour of the correlation function for lags outside the neighbourhood. We propose a new criterion that resolves this difficulty, and demonstrate that GMRFs with small neighbourhoods can approximate Gaussian fields surprisingly well even with long correlation lengths. Finally, we discuss implications of our findings for likelihood based inference for general Markov random fields when global properties are also important.     

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.     

A New Markov Binomial Distribution

In this article, we introduce a two-state homogeneous Markov chain and define a geometric distribution related to this Markov chain. We define also the negative binomial distribution similar to the classical case and call it NB related to interrupted Markov chain. The new binomial distribution is related to the interrupted Markov chain. Some characterization properties of the geometric distributions are given. Recursion formulas and probability mass functions for the NB distribution and the new binomial distribution are derived.     

The generalizations of strong law of large numbers for asymptotic even–odd Markov chains indexed by a homogeneous tree

Yang et al. (Yang et al., J. Math. Anal. Appl., 410 (2014), 179–189.) have obtained the strong law of large numbers and asymptotic equipartition property for the asymptotic even–odd Markov chains indexed by a homogeneous tree. In this article, we are going to study the strong law of large numbers and the asymptotic equipartition property for a class of non homogeneous Markov chains indexed by a homogeneous tree which are the generalizations of above results. We also provide an example showing that our generalizations are not trivial.     

Reversible jump and the label switching problem in hidden Markov models

Reversible jump Markov chain Monte Carlo (RJMCMC) algorithms can be efficiently applied in Bayesian inference for hidden Markov models (HMMs), when the number of latent regimes is unknown. As for finite mixture models, when priors are invariant to the relabelling of the regimes, HMMs are unidentifiable in data fitting, because multiple ways to label the regimes can alternate during the MCMC iterations; this is the so-called label switching problem. HMMs with an unknown number of regimes are considered here and the goal of this paper is the comparison, both applied and theoretical, of five methods used for tackling label switching within a RJMCMC algorithm; they are: post-processing, partial reordering, permutation sampling, sampling from a Markov prior and rejection sampling. The five strategies we compare have been proposed mostly in the literature of finite mixture models and only two of them, i.e. rejection sampling and partial reordering, have been presented in RJMCMC algorithms for HMMs. We consider RJMCMC algorithms in which the parameters are updated by Gibbs sampling and the dimension of the model changes in split-and-merge and birth-and-death moves. Finally, an example illustrates and compares the five different methodologies.     

A distance-based diagnostic for trans-dimensional Markov chains

Over the last decade the use of trans-dimensional sampling algorithms has become endemic in the statistical literature. In spite of their application however, there are few reliable methods to assess whether the underlying Markov chains have reached their stationary distribution. In this article we present a distance-based method for the comparison of trans-dimensional Markov chain sample output for a broad class of models. This diagnostic will simultaneously assess deviations between and within chains. Illustration of the analysis of Markov chain sample-paths is presented in simulated examples and in two common modelling situations: a finite mixture analysis and a change-point problem.     

The strong laws of large numbers for countable non homogeneous hidden Markov models

In this article, we are going to study the strong laws of large numbers for countable non homogeneous hidden Markov models. First, we introduce the notion of countable non homogeneous hidden Markov models. Then, we obtain some properties for those Markov models. Finally, we establish two strong laws of large numbers for countable non homogeneous hidden Markov models. As corollaries, we obtain some known results of strong laws of large numbers for finite non homogeneous Markov chains.     

Application of Markov chain Monte Carlo methods to modelling birth prevalence of Down syndrome

Data collected before the routine application of prenatal screening are of unique value in estimating the natural live-birth prevalence of Down syndrome. However, much of these data are from births from over 20 years ago and they are of uncertain quality. In particular, they are subject to varying degrees of underascertainment. Published approaches have used ad hoc corrections to deal with this problem or have been restricted to data sets in which ascertainment is assumed to be complete. In this paper we adopt a Bayesian approach to modelling ascertainment and live-birth prevalence. We consider three prior specifications concerning ascertainment and compare predicted maternal-age-specific prevalence under these three different prior specifications. The computations are carried out by using Markov chain Monte Carlo methods in which model parameters and missing data are sampled.     

Transient Analysis of the M/M/k/N/N Queue using a Continuous Time Homogeneous Markov System with Finite State Size Capacity

In this article, the M/M/k/N/N queue is modeled as a continuous-time homogeneous Markov system with finite state size capacity (HMS/c_s). In order to examine the behavior of the queue a continuous-time homogeneous Markov system (HMS) constituted of two states is used. The first state of this HMS corresponds to the source and the second one to the state with the servers. The second state has a finite capacity which corresponds to the number of servers. The members of the system which can not enter the second state, due to its finite capacity, enter the buffer state which represents the system's queue. In order to examine the variability of the state sizes formulae for their factorial and mixed factorial moments are derived in matrix form. As a consequence, the pmf of each state size can be evaluated for any t ∈ ?⁺. The theoretical results are illustrated by a numerical example.     

Transient analysis of a finite source discrete-time queueing system using homogeneous Markov system with state size capacities (HMS/c)

Abstract

In this article, a finite source discrete-time queueing system is modeled as a discrete-time homogeneous Markov system with finite state size capacities (HMS/c) and transition priorities. This Markov system is comprised of three states. The first state of the HMS/c corresponds to the source and the second one to the state with the servers. The second state has a finite capacity which corresponds to the number of servers. The members of the system which can not enter the second state, due to its finite capacity, enter the third state which represents the system's queue. In order to examine the variability of the state sizes recursive formulae for their factorial and mixed factorial moments are derived in matrix form. As a consequence the probability mass function of each state size can be evaluated. Also the expected time in queue is computed by means of the interval transition probabilities. The theoretical results are illustrated by a numerical example.     

Strong law of large numbers for generalized sample relative entropy of non homogeneous Markov chains

In this paper, we study the strong law of large numbers for the generalized sample relative entropy of non homogeneous Markov chains taking values from a finite state space. First, we introduce the definitions of generalized sample relative entropy and generalized sample relative entropy rate. Then, using a strong limit theorem for the delayed sums of the functions of two variables and a strong law of large numbers for non homogeneous Markov chains, we obtain the strong law of large numbers for the generalized sample relative entropy of non homogeneous Markov chains. As corollaries, we obtain some important results.     

Distribution of busy period in stochastic fluid models

We consider the busy period in a stochastic fluid flow model with infinite buffer where the input and output rates are controlled by a finite homogeneous Markov process. We derive an explicit expression for the distribution of the busy period and we obtain an algorithm to compute it which exhibits nice numerical properties.

     

A Markov Chain Monte Carlo version of the genetic algorithm Differential Evolution: easy Bayesian computing for real parameter spaces

Differential Evolution (DE) is a simple genetic algorithm for numerical optimization in real parameter spaces. In a statistical context one would not just want the optimum but also its uncertainty. The uncertainty distribution can be obtained by a Bayesian analysis (after specifying prior and likelihood) using Markov Chain Monte Carlo (MCMC) simulation. This paper integrates the essential ideas of DE and MCMC, resulting in Differential Evolution Markov Chain (DE-MC). DE-MC is a population MCMC algorithm, in which multiple chains are run in parallel. DE-MC solves an important problem in MCMC, namely that of choosing an appropriate scale and orientation for the jumping distribution. In DE-MC the jumps are simply a fixed multiple of the differences of two random parameter vectors that are currently in the population. The selection process of DE-MC works via the usual Metropolis ratio which defines the probability with which a proposal is accepted. In tests with known uncertainty distributions, the efficiency of DE-MC with respect to random walk Metropolis with optimal multivariate Normal jumps ranged from 68% for small population sizes to 100% for large population sizes and even to 500% for the 97.5% point of a variable from a 50-dimensional Student distribution. Two Bayesian examples illustrate the potential of DE-MC in practice. DE-MC is shown to facilitate multidimensional updates in a multi-chain “Metropolis-within-Gibbs” sampling approach. The advantage of DE-MC over conventional MCMC are simplicity, speed of calculation and convergence, even for nearly collinear parameters and multimodal densities.     

Looking at Markov samplers through cusum path plots: a simple diagnostic idea

In this paper, we propose to monitor a Markov chain sampler using the cusum path plot of a chosen one-dimensional summary statistic. We argue that the cusum path plot can bring out, more effectively than the sequential plot, those aspects of a Markov sampler which tell the user how quickly or slowly the sampler is moving around in its sample space, in the direction of the summary statistic. The proposal is then illustrated in four examples which represent situations where the cusum path plot works well and not well. Moreover, a rigorous analysis is given for one of the examples. We conclude that the cusum path plot is an effective tool for convergence diagnostics of a Markov sampler and for comparing different Markov samplers.     

Quantitative convergence assessment for Markov chain Monte Carlo via cusums

Yu (1995) provides a novel convergence diagnostic for Markov chain Monte Carlo (MCMC) which provides a qualitative measure of mixing for Markov chains via a cusum path plot for univariate parameters of interest. The method is based upon the output of a single replication of an MCMC sampler and is therefore widely applicable and simple to use. One criticism of the method is that it is subjective in its interpretation, since it is based upon a graphical comparison of two cusum path plots. In this paper, we develop a quantitative measure of smoothness which we can associate with any given cusum path, and show how we can use this measure to obtain a quantitative measure of mixing. In particular, we derive the large sample distribution of this smoothness measure, so that objective inference is possible. In addition, we show how this quantitative measure may also be used to provide an estimate of the burn-in length for any given sampler. We discuss the utility of this quantitative approach, and highlight a problem which may occur if the chain is able to remain in any one state for some period of time. We provide a more general implementation of the method to overcome the problem in such cases.     

Estimation of the Entropy Rate of a Countable Markov Chain

We consider here ergodic homogeneous Markov chains with countable state spaces. The entropy rate of the chain is an explicit function of its transition and stationary distributions. We construct estimators for this entropy rate and for the entropy of the stationary distribution of the chain, in the parametric and nonparametric cases. We study estimation from one sample with long length and from many independent samples with given length. In the parametric case, the estimators are deduced by plug-in from the maximum likelihood estimator of the parameter. In the nonparametric case, the estimators are deduced by plug-in from the empirical estimators of the transition and stationary distributions. They are proven to have good asymptotic properties.