A counterexample to monotonicity of relative mass in random walks

Oded Regev; Igor Shinkar

doi:10.1214/16-ECP4392

A counterexample to monotonicity of relative mass in random walks

Oded Regev, Igor Shinkar

Computer Science

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

Abstract

For a finite undirected graph G = (V,E), let p_u,v(t) denote the probability that a continuous-time random walk starting at vertex u is in v at time t. In this note we give an example of a Cayley graph G and two vertices u, v ε G for which the function r_u;v(t) = p_u,v(t)/p_u,u(t) t ≥ 0 is not monotonically non-decreasing. This answers a question asked by Peres in 2013.

Original language	English (US)
Article number	8
Journal	Electronic Communications in Probability
Volume	21
DOIs	https://doi.org/10.1214/16-ECP4392
State	Published - 2016

Keywords

Continuous-time random walk
Lamplighter graph

ASJC Scopus subject areas

Statistics and Probability
Statistics, Probability and Uncertainty

Access to Document

10.1214/16-ECP4392

Cite this

@article{1e7ab7d1fe7e42e1901645d6f0c9f695,

title = "A counterexample to monotonicity of relative mass in random walks",

abstract = "For a finite undirected graph G = (V,E), let pu,v(t) denote the probability that a continuous-time random walk starting at vertex u is in v at time t. In this note we give an example of a Cayley graph G and two vertices u, v ε G for which the function ru;v(t) = pu,v(t)/pu,u(t) t ≥ 0 is not monotonically non-decreasing. This answers a question asked by Peres in 2013.",

keywords = "Continuous-time random walk, Lamplighter graph",

author = "Oded Regev and Igor Shinkar",

year = "2016",

doi = "10.1214/16-ECP4392",

language = "English (US)",

volume = "21",

journal = "Electronic Communications in Probability",

issn = "1083-589X",

publisher = "Institute of Mathematical Statistics",

}

TY - JOUR

T1 - A counterexample to monotonicity of relative mass in random walks

AU - Regev, Oded

AU - Shinkar, Igor

PY - 2016

Y1 - 2016

N2 - For a finite undirected graph G = (V,E), let pu,v(t) denote the probability that a continuous-time random walk starting at vertex u is in v at time t. In this note we give an example of a Cayley graph G and two vertices u, v ε G for which the function ru;v(t) = pu,v(t)/pu,u(t) t ≥ 0 is not monotonically non-decreasing. This answers a question asked by Peres in 2013.

AB - For a finite undirected graph G = (V,E), let pu,v(t) denote the probability that a continuous-time random walk starting at vertex u is in v at time t. In this note we give an example of a Cayley graph G and two vertices u, v ε G for which the function ru;v(t) = pu,v(t)/pu,u(t) t ≥ 0 is not monotonically non-decreasing. This answers a question asked by Peres in 2013.

KW - Continuous-time random walk

KW - Lamplighter graph

UR - http://www.scopus.com/inward/record.url?scp=84964322480&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84964322480&partnerID=8YFLogxK

U2 - 10.1214/16-ECP4392

DO - 10.1214/16-ECP4392

M3 - Article

AN - SCOPUS:84964322480

SN - 1083-589X

VL - 21

JO - Electronic Communications in Probability

JF - Electronic Communications in Probability

M1 - 8

ER -

A counterexample to monotonicity of relative mass in random walks

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this