probability puzzle - selecting a person

there are n people on a round table. one of the them is the head and he plans to make another person from the rest the new head. he has a coin. he flips the coin. if he gets a head he gives the coin to the person to his left and if he gets a tail he gives the coin to the person to his right. anyone who receives the coin can no longer become the head. the person who receives the coin repeats the similar procedure. when there is only one person remaining who has not received the coin, he becomes the head. what is the probability of each of the n-1 people becoming a head.

for n = 3, 4 we get a uniform probability distribution. how to solve it for higher n?

i have struggled with this for some time but could not solve yet.

it seems you are having a tough time solving this! i could not find the solution on google.

Update:

approach that i was using:

  let ai be the probability of that the ith person is not selected.
summation i:1 to n (1-ai) = 1;
a1 = 0;
we need another equation to use the fact that the probability of getting a head on a
coin flip is 1/2.
tried Bayes etc. could not get it.

try induction

anything else you might like

-
I don't know if this question is proper here. I think you might want to look at random walk. See en.wikipedia.org/wiki/Random_walk – abcdxyz Jan 16 '10 at 14:16
friends at stackoverflow told me it is not programming related. it is mathematics related. right? – Rohit Banga Jan 16 '10 at 14:46
BTW, saying "it seems you are having a hard time solving this" is being a bit presumptuous, unless you have some way of knowing how many people are actually trying to answer your question – Yemon Choi Jan 16 '10 at 15:34
That looks like part of a conversation with someone else which was accidentally left in. – Douglas Zare Jan 16 '10 at 17:29
This is an example of a result I put in the category of "hidden independence and uniformity." For more such problems, see math.mit.edu/~rstan/s34/indep.pdf. – Richard Stanley Apr 10 '10 at 0:30

The probability distribution is uniform. Each person P has two neighbors, R and L. One is eliminated before the other, say R. Then the probability P is selected is the conditional probability that L is eliminated before P, with the coin starting at R. By symmetry, this is the same for each person.

-
not very clear. how is it the same for each person. – Rohit Banga Jan 16 '10 at 14:47
For each person P, it's the same random walk problem: One neighbor is eliminated. Will the coin go around the table to the other neighbor before getting to P? If so, P is selected. If not, P is eliminated. It's also a standard exercise that the probability is 1/(n-1) as discussed <a href="mathoverflow.net/questions/7004/…;. – Douglas Zare Jan 16 '10 at 14:54
In fact, this is clearly not right for n=4: heads-heads selects person 0, and tails-tails person 2, but person 1 is selected for either heads-tails or tails-heads. Thus, the probability is not uniform. – Neil Apr 13 '10 at 22:13
@Neil If there are 4 people at the table, then when the coin is passed left and then right, the second pass does not eliminate a person. The coin is back in the original position, and there are two people who have not received the coin. The player to the right of the head has probability 1/3 of being the last not to hold the coin, and the player opposite the head now has a 2/3 chance to be the last. At the start, the probability distribution is uniform over all people except the head. – Douglas Zare Apr 13 '10 at 22:48
Oh, I assumed that people get up from the table when they can no longer be head of the table... Sorry. – Neil Apr 14 '10 at 0:23

The following argument is from A note on the last new vertex visited by a random walk, L. Lovasz, P. Winkler, Journal of Graph Theory, Vol. 17, No. 5, 1993.

Each person P has two neighbors R and L. Let $p$ be the probability that starting from node R you visit P last. By symmetry, $p$ is also the probability that starting from node L you visit P last. Also by symmetry, $p$ does not depend on the starting person $P$ - it only depends on $n$.

Claim: If your starting person is not P, then $p$ is the probability that P is visited last.

Proof: You will get to R or L before P with probability 1. The probability that $P$ is then visited last is $p$.

This proves that the probability of P being last does not depend on the person P, so it must be $1/(n-1)$.

-

It's uniform for all n. First consider the person on the immediate right of the head. The probability he gets it last can be calculated using random walk theory as 1/(n-1). The same argument works for the person on the immediate left of the head.

Now consider someone in an arbitrary position (not next to the head) He can't receive the coin before both the person on his right and before the person on his left. call him k , the person on his left k-1 and the person on his right k+1. Then P[k is last]= P[K+1 before k-1 before k]+P[k-1 before k+1 before k] =P[k+1 before k-1]/(n-1)+P[k-1 before k+1]/(n-1) this is because once k-1 or K+1 gets it were in the position on the person immediately to the right on the head.

=1/(n-1)

-

This is to answer a question raised by unknown: in the asymmetric case where the coin moves clockwise with probability $p$ and counterclockwise with probability $1-p$, the new head is located $k$ seats away from the former head, counting seats clockwise, with probability $r^k(r-1)/(r^n-r)$, for every $1\le k\le n-1$, where $r=(1-p)/p$. (When $p\to1/2$, $r\to1$ and the limit is indeed uniform, that is, equal to $1/(n-1)$ for every $k$.)

-

I have written an article about this game, and solved it numerically for the case of 10 person. I computed that the probability is the same for each of the 9 person.

In short, I have defined the following:

Let P(n,i,j,k) be the probability of at the n-th round, the k person is having the coin, while the people from i counting clockwise to k have all received the coin before.

And 3 recurrence equations are formulated:

$P (n+1,i,j,k)= \frac{1}{2} P (n,i,j,k-1)+ \frac{1}{2} P (n,i,j,k+1)$ ........(1)

$P (n+1,i,j,j)=\frac{1}{2} P (n,i,j-1,j-1)+ \frac{1}{2} P(n,i,j,j-1)$ ........(2)

....(3)