Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Discrete mathematics, probability and continuous mathematics / 7 / b

The first exchange removes one red ball from urn 1 and replaces it with a blue ball. Hence $R_1=n-1$ with probability one.

At state $r$, urn 1 has $r$ red and $n-r$ blue balls, while urn 2 has $n-r$ red and $r$ blue balls. Conditional on the state, the two choices are independent, each assigning probability $1/n$ to every ball. A red–blue exchange decreases $r$; a blue–red exchange increases it; equal colours leave it unchanged. Thus the conditional probability mass function isThe three numerators sum to $n^2$. At $r=0$ or $n$, the outward transition has probability zero. These are the transitions of the Bernoulli-Laplace diffusion model. The displayed formula is a transition kernel on every state; a literal conditional probability at a particular time requires the conditioning event to have positive probability.

Compute the conditional expectation from the possible increments:Therefore $\alpha =1$ and $\beta =1-2/n$. This calculation uses the conditional independence of the two selections, not independence of the successive counts $R_k$.

Apply the law of total expectation to the bounded random variable $R_{k+1}$. Linearity of expectation givesThis also holds for the first step from $r_0=n$.

Put $\beta =1-2/n$. The fixed point of this affine recurrence is $n/2$. Subtracting it gives $r_{k+1}-n/2=\beta (r_k-n/2)$. Repeated substitution, or mathematical induction, therefore yieldsFor $n>2$ this expression applies to every $k\ge 0$. For $n=2$, state the initial value $r_0=2$ separately and obtain $r_k=1$ for every $k\ge 1$, avoiding any need to interpret $0^0$. The expected red imbalance decays towards zero, although the urn composition itself remains random.