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

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 (X_n)_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 (X_n) 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 = {v₁, …, v_n }, then C ∈ Rif and only if C is fixed by the composition E_v1 ◦ · · · ◦ E_vn; this property eventually yields the irreducibility of (X_n).