Paper 4, Section I, H

Markov Chains | Part IB, 2016

Consider two boxes, labelled A\mathrm{A} and B. Initially, there are no balls in box A\mathrm{A} and kk balls in box B. Each minute later, one of the kk balls is chosen uniformly at random and is moved to the opposite box. Let XnX_{n} denote the number of balls in box A at time nn, so that X0=0X_{0}=0.

(a) Find the transition probabilities of the Markov chain (Xn)n0\left(X_{n}\right)_{n \geqslant 0} and show that it is reversible in equilibrium.

(b) Find E(T)\mathbb{E}(T), where T=inf{n1:Xn=0}T=\inf \left\{n \geqslant 1: X_{n}=0\right\} is the next time that all kk balls are again in box BB.

Typos? Please submit corrections to this page on GitHub.