Mixing Time and Cutoff for a Random Walk on the Ring of Integers mod n

Michael E. Bate; Stephen B. Connor

Mixing Time and Cutoff for a Random Walk on the Ring of Integers mod n

Mathematics

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

Abstract

We analyse a random walk on the ring of integers mod $n$, which at each time point can make an additive `step' or a multiplicative `jump'. When the probability of making a jump tends to zero as an appropriate power of $n$ we prove the existence of a total variation pre-cutoff for this walk. In addition, we show that the process obtained by subsampling our walk at jump times exhibits a true cutoff, with mixing time dependent on whether the step distribution has zero mean.

Original language	English
Pages (from-to)	993-1009
Journal	Bernoulli
Volume	24
Issue number	2
Early online date	16 Feb 2016
Publication status	Published - 2018

Bibliographical note

© 2017 Bernoulli Society. This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details.

Keywords

math.PR
60J10

Access to Document

14073580v2
© 2017 Bernoulli Society. This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details.
Accepted author manuscript, 186 KB

http://arxiv.org/abs/1407.3580

Cite this

@article{66cc4a4360204c138c6c77afe1680e4e,

title = "Mixing Time and Cutoff for a Random Walk on the Ring of Integers mod n",

abstract = "We analyse a random walk on the ring of integers mod $n$, which at each time point can make an additive `step' or a multiplicative `jump'. When the probability of making a jump tends to zero as an appropriate power of $n$ we prove the existence of a total variation pre-cutoff for this walk. In addition, we show that the process obtained by subsampling our walk at jump times exhibits a true cutoff, with mixing time dependent on whether the step distribution has zero mean.",

keywords = "math.PR, 60J10",

author = "Bate, {Michael E.} and Connor, {Stephen B.}",

note = "{\textcopyright} 2017 Bernoulli Society. This is an author-produced version of the published paper. Uploaded in accordance with the publisher{\textquoteright}s self-archiving policy. Further copying may not be permitted; contact the publisher for details.",

year = "2018",

language = "English",

volume = "24",

pages = "993--1009",

journal = "Bernoulli",

issn = "1350-7265",

publisher = "International Statistical Institute",

number = "2",

}

TY - JOUR

T1 - Mixing Time and Cutoff for a Random Walk on the Ring of Integers mod n

AU - Bate, Michael E.

AU - Connor, Stephen B.

N1 - © 2017 Bernoulli Society. This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details.

PY - 2018

Y1 - 2018

N2 - We analyse a random walk on the ring of integers mod $n$, which at each time point can make an additive `step' or a multiplicative `jump'. When the probability of making a jump tends to zero as an appropriate power of $n$ we prove the existence of a total variation pre-cutoff for this walk. In addition, we show that the process obtained by subsampling our walk at jump times exhibits a true cutoff, with mixing time dependent on whether the step distribution has zero mean.

AB - We analyse a random walk on the ring of integers mod $n$, which at each time point can make an additive `step' or a multiplicative `jump'. When the probability of making a jump tends to zero as an appropriate power of $n$ we prove the existence of a total variation pre-cutoff for this walk. In addition, we show that the process obtained by subsampling our walk at jump times exhibits a true cutoff, with mixing time dependent on whether the step distribution has zero mean.

KW - math.PR

KW - 60J10

M3 - Article

SN - 1350-7265

VL - 24

SP - 993

EP - 1009

JO - Bernoulli

JF - Bernoulli

IS - 2

ER -