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/b/iii/solution

Write and . Since , the latter expected value is finite. Conditional on the first move to or , total time is one plus the remaining time, while the terminal success indicator random variable is unchanged. The Markov property and linearity of expectation give
At either absorbing boundary the remaining time is zero, so .
Let . The linear term has zero second difference and has second difference . Consequently
which is exactly the required recurrence, and . Uniqueness follows as before: the difference of two solutions has zero second difference and zero endpoint values. Hence
This is the success-weighted duration underlying the duration of gambler's ruin conditioned on a chosen boundary.

New to topics? Read the docs here!