 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2021/discrete-mathematics-continuous-mathematics-and-probability/9/a/solution

Condition on the fair coin choosing the initial chamber. The law of total probability gives

P (reach k) = (p_{1} + p_{2}) /2

. With

r = (1 - p) / p

P (reach k) = ⎩ ⎨ ⎧ \frac{2 - r - r ^{2}}{2 ( 1 - r ^{k} )}, \frac{3}{2 k}, p \neq = \frac{1}{2}, p = \frac{1}{2} .

Both numerator and denominator in the first case have the same sign. Its limit as

r \to 1

is the fair-walk value, since the ratio of their first derivatives is

3/ (2 k)

. The averaging is over initial locations, not over the transition probabilities.

 New to topics? Read the docs here!