A greedy chip‐firing game

DOI10.1002/RSA.21119MaRDI QIDQ6074879zbMATH OpenOpenAlexFDO

Authors Rupert Li, James Propp

Publication date 19 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://arxiv.org/abs/2102.00346

zbMATH Keywords

recurrencestationary distributionchip-firing

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: 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.

Recommendations

• A chip-firing variation and a Markov chain with uniform stationary distribution
• Addition of recurrent configurations in chip firing games: finding minimal recurrent configurations with Markov chains
• Chip-firing games on graphs
• Chip-firing games on directed graphs
• Algorithmic aspects of a chip-firing game

Cites work

• scientific article; zbMATH DE number 3145626 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• Chip-Firing and Rotor-Routing on Directed Graphs
• Chip-firing games on graphs
• Divisors and sandpiles. An introduction to chip-firing
• Goldbug variations
• Markov Chains
• Rotor walks and Markov chains
• The mathematics of chip-firing
• The probabilistic abacus
• Why does the probabilistic abacus work?

This page was built for publication: A greedy chip‐firing game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074879)