1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Ross Millikan Oct 9 at 19:00
  • $\begingroup$ 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. $\endgroup$ – saulspatz Oct 9 at 19:10
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.