Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-08T15:13:08.090Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Embedding Problem for Discrete-Time Markov Chains

Part of: Special matrices Basic linear algebra Markov processes

Published online by Cambridge University Press:  30 January 2018

Marie-Anne Guerry
Marie-Anne Guerry*
Affiliation:
Vrije Universiteit Brussel
*
∗ Postal address: Department of Business Technology and Operations, Vrije Universiteit Brussel, Pleinlaan 2, B-1050 Brussels, Belgium. Email address: marie-anne.guerry@vub.ac.be
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

When a discrete-time homogenous Markov chain is observed at time intervals that correspond to its time unit, then the transition probabilities of the chain can be estimated using known maximum likelihood estimators. In this paper we consider a situation when a Markov chain is observed on time intervals with length equal to twice the time unit of the Markov chain. The issue then arises of characterizing probability matrices whose square root(s) are also probability matrices. This characterization is referred to in the literature as the embedding problem for discrete time Markov chains. The probability matrix which has probability root(s) is called embeddable.

In this paper for two-state Markov chains, necessary and sufficient conditions for embeddability are formulated and the probability square roots of the transition matrix are presented in analytic form. In finding conditions for the existence of probability square roots for (k x k) transition matrices, properties of row-normalized matrices are examined. Besides the existence of probability square roots, the uniqueness of these solutions is discussed: In the case of nonuniqueness, a procedure is introduced to identify a transition matrix that takes into account the specificity of the concrete context. In the case of nonexistence of a probability root, the concept of an approximate probability root is introduced as a solution of an optimization problem related to approximate nonnegative matrix factorization.

Keywords

Markov chainprobability matrixroot of a matrixembedding problem

MSC classification

Primary: 15A23: Factorization of matrices 15B51: Stochastic matrices 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)

Information

Type
Research Article
Information
Journal of Applied Probability , Volume 50 , Issue 4 , December 2013 , pp. 918 - 930
Copyright
© Applied Probability Trust 

References

Bartholomew, D. J., Forbes, A. F. and McClean, S. I. (1991). Statistical Techniques for Manpower Planning, 2nd edn. John Wiley, Chichester.Google Scholar
Bazaraa, M. S., Sherali, H. D. and Shetty, C. M. (2006). Nonlinear Programming: Theory and Algorithms, 3rd edn. John Wiley, Hoboken, NJ.Google Scholar
Berry, M. W. et al. (2007). Algorithms and applications for approximate nonnegative matrix factorization. Comput. Statist. Data Anal. 52, 155–173.Google Scholar
Butler, J. C. (1981). Effect of various transformations on the analysis of percentage data. Math. Geology 13, 53–68.Google Scholar
Cappé, O., Moulines, E. and Rydén, T. (2005). Inference in Hidden Markov Models. Springer, New York.Google Scholar
Guerry, M.-A. (2011). Hidden heterogeneity in manpower systems: a Markov-switching model approach. Europ. J. Operat. Res. 210, 106–113.Google Scholar
Guerry, M.-A. (2012). Necessary conditions for the embeddability of discrete-time state-wise monotone Markov chains. Working paper MOSI/53.Google Scholar
Lee, D. D. and Seung, H. S. (2001). Algorithms for non-negative matrix factorization. Adv. Neural Inf. Processing Systems 13, 556–562.Google Scholar
Minc, H. (1988). Nonnegative Matrices. John Wiley, New York.Google Scholar
Moon, S., Kamakura, W. A. and Ledolter, J. (2007). Estimating promotion response when competitive promotions are unobserved. J. Marketing Res. 44, 503–515.Google Scholar
Singer, B. and Spilerman, S. (1973/1974). Social mobility models for heterogeneous populations. Sociological Method. 5, 356–401.Google Scholar
Singer, B. and Spilerman, S. (1976). The representation of social processes by Markov models. Amer. J. Sociology 82, 1–54.Google Scholar
Ugwuowo, F. I. and McClean, S. (2000). Modelling heterogeneity in a manpower system: a review. Appl. Stoch. Models Business Industry 16, 99–110.Google Scholar