Hostname: page-component-8448b6f56d-qsmjn Total loading time: 0 Render date: 2024-04-25T04:10:17.976Z Has data issue: false hasContentIssue false
  • English
  • Français

Composition Markov chains of multinomial type

Part of: Markov processes

Published online by Cambridge University Press:  01 July 2016

Hua Zhou  and
Kenneth Lange
Hua Zhou*
Affiliation:
Stanford University
Kenneth Lange*
Affiliation:
University of California, Los Angeles
*
∗ Current address: Department of Human Genetics, University of California, Los Angeles, CA 90095, USA. Email address: huazhou@ucla.edu
∗∗ Postal address: Departments of Biomathematics, Human Genetics, and Statistics, University of California, Los Angeles, CA 90095-1766, USA.
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.

Suppose that n identical particles evolve according to the same marginal Markov chain. In this setting we study chains such as the Ehrenfest chain that move a prescribed number of randomly chosen particles at each epoch. The product chain constructed by this device inherits its eigenstructure from the marginal chain. There is a further chain derived from the product chain called the composition chain that ignores particle labels and tracks the numbers of particles in the various states. The composition chain in turn inherits its eigenstructure and various properties such as reversibility from the product chain. The equilibrium distribution of the composition chain is multinomial. The current paper proves these facts in the well-known framework of state lumping and identifies the column eigenvectors of the composition chain with the multivariate Krawtchouk polynomials of Griffiths. The advantages of knowing the full spectral decomposition of the composition chain include (a) detailed estimates of the rate of convergence to equilibrium, (b) construction of martingales that allow calculation of the moments of the particle counts, and (c) explicit expressions for mean coalescence times in multi-person random walks. These possibilities are illustrated by applications to Ehrenfest chains, the Hoare and Rahman chain, Kimura's continuous-time chain for DNA evolution, a light bulb chain, and random walks on some specific graphs.

Keywords

Orthogonal polynomialKrawtchouk polynomialEhrenfest chaininhomogeneous Markov chaincoalescent timerandom walkconvergence rate

MSC classification

Primary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Secondary: 60J22: Computational methods in Markov chains 60J25: Continuous-time Markov processes on general state spaces 60J27: Continuous-time Markov processes on discrete state spaces
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 41 , Issue 1 , March 2009 , pp. 270 - 291
Copyright
Copyright © Applied Probability Trust 2009 

References

Barr, D. R. and Thomas, M. U. (1977). An eigenvector condition for Markov chain lumpability. Operat. Res. 25, 1028–1031.Google Scholar
Boyd, S., Diaconis, P., Parrilo, P. and Xiao, L. (2005). Symmetry analysis of reversible Markov chains. Internet Math. 2, 31–71.Google Scholar
Cobb, G.W. and Chen, Y-P. (2003). An application of Markov chain Monte Carlo to community ecology. Amer. Math. Monthly 110, 265–288.Google Scholar
Diaconis, P. (1988). Group Representations in Probability and Statistics. Institute of Mathematical Statistics, Hayward, CA.Google Scholar
Diaconis, P., Khare, K. and Saloff-Coste, L. (2008). Gibbs sampling, exponential families and orthogonal polynomials. Statist. Sci. 23, 151–200.Google Scholar
Erdős, P., Rényi, A. and Sós, V. T. (1966). On a problem of graph theory. Studia Sci. Math. Hung. 1, 215–235.Google Scholar
Feller, W. (1968). An Introduction to Probability Theory and Its Applications, Vol. I, 3rd edn. John Wiley, New York.Google Scholar
Graham, R. L., Knuth, D. E. and Patashnik, O. (1989). Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, Reading, MA.Google Scholar
Griffiths, R. C. (1971). Orthogonal polynomials on the multinomial distribution. Austral. J. Statist. 13, 27–35.Google Scholar
Griffiths, R. C. (2007). Notes on ‘A probabilistic origin for a new class of bivariate polynomials’ by Hoare, M. R. and Rahman, M.. Unpublished notes.Google Scholar
Henrici, P. (1979). Fast Fourier methods in computational complex analysis. SIAM Rev. 21, 481–527.Google Scholar
Hoare, M. R. and Rahman, M. (2008). A probabilistic origin for a new class of bivariate polynomials. SIGMA 4, 089.Google Scholar
Ismail, M. E. H. (2005). Classical and Quantum Orthogonal Polynomials in One Variable (Encyclopaedia Math. Appl. 98). Cambridge University Press.CrossRefGoogle Scholar
Iliev, P. and Xu, Y. (2007). Discrete orthogonal polynomials and difference equations of several variables. Adv. Math. 212, 1–36.Google Scholar
Kac, M. (1947). Random walk and the theory of Brownian motion. Amer. Math. Monthly 54, 369–391.Google Scholar
Karlin, S. and McGregor, J. (1965). Ehrenfest urn models. J. Appl. Prob. 2, 352–376.Google Scholar
Karlin, S. and Taylor, H. M. (1975). A First Course in Stochastic Processes. Academic Press, New York.Google Scholar
Karlin, S. and Taylor, H. M. (1981). A Second Course in Stochastic Processes. Academic Press, New York.Google Scholar
Kemeny, J. G. and Snell, J. L. (1983). Finite Markov Chains. Springer, New York.Google Scholar
Khare, K. and Zhou, H. (2009). Rates of convergence of some multivariate Markov chains with polynomial eigenfunctions. To appear in Ann. Appl. Prob. Google Scholar
Kimura, M. (1980). A simple method for estimating evolutionary rates of base substitutions through comparative studies of nucleotide sequences. J. Molec. Evol. 16, 111–120.Google Scholar
Lange, K. (1999). Numerical Analysis for Statisticians. Springer, New York.Google Scholar
Lazzeroni, L. C. and Lange, K. (1997). Markov chains for Monte Carlo tests of genetic equilibrium in multidimensional contingency tables. Ann. Statist. 25, 138–168.Google Scholar
Rao, C. R., Rao, M. B. and Zhang, H. (2007). One bulb? Two bulbs? How many bulbs light up—a discrete probability problem involving dermal patches. Sankhyā 69, 137–161.Google Scholar
Tian, J. P. and Liu, Z. (2007). Coalescent random walks on graphs. J. Comput. Appl. Math. 202, 144–154.Google Scholar