Chip-Firing Analysis of Stabilization Behaviors, Hitting Times, and Candy-Passing Games
By Paul Kominers
Math can be an intimidating field. To work on some problems, one must know decades or centuries of background before one can even understand the question. However, what tends to get lost in all of that is that math can be fun, even for the relatively uninitiated. There are problems in mathematics that are discrete (essentially, self-contained) and with some combination of background research, mathematical thought, and appropriate mentoring, they are easily within reach of the high school student. Generally, random walks on graphs are approximated by computing the expected hitting time, or probable number of random moves required to go from one vertex to another. Although random walks are useful in mathematics and computer science, probabilistic systems do not offer sufficient precision for some applications. There are, however, several emerging methods of deterministically simulating random walks which can be used to more efficiently compute hitting times [4, 6]. One such deterministic simulation uses a process known as chip-firing. Read More