Total variation discrepancy of deterministic random walks for ergodic Markov chains

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., L₁-discrepancy), which plays an important role in the analysis of an FPRAS based on MCMC. This paper investigates the L₁-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 L₁-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.