A greedy chip‐firing game

DOI10.1002/RSA.21119zbMATH Open1524.60168arXiv2102.00346OpenAlexW4308595843MaRDI QIDQ6074879FDOQ6074879

Authors: Rupert Li, James Propp 

Publication date: 19 October 2023

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

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.

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

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

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)

Cites Work

• Chip-firing games on graphs
• Title not available (Why is that?)
• Markov Chains
• Title not available (Why is that?)
• The probabilistic abacus
• Why does the probabilistic abacus work?
• Rotor walks and Markov chains
• Chip-Firing and Rotor-Routing on Directed Graphs
• Goldbug variations
• The mathematics of chip-firing
• Divisors and sandpiles. An introduction to chip-firing

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)