Who gets a free dinner?

[bonanova]

You're out with friends at Chuck's Steak House and decide to flip a coin to select one person get a free dinner. The bill will be split n-1 ways instead of n ways. Since I was not invited, I don't know how many are in the group. (Maybe next time you'll include me; I love Chuck's place.) So anyway, your selection method has to work for an arbitrary numbers of participants.

You have only a fair coin, and the method has to treat everyone equally.

It must be absolutely fair and unbiased.

There might be many ways; bonus points await methods with originality, flair, and minimization of flips.

Pick one person out of n, fairly, with a sequence of fair coin tosses.

[James33]

One way would be to flip the coin once of each person, on a heads that person moves into group 1, on a tails that person moves into group 2. Repeat this for everyone on group 1, with people getting tails moving to group 2. If no-one in group 1 gets a head just ignore that round and go again. Eventually there will only be 1 person in group 1 which is the one who gets a free meal. I'm certain this is equal for everybody although there could be an unlimited number of coin flips.

[Rob_Gandy]

My method is similar to James's. Flip the coin once for each person and assign them heads or tails. All who match the next coin flip (after everyone is assigned) stay in for another round. Continue until one person is left. If everyone is assigned the same thing then reflip and reassign everyone. Or have each person choose heads or tails then flip the coin and everyone who chose what the coin lands on gets to stay. Repeat until finished.

Edited March 22, 2013 by Rob_Gandy

[bonanova]

One way would be to flip the coin once of each person, on a heads that person moves into group 1, on a tails that person moves into group 2. Repeat this for everyone on group 1, with people getting tails moving to group 2. If no-one in group 1 gets a head just ignore that round and go again. Eventually there will only be 1 person in group 1 which is the one who gets a free meal. I'm certain this is equal for everybody although there could be an unlimited number of coin flips.

OK, that works. Any others? What if n was large? Like 100.

[James33]

Thought about it some more I I think I have an algorithm that would do it more efficiantly

Suppose at some stage in this proccess we have k people.

If k is even, split the group in 2, asign each a side of the coin and flip it, discard the incorrect group (how you split into 2 and choose who is heads is irrelivent since the coin toss randomises it whatever the case).

If k is odd remove someone from the group and do the same as above to the remaining even-numbered group, for the additional person flip the coin to determain where they are discarded or not. This is fair on everyone as each individual has a 50/50 chance of being discarded.

Eventually there will only be 1 person remaining.

[James33]

Flip the coin 1+floor(log(base2)(n)) times, record a 1 for each heads and a 0 for each tails to get a binary number, also assign each person a number between 1 and n. The person you choose is the one with the number which is equal to the binary number once it has been converted into decimal.

[bonanova]

Flip the coin 1+floor(log(base2)(n)) times, record a 1 for each heads and a 0 for each tails to get a binary number, also assign each person a number between 1 and n. The person you choose is the one with the number which is equal to the binary number once it has been converted into decimal.

I'll take that.

Very nice.

[bushindo]

Flip the coin 1+floor(log(base2)(n)) times, record a 1 for each heads and a 0 for each tails to get a binary number, also assign each person a number between 1 and n. The person you choose is the one with the number which is equal to the binary number once it has been converted into decimal.

Question

Let's say we have 9 participants. The method above says flip a coin 4 times and then convert the 4 flips into a number from 1-16.

Obviously, chances are about 7/16 that no one gets selected with this methodology. What then? Do we repeat the procedure and flip the coin 4 more times and see whose number gets matched?

[bushindo]

You're out with friends at Chuck's Steak House and decide to flip a coin to select one person get a free dinner. The bill will be split n-1 ways instead of n ways. Since I was not invited, I don't know how many are in the group. (Maybe next time you'll include me; I love Chuck's place.) So anyway, your selection method has to work for an arbitrary numbers of participants.

You have only a fair coin, and the method has to treat everyone equally.

It must be absolutely fair and unbiased.

There might be many ways; bonus points await methods with originality, flair, and minimization of flips.

Pick one person out of n, fairly, with a sequence of fair coin tosses.

I'm trying to go for the minimum expected number of flips here. This is my best attempt so far

If N is a power of 2, the solution is trivial. Let's assume N is not a power of 2. Divide the interval from 0 to 1 into N sub-intervals. Each person will be assigned a sub-interval. So, if there are 3 participant, the first one would be assigned [0, 1/3), the second [1/3, 2/3), and the third [2/3, 1].

