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
$\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
    Jan 16, 2010 at 14:16
  • $\begingroup$ friends at stackoverflow told me it is not programming related. it is mathematics related. right? $\endgroup$ 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
    Jan 16, 2010 at 15:34
  • $\begingroup$ That looks like part of a conversation with someone else which was accidentally left in. $\endgroup$ 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$ Apr 10, 2010 at 0:30

5 Answers 5

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.

$\endgroup$
6
  • $\begingroup$ not very clear. how is it the same for each person. $\endgroup$ 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$ 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
    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$ 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
    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)$.

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

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

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

$\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$ 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
    Apr 17, 2010 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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