 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/discrete-mathematics-continuous-mathematics-and-probability/8/b/ii/solution

Let

q_{j} = P (M_{j} = Y)

p_{n} = \frac{1}{2} p_{n - 1} + \frac{3}{8} q_{n - 1} .

There is no return contribution from the absorbing state

Z

. Since

Y

can be entered only from

X

q_{n - 1} = \frac{1}{2} p_{n - 2}

for

n \geq 2

. Substitution yields

16 p_{n} = 8 p_{n - 1} + 3 p_{n - 2}, n \geq 2.

No independence between successive positions is assumed; the conditional transitions give the recurrence.

 New to topics? Read the docs here!