Deterministic Random Walks for Rapidly Mixing Chains
From MaRDI portal
Publication:4584953
DOI10.1137/16M1087667zbMath1394.05118arXiv1311.3749OpenAlexW2963811310WikidataQ129270916 ScholiaQ129270916MaRDI QIDQ4584953
Takeharu Shiraga, Shuji Kijima, Yukiko Yamauchi, Masafumi Yamashita
Publication date: 5 September 2018
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.3749
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Randomized algorithms (68W20) Random walks on graphs (05C81)
Related Items (2)
Deterministic Random Walks for Rapidly Mixing Chains ⋮ The cover time of deterministic random walks for general transition probabilities
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The cover time of deterministic random walks
- The hitting and cover times of random walks on finite graphs using local degree information
- Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile
- The Chairman assignment problem
- Internal diffusion limited aggregation
- Faster random generation of linear extensions
- Limit behavior of the multi-agent rotor-router system
- Total variation discrepancy of deterministic random walks for ergodic Markov chains
- Goldbug variations
- A distributed ant algorithm for efficiently patrolling a network
- \(m\)-balanced words: A generalization of balanced words
- Strong robustness of randomized rumor spreading protocols
- Tight bounds for quasirandom rumor spreading
- Deterministic random walks on the integers
- The rotor-router shape is spherical
- Improved Analysis of Deterministic Load-Balancing Schemes
- Quasirandom Rumor Spreading on Expanders
- Quasirandom broadcasting on the complete graph is as fast as randomized broadcasting
- L ∞ -Discrepancy Analysis of Polynomial-Time Deterministic Samplers Emulating Rapidly Mixing Chains
- Deterministic random walks on regular trees
- Rotor Walks and Markov Chains
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Logarithmic fluctuations for internal DLA
- Quasirandom Load Balancing
- Approximation Algorithm and Perfect Sampler for Closed Jackson Networks with Single Servers
- Simulating a Random Walk with Constant Error
- Deterministic Random Walks on the Two-Dimensional Grid
- Mathematical Aspects of Mixing Times in Markov Chains
- Introducing Quasirandomness to Computer Science
- Euler Tour Lock-In Problem in the Rotor-Router Model
- Quasi-Monte Carlo methods and pseudo-random numbers
- Deterministic Random Walks for Rapidly Mixing Chains
- Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
- Exact sampling with coupled Markov chains and applications to statistical mechanics
- Does Adding More Agents Make a Difference? A Case Study of Cover Time for the Rotor-Router
- Deterministic random walks on finite graphs
- Quasirandom rumor spreading
- Spherical asymptotics for the rotor-router model in $\mathbb{Z}^d$
This page was built for publication: Deterministic Random Walks for Rapidly Mixing Chains
