Total Variation Discrepancy of Deterministic Random Walks for Ergodic Markov Chains

Autor: Masafumi Yamashita, Takeharu Shiraga, Shuji Kijima, Yukiko Yamauchi
Rok vydání: 2015
Předmět:
FOS: Computer and information sciences
Markov kernel
General Computer Science
Discrete Mathematics (cs.DM)
0102 computer and information sciences
02 engineering and technology
Expected value
Markov model
01 natural sciences
Upper and lower bounds
Theoretical Computer Science
Combinatorics
010104 statistics & probability
symbols.namesake
Mixing (mathematics)
Markov renewal process
Simple (abstract algebra)
0202 electrical engineering
electronic engineering
information engineering
Ergodic theory
Statistical physics
0101 mathematics
Mathematics
Markov chain mixing time
Markov chain
Variable-order Markov model
Markov chain Monte Carlo
Random walk
010201 computation theory & mathematics
symbols
Markov property
020201 artificial intelligence & image processing
Computer Science - Discrete Mathematics
Zdroj: ANALCO
Scopus-Elsevier
DOI: 10.48550/arxiv.1508.03458
Popis: 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 1 -discrepancy), which plays an important role in the analysis of an FPRAS based on MCMC. This paper investigates the L 1 -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 ( m t ⁎ ) of the L 1 -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 ⁎ ) for non-oblivious deterministic random walks, if the corresponding Markov chain is ergodic and lazy. We also present some lower bounds.
Databáze: OpenAIRE
Externí odkaz: