[Guest]

You need to select one among p persons in a fair manner - i.e, probability of choosing any one should be 1/p. You have a fair coin at your disposal.

Assume p is not of the form 2^N for some positive N.

a. What will be your strategy for least number of coin tosses? What is this least number?

b. What will be the average number of coin tosses?

b. Can you solve for the generic case, where you have to choose one among p persons, assuming you have a rand() function that returns a random number between 1 to q with uniform probability?

[bonanova]

Write the number p in binary.

It will have n digits, where n = log₂(p).

Flip the coin n times, calling heads=1 and tails=0, to spell out a number.

Discard the result if the number is greater than p.

That gives a fair selection of numbers 1-p.

But it's probably not done with the fewest possible coin tosses.

This method avoids possibly throwing out a result.

Divide the interval [0,1] into p equal parts. The intervals are [0, 1/p), [1/p, 2/p), ... [(p-1)/p, p].

Find the number of digits in the binary representation of 1/p and toss the coin that many times.

The string of digits will define a number in [0, 1] with equal probability of falling in any of the p segments.

This produces a fair selection among p choices.

[Guest]

Write the number p in binary.

It will have n digits, where n = log₂(p).

Flip the coin n times, calling heads=1 and tails=0, to spell out a number.

Discard the result if the number is greater than p.

That gives a fair selection of numbers 1-p.

But it's probably not done with the fewest possible coin tosses.

This method avoids possibly throwing out a result.

Divide the interval [0,1] into p equal parts. The intervals are [0, 1/p), [1/p, 2/p), ... [(p-1)/p, p].

Find the number of digits in the binary representation of 1/p and toss the coin that many times.

The string of digits will define a number in [0, 1] with equal probability of falling in any of the p segments.

This produces a fair selection among p choices.

First one is correct (and that is the only method I know). I think the second one may not be a solution..

1/p in binary may not terminate.

[bushindo]

First one is correct (and that is the only method I know). I think the second one may not be a solution..

1/p in binary may not terminate.

Let me refine bonanova's approach a bit

Let head=1, tail = 0. Suppose that you flipped a coin three times, and the number x turn out as .101. If you continue flipping until infinity, the number x must belong in the interval [ .10100000000..., .1011111111111...], which has a width of 1/2ⁿ, n being the number of flips. So we revise bonanova's strategy as follow

1) Divide the interval into p parts [0, 1/p), [1/p, 2/p), ... [(p-1)/p ].

2) Flip the coin as many times as it takes. Update the value of x at every turn.

3) Stop flipping once the interval [x, x + 1/2ⁿ ] belongs entirely within one of the p intervals from part 1).

I'll work on the optimal part later. Need to do other work that actually paids for now.

Edited August 21, 2009 by bushindo

[bonanova]

I forgot to point out, so I will now, that the interval method permits one

to assign any desired weighted probability to each choice, in addition to

providing a fair choice.

[Guest]

Write the number p in binary.

It will have n digits, where n = log₂(p).

Flip the coin n times, calling heads=1 and tails=0, to spell out a number.

Discard the result if the number is greater than p.

That gives a fair selection of numbers 1-p.

But it's probably not done with the fewest possible coin tosses.

This method avoids possibly throwing out a result.

Divide the interval [0,1] into p equal parts. The intervals are [0, 1/p), [1/p, 2/p), ... [(p-1)/p, p].

Find the number of digits in the binary representation of 1/p and toss the coin that many times.

The string of digits will define a number in [0, 1] with equal probability of falling in any of the p segments.

This produces a fair selection among p choices.

I prefer the second method too.

In the first method, the probability of choosing one person out of p is not 1/p but 1/2ⁿ where n is the smallest number such that 2ⁿ is greater than p (mentioned by bonanova as discarding outputs greater than p).

[Guest]

This reminds me of that buffon's needle problem, but using buffon's needle for numbers this normal would be kind of hard.