TY - GEN

T1 - Total variation discrepancy of deterministic random walks for ergodic Markov chains

AU - Shiraga, Takeharu

AU - Yamauchi, Yukiko

AU - Kijima, Shuji

AU - Yamashita, Masafumi

N1 - Funding Information:
The authors would like to thank the anonymous reviewers for their valuable comments, especially for the proof of Proposition 3.4 . This work is supported by JSPS KAKENHI Grant Numbers 15J03840 , 15K15938 , 25700002 , 15H02666 .

PY - 2016

Y1 - 2016

N2 - Motivated by a derandomization of Markov chain Monte Carlo (MCMC), this paper investigates deterministic random walks, which is a deterministic process analogous to a random walk. While there are some progress on the analysis of the vertex-wise discrepancy (i.e., L∞ discrepancy), little is known about the total variation discrepancy (i.e., Li discrepancy), which plays a significant role in the analysis of an FPRAS based on MCMC. This paper investigates upper bounds of 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(m√t∗ log t∗) for non-oblivious deterministic random walks, if the corresponding Markov chain is ergodic and lazy. We also present some lower bounds.

AB - Motivated by a derandomization of Markov chain Monte Carlo (MCMC), this paper investigates deterministic random walks, which is a deterministic process analogous to a random walk. While there are some progress on the analysis of the vertex-wise discrepancy (i.e., L∞ discrepancy), little is known about the total variation discrepancy (i.e., Li discrepancy), which plays a significant role in the analysis of an FPRAS based on MCMC. This paper investigates upper bounds of 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(m√t∗ log t∗) for non-oblivious deterministic random walks, if the corresponding Markov chain is ergodic and lazy. We also present some lower bounds.

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

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

U2 - 10.1137/1.9781611974324.13

DO - 10.1137/1.9781611974324.13

M3 - Conference contribution

AN - SCOPUS:84965173529

T3 - 13th Workshop on Analytic Algorithmics and Combinatorics 2016, ANALCO 2016

SP - 138

EP - 148

BT - 13th Workshop on Analytic Algorithmics and Combinatorics 2016, ANALCO 2016

A2 - Fill, James Allen

A2 - Ward, Mark Daniel

PB - Society for Industrial and Applied Mathematics Publications

T2 - 13th Workshop on Analytic Algorithmics and Combinatorics 2016, ANALCO 2016

Y2 - 11 January 2016

ER -