Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2102.00346 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916865117257728 |
|---|---|
| author | Li, Rupert Propp, James |
| author_facet | Li, Rupert Propp, James |
| contents | We introduce a deterministic analogue of Markov chains that we call the hunger game. Like rotor-routing, the hunger game deterministically mimics the behavior of both recurrent Markov chains and absorbing Markov chains. In the case of recurrent Markov chains with finitely many states, hunger game simulation concentrates around the stationary distribution with discrepancy falling off like $N^{-1}$, where $N$ is the number of simulation steps; in the case of absorbing Markov chains with finitely many states, hunger game simulation also exhibits concentration for hitting measures and expected hitting times with discrepancy falling off like $N^{-1}$ rather than $N^{-1/2}$. When transition probabilities in a finite Markov chain are rational, the game is eventually periodic; the period seems to be the same for all initial configurations and the basin of attraction appears to tile the configuration space (the set of hunger vectors) by translation, but we have not proved this. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2102_00346 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | A Greedy Chip-firing Game Li, Rupert Propp, James Probability Combinatorics 60C05 We introduce a deterministic analogue of Markov chains that we call the hunger game. Like rotor-routing, the hunger game deterministically mimics the behavior of both recurrent Markov chains and absorbing Markov chains. In the case of recurrent Markov chains with finitely many states, hunger game simulation concentrates around the stationary distribution with discrepancy falling off like $N^{-1}$, where $N$ is the number of simulation steps; in the case of absorbing Markov chains with finitely many states, hunger game simulation also exhibits concentration for hitting measures and expected hitting times with discrepancy falling off like $N^{-1}$ rather than $N^{-1/2}$. When transition probabilities in a finite Markov chain are rational, the game is eventually periodic; the period seems to be the same for all initial configurations and the basin of attraction appears to tile the configuration space (the set of hunger vectors) by translation, but we have not proved this. |
| title | A Greedy Chip-firing Game |
| topic | Probability Combinatorics 60C05 |
| url | https://arxiv.org/abs/2102.00346 |