Strong uniform times and finite random walks. (English) Zbl 0631.60065
This paper is concerned with obtaining bounds for the rate of convergence to the stationary distribution for finite Markov chains \(\{X_ n,n\geq 0\}\) having strong symmetry properties for the transition matrices. The use of strong uniform times to bound separation distance is emphasized, the strong uniform time T being a randomized stopping time such that \(P(X_ k=i| T=k)=\pi (i)\) for all \(0\leq k<\infty\) and i, \(\pi\) being the stationary distribution.
It is shown that a strong uniform time T always exists and that, if \(\pi_ n\) is the distribution of \(X_ n\), the separation distance \(\max_{i}(1-\pi_ n(i)/\pi (i))\leq P(T>n)\), \(n\geq 0\). This methodology is related to coupling and Fourier analysis procedures. Various examples for random walks on groups are given to illustrate the results.
It is shown that a strong uniform time T always exists and that, if \(\pi_ n\) is the distribution of \(X_ n\), the separation distance \(\max_{i}(1-\pi_ n(i)/\pi (i))\leq P(T>n)\), \(n\geq 0\). This methodology is related to coupling and Fourier analysis procedures. Various examples for random walks on groups are given to illustrate the results.
Reviewer: C.C.Heyde
MSC:
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
| 60G50 | Sums of independent random variables; random walks |
Keywords:
bounds for the rate of convergence to the stationary distribution; strong symmetry properties; randomized stopping time; coupling; Fourier analysis proceduresReferences:
| [1] | Aldous, D., Random walks on finite groups and rapidly mixing Markov chains, (Seminaire de Probabilities XVII. Seminaire de Probabilities XVII, Lecture Notes in Math., Vol. 986 (1983), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0514.60067 |
| [2] | Aldous, D., On the Markov chain simulation method for uniform combinatorial distributions and simulated annealingm, preprint (1986) |
| [3] | Aldous, D.; Diaconis, P., Shuffling cards and stopping times, Amer. Math. Monthly, 93, 333-348 (1986) · Zbl 0603.60006 |
| [4] | D. Aldous and P. Diaconis; D. Aldous and P. Diaconis |
| [5] | Alon, N., Eigenvalues and expanders, Combinatorica (1986), in press · Zbl 0661.05053 |
| [6] | Biggs, N., Algebraic Graph Theory (1974), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0284.05101 |
| [7] | Bollabas, B., Random Graphs (1985), Academic Press: Academic Press New York · Zbl 0567.05042 |
| [8] | A. Broder; A. Broder |
| [9] | Broder, A., How Hard Is it to Marry at Random?, (STOC 85 (1986)), to appear |
| [10] | Chung, F. R.C; Diaconis, P.; Graham, R. L., Random walks arising in random number generation, Ann. Probab. (1986), in press |
| [11] | Diaconis, P., Group Theory in Statistics (1986), IMS: IMS Hayward, CA, to appear |
| [12] | Diaconis, P.; Shahshahani, M., Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete, 57, 159-179 (1981) · Zbl 0485.60006 |
| [13] | Diaconis, P.; Shahshahani, M., Factoring probabilities on compact groups, preprint (1983) |
| [14] | Diaconis, P.; Shahshahani, M., Products of random matrices as they arise in the study of random walks on groups, Contemporary Math., 50, 183-195 (1986) · Zbl 0586.60012 |
| [15] | Diaconis, P.; Shahshahani, M., Time to reach stationarity in the Bernouilli—Laplace diffusion model, SIAM J. Math. Anal. (1986), in press |
| [16] | P. Diaconis and M. Shahshahani; P. Diaconis and M. Shahshahani |
| [17] | Goldstein, S., Maximal coupling, Z. Wahrsch. Verw. Gebiete, 46, 193-204 (1979) · Zbl 0398.60097 |
| [18] | Griffeath, D., A maximal coupling for Markov chain, Z. Wahrsch. Verw. Gebiete, 31, 95-106 (1975) · Zbl 0301.60043 |
| [19] | Heyer, H., Probability Measures on Locally Compact Groups (1977), Springer: Springer Berlin · Zbl 0373.60011 |
| [20] | Heyer, H., Convolution semigroups of probability measures on Gelfand pairs, Exposition Math., 1, 3-45 (1983) · Zbl 0517.60004 |
| [21] | Iosifescu, M., Finite Markov Processes and Their Applications (1980), Wiley: Wiley New York · Zbl 0436.60001 |
| [22] | Letac, G., Problèmes Classiques de Probabilité sur un couple de Gelfand, (Analytic Methods in Probability Theory. Analytic Methods in Probability Theory, Lecture Notes in Math., Vol. 861 (1981), Springer-Verlag: Springer-Verlag New York) · Zbl 0463.60010 |
| [23] | Letac, G.; Takács, L., Random walks on an \(m\)-dimensional cube, J. Reine Angew Math., 310, 187-195 (1979) · Zbl 0411.60072 |
| [24] | Letac, G.; Takács, L., Random walk on a 600-cell, SIAM J. Alg. Discrete Methods, 1, 114-120 (1980) · Zbl 0498.60073 |
| [25] | Letac, G.; Takács, L., Random walks on a dodecahedron, J. Appl. Probab., 17, 373-384 (1980) · Zbl 0428.60083 |
| [26] | P. Matthews; P. Matthews · Zbl 0637.60087 |
| [27] | Nummelin, E., General Irreducible Markov Chains and Non-negative Operators (1986), Cambridge Univ. Press: Cambridge Univ. Press Cambridge |
| [28] | R. Pemantle; R. Pemantle |
| [29] | Pitman, J., On coupling of Markov chains, Z. Wahrsch. Verw. Gebiete, 35, 315-322 (1976) · Zbl 0356.60003 |
| [30] | Seneta, E., Coefficients of ergodicity: structure and applications, Advan. Appl. Probab., 11, 576-590 (1979) · Zbl 0406.60060 |
| [31] | Serre, J. P., Linear Representations of Finite Groups (1977), Springer: Springer New York · Zbl 0355.20006 |
| [32] | Stanton, D., Orthogonal polynomials and Chevalley groups, (Askey, R.; etal., Special Functions: Group Theoretic Aspects and Applications (1984), Reidel: Reidel Dordrecht) · Zbl 0578.20041 |
| [33] | Takács, L., Random flights on regular polytopes, SIAM J. Algebra Discrete Methods, 2, 153-171 (1981) · Zbl 0498.60074 |
| [34] | Takács, L., Random walks on groups, Linear Algebra Appl., 43, 49-67 (1982) · Zbl 0488.60012 |
| [35] | Takács, L., Random walk on a finite group, Acta. Sci. Math. Szeged., 45, 395-408 (1983) · Zbl 0534.60064 |
| [36] | Takács, L., Random flights on regular graphs, Advan. Appl. Probab., 16, 618-637 (1984) · Zbl 0549.60062 |
| [37] | Thorisson, H., On maximal and distributional coupling, Ann. Probab., 14, 873-876 (1986) · Zbl 0604.60034 |
| [38] | Thorp, E., Nonrandom shuffling with applications to the game of Faro, J. Amer. Statist. Assoc., 68, 842-847 (1973) · Zbl 0274.90086 |
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.
