COMPARISON TECHNIQUES FOR RANDOM-WALK ON FINITE-GROUPS

被引：135

作者：

DIACONIS, P ^{[1
]}

SALOFFCOSTE, L ^{[1
]}

机构：

[1] UNIV PARIS 06,CNRS,F-75252 PARIS 05,FRANCE

来源：

ANNALS OF PROBABILITY | 1993年 / 21卷 / 04期

关键词：

CARD SHUFFLING; REVERSIBLE MARKOV CHAINS; RANDOM WALK; GROUPS; EIGENVALUES;

D O I：

10.1214/aop/1176989013

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

We develop techniques for bounding the rate of convergence of a symmetric random walk on a finite group to the uniform distribution. The techniques gives bounds on the second largest (and other) eigenvalues in terms of the eigenvalues of a comparison chain with known eigenvalues. The techniques yield sharp rates for a host of previously intractable problems on the symmetric group.

引用

页码：2131 / 2156

页数：26

共 24 条

[1] HITTING TIMES FOR RANDOM-WALKS ON VERTEX-TRANSITIVE GRAPHS
ALDOUS, D
[J]. MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1989, 106 : 179 - 191
[2] ALDOUS D, 1987, PROBAB ENG INFORM SC, V1, P33
[3] [Anonymous], ANN APPL PROBAB, DOI [DOI 10.1214/AOAP/1177005980, DOI 10.1214/aoap/1177005980]
[4] BABAI L, 1909, EUROPEAN J COMBIN, V10, P507
[5] BABAI L, 1990, 31ST P ANN S F COMP
[6] DESAI, 1991, IN PRESS SIAM J MATR
[7] GENERATING A RANDOM PERMUTATION WITH RANDOM TRANSPOSITIONS
DIACONIS, P
SHAHSHAHANI, M
[J]. ZEITSCHRIFT FUR WAHRSCHEINLICHKEITSTHEORIE UND VERWANDTE GEBIETE, 1981, 57 (02): : 159 - 179
[8] TIME TO REACH STATIONARITY IN THE BERNOULLI LAPLACE DIFFUSION-MODEL
DIACONIS, P
SHAHSHAHANI, M
[J]. SIAM JOURNAL ON MATHEMATICAL ANALYSIS, 1987, 18 (01) : 208 - 218
[9] DIACONIS P, 1992, MODERATE GROWTH RAND
[10] Diaconis P., 1988, GROUP REPRESENTATION

← 1 2 3 →