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 / v / Solution

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.