This page is being updated…

An Implementation of  a Maximal Coupling Algorithm for Markov Chains

Alan Boles (U Tennessee, Knoxville), Leila Dahlia (UIC), Scott McIntyre (UCB), Bronson Zhou (U Texas, Austin)

Sampling Minimal Quasistationary Distributions through a Renewal Formula

Gabe Cantanelli (U Texas, Arlington), Elza Moore (Scripps College)

Coalescing Random Walks

Bram Silbert (Wesleyan U), Lillian (Ian) Makhoul (Lehigh University)

We studied a particle system on the N-cycle under the following process:

• At time t = 0, all vertices on the cycle are occupied by a particle
• At each time step, one particle is sampled uniformly and moved one vertex in the clockwise direction
• If the new vertex is occupied, the particle absorbs the previous occupant
• Repeat until only one particle remains

The central questions we sought to answer were: what can we say about the time before all particles coalesce, and what can we say about the number of steps taken by the last surviving particle? Regarding the first question, we were able to prove an exact formula for the expected time to coalescence as a function of N. For the second, we were able to find a moment generating function for the steps of the last surviving particle, making it easy to produce formulas for the expectation, second moment, and variance.

We also looked at a similar model on the N-cycle wherein any collision between two particles results in the annihilation of both. This means that for even N, the process concludes when no particles remain, while for odd N the process will leave a single particle alive. We were able to completely describe the even case, getting explicit formulas for the expectation, second moment, and variance.

On the applied side the work involved extensive simulation and multilinear regression on the simulation results, while on the theoretical side we worked with optional stopping and Markov chains conditioned to hit one set before another.