Primitive periods in greedy chip-firing games
Abstract
For a finite irreducible rational transition matrix P=(Pij) on n states, the hunger game introduced by Li and Propp is a greedy chip-firing process in which each state i carries a real-valued hunger hi. At each step, a state i of maximal hunger is selected, with ties resolved by a fixed order on the states. Firing i subtracts one from its hunger and then adds Pij to the hunger of each state j. Let π be the stationary distribution of P, and let T be the least positive integer such that Tπ is integral. We prove that every periodic orbit has least period T, with state i firing Tπi times, and that the set of periodic states of total hunger zero tiles the corresponding hyperplane by lattice translations. These results settle two conjectures of Li and Propp. We also prove an analogous least-period theorem for nontrivial periodic orbits of fixed-priority chip-firing on finite strongly connected digraphs, another greedy chip-firing model. We then find a connection between the hunger game and the chairman assignment problem: the greedy rule that always chooses the state furthest below its proportional target is precisely a rank-one hunger game. Motivated by this application and related allocation rules, we generalize the hunger game by assigning each state a score that is a nondecreasing function of its hunger and firing a state of maximal score each time. For these monotone-score hunger games, we prove that every periodic orbit still has least period T and give a sufficient condition for eventual periodicity from every initial state.
Related
- Support periods of polynomials and support-primitive decomposition of constacyclic codes over Galois rings
- A semi-greedy Markushevich basis which is not quasi-greedy
- Isometric Theory for Greedy-Type Properties with Enlarged Greedy Sums
- A Note on Universal Positivity of Rank-Two Quantum Greedy Elements
- A greedy double-block nonlinear Bregman-Kaczmarz method for nonlinear equations
BibTeX
@misc{huang2026primitive,
title = {{Primitive periods in greedy chip-firing games}},
author = {Zheng Huang and Anyuan Tian},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08949},
eprint = {2610.08949},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08949},
}
RIS
TY - UNPB
TI - Primitive periods in greedy chip-firing games
AU - Zheng Huang
AU - Anyuan Tian
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08949
UR - https://arxiv.org/abs/2610.08949
AB - For a finite irreducible rational transition matrix P=(P_ij) on n states, the hunger game introduced by Li and Propp is a greedy chip-firing process in which each state i carries a real-valued hunger h_i. At each step, a state i of maximal hunger is selected, with ties resolved by a fixed order on the states. Firing i subtracts one from its hunger and then adds P_ij to the hunger of each state j. Let π be the stationary distribution of P, and let T be the least positive integer such that Tπ is integral. We prove that every periodic orbit has least period T, with state i firing Tπ_i times, and that the set of periodic states of total hunger zero tiles the corresponding hyperplane by lattice translations. These results settle two conjectures of Li and Propp. We also prove an analogous least-period theorem for nontrivial periodic orbits of fixed-priority chip-firing on finite strongly connected digraphs, another greedy chip-firing model. We then find a connection between the hunger game and the chairman assignment problem: the greedy rule that always chooses the state furthest below its proportional target is precisely a rank-one hunger game. Motivated by this application and related allocation rules, we generalize the hunger game by assigning each state a score that is a nondecreasing function of its hunger and firing a state of maximal score each time. For these monotone-score hunger games, we prove that every periodic orbit still has least period T and give a sufficient condition for eventual periodicity from every initial state.
ER -