Article Contentsp. 387p. 388p. 389p. 390p. 391p. 392p. 393p. 394p. 395p. 396p. 397p. 398p. 399p. 400p. 401p. 402p. 403p. 404p. 405Issue Table of ContentsSIAM Review, Vol. 37, No. 3 (Sep., 1995), pp. 297-490Front MatterDisplacement Structure: Theory and Applications [pp. 297-386]Convergence Rates for Markov Chains [pp. 387-405]Case Study from IndustryGeometry of the Shoulder of a Packaging Machine [pp. 406-422]Classroom NotesA Motivational Example for the Numerical Solution of Two-Point Boundary-Value Problems [pp. 423-427]Series, the Convergence of Which Should be Interpreted in the Sense of L. Schwartz's Distributions [pp. 428-435]Spherical Harmonics Representation of an Inhomogeneous Plane Wave [pp. 436-438]Problems and Solutions [pp. 439-458]Book ReviewsReview: untitled [p. 459]Review: untitled [pp. 459-460]Review: untitled [pp. 460-461]Review: untitled [pp. 461-462]Review: untitled [pp. 462-464]Review: untitled [pp. 464-466]Review: untitled [pp. 466-467]Review: untitled [pp. 467-468]Review: untitled [pp. 468-469]Review: untitled [pp. 469-470]Review: untitled [pp. 470-471]Review: untitled [pp. 471-472]Review: untitled [p. 472]Review: untitled [pp. 472-473]Review: untitled [pp. 473-474]Review: untitled [p. 474]Review: untitled [pp. 474-475]Review: untitled [pp. 475-476]Review: untitled [pp. 476-477]Review: untitled [pp. 477-479]Review: untitled [p. 479]Review: untitled [pp. 479-481]Selected Collections [pp. 481-484]Later Editions [pp. 484-485]Back Matter [pp. 486-490]Convergence Rates for Markov ChainsAuthor(s): Jeffrey S. RosenthalSource: SIAM Review, Vol. 37, No. 3 (Sep., 1995), pp. 387-405Published by: Society for Industrial and Applied MathematicsStable URL: http://www.jstor.org/stable/2132659Accessed: 14/01/2009 11:53Your use of the JSTOR archive indicates your acceptance of JSTOR's Terms and Conditions of Use, available athttp://www.jstor.org/page/info/about/policies/terms.jsp. JSTOR's Terms and Conditions of Use provides, in part, that unlessyou have obtained prior permission, you may not download an entire issue of a journal or multiple copies of articles, and youmay use content in the JSTOR archive only for your personal, non-commercial use.Please contact the publisher regarding any further use of this work. Publisher contact information may be obtained athttp://www.jstor.org/action/showPublisher?publisherCode=siam.Each copy of any part of a JSTOR transmission must contain the same copyright notice that appears on the screen or printedpage of such transmission.JSTOR is a not-for-profit organization founded in 1995 to build trusted digital archives for scholarship. We work with thescholarly community to preserve their work and the materials they rely upon, and to build a common research platform thatpromotes the discovery and use of these resources. For more information about JSTOR, please contact [email protected] for Industrial and Applied Mathematics is collaborating with JSTOR to digitize, preserve and extendaccess to SIAM Review.http://www.jstor.orgCONVERGENCE RATES FOR MARKOV CHAINS 391 FACT 1. Any stochastic matrix P has an eigenvalue equal to 1. Proof. Define the vector u by u(x) = 1 for all x E X, then it is easily verified that Pu=u. D We now write the (generalized) eigenvalues of P (counted with algebraic multiplic- ity) as Xo, XA, . . ., Anl-. Without loss of generality we take Xo = 1. We further set A* = maxI<j <n-I IXj1 the largest absolute value of the nontrivial eigenvalues of P. FACT 2. We have XA < 1. Furthermore, if P (x, y) > Ofor all x, y e X, then XA < 1. Proof. Suppose Pv = Av. Choose an index x so that I v(x)I > Iv(y)I for all y e X. Then AXv(x)I = I(Pv)xI = I E P(X, y)v(y)I < E Iv(y)lP(x, y) < E Iv(x)IP(x, y) = Iv(x)l, y y y so that IXI < 1. Hence XA, < 1. Now suppose P (x, y) > 0 for all x and y. It is then easily seen that the inequality above can only be equality if v is a constant vector, i.e., v(O) = v(1) = *.* = v(n - 1). This shows that Xo = 1 is the only eigenvalue of absolute value 1 in this case. Hence if P is diagonalizable we are done. If P is not diagonalizable, then we still need to prove that the eigenvalue Xo = 1 is not part of a larger Jordan block. If it were, then for some vector v we would have Pv = v + u, where u = (1, 1, . . ., 1)t. But then, choosing x E X with .91e v(x) > 'Re v(y) for all y E X, we have that 1 + Re v(x) = ie (Pv)x = 'JRe , P(x, y)v(y) < .9te , P(x, y)v(x) = Nte v(x), y y a contradiction. D The importance of eigenvalues for convergence properties comes from the following. FACT 3. Suppose P satisfies X,, < 1. Then, there is a unique stationary distribution 7r on X and, given an initial distribution ,uo and point x E X, there is a constant Cx > 0 such that Ivtk(X) - (X) < CxkJi (X*)k-J+l, where J is the size of the largest Jordan block of P. (Itfollows immediately that 11k - 11 < CkJ-I (X*)k-J+l, where C = 2 Cx.) In particular, if P is diagonalizable (so that J = 1), then n-I n-I Lk(x)-T(X)| < Ea1 (X)<, Ik < l lam. v. (x)J ) (X*)k, m=1 m=l where vO . . ., Vn,I are a basis of right eigenvectors corresponding to Xo, . Xn. , respec- tively, and where am are the (unique) complex coefficients satisfying Alo = aovo+ajv +***+an_1Vnv-1 If the eigenvectors vj are orthonormal in L2(7w), i.e., if Ex vi (x)vj (x)w(x) = ij, then we get the further bound l-i /n-1 E i (a(x) - 7z(X) 127(X) = l12 I XmI2 k < (E lam 12) (X*)k. x tn=1 \n=1 Proof. We begin by assuming that P is diagonalizable. Then, using that I1k = ,o pk, that Vm P = AZn Vin, and that Xo = 1, we have that I1k = aovo+ a IvI (X 1)k + + a,,Iv-, (Xn-I )k.392 JEFFREY S. ROSENTHAL Since < 1, we have (m)k _0 as k -+oo for I < m < n-1, so thatgA -* aovo. It follows that r = aovo must be a probability distribution. Hence, in particular, ao = (ZX vo(y))-l so it does not depend on the choice of go. Thus, gk(X) -7r(X) = aivi(x)(Xi)k + * + an-ivn-I(x)(Xn-I)k. The stated bound on I gk (x) - 7r (x) I now follows from the triangle inequality. The expression for the L2(wT) norm of gk - w follows immediately from orthonormality. For nondiagonalizable P, we must allow some of the vectors vm to be generalized eigen- vectors in the sense that we may have Vm P = Xm Vm + Xm+ 1. The only difference from the previous argument is that now Ilk may contain some additional terms. If vj, vj+l . . . vj+f_ form a Jordan block of size e, corresponding to the value