2015/08/14 by Takeharu Shiraga, Shiraga, Takeharu, Yukiko Yamauchi +5
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM
paper · pdf · doi:10.48550/arxiv.1508.03458
arxiv created 2015/08/14 · arxiv updated 2015/08/17
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 several progresses on the analysis of the vertex-wise discrepancy (i.e., L_∞ discrepancy), little is known about the \em total variation discrepancy (i.e., L1 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 \rm 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 \rm 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.