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 [J].

ALDOUS, D .

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 [J].

DIACONIS, P ;

SHAHSHAHANI, M .

ZEITSCHRIFT FUR WAHRSCHEINLICHKEITSTHEORIE UND VERWANDTE GEBIETE, 1981, 57 (02) :159-179

[8] TIME TO REACH STATIONARITY IN THE BERNOULLI LAPLACE DIFFUSION-MODEL [J].

DIACONIS, P ;

SHAHSHAHANI, M .

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 →