×

Composition Markov chains of multinomial type. (English) Zbl 1161.60023

Summary: 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.

MSC:

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60J22 Computational methods in Markov chains
60J25 Continuous-time Markov processes on general state spaces
60J27 Continuous-time Markov processes on discrete state spaces
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barr, D. R. and Thomas, M. U. (1977). An eigenvector condition for Markov chain lumpability. Operat. Res. 25 , 1028–1031. JSTOR: · Zbl 0383.60063 · doi:10.1287/opre.25.6.1028
[2] Boyd, S., Diaconis, P., Parrilo, P. and Xiao, L. (2005). Symmetry analysis of reversible Markov chains. Internet Math. 2 , 31–71. · Zbl 1087.60057 · doi:10.1080/15427951.2005.10129100
[3] Cobb G. W. and Chen, Y-P. (2003). An application of Markov chain Monte Carlo to community ecology. Amer. Math. Monthly 110 , 265–288. JSTOR: · Zbl 1187.05069 · doi:10.2307/3647877
[4] Diaconis, P. (1988). Group Representations in Probability and Statistics . Institute of Mathematical Statistics, Hayward, CA. · Zbl 0695.60012
[5] Diaconis, P., Khare, K. and Saloff-Coste, L. (2008). Gibbs sampling, exponential families and orthogonal polynomials. Statist. Sci. 23 , 151–200. · Zbl 1327.62058 · doi:10.1214/07-STS252
[6] 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. · Zbl 0144.23302
[7] Feller, W. (1968). An Introduction to Probability Theory and Its Applications , Vol. I, 3rd edn. John Wiley, New York. · Zbl 0155.23101
[8] Graham, R. L., Knuth, D. E. and Patashnik, O. (1989). Concrete Mathematics: A Foundation for Computer Science . Addison-Wesley, Reading, MA. · Zbl 0668.00003
[9] Griffiths, R. C. (1971). Orthogonal polynomials on the multinomial distribution. Austral. J. Statist. 13 , 27–35. · Zbl 0222.60009 · doi:10.1111/j.1467-842X.1971.tb01239.x
[10] Griffiths, R. C. (2007). Notes on ‘A probabilistic origin for a new class of bivariate polynomials’ by M. R. Hoare and M. Rahman. Unpublished notes.
[11] Henrici, P. (1979). Fast Fourier methods in computational complex analysis. SIAM Rev. 21 , 481–527. JSTOR: · Zbl 0416.65022 · doi:10.1137/1021093
[12] Hoare, M. R. and Rahman, M. (2008). A probabilistic origin for a new class of bivariate polynomials. SIGMA 4, 089. · Zbl 1163.33308 · doi:10.3842/SIGMA.2008.089
[13] Ismail, M. E. H. (2005). Classical and Quantum Orthogonal Polynomials in One Variable (Encyclopaedia Math. Appl. 98 ). Cambridge University Press. · Zbl 1082.42016
[14] Iliev, P. and Xu, Y. (2007). Discrete orthogonal polynomials and difference equations of several variables. Adv. Math. 212 , 1–36. · Zbl 1133.47027 · doi:10.1016/j.aim.2006.09.012
[15] Kac, M. (1947). Random walk and the theory of Brownian motion. Amer. Math. Monthly 54 , 369–391. JSTOR: · Zbl 0031.22604 · doi:10.2307/2304386
[16] Karlin, S. and McGregor, J. (1965). Ehrenfest urn models. J. Appl. Prob. 2 , 352–376. JSTOR: · Zbl 0143.40501 · doi:10.2307/3212199
[17] Karlin, S. and Taylor, H. M. (1975). A First Course in Stochastic Processes . Academic Press, New York. · Zbl 0315.60016
[18] Karlin, S. and Taylor, H. M. (1981). A Second Course in Stochastic Processes . Academic Press, New York. · Zbl 0469.60001
[19] Kemeny, J. G. and Snell, J. L. (1983). Finite Markov Chains . Springer, New York. · Zbl 0537.60061
[20] Khare, K. and Zhou, H. (2009). Rates of convergence of some multivariate Markov chains with polynomial eigenfunctions. To appear in Ann. Appl. Prob. · Zbl 1171.60016
[21] 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.
[22] Lange, K. (1999). Numerical Analysis for Statisticians . Springer, New York. · Zbl 0920.62001 · doi:10.1007/b98850
[23] 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. · Zbl 0871.62094 · doi:10.1214/aos/1034276624
[24] 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. · Zbl 1192.60024
[25] Tian, J. P. and Liu, Z. (2007). Coalescent random walks on graphs. J. Comput. Appl. Math. 202 , 144–154. · Zbl 1129.60078 · doi:10.1016/j.cam.2005.10.039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.