Consider a sequence of 4 vaults labelled as E = {1, 2, 3, 4}. In vault 1 there is a policeman and in vault 4 there is a treasure chest. Vaults 2 and 3 are empty. Suppose there is a thief walking through the vaults and you can model the location of the thief, i.e. the corresponding vault number, at each point in time by a homogeneous Markov chain denoted by $(X_n)_{n∈{0,1,2,... }}$. If the thief is in vault 1 (together with the policeman), he will run out of vault 1 to vault 2 with probability one. If the thief is in vault 4 (with the treasure), he will stay there forever. If the thief is in vault 2 or 3, he will either go left with probability 1/2 or he will go right with probability 1/2. Moreover, assume that the thief is not very clever, so he might return to vault 1 (with the policeman) several times. Also, suppose the policeman never manages to catch the thief and jail him (even if they are in the same vault).
Q) Suppose the thief starts his journey in vault 1. What is the expected number of moves required until the thief reaches the treasure chest? Justify your answer carefully.
I tried to solve this using the first hitting probability from vault 1 to 4:
$f_{14}(n)$ denotes the first hitting probability in n steps. $P_{ij}(n)$ denotes the probability of going from state i to j in n steps $f_{14}(n) = P_{13}(n-1)*1/2$ since we have to go from state 3 $P_{13}(n-1) = P_{12}(n-2)*1/2$ since we must have come from state 2
Then I attempted to find $P_{12}(n)$ which I said was equal to $(\frac{3}{4})^{(n-1)/2}$ since $P_{12}(n) = P_{12}(n-2) * 3/4$. (this may be a point of error but I believe this is correct).
Then $f_{14}(n) = \frac{1}{4} * (\frac{3}{4})^{(n-3)/2}$
To find the expected time I used $d/ds(\sum(f_{14}s^n))$ and set s = 1 after differentiating. I do not however get the correct answer and I'm not sure if this is an error in the method or a calculation error. If it is an error in the method what is wrong?
Because this is an absorbing Markov chain, we can write the transition matrix $$ P = \left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 0 & 1 \\ \end{array} \right) = \begin{pmatrix}T &\mathbf T^0\\\mathbf 0^\intercal&1\end{pmatrix}, $$ where $T$ coresponds to transitions between transient states and $\mathbf T^0 + T\mathbf 1=\mathbf 1$. Here the initial distribution is $\mathbf \tau=(1,0,0)$, and so for $k=1,2,\ldots$ the probability that it takes the thief $k$ moves to reach the chest is given by $$ f(k) = \mathbf \tau T^{k-1}\mathbf T^0 = \begin{cases} \frac{3^{\frac {k-1}2-1}}{2^k},& k=3,5,7,9,\ldots\\ 0,& \text{otherwise} \end{cases} $$ (with $T^0$ defined as the identity matrix). The expected number of steps to reach the vault is thus $$ \sum_k k\cdot f(k) = \sum _{k=3}^{\infty } k\cdot \frac{3^{\frac {k-1}2-1}}{2^k} \left((-1)^k-1\right) = 9. $$