| course |
course_year |
question_number |
tags |
title |
year |
Markov Chains |
IB |
45 |
|
Paper 2, Section II, H |
2019 |
Fix $n \geqslant 1$ and let $G$ be the graph consisting of a copy of ${0, \ldots, n}$ joining vertices $A$ and $B$, a copy of ${0, \ldots, n}$ joining vertices $B$ and $C$, and a copy of ${0, \ldots, n}$ joining vertices $B$ and $D$. Let $E$ be the vertex adjacent to $B$ on the segment from $B$ to $C$. Shown below is an illustration of $G$ in the case $n=5$. The vertices are solid squares and edges are indicated by straight lines.
Let $\left(X_{k}\right)$ be a simple random walk on $G$. In other words, in each time step, $X$ moves to one of its neighbours with equal probability. Assume that $X_{0}=A$.
(a) Compute the expected amount of time for $X$ to hit $B$.
(b) Compute the expected amount of time for $X$ to hit $E$. [Hint: first show that the expected amount of time $x$ for $X$ to go from $B$ to $E$ satisfies $x=\frac{1}{3}+\frac{2}{3}(L+x)$ where $L$ is the expected return time of $X$ to $B$ when starting from $B$.]
(c) Compute the expected amount of time for $X$ to hit $C$. [Hint: for each $i$, let $v_{i}$ be the vertex which is $i$ places to the right of $B$ on the segment from $B$ to $C$. Derive an equation for the expected amount of time $x_{i}$ for $X$ to go from $v_{i}$ to $v_{i+1}$.]
Justify all of your answers.
