Picking a random person with coin flips

[Trojan Horse]

This one is inspired by some experimenting I did at www.random.org recently.

1. Three friends go out to lunch together, and they decide to pick one person at random to pay the bill. Unfortunately, the only randomizing device they have is a single coin.

Your task: find a way to pick one of the three people at random using a series of coin flips. Each person must have a 1/3 chance of being selected. Also, you need to minimize the number of coin flips that will be needed on average.

2. Same scenario as #1, but now there are five friends. Find a way to pick one of the five at random (each with a 1/5 chance), using as few coin flips (on average) as possible.

3. Now there are only four friends. This would make things far easier, except for one thing: one person in the group (let's call him Mr. X) has ordered a much more expensive meal than anyone else. It is decided that Mr. X should have double the chance of paying the bill as anyone else. (So, Mr. X should have a 2/5 chance, and everyone else should have a 1/5 chance.) How can they do this, using as few coin flips (on average) as possible?

[jadesmar]

Here's the naive answer.

1. For three:
If Alice H, Bob H -> Charlie pays
If Alice T, Bob H -> Alice pays
If Alice H, Bob T -> Bob pays
If Alice T, Bob T -> flip again.

That's about 3 1/3 rolls on average I think (I have to sum an infinite geometric series which I forget how to do).

2, For five is it just, 3 people roll, pick your permutations, and reroll on 3/5 of the possible outcomes?

What's the average number of rolls on that? Around 4.6?

3. Give one guy 2 outcomes, 3 people 1 outcomes, and reroll on 3 outcomes.

[groza528]

For 1. that infinite sum is actually 2.666667
For 2. it comes out to 4.8; I can improve on that by having four people flip coins and each person taking 3 permutations. Then it drops to 4.266667

[groza528]

Actually I think I can improve on my previous improvement with a minor change...
It all comes down to taking care which permutations you assign. For example, if the three permutations assigned to Alice are HHHH, HHHT, and HHTH, then you can get away with only three tosses some of the time. If the first three come up heads then you know it will be Alice regardless of the fourth toss and you need not flip the fourth coin. All five friends can be assigned in such a manner, such that 2/3 of the time the fourth toss is not needed. This brings the average number of tosses down to 3.6 for question 2.

As for question 3. we can apply a similar model, but for the chap that has twice the chances we can get away with only *two* tosses in some cases, which should bring the average I believe to 3.2

[lostdummy]

This depend on what we want to minimize, number of coin ROUNDS (ie minimizing time), or number of individual coin tosses.

If minimizing individual coins, then I also have 3.6 average tosses for #2 and 3.2 average tosses for #3, by using 4 coins per round.

[Trojan Horse]

[Trojan Horse]

My inspiration for this puzzle:

www.random.org uses atmospheric noise to generate a truly random sequence of bits. These bits can then be used to generate all sorts of random things; you can use random.org to get a sequence of random die rolls, or to get a random ordering for names in a list, or whatever.

Thing is, it costs money to generate random bits this way, so the guy running random.org wants to make sure that no one person hogs all the bits. He has set up a quota system; each IP address gets a quota of 1,000,000 bits. Each day, you gain back 200,000 of the bits you have used up, until you are back up to a total of 1,000,000 bits. (Those who really need more bits can always pay for more.)

Given that random.org has these measures in place, I was curious: what does random.org do to minimize the number of bits used for each request? Let's say I asked random.org for 1000 rolls of a 20-sided die. Here are a few ways random.org could do that:

1. The naive solution. Assign each number from 1 to 20 a sequence of five bits. Then get five bits from the stream. If they match one of the 20 chosen sequences, fine. Otherwise, throw them out, and grab five more bits. On average, this requires 5x(32/20)=8 bits per die roll, for an overall average of 8000 bits.

2. Optimize each die roll. You guys figured out that picking a number from 1 to 5 requires 3.6 bits on average. Using that, you can pick a number from 1 to 20 using 5.6 bits on average. For 1000 die rolls, that comes to 5600 bits on average.

3. Buy in bulk. Instead of generating 1000 numbers from 1 to 20, you can generate a single number from 1 to 20^1000. Then use that to get the 1000 die rolls. You have to keep track of a lot more bits at the same time, but you end up using fewer bits: 4323, on average (rounded up to the nearest integer).

So, how much optimizing does random.org do? I asked random.org for 1000 rolls of a 20-sided die, then I checked to see how many bits I had used up.

The total was roughly 8000 bits, and it was an exact multiple of five.

From that, and from further tests, I have concluded that random.org is using the naive solution for everything. Given that they are trying to be frugal with their bits, that's disappointing.

[Zag]

[gftt*]

All of the above scenarios require an unbounded number of flips. They'll all terminate in a finite number of flips with probability one, but you can't set a cap on the number of flips prior to carrying out the experiment.

Can you pick between three options with exactly 1/3 probability each if you have a bounded number of flips of an UNFAIR coin? You can choose how the coin is weighted.

[Zag]

[Trojan Horse]

[grz*]

[Zag]

I guess. I'm a little surprised that they would charge you for actual bits generated, rather than bits delivered. We could do a test: 1000 d32 's should be exactly 5000 bits, while 1000 d17's would be nearly 10,000.

TH: Nicely done.

[gftt*]

[Trojan Horse]

Because I think I found a proof for it.

My first attempts were with p rational: I first tried p=2/3. I thought it would be a cinch. Then an issue arose that I hadn't expected. The issue was so pervasive that it seemed to preclude p from being rational at all. So I tried to prove that p can't be rational, and I think I've succeeded.

To be more precise, here's what I claim:

Say you are going to use a (possibly unfair) coin to choose between n alternatives, and you want each alternative to be chosen exactly 1/n of the time. Assume that

1. the probability, p, of getting heads must be rational, and
2. the overall protocol must have a finite upper bound for the number of required coin tosses.

This is only possible if the coin is fair, and n is a power of 2.

Due to laziness and a desire to give you guys a challenge (but mostly laziness), I won't post the proof right now.

[Scurra]

[groza528]

[Amb]

[groza528]

We usually just play credit card roulette

[bonanova]

Corollary: simulate an unfair coin (heads has probability p) using a fair coin, and fewest flips.
_________________
_{Vidi, vici, veni.}

[lostdummy]

[lostdummy]

[bonanova]

Actually it's the inverse problem. You want to use a fair coin but not have the outcomes be equally probable: Option a is to be chosen with probability p and option b with (1-p). How, using fewest flips could that be done?
_________________
_{Vidi, vici, veni.}

[lostdummy]

[lostdummy]

Actually, some general rule for p=A/B (p<=0.5, A&B integer) could be also made:

1) find N such that 2^N >= B
2) out of 2^N combinations of N coin toss, select A of them to be "Head", and (B-A) to be "Tail"
3) if combination not in those falls, reroll. Average number of coin flps=N*2^N/B

