Orthogonality and probability: mixing times

Yevgeniy V Kovchegov (Oregon State University)

Abstract


We produce the first example of bounding total variation distance to stationarity and estimating mixing times via orthogonal polynomials diagonalization of discrete reversible Markov chains, the Karlin-McGregor approach.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 59-67

Publication Date: February 28, 2010

DOI: 10.1214/ECP.v15-1525

References

  1. P.H.Baxendale. Renewal theory and computable convergence rates for geometrically ergodic Markov chains Annals of Applied Probability 15 No.1B (2005), 700-738 MR2114987
  2. S.Karlin and J.L.McGregor. Random Walks Illinois Journal of Math., 3, No.1, (1959), 417-431. MR0100927
  3. Y.Kovchegov. Orthogonality and probability: beyond nearest neighbor transitions Electronic Communications in Probability, 14, (2009), 90-103 MR2481669
  4. T.Lindvall. Lectures on the coupling method John Wiley & Sons, Inc., New York, (1992) MR1180522; Corrected reprint of the 1992 original Dover Publications, Inc., Mineola, NY, (2002) MR1924231
  5. R.B.Lund and R.L.Tweedie. Geometric convergence rates for stochastically ordered Markov chains Math. Oper. Res., 21, (1996), 182-194 MR1385873
  6. S.Meyn and R.L.Tweedie. Markov Chains and Stochastic Stability. Second edition Cambridge University Press, (2009) MR2509253
  7. J.S.Rosenthal. Minorization conditions and convergence rates for Markov chain Monte Carlo J. Amer. Stat. Assoc., 90, (1995), 558-566 MR1340509
  8. G.Szegö. Orthogonal Polynomials. Fourth edition AMS Colloquium Publications, 23, (1975) MR0372517
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.