If you are looking at past Markov chains tripos questions you might like to know that it has recently come to light that there is a mistake in 2012/3/9H.
The answer asked for, $1/(2k)$, should actually be $1/(2k+1)$.
The transition matrix $P$ is 1/4 of
2 2 0 0 0 0 0 0
1 2 1 0 0 0 0 0
0 1 2 1 0 0 0 0
0 0 1 2 1 0 0 0
0 0 0 1 2 0 0 0
0 0 0 0 1 2 1 0
0 0 0 0 0 1 2 1
0 0 0 0 0 0 1 3
(here illustrated for $k=7$) and so detailed balance gives the invariant distribution as proportional to (1,2,2,2,2,2,2,2).
Unfortunately, the examiner had put 0 0 0 0 0 0 2 2 in the bottom row and so calculated the invariant distribution as proportional to (1,2,2,2,2,2,2,1). But if the runner starts with $k$ shoes at the front door, the probability that she has $k$ shoes there after the next two runs is 3/4, not 1/2.
This question was intended to be similar to Example Sheet 2, #11 (the professor carrying umbrellas between home and office.)