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

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 gives
Substituting yields , so
This 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.
Figure 1.
The maze reduced to level exits has upward probability one quarter and downward probability three quarters
. Details.

New to topics? Read the docs here!