I am really stuck on the following question:
So first I need to work out the transition matrix. But I am not sure how? Lets say I am at square 0 and I want to square 1, is the probability of moving to that square .5 since the coin is fair. I tried to work out the matrix:
The numbers in red are just to help with the indexes. Is this matrix correct?
I am stuck on how work out that that I will finish in 4 turns given that I am on square 3? I was thinking of using the nth probability state vector, let n be the turn number, so I would need to find $\pi^{\{4\}}$ but wont this be very tedious since our matrix is 10x10... And I don't know how to condition on the fact we are on square 3.
Edit: I was looking over my book again and re-read n-stage transition probabilities. So I guess I need to use this $$ P^{(n)}_{ij} = P(X_n = j | X_0 = i)$$
So I need to work out $$ P^{(4)}_{39} = P(X_4 = 9 | X_0 = 3)$$ $$= \sum_{i=3}^{9} p_{3i}p_{i9}$$ but working this summation out gives 0. What have I done wrong?
Here's a good reference for exactly your problem: http://www.sosmath.com/matrix/markov/markov.html
Since landing on 4 or 8 moves the player immediately (i.e. without requiring another turn, Your transition matrix $P$ should actually be the black numbers below: $$ \begin{matrix} & \color{red}0& \color{red}1& \color{red}2& \color{red}3& \color{red}5& \color{red}6& \color{red}7& \color{red}9\\ \color{red}0&0 & .5 & .5 & 0 & 0 &0&0&0\\ \color{red}1&0&0&.5&.5&0&0&0&0 \\ \color{red}2&0&0&0&.5&0&0&.5&0\\ \color{red}3&0&0&0&0&.5&0&.5&0\\ \color{red}5&0&0&0&0&0&.5&.5&0\\ \color{red}6&0&0&.5&0&0&0&.5&0\\ \color{red}7&0&0&.5&0&0&0&0&.5\\ \color{red}9&0&0&0&0&0&0&0&1 \end{matrix} $$
Spaces 4 and 8 are removed since it's impossible to move to and stay on them in the same turn. Then the initial state of the player on space 3 is defined as $X$: $$ \begin{bmatrix} 0&0&0&1&0&0&0&0 \end{bmatrix} $$
The formula $XP^n$ yields the probabilities of the player being at each state after $n$ moves. In your case, starting at space 3 and tossing the coin 4 times: $$ \begin{bmatrix} 0&0&{1\over 8}&{1\over 8}& {1 \over 16}& 0&{3 \over 16}& {1 \over 2} \end{bmatrix} $$
The probability of you reaching space 9 within 4 turns is ${1 \over 2}$.