Flip the coin and treat the resulting string of outcomes as a fractional binary number. For instance, let head = 1 and tail = 0. If we flip head two times in a row, that is the equivalent of .11 in binary or (1/2 + 1/4 = .75 in decimal). Let the fractional binary number we construct after N flip be B_N. The range of values for the binary number B_infinity after the first N flip is [b_N,B_N + 2^-N].

So, let's say after two flips the binary number is .11 in binary or .75 in decimal. The range of possible binary number, assuming an infinite number of continuing flips, in decimal form is [.75, 1].

The idea is as soon as the possible values [b_N,B_N + 2^-(N) ] is entirely contained within 1 person's subinterval, that person is selected.

Let's calculate the expected number of flips required. For N participants where N is not a power of 2, we would require ceiling( log2( N ) ) flips to narrow the field down to two people. From there it takes an expected number of 2 further flips to further select one of those two. That gives us an upper bound of ceiling( log2( N ) ) + 2 for the expected number of flips.

[Prime]

I want to be a party pooper.

Thought about it some more I I think I have an algorithm that would do it more efficiantly

Suppose at some stage in this proccess we have k people.

If k is even, split the group in 2, asign each a side of the coin and flip it, discard the incorrect group (how you split into 2 and choose who is heads is irrelivent since the coin toss randomises it whatever the case).

If k is odd remove someone from the group and do the same as above to the remaining even-numbered group, for the additional person flip the coin to determain where they are discarded or not. This is fair on everyone as each individual has a 50/50 chance of being discarded.

Eventually there will only be 1 person remaining.

This one is unfair.

Example

Consider decision between 3 participants. For either of the two guys who were paired against each other in the first round the probability of win is winning the first round and the 3rd man not advancing to finals, plus winning the first round and the finals, should the 3rd man advance. Or 1/4 + 1/8 = 3/8.
The man who plays the first round by himself, must always win two rounds, his probability is 1/4.

Flip the coin 1+floor(log(base2)(n)) times, record a 1 for each heads and a 0 for each tails to get a binary number, also assign each person a number between 1 and n. The person you choose is the one with the number which is equal to the binary number once it has been converted into decimal.

Nice. However, as Bushindo has noticed this one may require replay for number of participants other than power of 2. So there is no ceiling on how many coin throws decide the winner.

You're out with friends at Chuck's Steak House and decide to flip a coin to select one person get a free dinner. The bill will be split n-1 ways instead of n ways. Since I was not invited, I don't know how many are in the group. (Maybe next time you'll include me; I love Chuck's place.) So anyway, your selection method has to work for an arbitrary numbers of participants.

You have only a fair coin, and the method has to treat everyone equally.
It must be absolutely fair and unbiased.

There might be many ways; bonus points await methods with originality, flair, and minimization of flips.

Pick one person out of n, fairly, with a sequence of fair coin tosses.

I'm trying to go for the minimum expected number of flips here. This is my best attempt so far

If N is a power of 2, the solution is trivial. Let's assume N is not a power of 2. Divide the interval from 0 to 1 into N sub-intervals. Each person will be assigned a sub-interval. So, if there are 3 participant, the first one would be assigned [0, 1/3), the second [1/3, 2/3), and the third [2/3, 1].

Flip the coin and treat the resulting string of outcomes as a fractional binary number. For instance, let head = 1 and tail = 0. If we flip head two times in a row, that is the equivalent of .11 in binary or (1/2 + 1/4 = .75 in decimal). Let the fractional binary number we construct after N flip be B_N. The range of values for the binary number B_infinity after the first N flip is [b_N,B_N + 2^-N].

So, let's say after two flips the binary number is .11 in binary or .75 in decimal. The range of possible binary number, assuming an infinite number of continuing flips, in decimal form is [.75, 1].

The idea is as soon as the possible values [b_N,B_N + 2^-(N) ] is entirely contained within 1 person's subinterval, that person is selected.

Let's calculate the expected number of flips required. For N participants where N is not a power of 2, we would require ceiling( log2( N ) ) flips to narrow the field down to two people. From there it takes an expected number of 2 further flips to further select one of those two. That gives us an upper bound of ceiling( log2( N ) ) + 2 for the expected number of flips.

Awesome. Same problem though – no ceiling. And it seems fair, but not in an obvious way. A proof of fairness would be nice.

[Prime]

I'd like to enter the following solution and claim the minimum number of throws.

Divide the entire table cloth into n rectangles of equal area with a permanent marker. Each participant must be assigned his rectangle. Then ask the waiter to throw the coin onto the table cloth from afar.

[bushindo]

