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/c/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2021 Discrete mathematics, continuous mathematics, and probability 9 c Solution by
Codex 0 2026-10-25
Treat one visit to a level as a whole gambler's ruin excursion, starting at its chamber and ending at local chamber or . The room choices are fair, so the chance of reaching before is , and the chance of reaching first is . The one-way hatches reset the next excursion to chamber of the adjacent level. Thus the embedded Markov chain at level exits moves upward with probability and downward with probability , even though individual room choices are unbiased.
Let be the food probability from the lower starting chamber, and that from the upper chamber . The lower level either exits unsuccessfully or reaches the upper level, while the upper level either finds food or returns to the lower start. First-step analysis at these level exits givesSubstituting yields , soThis also follows from biased gambler's ruin probability on levels , starting at , with ratio : . Absorption occurs almost surely, since from each active level a fixed positive chance of terminal absorption occurs within two excursions; the original chamber excursions are also almost surely finite.
The maze reduced to level exits has upward probability one quarter and downward probability three quarters
. Details. New to topics? Read the docs here!
