A NON-LOCAL RANDOM WALK ON THE HYPERCUBE

被引：2

作者：

Nestoridi, Evita ^{[1
,2
]}

机构：

[1] Stanford Univ, Stanford, CA 94305 USA

[2] Princeton Univ, Dept Math, Fine Hall,Washington Rd, Princeton, NJ 08544 USA

来源：

ADVANCES IN APPLIED PROBABILITY | 2017年 / 49卷 / 04期

关键词：

Hypercube; coupling; random walk; Ehrenfest urn model; MARKOV-CHAINS; FINITE-GROUPS;

D O I：

10.1017/apr.2017.42

中图分类号：

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

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

In this paper we study the random walk on the hypercube (Z/2Z)(n) which at each step flips k randomly chosen coordinates. We prove that the mixing time for this walk is of the order (n/k) log n. We also prove that if k = o(n) then the walk exhibits cutoff at (n/2k) log n with window n/2k.

引用

收藏

页码：1288 / 1299

页数：12

相关论文

共 16 条

[1] SHUFFLING CARDS AND STOPPING-TIMES [J].

ALDOUS, D ;

DIACONIS, P .

AMERICAN MATHEMATICAL MONTHLY, 1986, 93 (05) :333-348

[2] MINIMIZATION ALGORITHMS AND RANDOM-WALK ON THE D-CUBE [J].

ALDOUS, D .

ANNALS OF PROBABILITY, 1983, 11 (02) :403-413

[3]

ALDOUS D, 1983, LECT NOTES MATH, V986, P243

[4]

Andersen HC, 2007, Journal de la Societe francaise de statistique Revue de statistique appliquee, V148, P5

[5]

[Anonymous], 1947, AM MATH MON, DOI DOI 10.2307/2304386

[6] Path coupling: A technique for proving rapid mixing in Markov chains [J].

Bubley, R ;

Dyer, M .

38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1997, :223-231

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

[8] COMPARISON TECHNIQUES FOR RANDOM-WALK ON FINITE-GROUPS [J].

DIACONIS, P ;

SALOFFCOSTE, L .

ANNALS OF PROBABILITY, 1993, 21 (04) :2131-2156

[9]

Diaconis P., 1990, Random Structures & Algorithms, V1, P51, DOI [10.1002/rsa.3240010105, DOI 10.1002/RSA.3240010105]

[10]

DIACONIS P., 1988, Lect. Notes-Monogr. Ser., V11