top of page

Mixing Behavior of Uniformly Weighted and Gamma-Weighted Random Walks on Erdős–Rényi Graphs

Aksh Agarwal
21/11/26

The study of Markov chains occupies a central position in probability theory, and the design of randomized algorithms. A Markov chain is a stochastic process defined by the property that the future state of the system depends only on its present state, known as memorylessness. As a chain continues to move, the fraction of time spent in each state of the chain begins to stabilize, to what is known as the “Steady State Distribution”.

This paper compares the convergence of random walks with uniform-weighted and Gamma-normalized outgoing weights on matched directed Erdős–Rényi graphs. The paper analyzes 11 graphs from 50 to 100 states with uniform teleportation probability of τ = 0.001, ensuring unique stationary distributions. For each chain, 100 Monte Carlo trials with 25 million walkers were used to estimate convergence time from uniform initial distribution with a total-variation tolerance of ε = 0.01, along with the worst-case mixing from every starting state. Uniform-start convergences took anywhere from 10-136 steps, while worst-case mixing was found to occur between 4,297-4592 steps. The uniform-start simulation estimates were within a single step of their exact references. Little consistent ordering was found between weighting schemes for uniform-start convergence across tested topologies.

bottom of page