4
$\begingroup$

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
Improve this question
$\endgroup$
6
  • $\begingroup$ 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 $\endgroup$
    – abcdxyz
    Commented Jan 16, 2010 at 14:16
  • $\begingroup$ friends at stackoverflow told me it is not programming related. it is mathematics related. right? $\endgroup$
    – Rohit Banga
    Commented Jan 16, 2010 at 14:46
  • 4
    $\begingroup$ 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 $\endgroup$
    – Yemon Choi
    Commented Jan 16, 2010 at 15:34
  • $\begingroup$ That looks like part of a conversation with someone else which was accidentally left in. $\endgroup$
    – Douglas Zare
    Commented Jan 16, 2010 at 17:29
  • 5
    $\begingroup$ 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. $\endgroup$
    – Richard Stanley
    Commented Apr 10, 2010 at 0:30

5 Answers 5

Reset to default
15
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ not very clear. how is it the same for each person. $\endgroup$
    – Rohit Banga
    Commented Jan 16, 2010 at 14:47
  • $\begingroup$ 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/…>. $\endgroup$
    – Douglas Zare
    Commented Jan 16, 2010 at 14:54
  • 1
    $\begingroup$ 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. $\endgroup$
    – Neil
    Commented Apr 13, 2010 at 22:13
  • 1
    $\begingroup$ @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. $\endgroup$
    – Douglas Zare
    Commented Apr 13, 2010 at 22:48
  • 2
    $\begingroup$ Oh, I assumed that people get up from the table when they can no longer be head of the table... Sorry. $\endgroup$
    – Neil
    Commented Apr 14, 2010 at 0:23
6
$\begingroup$

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)$.

Improve this answer
$\endgroup$
4
$\begingroup$

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)

Improve this answer
$\endgroup$
2
$\begingroup$

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$.)

Improve this answer
$\endgroup$
-1
$\begingroup$

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)

For details, please refer to:

Solving a probability game using recurrence equations and python

In this article, a(n,i) which denotes the probability of the i-th person being the head in the n-th round is found and plotted out as well.

Improve this answer
$\endgroup$
2
  • $\begingroup$ You can make explicit formulas involving a single summation for your a(n,i). The number of walks which stay within an interval can be counted, and you want the walks from the origin to L or R which do stay inside the path excluding i, but which do not stay inside the path excluding i and the other neighbor. See mathoverflow.net/questions/16892/… $\endgroup$
    – Douglas Zare
    Commented Apr 9, 2010 at 18:43
  • $\begingroup$ @Douglas: I read your comment of random walk before giving the answer. I gave this answer, since unknown (google) asked for any approach for this problem. I am just giving a general approach for a complicated probability problem. Sorry that I can't solve the equations analytically. Would you mind giving me some guide in solving these kinds of partial difference equations? I don't know if generating function works in this case, due to the circle index. $\endgroup$
    – Ross Tang
    Commented Apr 17, 2010 at 23:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .