# Probability of a game

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?

• You need one more number in your state description. It needs to be $(a,b,c)$ where $a$ is the person with the book and the range that have touched the book are $b$ to $c$. I don't have anything better – Ross Millikan Oct 9 at 19:00
• Does person $1$'s having the book to begin with count as "touching" the book, so that the game can never end at person $1$? Or perhaps you mean "receiving" the book rather than "touching" it. – saulspatz Oct 9 at 19:10

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.