C&SA | Contents

Volume 62 >>> № 5 SEPTEMBER — OCTOBER 2026

-->

UDC 519.21

A.O. Misnik
National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute,”
Kyiv, Ukraine, alimis2402@gmail.com

I.I. Nishchenko
National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute,”
Kyiv, Ukraine, nishchenkoii-ipt@lll.kpi.ua

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.

full text

REFERENCES

Diaconis P. The cutoff phenomenon in finite Markov chains. Proceedings of the National Academy of Sciences of the USA 93. 1996. Р. 1659–1664.
Ben-Hamou A., Peres Y. Cutoff for a stratified random walk on the hypercube. Electronic Communications in probability. 2018. Vol. 23. P. 1–10. https://doi.org/10.1214/18-ECP132.
Flajolet P., Dumas P., Puyhaubert V. Some exactly solvable models of urn process theory. Discrete mathematics and Theoretical Cumputer Science. 2006, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities. https://doi.org/10.46298/dmtcs.3506.
Baum I.E., Billingsly P. Asymptotic distributions for the coupon collector’s problem. Ann. Math. Statist. 1965. Vol. 36. P. 1835–839.

UDC 519.21

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

REFERENCES

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