You're out with friends at Chuck's Steak House and decide to flip a coin to select one person get a free dinner. The bill will be split n-1 ways instead of n ways. Since I was not invited, I don't know how many are in the group. (Maybe next time you'll include me; I love Chuck's place.) So anyway, your selection method has to work for an arbitrary numbers of participants.

You have only a fair coin, and the method has to treat everyone equally.

It must be absolutely fair and unbiased.

There might be many ways; bonus points await methods with originality, flair, and minimization of flips.

Pick one person out of n, fairly, with a sequence of fair coin tosses.

I'm trying to go for the minimum expected number of flips here. This is my best attempt so far

If N is a power of 2, the solution is trivial. Let's assume N is not a power of 2. Divide the interval from 0 to 1 into N sub-intervals. Each person will be assigned a sub-interval. So, if there are 3 participant, the first one would be assigned [0, 1/3), the second [1/3, 2/3), and the third [2/3, 1].

Flip the coin and treat the resulting string of outcomes as a fractional binary number. For instance, let head = 1 and tail = 0. If we flip head two times in a row, that is the equivalent of .11 in binary or (1/2 + 1/4 = .75 in decimal). Let the fractional binary number we construct after N flip be B_N. The range of values for the binary number B_infinity after the first N flip is [b_N,B_N + 2^-N].

So, let's say after two flips the binary number is .11 in binary or .75 in decimal. The range of possible binary number, assuming an infinite number of continuing flips, in decimal form is [.75, 1].

The idea is as soon as the possible values [b_N,B_N + 2^-(N) ] is entirely contained within 1 person's subinterval, that person is selected.

Let's calculate the expected number of flips required. For N participants where N is not a power of 2, we would require ceiling( log2( N ) ) flips to narrow the field down to two people. From there it takes an expected number of 2 further flips to further select one of those two. That gives us an upper bound of ceiling( log2( N ) ) + 2 for the expected number of flips.

Awesome. Same problem though no ceiling. And it seems fair, but not in an obvious way. A proof of fairness would be nice.

I don't think this problem can be decided with a fixed ceiling method. That is, I don't think there exist a method that guarantees a maximum number of fixed maximum flips m(N) for every N. See below for reason + proof of fairness

Let's assume there's a method with a maximum flips m(N) for N participants. There are roughly 2^m(N) possible outcomes. Since that is a power of 2, it doesn't divide nicely when N includes non-2 factors. There are bound to be events when the method can not select someone, and then we are back to square one.

As for the fairness issue, the point of the method is to randomly sample (via binary flip) 1 single point B_infinity from 0 to 1. Given infinite random flips, we are guaranteed that B_infinity falls uniformly and randomly within that interval. Since the method picks a persons as soon as B_infinity, or its interval [b_N, B_N + 2^-n ], falls entirely within a subregion, we are then covered with respect to fairness.

[bushindo]

I'd like to enter the following solution and claim the minimum number of throws.

Divide the entire table cloth into n rectangles of equal area with a permanent marker. Each participant must be assigned his rectangle. Then ask the waiter to throw the coin onto the table cloth from afar.

I see your 1 and I will raise you a 0 =)

Arrange the participants into a circle and tell them to simultaneously throw out their hand with the fists made into either a rock, paper, or scissor. That is, let them play N-person paper-rock-scissor. Keep the participants with the least frequent hand-formation. For instance, if there are 12 people, and 4 has rock, 5 has scissor, and 3 has paper, then we keep the party of 3 that made the paper.

Let the subparty play the modified paper-rock-scissor game again until 1 person remains. If at any point there is a 3-way tie of hand-formation, let them play again. Also, if there are 2 people left at some point, then let them play normal paper-rock-scissor instead of the modified version.

Oh, the coin? Tip it to the waiter.

[Prime]

I don't think this problem can be decided with a fixed ceiling method. That is, I don't think there exist a method that guarantees a maximum number of fixed maximum flips m(N) for every N. See below for reason + proof of fairness

Let's assume there's a method with a maximum flips m(N) for N participants. There are roughly 2^m(N) possible outcomes. Since that is a power of 2, it doesn't divide nicely when N includes non-2 factors. There are bound to be events when the method can not select someone, and then we are back to square one.

As for the fairness issue, the point of the method is to randomly sample (via binary flip) 1 single point B_infinity from 0 to 1. Given infinite random flips, we are guaranteed that B_infinity falls uniformly and randomly within that interval. Since the method picks a persons as soon as B_infinity, or its interval [b_N, B_N + 2^-n ], falls entirely within a subregion, we are then covered with respect to fairness.

