An Unfair Coin 2: Fairness Strikes Back

[EventHorizon]

I took the coin from out of the biased random number generators jar that had been collecting dust in the corner of the Den, but I needed to choose between two options with 50% probability each. I thought this would be easy since I already calculated the probability that heads would come up for this coin.

From ujjagrawal's puzzle: After flipping the coin 4 times, having heads come up 2 times is the same probability as heads coming up 3 times.

Also, assume the probability heads comes up on any given flip is neither 1 nor 0. Yeah, it's a coin so those are veritable impossibilities, but thought I'd spell it out regardless.

1) How can I choose between the two options with 50% probability?

2) I accidently drop ujjagrawal's coin in the jar, and now don't know which one it is. I grab another coin from the jar. How can I choose between the two options with equal probability using this new coin (assuming both heads and tails can be outcomes on any given flip and occur with constant probabilities)?

3) How can I use the coin from (2) to choose between N options, where N is a positive integer, with the fewest number of coin flips needed on average?

[phil1882]

not sure i understand the puzzle.

for question 1 it seems to me if the chances of getting 3 heads is equal to the chances of getting 2 heads on four flips, just flip the coin four times. am i missing something?

for question 2 i have no idea. it depends on the probability of coming up with head/tails.

question 3 is poorly defined. one way would be to simply flip the coin n times, count the number of heads and use that number for your choice. another way would be to flip the coin log2(N) times. let heads be 0 and tails be 1., and express the choice in binary.

[jim]

--I flip the coin twice.

HT is one outcome and TH is the other. If I get either HH or TT I repeat the procdure.

-- I look for the first number in Pascal's triangle that is at least N. I select N possible outcomes with the same number of heads and tails specifying which correspond to j/N and which to (N-j)/N. In your puzzle j=1 but it could be any number less than N and relatively prime to N. A success is getting one of these outcomes.

Following a failure we repeat the process with a difference. For our first try our best guess for the ratio of the likelyhood of getting head and tails was 1:1. Now it would be the maximum likelyhood estimate of (h+1):(t+1) where h is the total number of heads we have gotten up to this time and t is the total number of tails. This time we select a number from Pascal's triangle where the ratio of the likelyhood af a successful trial to the number of flips involved is as large as possible

[EventHorizon]

Hey jim. It is common courtesy to use spoilers so others will see your answer only if they want to. Please use them in the future. (Will a mod spoilerify his post please?)

That being said... good job on 1&2. I wanted a different answer for 1, but 2's answer will obviously work too.

As for 3, it was a valiant attempt. You've identified a number of the needed elements in the solution, but you've missed something. Also, I think you may have misunderstood the problem as choosing between two options with an unequal probability based on N. The problem is asking you to choose from from a set of N different options with equal probability. This is a simple difference, but not the only thing I believe is missing from the solution.

Though I should point out that I don't have a full solution worked up yet.

[CaptainEd]

The basic principle, extrapolating from the previous posts, is that every sequence with M heads and M tails has the same probability, whatever it is.

So, we will create N different sequences of M heads and M tails. One easy way is to create ANY sequence of M flips, followed by its complement.

For example, if N = 3, you could use

A: HTTH

B: THHT

C: HHTT

for N=5, you could use

A: HHHTTT

B: HHTTTH

C: HTHTHT

D: HTTTHH

E: THHHTT

You need sequences long enough so that there are N sequences. So choose M so that 2^M >= N.

You flip the coins 2M times to make a sequence. If it's one of the desired sequences, you have successfully Chosen. If not, discard this attempt, and flip another sequence. You can shortcut: if you flip any of HTH, HHH, TT, THT you know you have missed, so discard and start again.

Oh, you want the minimum flip solution...sorry

Edited August 9, 2012 by CaptainEd

[CaptainEd]

All sequences of M flips with P heads have the same probability.

for N=3, use, for example

A: HHT

B: HTH

C: THH

for N=5, you might choose to use

A: HHTT

B: HTHT

C: HTTH

D: THHT

E: THTH

Still doesn't minimize flips, I expect.

[CaptainEd]

since all sequences of 3 flips with 1 head have the same probability, and all sequences of 3 flips with 2 heads have the same probability (though probably different from the 1 head probability), we can avoid discarding more of the sequences by accepting one sequence from each of the two sets..

For N = 3; if the outcome is:

HHT or TTH, select A

HTH or THT, select B

THH or HTT, select C

Now we only discard HHH and TTT, which occur with probability p^3 and q^3. So expected number of flips E = 3 * (1 - p^3 - q^3) + (E+3) * (p^3+q^3))

E = 3 + E * (p^3+q^3)

E = 3 / (1 - p^3 - q^3)

for p = 0.5, E = 4

for p = 0.1, E > 13

Clearly, generalizing this approach is difficult algorithmically.

for N = 4; pascal's triangle is 1,4,6,4,1 So we can use choose one from each of the 4, one from each of the other 4, and one from each of four of the 6, leaving 4 sequences to be discarded.

for N = 5; 1,5,10,10,5,1 Similar to the 3 case, we can divide the 5, divide the other 5, divide the 10 into 5 pairs, ditto for the other 10, winding up with only two sequences to discard.

for N = 6; 1,6,15,20,15,6,1 we can use 6 of the 6, 12 of the 15, 18 of the 20, 12 of the 15, and 6 of the 6.

for N = 7; 1,7,21,35,35,21,7,1 since all the groups are divisible by 7, we can use up all the cases but all-heads and all-tails.

for N=8; 1,8,28,56,70,56,28,8,1

for N=9; 1,9,36,84,126,126,84,36,9,1

Apparently, for odd N, we can use up all the cases but all-heads and all-tails, so it approaches a very good, if not minimal, numbr of flips.