Probability of a game

Question

Suppose there are 10 people sit in a circle, start from player 1, there is a book, at each time, the book can pass to the left neighboring player, or pass to the right neighboring player, with equal probability $0.5$. The game stops once all player have touched this book. Compute the probability that the book is locate at player 7 when the game stop.

I try to use Markov chain to compute the probability, we let $(a,b)$ denote the state of the game, for example, $(2,-1)$ means the book is currently at player 2, and players 1,2, and player -1(in our case with 10 people, the 10th player) all toched this book. Then I try to write down a recursion relation equation, this approach is very messy, and I want to ask whether you guys can have a better method?

Answer 1

A tool that makes this problem much easier is the following lemma. Consider a symmetric random walk on the $n$-edge path with vertices $v_0, v_1, \dots, v_n$. Then, starting from vertex $1$, the probability of reaching vertex $v_n$ before reaching vertex $v_0$ is $\frac 1n$.

More generally, the probability is $\frac kn$ when starting from vertex $v_k$. We can prove this by verifying that $p_k = \frac kn$ satisfies the equations $$ p_0 = 0,\quad p_n = 1,\quad p_k = \frac12(p_{k-1} + p_{k-1}) \text{ for } 1 \le k \le n-1. $$

---

Assuming this lemma, let's play the game until one of players $6$ or $8$ receives the book. The two cases are symmetric; assume it's player $6$, but the exact same argument will work for the other case. Then we know that

• From here on out, if we see player $8$ before we see player $7$, we know player $7$ will be last: if we've seen both of $7$'s neighbors, we've seen everyone else.
• If we see player $7$ before we see player $8$, we know player $7$ won't be last.

So the probability that player $7$ is last is the probability that we see player $8$ before player $7$, which is the probability of seeing the end of the path $$7 - 6 - 5 - 4 - 3 - 2 - 1 - 10 - 9 - 8$$ before seeing the start, beginning from vertex $6$. That probability is $\frac19$.

So player $7$ has a $\frac19$ probability of being the last player.

In general, the same is true for any player, except possibly for players $10, 1, 2$ depending on how you want to handle the starting player. If player $1$ counts as having touched the book, then player $1$ has a $0$ chance of being last and the other players all have a $\frac19$ chance. If player $1$ doesn't count as having touched the book, then players $10$ and $2$ have a $\frac1{18}$ chance and the other players (including $1$) have a $\frac19$ chance.