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

Dave Perkins; P. Mark Kayll

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

Dave Perkins
, P. Mark Kayll

Mathematical Sciences

Hamilton College

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

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 (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).

Original language	English
Pages (from-to)	330-345
Number of pages	16
Journal	Australasian Journal of Combinatorics
Volume	68
Issue number	3
State	Published - 2017

Funding

This work was partially supported by a grant from the Simons Foundation (#279367 to Mark Kayll). The manuscript for this article was drafted while the second author was on sabbatical at the University of Otago in Dunedin, New Zealand. The author gratefully acknowledges the support of Otago’s Department of Mathematics and Statistics. Both authors appreciate the care the referees exercised in reading and commenting on the manuscript.

Funders	Funder number
Simons Foundation	279367

Cite this

@article{b973c465f78e46ca8439b1ebdfccbeca,

title = "A chip-firing variation and a Markov chain with uniform stationary distribution",

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).",

author = "Dave Perkins and Kayll, \{P. Mark\}",

year = "2017",

language = "English",

volume = "68",

pages = "330--345",

journal = "Australasian Journal of Combinatorics",

issn = "1034-4942",

publisher = "University of Queensland Press",

number = "3",

}

TY - JOUR

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

AU - Perkins, Dave

AU - Kayll, P. Mark

PY - 2017

Y1 - 2017

N2 - 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).

AB - 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).

UR - https://www.scopus.com/pages/publications/85020120244

M3 - Article

AN - SCOPUS:85020120244

SN - 1034-4942

VL - 68

SP - 330

EP - 345

JO - Australasian Journal of Combinatorics

JF - Australasian Journal of Combinatorics

IS - 3

ER -

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

Abstract

Funding

Other files and links

Fingerprint

Cite this