Total variation discrepancy of deterministic random walks for ergodic Markov chains

DOI10.1016/j.tcs.2016.11.017zbMath1380.68304OpenAlexW2222348553MaRDI QIDQ1675930

Takeharu Shiraga, Shuji Kijima, Masafumi Yamashita, Yukiko Yamauchi

Publication date: 3 November 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.11.017

zbMATH Keywords

mixing timeload balancingMarkov chain Monte Carlo (MCMC)propp machinerotor router model

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Random walks on graphs (05C81) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (3)

Total variation discrepancy of deterministic random walks for ergodic Markov chains ⋮ Deterministic Random Walks for Rapidly Mixing Chains ⋮ The cover time of deterministic random walks for general transition probabilities

Cites Work

• Unnamed Item
• An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution
• Random generation of combinatorial structures from a uniform distribution
• The Chairman assignment problem
• Limit behavior of the multi-agent rotor-router system
• Total variation discrepancy of deterministic random walks for ergodic Markov chains
• A distributed ant algorithm for efficiently patrolling a network
• Deterministic random walks on the integers
• Improved Analysis of Deterministic Load-Balancing Schemes
• A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions
• L  ∞ -Discrepancy Analysis of Polynomial-Time Deterministic Samplers Emulating Rapidly Mixing Chains
• Counting independent sets up to the tree threshold
• Bypassing KLS
• Bounds on the Cover Time of Parallel Rotor Walks
• Deterministic random walks on regular trees
• Rotor Walks and Markov Chains
• Polynomial-Time Approximation Algorithms for the Ising Model
• Quasirandom Load Balancing
• Simulating a Random Walk with Constant Error
• Deterministic Random Walks on the Two-Dimensional Grid
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• Euler Tour Lock-In Problem in the Rotor-Router Model
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Deterministic random walks on finite graphs
• An FPTAS for #Knapsack and Related Counting Problems

This page was built for publication: Total variation discrepancy of deterministic random walks for ergodic Markov chains