Total variation discrepancy of deterministic random walks for ergodic Markov chains

Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


Motivated by a derandomization of Markov chain Monte Carlo (MCMC), this paper investigates a deterministic random walk, which is a deterministic process analogous to a random walk. There is some recent progress in the analysis of the vertex-wise discrepancy (i.e., L-discrepancy), while little is known about the total variation discrepancy (i.e., L1-discrepancy), which plays an important role in the analysis of an FPRAS based on MCMC. This paper investigates the L1-discrepancy between the expected number of tokens in a Markov chain and the number of tokens in its corresponding deterministic random walk. First, we give a simple but nontrivial upper bound O(mt) of the L1-discrepancy for any ergodic Markov chains, where m is the number of edges of the transition diagram and t is the mixing time of the Markov chain. Then, we give a better upper bound O(mt) for non-oblivious deterministic random walks, if the corresponding Markov chain is ergodic and lazy. We also present some lower bounds.

Original languageEnglish
Pages (from-to)63-74
Number of pages12
JournalTheoretical Computer Science
Publication statusPublished - Nov 7 2017

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Total variation discrepancy of deterministic random walks for ergodic Markov chains'. Together they form a unique fingerprint.

Cite this