Puzzle time - Hazards of Electronic Coin Flipping

[jon-nyc]

You have been hired as an arbitrator and called upon to award a certain indivisible widget randomly to either Alice, Bob, or Charlie, each with probability 1/3. Fortunately, you have an electronic coin flipping device with an analog dial that enables you to enter any desired probability p. Then you push a button and the device shows "Heads" with probability p, else "Tails."

Alas, your device is showing its "low battery" light and warning you that you may set the probability p only once, and then push the coin flip button at most 10 times. Can you still do your job?

[Klaus]

I have a solution that requires only two coin flips, but it has the small cosmetic disadvantage that I need the probability to be a complex number.

[Klaus]

I think this algorithm would yield the solution in principle (but is probably too expensive to actually compute):

Take all 2^10 = 1024 sequences of coin flips. Calculate its probability symbolically (which yields a polynomial of degree 10 in p).

Now iterate over all possible partitions of the set of sequences of coin flips into three disjoint sets. Compute the symbolic probability of each subset and generate an equation that that probability must be 1/3. Attempt to find a real-valued p that solves the three equations. If that fails, continue with the next possible partition.

[Axtremus]

I sort of gave up after getting to a point where it doesn't look like I can find a rational value for p to make it work with a finite number of coin flips. :man-shrugging:

[jon-nyc]

I have a solution that solves it sometimes but not always.

Set it to 1/3, use that to select/eliminate one player, then use von Neumann’s algorithm for getting a fair toss from a biased coin to select between the survivors.

But that can take arbitrarily long so isn’t really a solution.

[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.]