 Solution

ID: 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

β = 1 - 2/ n

n /2

. Subtracting it gives

r_{k + 1} - n /2 = β (r_{k} - n /2)

. Repeated substitution, or mathematical induction, therefore yields

r_{k} = \frac{n}{2} + \frac{n}{2} (1 - \frac{2}{n})^{k} .

For

n > 2

this expression applies to every

k \geq 0

. For

n = 2

, state the initial value

r_{0} = 2

separately and obtain

r_{k} = 1

for every

k \geq 1

, avoiding any need to interpret

0^{0}

. The expected red imbalance decays towards zero, although the urn composition itself remains random.

 New to topics? Read the docs here!