Puzzle time - Hazards of Electronic Coin Flipping

[Klaus]

There are standard algorithms to sample from a categorical distribution using a sampler for a binomial distribution, but they all involve changing the p....

[jon-nyc]

I have a solution that needs only four flips.

I could give a hint but it’s practically a give away.

[jon-nyc]

Can you find p such that p(HHHH or TTTT) = 1/3?

Or even show that such a p exists?

[Klaus]

Wouldn't that simply be (1/3)^(1/4)? Around 0.7598

[jon-nyc]

You want to solve p^4 + (1-p)^4 = 1/3, not just p^4 = 1/3.

[Klaus]

Oh, I just see that I messed up the parenthesis and read " p(HHHH or TTTT) = 1/3 " as " p(HHHH) = 1/3 or p(TTTT) = 1/3".

Your equation does have two solutions in the real numbers, p = 0.24213 and p=0.75787.

The question is whether any subset of the other combinations sums up to 0.5.

[Klaus]

Played around a little with your hints.

With p as about 0.24213 and 4 tosses, there are 120 out of 65536 possible combinations that are pretty close to 0.5.

For instance,
HTTT,THHH,THTH,THTT,TTHH,TTHT,TTTH
sums up to 0.49969773.

I'm not quite sure whether the deviation from 0.5 is due to rounding errors or whether it's actually only close to 0.5.

I'm sure there's a better way to do this...

[jon-nyc]

As long as we’re using an even power (4 in this case, but 6,8,10 should work if there’s a real solution to the equation that gives 1/3) the symmetry of the remaining flip combinations guarantees they can be split into groups of equal probability. Thus we have multiple solutions that give three equal outcomes, in as few as 4 flips.

[Klaus]

Oh, right, so you do it all in just 4 flips. Hence the task isn't to generate a p=0.5 flip after a p=1/3 flip (which is what I thought), but to generate three equally likely outcomes. The symmetry argument is nice.

Yes, that works.

[jon-nyc]

Here’s his Tuesday hint. He seems to be going in a different direction.

HINT: No matter what p is, if you flip three times and don't happen to get HHH or TTT, you could use the "odd" flip to choose among Alice, Bob, and Charlie.

[jon-nyc]

SOLUTION: If you could set p twice, two flips would be enough: Set p = 1/3 and on Heads give the widget to Alice, else reset to 1/2 and use the result to decide between Bob and Charlie. Since you can only set p once, it might make sense to try to design a scheme first, then pick p to make the scheme work.

For example, you could flip your coin three times and if the flips are not all the same, you could use the "different" flip to decide to whom to award the widget (e.g., "HTT" means Alice gets it). But if you get all heads or all tails, you'll have to do it again, and maybe yet again — so, it might take more than 10 flips.

But now suppose we flip the coin four times. There are four ways to get one head, six to get two, four to get three: Even numbers all, so anytime you get non-uniform results you can use the flips to decide between Alice and Bob. If the coin is fair, the remaining probability — that is, the probability q = p4 + (1 - p)4 of "HHHH or TTTT" — is only 1/8, too small for Charlie.

As you reduce p, however, q changes continuously and approaches 1. Thus, by the Intermediate Value Theorem, there is some p for which the probability of "HHHH or TTTT" is exactly the 1/3 you need.

[The actual value of p works out to 1/2 − sqrt(sqrt(2/3)−3/4), which is about 0.24213069021. The "other root," p = 1 − 0.24213069021, also works. Since these numbers are close to 1/4 and 3/4, you could do a pretty good job with 8 flips of a fair coin; think of each pair of 50-50 flips as one flip of a p-coin, e.g., HH is interpreted as H and HT or TH or TT as T. The result is "fair" between Alice and Bob but gives the widget to Charlie with probability (1/4)4 + (3/4)4 = 0.3203125, a bit short of his just desserts.]