I try to solve some exercises from olympiads and I have difficulties with this one:
Consider a round table with 20 people. One of these players receive a book and chooses one of his neighbors and passes the book to him (with probability 1/2). The next player again chooses one of his neighbors (each with prob 1/2) and passes the book. The game ends until at least everyone received the book one time.
Every person has of course a probability for being the last one getting the book. Which player of the group has the highest prob. reiceiving the book as the last player?
Intuitively I would say the player which sits opposite to the player that receives the book first (Lets call him Player 1 and the opposite player is Player 11).
I first tried to analyze the situation for 4 players. Assume at the bottom is Player 1, right to him Player 2, opposite of Player 1 is Player 3 and left to Player 1 is Player 4.
I assume Player 1 receives the book first:
=> Player 2 as the last one: 1->4->3->2 Player 3 as the last one: 1->4->1->2->3 or 1->2->1->4->3 Player 4as the last one: 1->2->3->4
Therefore I would say Player 3 has the prob. which attains the maximum over the group. This is exactly the opposite player of Player 1.
How can I use my argument for the case of 4 Players to prove it for 20 Players?
You may want to calculate the probability of expanding the current "territory" (set of people that have held the book) in either the forward or backward direction, as a function of the size of the territory.
When the territory has size $1$, forward and backward both have probability $1/2$. When the territory has size $2$, forward has probability $1/2+1/8+\ldots=2/3$ and backward has probability $1/3$. So expanding as $123$ or $143$ (leaving $4$ or $2$ as the last to hold the book, respectively) have probability $1/2\cdot 2/3=1/3$, while expanding as $124$ or $142$ (leaving $3$ as the last to hold the book) have probability $1/6$ each, for total probability $1/3$.
In other words, in the $n=4$ case, all players but player $1$ are, in fact, equally likely to hold the book last.