This could be probably optimized to select N such that both 2^N>=B and that 2^N mod B is minimal, to minimize rerolls, similar to what we did here with "5 person" original problem. Only then in 2nd step you need to select k*A to be "Head" and k*(B-A) to be tail, using max possible k (k= 2^N div B).

For example, p=2/5:
a) N=3 (2^3>5); Heads=A=2=(HHH,TTT), Tail=(B-A)=3=(HHT,HTH,HTT) -> avg flips=4.8
b) N=4, k=3, Heads=k*A=6combos, Tail=k*(B-A)=9combos -> avg flips=4*16/15=4.26 (optimized)

And then we could implement further optimization, of type we did also in random.org case, ie group as much as possible of "same starting sequence" combos in same Head or Tail group, so we can skip rest of coin flips .

For example, select for (b) case above:
Head= HHHH,HHHT,HHTH,HHTT,HTHH,HTHT -> meaning as soon as HHH, HHT or HTH appears, we have "Head" and are done
Tail=TTTT,TTTH,TTHT,TTHH,THTT,THTH,THHT,THHH,HTTT -> meaning as soon as T appears, or HTTT appears, we have "Tail" and are done
Reroll=HTTH, next round

That means average coin flips in one round is (8*1+6*3+2*4)/16=34/16, and that means average number of total coin flips is [flips per round]*16/15=34/15= 2.27 ! (optimized #2)

Not sure if 2nd optimization benefit can be calculated so clearly as first one, for general case. But here is revised, optimized, approach:

1) find N such that 2^N >= B, and that 2^N mod B is minimal (but not too high N, check only minimal N, and up to +2)
2) get multiplier k=2^N div B
3) out of 2^N combinations of N coin toss, select nH=k*A of them to be "Head", and nT=k*(B-A) to be number of "Tail" combos
4) select Head combos from "all Hs" upward (HHH,HHT,HTH...) and Tail combos from "all Ts" downward (TTT,TTH,...), such that you can maximize grouping combos and not needing to flip all N coins
5) calculate average number of needed coin flips per round (avgRound), which should be less than N if #4 grouping optimization is used
6) if combination not in Head/Tail combos falls, reroll. Average number of coin flips= avgRound*2^N/B

Example for this optimized approach for p=3/13 would give N=4 coins to flip, k=1, nH=3 combos for Head (HHHH to HHTH), nT=10 combos for Tail (HTTH to TTTT), average number of flips per round=34/16, average number of rounds 16/13, and average total number of flips 34/13= 2.62

[esme]

[bonanova]

My approach was this. Write the fractional binary expansion of p with coin tosses. H = 1, say, and T = 0. As soon as there is disagreement, the selection has been made.
_________________
_{Vidi, vici, veni.}

[esme]

@bonanova:

And how do you know that your approach has the fewest flips?
_________________
Mundus vult decipi, ergo decipiatur.

[bonanova]

[esme]

Well, it is definitely not the most efficient method to simulate a fair coin (or any power of two).
_________________
Mundus vult decipi, ergo decipiatur.

[bonanova]

Right. And perhaps by extension any rational.
But how better could you discern probability regions bounded by 0, 1/pi, 1/e and 1?
_________________
_{Vidi, vici, veni.}

[lostdummy]

[Thok]

[bonanova]

Neither really. My post 20 stated a new problem: using a fair coin to simulate an arbitrarily biased one.

In binary, 1/3 is .010101010101010101010....

Flip an unbiased coin, and associate say H with 1 and T with 0.
A flip sequence that evaluates to a smaller value chooses the p case.
A larger value chooses the 1-p case.

First flip is T, it matches 0 so flip again.
Second flip is H, it matches 1 so flip again.
Third flip is H, it does not match 0 so you're done.
THH evaluates to .011, larger than p, so you've chosen the 1-p case.

First flip is H, evaluates to .1, larger than p, you've chosen 1-p case.

First two flips are TT, evaluates to .00, smaller than p, you've chosen the p case.

And of course you can divide [0, 1] arbitrarily into multiple intervals whose widths give arbitrary handicaps to multiple players.
_________________
_{Vidi, vici, veni.}

[bonanova]

So, who gets a free dinner? Have everyone write down a number in [0, 1]. Convert to binary and start flipping. Each person's interval starts at his number and extends down to next lowest. If the flip sequence ends up in the top interval, above the highest number chosen, everyone buys his own.
_________________
_{Vidi, vici, veni.}

[lostdummy]

[lostdummy]

[bonanova]

[bonanova]

[lostdummy]