A chip-firing variation and a Markov chain with uniform stationary distribution

Dave Perkins, P. Mark Kayll

Research output: Contribution to journalArticlepeer-review

Abstract

We continue our study of burn-off chip-firing games on graphs initiated in [Discrete Math. Theor. Comput. Sci. 15 (2013), no. 1, 121–132]. Here we introduce randomness by choosing each successive seed uniformly from among all possible nodes. The resulting stochastic process—a Markov chain (Xn)n≥0 with state space the set R of relaxed legal chip configurations C: V → N on a connected graph G = (V, E) —has the property that, with high probability, each state appears equiproportionally in a long sequence of burn-off games. This follows from our main result that (Xn) has a doubly stochastic transition matrix. As tools supporting our main proofs, we establish several properties of the chip addition operator E(·) (·): V ×R → R that may be of independent interest. For example, if V = {v1, …, vn }, then C ∈ Rif and only if C is fixed by the composition Ev1 ◦ · · · ◦ Evn; this property eventually yields the irreducibility of (Xn).

Original languageEnglish
Pages (from-to)330-345
Number of pages16
JournalAustralasian Journal of Combinatorics
Volume68
Issue number3
StatePublished - 2017

Fingerprint

Dive into the research topics of 'A chip-firing variation and a Markov chain with uniform stationary distribution'. Together they form a unique fingerprint.

Cite this