Deterministic random walks for rapidly mixing chains
From MaRDI portal
Publication:4584953
DOI10.1137/16M1087667zbMATH Open1394.05118arXiv1311.3749OpenAlexW2963811310WikidataQ129270916 ScholiaQ129270916MaRDI QIDQ4584953FDOQ4584953
Authors: Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita 
Publication date: 5 September 2018
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Abstract: The rotor-router model is a deterministic process analogous to a simple random walk on a graph. This paper is concerned with a generalized model, functional-router model, which imitates a Markov chain possibly containing irrational transition probabilities. We investigate the discrepancy of the number of tokens at a single vertex between the functional-router model and its corresponding Markov chain, and give an upper bound in terms of the mixing time of the Markov chain.
Full work available at URL: https://arxiv.org/abs/1311.3749
Recommendations
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Randomized algorithms (68W20) Random walks on graphs (05C81)
Cites Work
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- Approximation algorithms for NP-hard problems.
- Title not available (Why is that?)
- Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile
- A distributed ant algorithm for efficiently patrolling a network
- The rotor-router shape is spherical
- Simulating a Random Walk with Constant Error
- Deterministic random walks on the two-dimensional grid
- Euler Tour Lock-In Problem in the Rotor-Router Model
- Does Adding More Agents Make a Difference? A Case Study of Cover Time for the Rotor-Router
- Spherical asymptotics for the rotor-router model in $\mathbb{Z}^d$
- Rotor walks and Markov chains
- The Chairman assignment problem
- Improved analysis of deterministic load-balancing schemes
- Exact sampling with coupled Markov chains and applications to statistical mechanics
- Mathematical aspects of mixing times in Markov chains.
- Quasi-Monte Carlo methods and pseudo-random numbers
- Internal diffusion limited aggregation
- Goldbug variations
- Logarithmic fluctuations for internal DLA
- Title not available (Why is that?)
- Title not available (Why is that?)
- Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
- The hitting and cover times of random walks on finite graphs using local degree information
- Approximation Algorithm and Perfect Sampler for Closed Jackson Networks with Single Servers
- Deterministic random walks on the integers
- Deterministic random walks on regular trees
- Quasirandom load balancing
- \(m\)-balanced words: A generalization of balanced words
- Deterministic random walks on finite graphs
- Faster random generation of linear extensions
- Total variation discrepancy of deterministic random walks for ergodic Markov chains
- Deterministic random walks for rapidly mixing chains
- Limit behavior of the multi-agent rotor-router system
- \(L _{ \infty }\)-discrepancy analysis of polynomial-time deterministic samplers emulating rapidly mixing chains
- Strong robustness of randomized rumor spreading protocols
- Tight bounds for quasirandom rumor spreading
- Quasirandom rumor spreading on expanders
- Quasirandom broadcasting on the complete graph is as fast as randomized broadcasting
- Introducing Quasirandomness to Computer Science
- Quasirandom rumor spreading, an experimental analysis
Cited In (10)
- Saturated chains of subsets and a random walk
- Deterministic random walks for rapidly mixing chains
- Deterministic random walks on finite graphs
- Deterministic random walks on finite graphs
- Unbounded discrepancy of deterministic random walks on grids
- Unbounded discrepancy of deterministic random walks on grids
- Pseudo-mixing Time of Random Walks
- \(L _{ \infty }\)-discrepancy analysis of polynomial-time deterministic samplers emulating rapidly mixing chains
- Total variation discrepancy of deterministic random walks for ergodic Markov chains
- Total variation discrepancy of deterministic random walks for ergodic Markov chains
This page was built for publication: Deterministic random walks for rapidly mixing chains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4584953)
