Who buys coffee?

[bonanova]

You're having coffee with friends sitting around a table on a work break. You paid for everyone's coffee the last time, and so you propose a method for randomly assigning that task to another person this time. Your proposal involves flipping a fair coin until a particular event happens. Here are the details:

You flip first. If it's heads, you pass the coin to your left; tails, you pass the coin to your right.

The person receiving the coin flips it and passes it left or right according to the same algorithm.

And so on.

As the process continues, more and more of the persons will receive the coin.

At some point, there will be just one person who has not received the coin.

That person must pay the bill.

Is this a fair method?

[BMAD]

Depending on what you mean by fair. If I start with the coin, I would love this idea. But if I were to be sitting equal spaced (the same amount of people either way from the start of the coin, I would scream foul as the probability of streaming enough heads or tails to get to me is unlikely or less likely depending on how many people there are. Because if there are two people then it won't matter.

[DeGe]

Looks like it is fair. The important point is not whether someone get the coin on first few throws but that they should not be the last one to get it. In such a case, the "endgame" would be symmetrical for any number of persons and for any position around the table.

Meaning that, after the first toss of coin for example, the situation is the same as in the beginning except that one person is sure to get a free coffee. Effectively, it is the same situation but with one person less. And the positions of some persons will have improved while that of others worsened.

In the end, there would be any two random persons left who would both have equal probability of getting the coin first (because the coin can be closer to either one of them).

[Anza Power]

contrary to the intuition that the person sitting on the opposite side would have the highest chance of losing, remember in order for him to lose everyone else should hold the coin including the two people directly beside him, so when the first of these two gets the coin that person will have a 50% chance for not losing.

Same goes for every other position, you may lose but at some point you had 50% chance when the first of the two people beside you got the coin...

Edited July 16, 2013 by Anza Power

[Anza Power]

Got it...

It's kinda but not completely fair, if there were k people on the table, then everyone has a probability of

to lose, except the two people beside you who each have probability each.

Ok assume you're not the game starter but someone on the table, in order for you to lose the coin must pass over all the other players but not you, particularly it must reach the person on your left then go all the way around and reach the person on your right (or the opposite) the game will keep going until it reaches one of the two people beside you (let's say it reaches the one on your left first) my claim is that all the events up until that moment don't matter, why? take a look at this picture:

Does it matter (for you) if you were in situation A or B? no, you'd win if the coin comes to you and you'd lose if the coin goes around you and reaches the person on your right, it does not matter what happens to the people in the middle since the coin gets passed around in a continuous way it will pass over everyone if it reaches the person to your right.

So that shows if you were somewhere on the table the probability of you losing is independent of your location, let's call that p_k.

This is true for everyone except the two people directly to the left and right of the person who starts the game, what is the probability of one of them losing? well at the start of the game he has 0.5 chance of getting the first coin, and 0.5 chance of not getting it in which case his chance of losing is p_k, so for the two people next to the game starter the probability of losing is 0.5*p_k.

Since exactly one person has to lose the probabilities must sum up to one, so you'll find that:

(k-2)*p_k + 0.5*p_k + 0.5*p_k = 1.

And from that you'll get 0.5*p_k = 1/(k-1)

[bonanova]

Someone has the right answer, and someone is close.

To decide, and get a clearer view of the processes,

conside a simpler case.

The case of three people (two others) is trivial.

Four people is rich enough to be instructive, and still tractable by hand.

It's an interesting result.

[DeGe]

Four people is rich enough to be instructive, and still tractable by hand.

In case of 4 people, the immediate neighbours of the starter each have a starting probability of 1/2 of not being the last.

For the one opposite, it does not matter whether the first toss is heads or tails. After the first toss, he also has a probability of 1/2 of not being the last. So his effective starting probability is also 1x1/2 = 1/2

All have equal probability of getting the coin before the last person.

[Anza Power]

Someone has the right answer, and someone is close.

To decide, and get a clearer view of the processes,

conside a simpler case.

The case of three people (two others) is trivial.

Four people is rich enough to be instructive, and still tractable by hand.

It's an interesting result.

The cases of 3 and 4 both match my answer above, in case of four people you and the person right in front of you have 1/3 chance each and the two others who are beside you have 1/6 chance each...

Edited July 17, 2013 by Anza Power

[bonanova]

Someone has the right answer, and someone is close.

To decide, and get a clearer view of the processes,

conside a simpler case.

The case of three people (two others) is trivial.

Four people is rich enough to be instructive, and still tractable by hand.

It's an interesting result.

The cases of 3 and 4 both match my answer above, in case of four people you and the person right in front of you have 1/3 chance each and the two others who are beside you have 1/6 chance each...

I didn't read your answer carefully enough to see that you included the initial flipper.

So that degrades the chances of the adjacent persons.

Do you get the expected result now if you exclude him?

The process is supposed to find "another" person. I.e. a person other than the initial flipper.

The one who buys is the one who never touches the coin.

1212(34) means the coin passed from 1 to 2 to 1 to 2, so that 3 and 4 are the remaining candidates:

[bonanova]

Let M be a candidate (not yourself) and let L and R sit to his left and right, respectively.

M is selected one of two ways:

1. The coin travels to L (but not M or R) then back around to R. (but not M)
2. The coin travels to R (but not M or L) then back around to L. (but not M)

Let p be the probability the coin travels from R to L (but not M). By symmetry,

1. p = p(L->R) = p(R->L)
2. P does not depend on M.

Here is the fun part. Let

1. q = probability the coin reaches L (before R or M)
2. r = probability the coin reaches R (before L or M)

We don't know q and we don't know r, but we can determine their sum.

Consider:

1. The coin does not start at M
2. M is sandwiched between L and R
3. visiting R (before L or M) means visiting R before L
4. visiting L (before R or M) means visiting L before R
5. Either 3 or 4 is certain to happen

Thus, q + r = p(R before L) + p(L before R) = 1.

Finally, the probability that M is selected is p x (q+r) = p, independent of M.

Since there are (n-1) candidates, p(M) = p = 1/(n-1) for all M.

[BMAD]

darn intuition

[bonanova]

Honorable Mention:

Anza Power had the right analysis for inclusion of the original person.