Cookies on this website

We use cookies to ensure that we give you the best experience on our website. If you click 'Accept all cookies' we'll assume that you are happy to receive all cookies and you won't see this message again. If you click 'Reject all non-essential cookies' only necessary cookies providing core functionality such as security, network management, and accessibility will be enabled. Click 'Find out more' for information on how to change your cookie settings.

<jats:p>Two urns initially contain <jats:italic>r</jats:italic> red balls and <jats:italic>n – r</jats:italic> black balls respectively. At each time epoch a ball is chosen randomly from each urn and the balls are switched. Effectively the same process arises in many other contexts, notably for a symmetric exclusion process and random walk on the Johnson graph. If <jats:italic>Y</jats:italic>(·) counts the number of black balls in the first urn then we give a direct asymptotic analysis of its transition probabilities to show that (when run at rate (<jats:italic>n – r</jats:italic>)/<jats:italic>n</jats:italic> in continuous time) for <jats:inline-graphic xmlns:xlink="" mime-subtype="gif" xlink:type="simple" xlink:href="S0001867800026513_inline1" /> as <jats:italic>n</jats:italic> →∞, where <jats:italic>π <jats:sub>n</jats:sub></jats:italic> denotes the equilibrium distribution of <jats:italic>Y</jats:italic>(·) and <jats:italic>γ <jats:sub>α</jats:sub></jats:italic> = 1 – <jats:italic>α</jats:italic> /<jats:italic>β</jats:italic> (1 – <jats:italic>β</jats:italic>). Thus for large <jats:italic>n</jats:italic> the transient probabilities approach their equilibrium values at time log <jats:italic>n</jats:italic> + log|<jats:italic>γ <jats:sub>α</jats:sub></jats:italic> | (≦log <jats:italic>n</jats:italic>) in a particularly sharp manner. The same is true of the separation distance between the transient distribution and the equilibrium distribution. This is an explicit analysis of the so-called cut-off phenomenon associated with a wide variety of Markov chains.</jats:p>

Original publication




Journal article


Advances in Applied Probability


Cambridge University Press (CUP)

Publication Date





715 - 727