Deterministic random walks for rapidly mixing chains
From MaRDI portal
Publication:4584953
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 420886 (Why is no real title available?)
- scientific article; zbMATH DE number 5764860 (Why is no real title available?)
- scientific article; zbMATH DE number 3019347 (Why is no real title available?)
- A distributed ant algorithm for efficiently patrolling a network
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- Approximation Algorithm and Perfect Sampler for Closed Jackson Networks with Single Servers
- Approximation algorithms for NP-hard problems.
- Deterministic random walks for rapidly mixing chains
- Deterministic random walks on finite graphs
- Deterministic random walks on regular trees
- Deterministic random walks on the integers
- Deterministic random walks on the two-dimensional grid
- Does Adding More Agents Make a Difference? A Case Study of Cover Time for the Rotor-Router
- Euler Tour Lock-In Problem in the Rotor-Router Model
- Exact sampling with coupled Markov chains and applications to statistical mechanics
- Faster random generation of linear extensions
- Goldbug variations
- Improved analysis of deterministic load-balancing schemes
- Internal diffusion limited aggregation
- Introducing Quasirandomness to Computer Science
- Limit behavior of the multi-agent rotor-router system
- Logarithmic fluctuations for internal DLA
- Mathematical aspects of mixing times in Markov chains.
- Quasi-Monte Carlo methods and pseudo-random numbers
- Quasirandom broadcasting on the complete graph is as fast as randomized broadcasting
- Quasirandom load balancing
- Quasirandom rumor spreading on expanders
- Quasirandom rumor spreading, an experimental analysis
- Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
- Rotor walks and Markov chains
- Simulating a Random Walk with Constant Error
- Spherical asymptotics for the rotor-router model in $\mathbb{Z}^d$
- Strong robustness of randomized rumor spreading protocols
- Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile
- The Chairman assignment problem
- The hitting and cover times of random walks on finite graphs using local degree information
- The rotor-router shape is spherical
- Tight bounds for quasirandom rumor spreading
- Total variation discrepancy of deterministic random walks for ergodic Markov chains
- \(L _{ \infty }\)-discrepancy analysis of polynomial-time deterministic samplers emulating rapidly mixing chains
- \(m\)-balanced words: A generalization of balanced words
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)
