ASYMPTOTIC DISTRIBUTION OF COALESCENT TIME FOR RANDOM WALKS ON THE HYPERCUBE OF INCREASING DIMENSION

Abstract

In the paper the asymptotic behavior of a pair of random walks on the hypercube is investigated. The joint distribution of the walks is specified by a Markov chain constructed optimally to minimize the mean time to their coalescence. Under various scenarios of the growth of the hypercube’s dimension and the initial distance between the particles, the exact asymptotic distribution of coalescent time has been determined. Keywords: random walks on the hypercube, Markov chain, optimization problem, coalescent time, Ehrenfest model.