Agree. A fair method cannot guaranty any maximum number of tosses.

I'd like to enter the following solution and claim the minimum number of throws.

Divide the entire table cloth into n rectangles of equal area with a permanent marker. Each participant must be assigned his rectangle. Then ask the waiter to throw the coin onto the table cloth from afar.

I see your 1 and I will raise you a 0 =)

Arrange the participants into a circle and tell them to simultaneously throw out their hand with the fists made into either a rock, paper, or scissor. That is, let them play N-person paper-rock-scissor. Keep the participants with the least frequent hand-formation. For instance, if there are 12 people, and 4 has rock, 5 has scissor, and 3 has paper, then we keep the party of 3 that made the paper.

Let the subparty play the modified paper-rock-scissor game again until 1 person remains. If at any point there is a 3-way tie of hand-formation, let them play again. Also, if there are 2 people left at some point, then let them play normal paper-rock-scissor instead of the modified version.

Oh, the coin? Tip it to the waiter.

Not acceptable. The winner must be decided by coin toss.

[bushindo]

I don't think this problem can be decided with a fixed ceiling method. That is, I don't think there exist a method that guarantees a maximum number of fixed maximum flips m(N) for every N. See below for reason + proof of fairness

Let's assume there's a method with a maximum flips m(N) for N participants. There are roughly 2^m(N) possible outcomes. Since that is a power of 2, it doesn't divide nicely when N includes non-2 factors. There are bound to be events when the method can not select someone, and then we are back to square one.

As for the fairness issue, the point of the method is to randomly sample (via binary flip) 1 single point B_infinity from 0 to 1. Given infinite random flips, we are guaranteed that B_infinity falls uniformly and randomly within that interval. Since the method picks a persons as soon as B_infinity, or its interval [b_N, B_N + 2^-n ], falls entirely within a subregion, we are then covered with respect to fairness.

Agree. A fair method cannot guaranty any maximum number of tosses.

I'd like to enter the following solution and claim the minimum number of throws.

Divide the entire table cloth into n rectangles of equal area with a permanent marker. Each participant must be assigned his rectangle. Then ask the waiter to throw the coin onto the table cloth from afar.

I see your 1 and I will raise you a 0 =)

Arrange the participants into a circle and tell them to simultaneously throw out their hand with the fists made into either a rock, paper, or scissor. That is, let them play N-person paper-rock-scissor. Keep the participants with the least frequent hand-formation. For instance, if there are 12 people, and 4 has rock, 5 has scissor, and 3 has paper, then we keep the party of 3 that made the paper.

Let the subparty play the modified paper-rock-scissor game again until 1 person remains. If at any point there is a 3-way tie of hand-formation, let them play again. Also, if there are 2 people left at some point, then let them play normal paper-rock-scissor instead of the modified version.

Oh, the coin? Tip it to the waiter.

Not acceptable. The winner must be decided by coin toss.

My interpretation of the OP is that the coin flip is optional rather than mandatory. The OP says "Pick a person out of n with a sequence of coin toss". I submit that it is possible to construct a sequence of length 0.

[bonanova]

I'm trying to go for the minimum expected number of flips here. This is my best attempt so far

If N is a power of 2, the solution is trivial. Let's assume N is not a power of 2. Divide the interval from 0 to 1 into N sub-intervals. Each person will be assigned a sub-interval. So, if there are 3 participant, the first one would be assigned [0, 1/3), the second [1/3, 2/3), and the third [2/3, 1].

Flip the coin and treat the resulting string of outcomes as a fractional binary number. For instance, let head = 1 and tail = 0. If we flip head two times in a row, that is the equivalent of .11 in binary or (1/2 + 1/4 = .75 in decimal). Let the fractional binary number we construct after N flip be B_N. The range of values for the binary number B_infinity after the first N flip is [b_N,B_N + 2^-N].

So, let's say after two flips the binary number is .11 in binary or .75 in decimal. The range of possible binary number, assuming an infinite number of continuing flips, in decimal form is [.75, 1].

The idea is as soon as the possible values [b_N,B_N + 2^-(N) ] is entirely contained within 1 person's subinterval, that person is selected.

Let's calculate the expected number of flips required. For N participants where N is not a power of 2, we would require ceiling( log2( N ) ) flips to narrow the field down to two people. From there it takes an expected number of 2 further flips to further select one of those two. That gives us an upper bound of ceiling( log2( N ) ) + 2 for the expected number of flips.

This is the method I had in mind. It follows from a previous discussion of simulating an arbitrarily biased outcome using a fair coin.

But let the discussion continue.