A non-local random walk on the hypercube

Evita Nestoridi

doi:10.1017/apr.2017.42

A non-local random walk on the hypercube

Evita Nestoridi

Mathematics

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

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

Original language	English
Pages (from-to)	1288-1299
Number of pages	12
Journal	Advances in Applied Probability
Volume	49
Issue number	4
DOIs	https://doi.org/10.1017/apr.2017.42
State	Published - Dec 1 2017

Keywords

coupling
Ehrenfest urn model
Hypercube
random walk

Access to Document

10.1017/apr.2017.42

Cite this

@article{68864263dfb44f3b908c1e2d97bb24b5,

title = "A non-local random walk on the hypercube",

abstract = "In this paper we study the random walk on the hypercube (ℤ / 2ℤ)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)logn. We also prove that if k = o(n) then the walk exhibits cutoff at (n / 2k)logn with window n / 2k.",

keywords = "coupling, Ehrenfest urn model, Hypercube, random walk",

author = "Evita Nestoridi",

note = "Publisher Copyright: Copyright {\textcopyright} Applied Probability Trust 2017.",

year = "2017",

month = dec,

day = "1",

doi = "10.1017/apr.2017.42",

language = "English",

volume = "49",

pages = "1288--1299",

journal = "Advances in Applied Probability",

issn = "0001-8678",

number = "4",

}

TY - JOUR

T1 - A non-local random walk on the hypercube

AU - Nestoridi, Evita

PY - 2017/12/1

Y1 - 2017/12/1

N2 - In this paper we study the random walk on the hypercube (ℤ / 2ℤ)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)logn. We also prove that if k = o(n) then the walk exhibits cutoff at (n / 2k)logn with window n / 2k.

AB - In this paper we study the random walk on the hypercube (ℤ / 2ℤ)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)logn. We also prove that if k = o(n) then the walk exhibits cutoff at (n / 2k)logn with window n / 2k.

KW - coupling

KW - Ehrenfest urn model

KW - Hypercube

KW - random walk

UR - https://www.scopus.com/pages/publications/85044260597

U2 - 10.1017/apr.2017.42

DO - 10.1017/apr.2017.42

M3 - Article

AN - SCOPUS:85044260597

SN - 0001-8678

VL - 49

SP - 1288

EP - 1299

JO - Advances in Applied Probability

JF - Advances in Applied Probability

IS - 4

ER -

A non-local random walk on the hypercube

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this