Heads, or Tails?


Here’s a nifty little problem that a friend gave me yesterday that i thought i’d share with you:



You have three items (call them ‘a’, ‘b’ and ‘c’) that you want to choose any one from without bias.  If you had a fair three sided die, you could assign an item to each side of the die, then simply toss the die once and pick the item that it lands on.


However, you don’t have such a fair three sided die.  Instead, you have a fair two sided coin.  Note: ‘fair’ means ‘there is an equal chance of coming up heads or tails’.  Can you come up with an algorithm that uses said coin in order to pick any one of those items with equal probability?


Have fun!



Edit: Clarified the wording for how ‘fair’ is defined.  Sorry if this tripped anyone up.


Comments (149)

  1. Ariel says:

    1. Throw the coin twice.

    2. if throws were "h-h" select ‘A’

    if throws were "h-t" select ‘B’

    if throws were "t-h" select ‘C’

    if throws were "t-t" goto(1)

    So it’s not finite. so what? We’ve got time.

  2. CyrusN says:

    Ariel: I asked for an algorith: http://en.wikipedia.org/wiki/Algorithm

    i.e. "a finite set of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a corresponding recognizable end-state"

    "So it’s not finite. so what? We’ve got time."

    Well, considering i asked for something that terminates, it matters πŸ™‚

  3. David Taylor says:

    It’s very easy to come up with an algorithm as follows.

    The algorithm has a decision cycle (described below) with the following possible results

    1. No decision. Probability 0.25

    2. Clear winner. Probability 0.375

    3. Clear loser. Probability 0.375.

    If the result of the decision cycle is ‘No decision’ repeat the cycle until a different result is obtained. the probability of two ‘No decisions’ in a row is 0.0625, of three is 0.015625 and of 4 is 0.00390625. The chance of an infinite number is zero, or impossible.

    When an different answer is obtained there is either a clear winner, or a clear loser. If there is a clear winner the choice has been made. If there is a clear loser then the decision is made between the other two items on the basis of a single toss of the coin.

    The decision cycle:

    1. Assign the score 1 to one side of the coin and zero to the other side.

    2. Toss the coin once for each item giving a score for that item.

    3. Possible outcomes:-

    a. Clear winner: Only 1 item with score of 1.

    b. Clear losser: Only 1 item with score of 0.

    c. No decision: Some other result.

    The down side of my solution is that it could potentially take too long.

  4. Rik Hemsley says:

    Using a two sided coin means that the set of outcomes will always be a power of two. I don’t think any powers of two are divisible by three.

    Is there a solution? This one will bug me!

  5. David Taylor says:

    After further thought I actually believe that an answer that is required to finish within a given number of throws of the coin is impossible. ie within a given finite time.

    If you throw the coin N times you have 2 to the power N equally possible outcomes. To fairly decide between 3 possabilities this number would need to be divisible by three. However the only factors of this number are 2 so it cannot be divisible by 3. Therefore it is not possible to fairly decide between 3 possible outcomes for any given finite N.

    Is there any flaw in my reasoning?

  6. David Taylor says:

    The pragmatic answer? The question as posed is impossible, there has to be some tradeoff if the decision is to be made. One can either decide the timeframe in which the decision must be made and accept the resulting bias or decide the minimum acceptable bias and thereby determine the maximum timeframe. No matter how small the acceptable bias, provided it is not zero, it is possible to determine a time frame in which the question can be answered within the acceptable bias.

  7. Ed Kaim says:

    Since you can’t evenly divide 2^N by 3, I would probably flip the coin once and use its final settled orientation to make the decision. If the angle were 0-120 degrees from a predetermined start angle I’d go with ‘a’, 120-240 I’d use ‘b’, 240-360 I’d use ‘c’.

    You could also time how long it takes for the coin to settle after leaving your hand and mod the milliseconds by 3 to get a result.

    Finally, since we have infinite budget but limited time, we could flip the coin and mod the force at which it hits the ground (or its peak height in cm) by 3 for a result.

    Then again, your mileage may vary depending on whether you’re using African or European coinage.

  8. Erno says:

    Easy!

    Make a funnel with three equally sized compartments at the bottom. Put A, B and C each in its own compartment.

    Throw the coin in the funnel.

    Pick the object from the compartment where the coin landed.

    Cheers,

    Erno

  9. Ando says:

    My 2c (Excuse the pun)

    Assign 2 options to one side and one to the other. All have an equal chance of winning initial toss. If winning side has 2 options then toss again to pick winner.

  10. TAG says:

    As Devid has pointed out – this is impossible to do in definitely finite amount of time.

    Suppose this will be requere at most N coin drops.

    This lead to 2^N possible outcomes.

    Even in case we will chose item before N-th drop – we can assume that all outcomes of drops after selection done lead to item we have choosen.

    This mean that we have to divide 2^N possible outcomes to 3 equal groups – but this is impossible.

    But algorithm pointed out by Ariel will most-likely finish in finite time. Probability that it will NOT finish in 2N drops is 2^(-2N).

  11. Darren Oakey says:

    Impossible? Why is everyone focusing on the "perfect" solution = there is a perfectly fair and pragmatic solution.

    You throw the coin twice, giving you two binary digits.

    HH : pick option 1

    HT : pick option 2

    TH : pick option 3

    TT : Do the whole process again

    While it’s mathematically not "guaranteed" to finish – in practice it’s very very likely to give you a solution, and it will always be fair.

  12. Place the coin in a vacuum and expose it to suitably high-frequency electromagnetic radiation. Position three detectors in the vacuum to detect the electrons given off due to the photoelectric effect. Choose the positions carefully to ensure that the chances of each being hit is the same. Whichever registers the first hit, that’s your winner.

    Melt down the coin and reform it into a triangular prism. Round the ends off to make sure it cannot stand on one end. Ensure that your work is uniform enough that the coin now has rotation symmetry of order three. Roll your coin and choose the results based on which side it stops on.

    Practice tossing the coin for several years and if you have a good sense of timing and the ability to be consistent with how much power you put into the toss, you will discover that you can influence the odds of which way the coin lands. Ideally you want to practice until you get to the point where you can bias the outcome to be heads 2/3 of the time. If it ends up as tails, pick a, if you get heads, throw once more, but this time without the biasing timing, and pick b or c based on heads or tails.

    Use the coin to pay a developer to write a suitable program.

    Balance the coin on top of an equilateral tetrahedron. Since this is a state of unstable equilibrium, random environmental perturbations will unsettle the coin. It will slide down one of the three upturned faces of the tetrahedron – use that to determine your choice.

    Just pick the one closest to you – you know it’s the polite thing to do.

    Put the coin into any fruit machine (aka ‘one-armed bandit’) with three tumblers; use your full understanding of the interior working of the machine to devise an appropriate system. Since fruit machines are all different, I won’t supply this piffling implementation detail here.

    Just pick the largest one – you know it’s what you want to do.

    Put the coin into a payphone and call the speaking clock. (You may need to make sure you’re in a country that offers such a service first – I’m not sure if this is available all over the world.) When it tells you the number of seconds, divide by three and then use the remainder (which will be 0, 1 or 2) to make your choice.

  13. TimW says:

    Easy…flip the coin 3 times. Flip 1 is for A, flip 2 is for B, flip 3 is for C. Whichever flip is heads goes to the next round.

    After round 1, there will either be a clear winner or 2 winners. (50% chance for 3 flips to be heads would say that there would be 1 or 2 heads flipped out of 3).

    If there needs to be a round 2, 50% chance says that one of the two winners will become the clear winner.

    Note: I’d like to see the coin that is 50%/50% fair πŸ˜‰

  14. Jeff Parker says:

    This is a difficult one, I can not think of any one line simple math sollution. However along the same lines as what Ariel posted when you think about how it works would simply to use a 12 sided dice. this would give you an equal number of chances, however then you use 1-4 = 1, 5-8 = 2, 9-12 = 3

    The common denominator (err denominator not right word but think of it as a fraction) but between the number 1/2 and 1/3 is 12 hence to 2 drops Ariel posted. So anyway a simple C# method is as so. Below is all I can think of Ariel and I are going to the same place just using different methods.

    class Class1

    {

    [STAThread]

    static void Main(string[] args)

    {

    for (int LoopCount = 0; LoopCount < 30; LoopCount++)

    {

    //sleeping the thread because the random class is based on PC clock time

    System.Threading.Thread.Sleep(500);

    Console.WriteLine(getRandom3());

    }

    }

    static private int getRandom3()

    {

    System.Random rndm = new Random();

    int randomReturn = rndm.Next(1,12);

    if(randomReturn > 8) return 3;

    if(randomReturn > 4) return 2;

    return 1;

    }

    }

  15. David Taylor says:

    A fair coin with no bias cannot be shown to exist. All that might be demonstratable is that the coin can be shown to have a worst a negliable bias within some meaning of negliable.

    Using the same definition of negliable it would be possible to make the decision by sufficient throws.

    Continuing beyond that point is meaningless because the inherent bias of the coin will have already caused any bias introduced by the method to be not significant. Thats the real world solution.

    The mathematical solution is something else again. To get it done mathematically in a finite time just half the time it takes to toss the coin every time you throw it. The fact that that’s impossible in the real world is not relevent because a coin with no bias is also impossible in the real world.

  16. I would do it as follows. Basically, assign heads a weight of 1, and tails a weight of 0. Flip the coin three times, corresponding to the three sizes, and note the weights. At the end of the first round, if one side has a greater weight than the other two, then you have your choice. Otherwise, go to round two, flipping the coin once per side. Add that weight to the weights from the previous round(s). If there is one clear outcome, then that is the side. Continue until there is one clear winner.

    This has the potential to go on forever, but you don’t have a choice.

    Personally, I like the funnel solution the best.

  17. Jeff Parker says:

    Hmm I am refining my code Actually this can be done for any number the more I think about it. And well me using 12 above should really be 6. You should find the least common multiple of 2 and X where X is the number you want to fairly roll.

    So a better method to replace thw one above would be

    class Class1

    {

    [STAThread]

    static void Main(string[] args)

    {

    Console.WriteLine("Random Numbers for 3");

    for (int LoopCount = 0; LoopCount < 30; LoopCount++)

    {

    //sleeping the thread because the random class is based on PC clock time

    System.Threading.Thread.Sleep(500);

    Console.WriteLine(getfairRandom(3));

    }

    Console.WriteLine("Random Numbers for 7");

    for (int LoopCount = 0; LoopCount < 30; LoopCount++)

    {

    //sleeping the thread because the random class is based on PC clock time

    System.Threading.Thread.Sleep(500);

    Console.WriteLine(getfairRandom(7));

    }

    }

    static private int getfairRandom(int MaxNumber)

    {

    int lcm = 2 * MaxNumber;

    System.Random rndm = new Random();

    double randomReturn = rndm.Next(1,lcm);

    return Convert.ToInt32(Math.Ceiling(randomReturn / 2));

    }

    }

  18. Jeff Parker says:

    Oh I could refine it like right now if you send an even number to it it will multiply it times 2 however this gets you the rough idea. This is also not calculating the LCM for every number combination the LCM for 2 for any number not even is going to be 2 * X.

  19. Raj Kaimal says:

    Throw the coin three times, there are 8 possible outcomes

    000

    001

    ..

    ..

    111

    Throw the coin two times, there are 4 possible outcomes

    00

    01

    ..

    11

    So now you have a total of 12 outcomes which is divisible by three.

    Am I wrong?

  20. DanT says:

    Well the office here is stumped. I’m leaning towards unsolvable without "outside influence", as no power of 2 is ever divisible by 3.

    (Prime factorization of any power of to is a list of twos, and in order to be divisible by 3, a 3 has to appear in there somewhere).

  21. Haacked says:

    Deposit the coin in your bank account. Paypal the value of the coin to my Paypal account. I’ll tell you which ball to pick. I’ll be fair.

    Or I like Raj’s approach, which I’ll just expand. Assign each ball a specific range: 0-3 4-7 8-11

    Then throw the coin 3 times, which creates a binary number 000 to 111 (0 to 7 in decimal). Then throw it two times to create another binary number 00 to 11 (0 to 3).

    Sum these two binary numbers. Then see which ball’s range that number falls into.

  22. DanT says:

    The problem with the two seperate rolls method is you do not have a consistent probability. For instance. There is only 1 way to get 1, assuming 0-7 on the first run, and 1-4 on the second. However there are 2 ways to get 2. 1, 1 or 0, 2. So that doesn’t work.

  23. Jeff Parker says:

    I think I am pretty sure I have it, with my code above it could be reduced to 2 simple lines.

    System.Random rndm = new Random();

    return Convert.ToInt32(Math.Ceiling(rndm.Next(1,(2 * MaxNumber)) / 2));

    Basically what it does is say you supply 3 as you want it as a randome number the least common Multiple of 2 and 3 is 6 which any number in 6 has an equal chance of being picked if you roll a 6 sided die. However then you have to take the number picked and divide it by 2, this could give you a decimal so you have to use rounding toward positive infinity.

    So say you get a 1 or a 2 then you dive that by 2 and you get a .5 or a 1.0 rounding up you get a 1, same thing for the rest of the numbers.

    7 works the same way, (7 * 2), then get a random number out of 14, divide that number by 2 then round up.

  24. Jeff Parker says:

    Opps the return line above should be the following.

    return Convert.ToInt32(Math.Ceiling(Convert.ToDouble(rndm.Next(1,(2 * MaxNumber))) / 2));

    forgot when diving an in by an int it will round down for you hence there could have been a zero in there.

  25. Flip the coin twice, tally up the number of heads.

    0 heads = a

    1 head = b

    2 heads = c

  26. I had a solution close to TimW’s:

    Throw the coin three times (once for A, once for B, once for C).

    If there is a single heads, then pick the corresponding letter, and the algorithm completes.

    If there is no heads or more than one, then try again.

    The probability of getting a single head is 3/8 (3 "single head" states from a total of 8 possible). The probability that the process hasn’t ended by the n-th iteration is (6/8)^n. So there is no upper bound to this process πŸ™

    Raj Kaimal’s solution seems to be the best so far, as it doesn’t require iterations.

  27. Hrm, no, I take that back. Hastily thought out and gives undue precedence to b.

  28. Raj Kaimal says:

    Ignore the previous one I posted…

    Take a piece of paper, draw a circle. Divide it into three parts. Put the coin vertically at the center of the circle and give it a spin. The area that the coin covers most when it lands is the item that gets picked.

  29. Robert Kozak says:

    Hmmm. "Instead, you have a fair two sided coin. Note: ‘fair’ means ‘comes up heads 50% of the time, and tails 50% of the time’."

    Based on this statement if you throw the coin 2 times there is only 2 possible outcomes : HT and TH. Since by definition the coins comes up heads 50% or the time and tails 50% of the time.

    So toss three times. You will always get either two heads in the set or two tails. (H = 2 and T = 1) or (H = 1 and T = 2)

    A B C

    T H T

    2 1 2

    A B C

    H T H

    2 1 2

    an so on…

    The item selected is the one with the 1 value.

  30. Robert Kozak says:

    I spoke too soon. I had a misunderstanding of the word "Fair". A math guru here at work pointed it out that fair only applied to an infinite series and not a finite one like I posted.

  31. Raj Kaimal says:

    Last post for me:

    stats for 1 million "tosses"

    a:333388 b:332944 c:333668

    public static string TossCoin()

    {

    int a = 0;

    int b = 0;

    int c = 0;

    string selectedItem = string.Empty;

    while(true)

    {

    a += TossOutcome();

    b += TossOutcome();

    c += TossOutcome();

    if ((a != b) && (a!= c) && (b!=c))

    {

    selectedItem = (a > b)? ((a > c) ? "a" : "c") : ((b > c) ? "b" : "c");

    break;

    }

    }

    return selectedItem;

    }

    public static int TossOutcome()

    {

    byte[] b = new byte[1];

    new RNGCryptoServiceProvider().GetBytes(b);

    return (b[0] > 127)? 1 : 0;

    }

  32. skywind8 says:

    I think this is an impossible problem, like writing 1/3 in base ten 0.3333333 it has to run infinitely. This problem is like trying to write one third in base two.

    Once you make a choice of something to be less than perfect, you can "round it off" and get close enough for most purposes, but the perfect solution is infinite.

  33. Eric Anderson says:

    (1)Assign the sides values of 1 and 0.

    (2)Toss the coin 3 times, and record the value as three digits – e.g. 111 or 110 and so on

    (3)Repeat (2) and record again.

    (4)compare the results of (2) and (3) on a column by column basis, and assign either A, B, or C depending on which column is the odd man out, reserving the cases which come up 111 or 000. [So 111 and 110 comes out 001 or C. You will get A, B, and C each occuring 8 times, with 12 left over values]

    (5)of the reserved values, discard the second series.

    (6) of the first series, if the first two columns are both "1", assign a value of "A" [you get 11 4 times]

    (7) else if the first column is 0 assign a value of "B" [ you get this 4 times]

    (8) else if the first column is 1 assign a value of "C" [ you get this 4 times].

    A B and C now all have equal probabilities of occuring. I’m sure there is a more clever way to express this with exponents and roots, but I can’t for the life of me think what it is.

  34. Eric Anderson says:

    I realised I was a little unclear – in (5) when I said discard the second series I meant the number you recorded in step (3), the remainin steps apply only to the number you recorded in step (2)

  35. loc says:

    not 100% sure this is right:

    coin1 coin2

    ———–

    head head => 1

    tail head => 2

    head tail => 3

    tail tail => start over

    there’s a chance for infinity, but it’s only 25% so if it goes on FOREVER, those coins CAN’T BE FAIR

    prove me wrong please.

  36. Andy White says:

    Think of it as a tournament.

    a and b compete until one of them gets heads.

    this "winner" competes against c until one of them gets heads.

  37. loc says:

    ok i’m wrong

  38. loc says:

    Is there another/better solution, anyone?

  39. loc says:

    How about we combine my solution (actually, Ariel found mine in the 1st reply) and Andy White’s? Would that make any difference?

    —————————————

    1. Throw the coin twice.

    2. if throws were "h-h" select ‘A’

    else if throws were "h-t" select ‘B’

    else if throws were "t-h" select ‘C’

    else if throws were "t-t", then:

    – set A=h and B=t

    – throw and select winner

    – set winner=h and C=t

    – throw and select winner

  40. loc says:

    After reading through every answer, it’s really really interesting. Imagine if there’s a website posting a brainteaser everyday and gets educated answers from hundreds of thousands people everyday. Analyzing those answers would be amazingly cool, huh? A correct solution isn’t the best solution, so the more the better! What’s your solution?

  41. Roman says:

    I’ve been reading through the solutions and the "tournament" variation seems the most likely to produce a finite solution:

    Toss 1: A meets B (50%/50%)

    Toss 2: Winner meets C (50%/50%)

    If Winner wins again, no more tosses.

    Toss 3: If C wins, C meets Loser (50%/50%)

    Whoever wins Toss 3, gets it.

    This is a finite loop. All participants have the the odds of winning at 50% each time they play (each plays twice at most), however there is no replay once a winner is decided.

    Given a tie, It revolves around who wins last.

    A & B -> A & C -> A

    A & B -> A & C -> C & B -> C

    A & B -> A & C -> C & B -> B

    A & B -> B & C -> B

    A & B -> B & C -> C & A -> C

    A & B -> B & C -> C & A -> A

    Since there is a variable 2 OR 3 rounds, the 2^N problem is resolved down to 6 possible outcomes, divisible by 3 and 2. A & B Always start.

    I think this is it? Any care for peer review?

  42. JohnFisher says:

    Well, the problem appears to be tied into the probabilities of the combinations appearing. So why not just modify the equation to deal specifically with the probabilities?

    Out of 2 throws, you get something like:

    HH = 25%

    TH or HT = 50%

    TT = 25%

    So, the setup could use weights. When you get HH add a weight of 2 for A. When you get TH or HT add a weight of 1 for B. When you get TT, add a weight of 2 for C.

    Now, you just need to do pair throws for whatever finite number of times makes you happy that the statistics balance out. (Didn’t do the math, but I’m guessing it would be a small number — maybe 10 pair throws?).

    If I’m way off here, could someone tell my why?

  43. loc says:

    when it gets to 50 replies, could you give us a remote hint?

  44. loc says:

    brainteasing resumed, i’m trying to think in a different direction. So how about this?

    Let A=h, B=t.

    With my eyes closed, throw the count and guess whether H/T is selected. If the guess is right, pick C, otherwise, pick whatever the coin selected for you

  45. loc says:

    wait a minute, I’m afraid my brain is biased and would always pick A over B, so let’s just throw a second time and let the 2nd result be my guess (so if both throws yield the same H or T, pick C, otherwise pick the 1st result)

  46. loc says:

    ok, both of my last 2 posts were wrong because C would get 50& chance to be picked

  47. loc says:

    one more try:

    Throw 3 times for A,B,and C.

    If you got 2 heads and 1 tail or 1 head and 2 tails, then pick the single head (or tail)

    Else, play again.

    A-B-C

    ——

    0-0-0 = play again

    0-0-1 = C

    0-1-0 = B

    0-1-1 = A

    1-0-0 = A

    1-0-1 = B

    1-1-0 = C

    1-1-1 = play again

    ok, this is pretty much like the hh,ht,th,tt one…. 25% of infinite

  48. CyrusN says:

    Ed Kaim & Erno: Love your answers πŸ™‚

  49. CyrusN says:

    Daniel: "The mathematical solution is something else again. To get it done mathematically in a finite time just half the time it takes to toss the coin every time you throw it. The fact that that’s impossible in the real world is not relevent because a coin with no bias is also impossible in the real world. "

    We’re talking about the mathematical world here.

    And it’s not time that we’re measuring. We’re asking if the algorithm will "terminate" or not.

    i.e. it’s not valid to say: i have a computer that takes no time to do anything. So no matter what it will always finish immediately, even if it takes infinitely long because it’s an instantaneous computer

    πŸ™‚

  50. CyrusN says:

    We seem to have some differing of opinion on this.

    Some people think that it must be impossible as given any set time that the algorithm must terminate, you cna show that there is a probability (however unlikely that it migth take that long).

    However, others have shown that regardless, it can’t take forever, and thus must eventually end at some point.

    Can these ideas be reconciled. Does either imply the existence of (or lack thereof) of a suitable algorithm that can solve the problem requirements?

  51. loc says:

    i think i got it this time

    a.value = b.value = c.value

    countToException = 0

    do {

    a.face=h

    b.face=t

    if throwCoin()==h then a.value++

    else if throwCoin()==t then b.value++

    //if countToException == 1000 then break

    b.face=h

    c.face=t

    if throwCoin()==h then b.value++

    else if throwCoin()==t then c.value++

    c.face=h

    a.face=t

    if throwCoin()==h then c.value++

    else if throwCoin()==t then a.value++

    }while(a.value==b.value && b.value==c.value)

    return MinOrMax(a,b,c) //take the single one, min or max

    there’s still a chance that a.value== b.value== c.value always. So, I wanted to include the countToException inconveniently to just decide the result btwn a & b.

  52. loc says:

    couldn’t think about the funnel, but i thought about the angle and the milisecond ones, although they would need additional equipments to carry out. and the latest solution was an improvement from Andy White’s a&b-b&c-c&a algo, or so i thought. good night.

  53. damien morton says:

    Ok, so my statistics are very rusty, but its possible that there exists some N, which has the property that for N coin tosses, the bernoulli distrbution of the head count could be partitioned into 3 equal-sized baskets.

  54. damien morton says:

    Hmm – just ran an exhaustive search on possible partitionings of bernoulli distributions for N < 30.

    For N<30, no combination of toss count frequencies sums up to 1/3.

    (its fortunate that python enables unlimited precision maths)

    fact = [1]*100;

    for i in range(1,len(fact)): fact[i] = i * fact[i-1]

    def b2(n,N): return (fact[N], fact[n] * fact[N-n] * N**2)

    def add((n1,d1), (n2,d2)): return (n1*d2 + n2*d1, d1*d2)

    def combsum(c, (a,b), i, N):

    for j in range(i,N):

    c.append(j)

    (x,y) = add((a,b), b2(j,N+1))

    if (y == 3*x): print c

    elif (y > 3*x): combsum(c, (x,y), j+1, N)

    c.pop()

    for N in range(2,50):

    print N

    combsum([], (0,1), 0, N)

  55. wpoust says:

    2 throws are required.

    The first throw is to determine whether its for A or B.

    Event(A|B) -> x

    The second throw is to determine if its the outcome of the first throw or C.

    Event(x|C) -> winner

  56. Andreas says:

    All "tournament" variations of a solution are incorrect since this will give the first two combatants advantage since they will always be given a second chance (in case the loser goes against the third), or disadvantage (in case the winner goes against the third).

    Experiment with a few million tosses will give C a 25% chance of being selected in a tournament where the loser of A and B goes against C. C will be given a 50% chance in a tournament where the winner goes against C.

  57. loc says:

    i implemented my last algo, ran it for a couple million times. The average seemed about right. (exception never occurred)

  58. CyrusN says:

    Loc: Does your algorithm terminate?

  59. loc says:

    at least it did for the last 100 million times i tested. but no, the algo may not terminate in a special case.

    but i’m sure that there’s something else more efficient/simple/elegant than mine

  60. Andy White says:

    In my tournament idea, there are only two "matches" to declare a winner.

    A against B

    Winner against C

  61. loc says:

    Andy, your tournament gives C 50% to win. The regular tournament would be

    A –

    — W1

    B –

    C –

    — W2

    D –

    then W1 vs. W2

  62. Andy White says:

    loc you are right.

    I am worthless.

  63. loc says:

    Andy: my solutions are based on yours =)

    ok cyrus, how about another answer:

    let’s split item b into b1 and b2. you have:

    a,b1,b2,c

    if throwing coin picks head:

    a,b1 wins

    else

    b2,c wins

    throw again to pick winner btwn a,b1 (or b2,c)

  64. loc says:

    man, the previous answer gives B 50% chance.

  65. Raj Kaimal says:

    The coin is tossed once for a, b, c. This is defined as a round.

    For each round, if a or b or c gets a tail, they get eliminated. If no one gets a tail, the round is repeated. For three tosses, there are 8 outcomes and the probability of one outcome containing a tail is 7/8 which is a high probability so eventually, someone will get eliminated.

    The process is repeated with the remaining two members. The probability of one of the rounds containing a tail is 3/4 which again is a high probability which leads to another member being eliminated.

    The remaining member [is the winner] gets picked.

    This is a finite solution since it is a process of elimination. It will not go on forever because the coin is fair sided.

  66. loc says:

    there are 8 outcomes, not 1 but 2 of them are undecided (no tail, and all tails)

    therefore, your solution is the same as the hh,ht,th,tt where tt is "play again"

  67. Raj Kaimal says:

    loc, thanks for pointing that out.

    To make it finite, how about we keep track of how many times each member has thrown tails. If a round repeats, we count how many times they have thrown tails, in previous rounds (with same member count) and whoever has most tails gets eliminated.

    This is the opposite of the source code I posted earlier where whoever has the most heads wins.

    Oh..well.

  68. DrPizza says:

    I don’t see why this thread didn’t end when someone posted the rotational answer. It’s simple and effective and finite.

  69. loc says:

    This is what i had that works. I need to prove it terminates though.

    public static int Pick(Item A, Item B, Item C)

    {

    int count = 0;

    do

    {

    A.Face = 1;

    B.Face = 0;

    if (Program.ThrowCoin()==1)

    A.Value++;

    else

    B.Value++;

    count++; //if (count==1000) break

    B.Face = 1;

    C.Face = 0;

    if (Program.ThrowCoin()==1)

    B.Value++;

    else

    C.Value++;

    C.Face=1;

    A.Face=0;

    if (Program.ThrowCoin() ==1)

    C.Value++;

    else

    A.Value++;

    }

    while(A.Value==B.Value && B.Value==C.Value);

    return MinOrMax(A, B, C);

    }

  70. Slusky says:

    I can prove that that could not terminate: if Program.ThrowCoin() always returns 1, then you’ll never break out of the while loop. QED.

    Sigh… I know I’ve ranted a bit about the CS curriculum of our alma mater being too focused on theory at the expense of actual programming, but now I see some wisdom in it.

  71. CyrusN says:

    Slusky: "I can prove that that could not terminate: if Program.ThrowCoin() always returns 1, then you’ll never break out of the while loop. QED. "

    Can Program.ThrowCoin always return 1?

  72. CyrusN says:

    DrPizza: "I don’t see why this thread didn’t end when someone posted the rotational answer. It’s simple and effective and finite. "

    because it measures properties that aren’t available on the coin provided. All you can do is flip it and find out if it was heads or tails.

  73. CyrusN says:

    Loc: "This is what i had that works. I need to prove it terminates though. "

    Does it terminate?

  74. loc says:

    It does terminate. The only ways it doesn’t is when ThrowCoint() returns:

    1 1 1, 1 1 1, …

    or

    1 1 1, 0 0 0, …

    or

    0 0 0, 0 0 0, …

    For case 1 and 3, it doesn’t seem like the coin is perfectly fair.

    For case 2, you might argue that it seems FAIRER over 6 throws, but 3 same results in a row proves the coin is not PERFECTLY fair. oooh my reasoning in this part is not very strong…

  75. loc says:

    No, actually Ariel got it right in the very first reply:

    HH -> 1

    HT -> 2

    TH -> 3

    TT -> play again

    It is finite because if it doesn’t terminate then the outcomes will always be Tail, which is not possible for a FAIR coin.

    Final answer.

  76. CyrusN says:

    Loc: "It is finite because if it doesn’t terminate then the outcomes will always be Tail, which is not possible for a FAIR coin.

    Final answer. "

    So when does it terminate?

  77. loc says:

    Since the coin is precisely fair, it terminates within 4 rounds

  78. loc says:

    never mind that answer, that’s my 1st thought when i woke up today.

    how about within 8 rounds (16 throws)

  79. CyrusN says:

    Loc: In 8 rounds (presuming 2 flips per round), it’s completely possible with a fair coin to get:

    t t t t t t t t t t t t t t t t

    There’s a: 1/(2^16) chance of that happening. Unlikely, sure, but it’s still quite possible that with your algorithm it won’t terminate within that number of throws.

    Remember, a "fair" coin doesn’t mean: "given 2n tosses of the coin, n must be heads and n must be tails". It means that given any toss of the coin (which *is* independent of any other toss), there’s an equal chance of heads or tials coming up.

  80. DrPizza says:

    "because it measures properties that aren’t available on the coin provided. All you can do is flip it and find out if it was heads or tails. "

    But that’s not what the question says!

    Perhaps you do not have a coin at all but rather a disc with each side painted a different uniform colour?

  81. damien morton says:

    Pizza – the coin is fair as far as coming up heads or tails goes. Its fairness as far as rotation goes is unknown.

    Cyrus – does this puzzle have a solution? Seems to me that it doesnt.

  82. Radu Grigore says:

    I had the same solution as Ariel. You can easily show that the answer will pop out in an expected number of 24 throws, with a standard deviation of about sqrt(1200)=36.641 (unless, I made a mistake πŸ™‚ ).

    It is possible for this algorithm not to terminate, even if the probability of this event is zero. (probability(event) == 0 does NOT mean it is impossible).

  83. loc says:

    So my precision is only up to 0.0000152587890625. But the algorithm is obviously converging, so it can terminate.

    http://en.wikipedia.org/wiki/Termination :

    "In essence, the problem is that an algorithm for computing a real number to infinite precision would never terminate. However, practical algorithms can all be shown to converge, thus, they can be made to terminate simply by accepting a limit on the achievable precision of the computation."

  84. Rik Hemsley says:

    To those who think it’s fine to have an algorithm which usually terminates ‘quickly’ (within a few hundred throws), it’s not.

    If the possibility of your algorithm taking over million throws is one in a million, and you run it a million times a day (this happens with software, you know?) then, on average, once a day, you’ll have to sit and wait for over one million throws.

    Of course the coin toss is just an example: we could be talking about an algorithm which needs to communicate over TCP, hit a database, or even simply cause a context switch.

    If the algorithm has a terrible worst case run time, then you could be in trouble. That’s why it’s important to find algorithms which can be proven to terminate within finite time.

    Thanks for the illustration Cyrus.

  85. Radu Grigore says:

    Rik, of course you are right. But your analysis is of a different algorithm complexity.

    In this case, if a flip takes one microsecond then you’ll have to run the algorithm about 1000…00 times – with 666666 zeros — to see a runtime greater than one second. In other words, you’ll need to wait for the universe to die, unless you are really unlucky.

  86. damien morton says:

    Of course, you can also bound the number of trials:

    string choose()

    {

    for (int i = 0; i < 1000; i++)

    switch (flip()<<1 | flip())

    {

    case 0: return "A";

    case 1: return "B";

    case 2: return "C";

    }

    return "C";

    }

    Guaranteed to terminate, fair to 1 part in 4**1000, i.e. more fair than any possible feat of physical engineering could possibly achieve, and more fair than any statisical measure could possibly detect.

    Remember that the coin is fair, so that means that saying "what if the coin always comes up heads" is changing the premise to test the algorithm. If the coin always comes up heads, then there is no possible algorithm that can produce a fair result.

  87. Robert Kozak says:

    1. Assign each of the sets a value. A B and C.

    2. Arrange these values into an array of each combination. {ABC, ACB, BAC, BCA, CAB, CBA}

    3. flipping coins 100 times and sum the Heads.

    4. Take a mod 6 of this sum and use that as an index into the array to get a combination.

    5. flip coins another 100 times and sum the heads.

    6. Take a mod 3 of this sum and use that as an index into the selected set to get the final value for the set.

    — Robert

  88. Radu Grigore says:

    Robert, there are two problems with your approach, one serious and one not so serious.

    (1) You assume that summing how many times heads appeared gives you a uniform distribution. It does not: the distribution is binomial, so you’d favor BAC and BCA and disfavor ABC and CBA.

    (2) If you have a uniform variable in the interval 0..M-1 you won’t get a uniform variable in the interval 0..N-1 (with N<M) if you take modulo N. Unless N is a divisor of M.

    And it’s too complicated :p

  89. David says:

    Flip the coin 3 times, assign heads=1 and tails=0

    Place the result of the first toss in the 4’s bit, the second in the 2’s bit and the third in the 1’s bit to get a decimal number between 1 and 8, called T.

    T is the number of times you will again flip the coin. Again assign heads=1 and tails=0, but now ADD your results to get S, a number between 0 and 36.

    The result is S % 3.

  90. Steven says:

    David, T would be a number from 0..7. So you’d need to add one first.

    The problem lies with S, though. Adding your results for T flips with H=1 and T=0 would give a number ranging from 0..T-1, not 0..36.

    Finally, 0..36 has 37 items, which is not divisible by 3.

  91. Steven says:

    Oops, that’s 0..T, not 0..T-1.

  92. Derek says:

    I’m with johnfisher,

    tt-25%

    ht or th-50%

    hh-25%

    Assign tt-a, ht or th-b, and hh-c.

    Any time a tt or hh comes up, give a or c 2 points and any time a th or ht comes up give b 1 point. This is statistically fair and simple. After reading all posts and seeing the flaws in all of them, I have to say this is the best solution.

  93. Andreas says:

    Derek and JohnFisher

    The problem with your solution is that it runs the risk of never giving a final answer. What if, after your finite number of throws, two or all alternatives have the same score?

  94. playersnoopy@yahoo.com says:

    ok… I sorta give up… so I’m gonna sorta cheat. While it says "uses said coin in order to pick any one of those items with equal probability", it doesn’t say the coin has to be the direct result of either A, B or C. So I’m suggesting using the coin to populate a data set and pick from that. So flip the coin and assign them values so there are an equal amount of ABCs and generate a random number, of course now you’re left w/ the random number generator.

    hh a

    ht b

    th c

    tt a

    hh a

    ht b

    th c

    tt b

    hh a

    ht b

    th c

    tt c

    you can now either generate a numer 1-12 and pick which of the 12. Now the coin would still be "fair" but the random number generator might not :p

    I NEED REST!!! WHERE’S THE ANSWER!!!

  95. DanT says:

    Gonna have to go with playersnoopy on the whole "where’s the answer" business. You’ve had you fun, watching us squirm. Now we demand recourse :p.

  96. loc says:

    Cyrus, if you do have the solution that ever halts (although i’m leaning toward that it doesn’t), don’t give it out yet. one more day. I can’t remember a puzzle that struggles me this long. Maybe I’ve lost "it".

  97. J Whattam says:

    You can have an effectively 3 sided die by marking two faces of a die with ‘a’, two faces with ‘b’ and two faces with ‘c’.

  98. loc says:

    I still like the hh,ht,th,tt one, with an improvement: if tt the first time give bonus 1 point, if next round is aslo tt, give bonus 2 pts, if the 3rd round is also tt, give bonus 3 pts. now the result will be decided by the bonus pts mod 3.

    Can anyone prove that the bonus system is not fair?

    ==================================

    bonus = 0

    result = ThrowTwice();

    if (result==tt){

    bonus = 1;

    result = ThrowTwice();

    if (result==tt){

    bonus = 2;

    result = ThrowTwice();

    if (result==tt){

    bonus = 3;

    }

    else { return DECIDED_RESULT; }

    }

    else { return DECIDED_RESULT; }

    }

    else { return DECIDED_RESULT; }

    return bonus % 3;

  99. loc says:

    Just a tweak

    bonus = 0

    result = ThrowTwice(); //can be 0, 1, 2, or 3

    if (result==3){

    bonus = 1;

    result = ThrowTwice();

    if (result==3){

    bonus = 2;

    result = ThrowTwice();

    if (result==3){

    bonus = 3;

    }

    else { return result % 3; }

    }

    else { return result % 3; }

    }

    else { return result % 3; }

    return bonus % 3;

  100. loc says:

    never mind, bonus will be just 3…

    what am i thinking? it won’t keep me awake tonight anymore.

  101. DodgyRabbit says:

    The solution involves a 2 step process (i.e. finite).

    Let’s say we have 3 candidates, A, B and C. We want to use the coin to randomly select one of them.

    Round 1: Elimination Round

    Throw the coin twice. Possible outcomes:

    HH HT TH TT

    If HH or HT, candidate A goes through

    If HT or TH, candidate B goes through

    If TH or TT, candidate C goes through

    As you can see, two random candidates will go through to round 2

    Round 2: Select Winner

    Now it’s trivial. You have two candidates to select from, and a coin that can choose for you.

  102. DodgyRabbit says:

    The solution involves a 2 step process (i.e. finite).

    Let’s say we have 3 candidates, A, B and C. We want to use the coin to randomly select one of them.

    Round 1: Elimination Round

    Throw the coin twice. Possible outcomes:

    HH HT TH TT

    If HH or HT, candidate A goes through

    If HT or TH, candidate B goes through

    If TH or TT, candidate C goes through

    As you can see, two random candidates will go through to round 2

    Round 2: Select Winner

    Now it’s trivial. You have two candidates to select from, and a coin that can choose for you.

  103. damien morton says:

    Dodgy – if you throw HH or TT, only one candidate will go through, and the probabilities of selecting a/b/c arent fair.

    Do they not teach basic statistics in school these days? Im asking, because it seems that so many people throwing out solutions to this question are making very basic mistakes.

  104. DodgyRabbit says:

    Doub! Found an obvious problem. If HH or TT then only one candidate goes through. πŸ™

  105. DodgyRabbit says:

    How silly of me. Even if you *could* select two members at random for elimination, you’ve already solved the problem. The remaining candidate might aswell be the winner.

    Show us your 10c damien or are you risking making a basic mistake?

  106. Sam Meldrum says:

    DodgyRabbit: A and C can win at first round, B cannot. Your system is not giving equal weight to each candidate.

  107. Sam Meldrum says:

    Cyrus, I don’t think your understanding of the definition of the word Algorithm is correct. An algorithm doesn’t have to terminate in finite time.

    i.e. "a finite set of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a corresponding recognizable end-state"

    "A finite set of well-definied instructions" means that the set of instructions is finite not that the time taken is finite.

    In the first comment, the set of instructions is 4, not infinite.

    The probability of this never terminating tends to zero.

    However, that problem is not interesting. The interesting one is the one that definitely terminates in finite time.

  108. damien morton says:

    Dodgy – appologies for seeming to direct my statistics question at you – it was a more general observation.

    I actually did give an answer above, but I had to redefine ‘fair’ to be ‘fair within some tolerance’ in order to do it.

    So your elimination aproach can be modelled as throwing two coins followed by a third, where sometimes the third coin toss is irrelevant, for a total of 3 coin tosses. Heres how your algorithm breaks down:

    HHH: A

    HHT: A

    HTH: A

    HTT: B

    THH: B

    THT: C

    TTH: C

    TTT: C

    As you can see, given an equal probability of any of those 8 choices coming up, the choice of A, B, or C is made in a ratio of 3:2:3.

    As far as I can tell, theres no exact solution to this problem. No matter how many coin tosses you make, any given sequence of toss results or combination of sequences of toss results will have a probability that is expressed as n/N^2, where n is any number, and N is the number of tosses. n/N^2 != 1/3 for any integer n or N.

  109. loc says:

    Would a probability of 1/2.99999..9 instead of 1/3 be acceptable?

    Say you have 2a,2b,2c

    if head

    {

    2a and 1b win

    if head

    {

    a wins

    }

    else

    {

    b and a/2 win

    if head

    {

    b wins

    }

    else

    {

    a/2 and b/4 win





    //converging until the denominator is the largest number possible

    }

    }

    else

    {

    2c & 1b win

    ….

    //symetric with the if-true case

    }

  110. loc says:

    I know that wasn’t very clear. Does anyone know what i’m getting at? Can anyone explain it better?

    16a,16b,16c

    if head then you take 16a and 8b. (else you take 8b and 16c then GOTO ELSE_CASE )

    if head again you take 8b and 4a. (else you take 12a which is winner)

    if head you take 4a and 2b. (else take 6b which decides winner.)

    if head you take 2b and 1a. (else take 1.5b as winner

    if head you take 1a and 0.5b (else take 0.75b as winner)

    if head you take 0.5b and 0.25a (else take .5b as winner)

    if head you take 0.25a and 0.125b (else take .25a as winner)

    if head you take 0.125b and 0.0625 (else take 0.125b as winner)





    keep on going until the number gets small enough. it can’t be infinite because it’s converging.

    ELSE_CASE:

    exactly like above, except it’s between 1b and 2c instead.



  111. loc says:

    a,b,c

    if head then you take a and b/2 (else you take b/2 and c then GOTO ELSE_CASE )

    if head again you take b/2 and a/4. (else you take 3a/4 which is winner)

    if head you take a/4 and b/8. (else b wins)

    if head you take b/8 and a/16. (else a wins)

    if head you take a/16 and b/32 (else b wins)

    if head you take b/32 and a/64 (else a wins)

    if head you take a/64 and b/128 (else b wins)

    if head you take b/128 and a/256 (else a wins)





    keep on going until the number gets small enough to be neligible. it can’t be infinite because it’s converging.

    ELSE_CASE:

    exactly like above, except it’s between b/2 and c instead.

  112. TimW says:

    Flip coin 3 times. Head is worth 2, Tails is worth 1.

    For the first 2 flips you have 4 possibilities. Multiply the values together.

    HH = 4

    HT = 2

    TT = 1

    TH = 2

    For all 3 flips, run through this equation

    (flip1 * flip2) – flip3

    HHH = 2

    HHT = 3

    HTH = 0

    HTT = 1

    THH = 0

    THT = 1

    TTH = -1

    TTT = 0

    So, there are 12 possibilities with 3 flips.

    #times possible

    -1 = 1

    0 = 3

    1 = 3

    2 = 3

    3 = 1

    4 = 1

    Set A = -1 or 0

    Set B = 1 or 3

    Set C = 2 or 4

    After 3 flips, you either have a winner or 2 winners.

    If 2 winners, flip 1 more time where heads = winner 1 and tails = winner2.

    So, you end after 3 or 4 flips.

    Next question please.

  113. Smarmy says:

    TimW:

    Given your algorithm, here are the percentages of probable victory:

    Winner of first two tosses:

    A – 0%

    B – 25%

    C – 75%

    Winner of the three tosses:

    A – 50%

    B – 37.5%

    C – 12.5%

    Overall A only has a 25% chance of making it to the contest. B has a 31.25% chance of making it to the contest, and C has a 43.75% chance of making it to the contest. The odds are not fair at all in this scenario.

    I also figure there is more going wrong when you consider the fact that A can never win outright while both B and C can. It’s been too long since I worked on any of this for me to figure it out off the top of my head.

    Run the code and see for yourself:

    #include <iostream>

    #include "assert.h"

    #include "time.h"

    using namespace std;

    void main()

    {

    srand((unsigned int)time(0));

    unsigned int aWinner[3];

    aWinner[0] = 0;

    aWinner[1] = 0;

    aWinner[2] = 0;

    for (unsigned int i = 0; i < 10000000; i++)

    {

    unsigned int uiCoin1 = (rand() % 2);

    unsigned int uiCoin2 = (rand() % 2);

    unsigned int uiCoin3 = (rand() % 2);

    unsigned int uiCoin4 = (rand() % 2);

    int iFirstResult = (uiCoin1 + 1) * (uiCoin2 + 1);

    int iSecondResult = iFirstResult – (uiCoin3 + 1);

    unsigned int uiFirstWinner = 0;

    unsigned int uiSecondWinner = 0;

    switch (iFirstResult)

    {

    case -1:

    case 0:

    { uiFirstWinner = 0;

    break; }

    case 1:

    case 3:

    { uiFirstWinner = 1;

    break; }

    case 2:

    case 4:

    { uiFirstWinner = 2;

    break; }

    default:

    { assert(0); }

    }

    switch (iSecondResult)

    {

    case -1:

    case 0:

    { uiSecondWinner = 0;

    break; }

    case 1:

    case 3:

    { uiSecondWinner = 1;

    break; }

    case 2:

    case 4:

    { uiSecondWinner = 2;

    break; }

    default:

    { assert(0); }

    }

    if (uiFirstWinner == uiSecondWinner)

    {

    aWinner[uiFirstWinner]++;

    }

    else

    {

    aWinner[uiCoin4?uiFirstWinner:uiSecondWinner]++;

    }

    }

    cout << "A won " << aWinner[0] << " times." << endl;

    cout << "B won " << aWinner[1] << " times." << endl;

    cout << "C won " << aWinner[2] << " times." << endl;

    }

  114. TimW says:

    Smarmy: Ah, but the 2 tosses are within the 3 tosses. therefore, you have 12 possibilities with 3 tosses instead of 8.

    A can win 4 ways, B can win 4 ways, C can win 4 ways.

    πŸ˜‰

  115. srcurrie says:

    TimW, each can win in 4 ways, but each of those ways does not have equal probability.

    This is impossible to do with a bounded number of flips. Here is a proof:

    Using Cyrus’s definition of algorithm, we must be able to select from a, b, and c using a bounded number of flips.

    Let N be the upper bound of the number of flips required for our input size of 3 (i.e. the 3 items a,b,c).

    Let x = x_1, x_2, …, x_n be the sequence of heads or tails values produced by flipping the coin N times.

    Let f(x) be any algorithm that takes as input an N length sequence of heads or tails values to produce an output of a or b or c.

    Since each element of x has two possible values and x has N elements, we know that there are 2^N possible values for the entire sequence x. Furthermore, since a fair coin is deciding the value of each element of x with equal probability for heads or tails, we know that the probability of any one of these 2^N sequence values occurring must be 1/(2^N).

    The probability of any output (a or b or c) occurring is equal to the sum of the probabilities of the inputs to f(x) that produce that output. Since all inputs have a probability of 1/(2^N) and since any finite sum of such probabilities can never be 1/3 (I can prove this separately if anyone doesn’t believe me), there is no bounded time algorithm that can use a fair coin to fairly select among three options.

    -Scott

  116. Smarmy says:

    TimW:

    You are right, since the results of the 3 toss round are dependent on the results of the 2 toss round, the actual probabilities are different than I suggested:

    Listed are the possible tosses enumerated with the winners of the 2 toss and 3 toss respectively:

    HHH = C C

    HHT = C B

    HTH = C A

    HTT = C B

    THH = C A

    THT = C B

    TTH = B A

    TTT = B A

    C will win 43.75% of the time, B will win 31.25% of the time and A will win only 25% of the time. The probabilities are not at all equal.

    Though all this is meaningless because I think Scott and Dan are right that there is no correct answer.

  117. Smarmy says:

    And by different I mean exactly the same. πŸ™‚

  118. loc says:

    Scott, I agree that 2^N % 3 will always be 1 or 2, for all N. But my point is that (2^N)/3 will get large enough such that 1/((2^N)/3) can be neligible. In theory, it can’t be achieved. But in real life, I would tolerate a fairly fair solution.

  119. CyrusN says:

    Loc: "Scott, I agree that 2^N % 3 will always be 1 or 2, for all N. But my point is that (2^N)/3 will get large enough such that 1/((2^N)/3) can be neligible. In theory, it can’t be achieved. But in real life, I would tolerate a fairly fair solution. "

    If you’re willing to tolerate the fairly fair solution, then

    while (true) {

    …Side flip1 = coin.Flip();

    …Side flip2 = coin.Flip();

    …if (flip1 == Side.Head && flip2 == Side.Head) {

    ……return Choice.A;

    …} else if (flip1 == Side.Head && flip2 == Side.Tail) {

    ……return Choice.B;

    …} else if (flip1 == Side.Tail && flip2 == Side.Head) {

    ……return Choice.C;

    …}

    }

    this will be quite fair. And the expected time to terminate is quite low.

    Ask yoursefl this: what is the expected number of flips/rounds, until this finishes?

  120. loc says:

    Cyrus, that solution has perfectly equal probability, but its problem is termination.

    Now let’s modify it a little bit:

    for (int counter=0; counter< 64; counter++){

    …Side flip1 = coin.Flip();

    …Side flip2 = coin.Flip();

    …if (flip1 == Side.Head && flip2 == Side.Head) {

    ……return Choice.A;

    …} else if (flip1 == Side.Head && flip2 == Side.Tail) {

    ……return Choice.B;

    …} else if (flip1 == Side.Tail && flip2 == Side.Head) {

    ……return Choice.C;

    …}

    }

    return A; //last line

    you see, the last line gives A an extra 1/2^128 chance of winning over B and C. Which to me is still a "fairly fair" solution.

  121. loc says:

    "But in real life, I would tolerate a fairly fair solution. "

    By that I mean the more recent solution I came up with (the "if head then you take a and b/2, else you take b/2 and c" one), which does terminate although the probability is slightly just a little off.

  122. srcurrie says:

    To answer Cyrus’s question:

    Cyrus asked for the expected value of the random variable whose values are the number of trials required for the non-bounded algorithm (i.e. the Las Vegas Algorithm) to terminate. The answer is 4/3 trials (i.e. 1 1/3) trials. Note that this value carries the caveats that expected values normally do. See Wikipedia for a decent treatment of these issues.

    Showing work for expected value calculations in blog comments is hard since I am limited by the medium in my ablity to write mathematical formulas (unless I embed links to images, which I won’t be doing). So please bear with me.

    Let X be the random variable of the number of trials of the Las Vegas Algorithm required for it to terminate. Then let EV(X) be its expected value. Let SUM(exp, var, low, high) be the sum of the values of expression "exp" when we set variable "var" from "low" to "high". For example, SUM(x, x, 1, n) is the familiar sum with a value of n(n+1)/2.

    We know that EV(X) is equal to the sum of all values of X multiplied by their respective probabilities. We also know that X can have any positive integer value. Consequently,

    EV(X) = SUM(x*p(x),x,1,infinity)

    We need an expression for p(x). To terminate on iteration x, that means that we have to get one of the 3 terminating flip cominations on that iteration (HH, HT, or TH from Cyrus’s code) and the non-terminating flip combination on all previous iterations (TT from Cyrus’s code). Since each combination occurs with probability 1/4, this translates to:

    p(x) = (3/4)*(1/4)^(x-1)

    p(x) = 3*(1/4)*(1/4)^(x-1)

    p(x) = 3*(1/4)^x

    Plugging our p(x) back into our expected value calculation, we obtain:

    EV(X) = SUM(x*3*(1/4)^x,x,1,infinity)

    The 3 is constant across all terms, so we can factor it out:

    EV(X) = 3*SUM(x*(1/4)^x)

    The infinite sum that we have now converges to a well-known closed form solution. Specifically:

    SUM(x*k^x,x,1,infinity) = k/(1-k)^2, for all |k| < 1

    I will leave it as an exercise for the reader to prove that this is true, if you don’t believe me.

    Plugging this back into our expected value calculation, we obtain:

    EV(X) = 3*(1/4)/(1-(1/4))^2

    EV(X) = 3*(1/4)/(3/4)^2

    EV(X) = 3*(1/4)/(9/16)

    EV(X) = 3*(1/4)*(16/9)

    EV(X) = (3*16)/(4*9)

    EV(X) = 4/3

  123. srcurrie says:

    "But in real life, I would tolerate a fairly fair solution."

    loc, it doesn’t matter what you would tolerate in real life. Cyrus is the one asking the question. πŸ™‚

    While it is framed as a toy problem, building algorithms that can do this is very important in cryptography and several other fields. I think that Cyrus’s point here is to get people to think deeply about what is and isn’t possible. That means being rigorous about what is asked for and is being delivered. Is a bias of 1/2^128 acceptable? I don’t know, since I don’t know what the application is, but being upfront about the bias enables you to decide. Is an unbounded algorithm with an expected iteration count of 4/3 (i.e. 8/3 flips) acceptable? I don’t know, but understanding the runtime characteristics of the algorithm is the first step to finding out.

    Cyrus originally asked for a fair (not fairly fair) bounded time algorithm. I proved that he can’t have that, because it is impossible.

    Then we came to a question about unbounded time algorithms and expected value. I derived the required EV.

    The third option is to accept a biased selection algorithm that runs in bounded time. Have we been rigorous enough about the characterstics of that option? What questions should we be asking and what are the answers to those questions?

    -Scott

  124. srcurrie says:

    "But in real life, I would tolerate a fairly fair solution."

    loc, it doesn’t matter what you would tolerate in real life. Cyrus is the one asking the question. πŸ™‚

    While it is framed as a toy problem, building algorithms that can do this is very important in cryptography and several other fields. I think that Cyrus’s point here is to get people to think deeply about what is and isn’t possible. That means being rigorous about what is asked for and is being delivered. Is a bias of 1/2^128 acceptable? I don’t know, since I don’t know what the application is, but being upfront about the bias enables you to decide. Is an unbounded algorithm with an expected iteration count of 4/3 (i.e. 8/3 flips) acceptable? I don’t know, but understanding the runtime characteristics of the algorithm is the first step to finding out.

    Cyrus originally asked for a fair (not fairly fair) bounded time algorithm. I proved that he can’t have that, because it is impossible.

    Then we came to a question about unbounded time algorithms and expected value. I derived the required EV.

    The third option is to accept a biased selection algorithm that runs in bounded time. Have we been rigorous enough about the characterstics of that option? What questions should we be asking and what are the answers to those questions?

    -Scott

  125. loc says:

    Scott, I fully aware that he asked for a perfectly fair solution. I had admitted that it’s not possible to come up with.

    My last solution is just kind of a bonus answer outside of his question, like "hey since we can’t do it, maybe we can do this (if we ever had to) because it’s very close to what you asked". =)

  126. loc says:

    By the way, I really like the helpful posts you have contributed, Scott.

  127. MaLio says:

    Hi

    what about converting the results from heads/tails trial to an int? [as in SelectNextItem() below]. The test code I left in as I used it for evaluation, and the chances of a, b or c beeing selected should be very close to equal (that is of course if I am not mistaken ;-). Termination is guaranteed after 8 ‘flips’ in this code.

    MaLio

    namespace HeadsTailsOutcomes {

    /// <summary>

    /// Summary description for SelectionTest.

    /// </summary>

    class SelectionTest {

    // number of distinct items

    private const int NUM_ITEMS = 3;

    // number of iterations for testing

    private const int NUM_ITERATIONS = 100000;

    // random number generator

    private static System.Random _Random = new System.Random();

    /// <summary>

    /// Main

    /// </summary>

    static void Main(string[] args) {

    int[] items = new int[NUM_ITEMS];

    for (int iteration = 0; iteration < NUM_ITERATIONS; iteration++) {

    items[SelectNextItem()]++;

    }

    for (int index = 0; index < NUM_ITEMS; index++) {

    System.Console.WriteLine("{0} has {1}", index, items[index]);

    }

    System.Console.WriteLine();

    System.Console.ReadLine();

    }

    // SelectNextItem

    public static int SelectNextItem() {

    int evaluator = 0;

    for (int i = 1; i < 9; i++) {

    if (IsHeads) {

    evaluator |= (1 << i);

    }

    }

    return evaluator % NUM_ITEMS;

    }

    // IsHeads

    private static bool IsHeads {

    get {

    return ((_Random.Next(int.MaxValue) % 2) == 0);

    }

    }

    }

    }

  128. CyrusN says:

    And scott wins the internet.

  129. MaLio says:

    Was I right? I’m most curious …

    MaLio

  130. damien morton says:

    Malio – yes, your algorithm is basically correct (though your code is awkward – using a property IsHeads instead of a function is bad style).

    Flip a coin N times to create an N bit integer, then mod 3 to determine which of the 3 choices are selected. One choice will be advantaged by one part in 2^N.

    Contrast this with the probablistic approach, which does pairs of flips to create numbers in the range 0..3, and terminates when a number in the range 0..2 is created. This requires an average of 8/3 coin flips to produce a result, and is fair to one part in 4^N, where N is the limit to the number of flip pairs you are prepared to consider. The average number of flips requied for a result is independant of the limit N, where N is large.

  131. CyrusN says:

    Final Answer:

    There is no bounded time algorithm for that can be used to pick a item with 1/3 probability given a fair coin. However, what’s interesting is that the formal definition of an algorithm doesn’t state whether an algorithm be bounded or unbounded. It simply states that it must terminate.

    To be quite specific, an algorithm will terminate if it does not take infinite time. (i.e. it takes finite time).

    So it’s important to distinguish bounded/unbounded and finite/infinite.

    In this case, the solutions provided present an unbounded *finite* solution to the problem.

    As scott astutely pointed out. The fun behind this problem is trying to think deeply about the problem and to be rigorous in coming up with a solution.

    It is also interesting to think about the actual implementations as well though and to consider if they woudl be viable. And, as scott excellently showed. The *expected* number of rounds necessary for this to terminate is 4/3s.

    So it would be quite simple to take any of these algorithms, convert them to actual code, and expect them to work excellently in practise. In the end, the expected big-O is O(4/3) (i.e. O(1)), and you really don’t get much better than that when coming up with real world algorithms.

    Hope you guys had fun and found it as much of a mind bender as i did.

  132. loc says:

    The Search feature on the upper right hand corner doesn’t work. Searching for "problem" resulted in 7 pages, which all looked the same somehow. But then there’s Google.

  133. loc says:

    confirmed. paging doesn’t work for any search

  134. Kristof Verbiest says:

    You ask for equal probability, not for being random.

    I propose this algorithm:

    1) select A

    2) select B

    3) select C

    4) goto 1

    You can use the coin to buy a soda.

  135. herbie says:

    The algorithm may actually take infinite time. There is no guarantee that a fair coin will ever come up heads, for example, even after an infinite number of tosses.

  136. CyrusN says:

    Herbie: Nope. The algorithm cannot take infinite time. It will always be finite and it will always terminate.

    however, the time it takes is not bounded. There’s a difference.

  137. herbie says:

    In an infinite sequence of coin flips, you may never see a terminating result, thus the algorithm will never terminate. Am I missing something here?

  138. herbie says:

    Sorry for the bluntness of the previous post, and perhaps I am misunderstanding your claim. I do agree that the algorithm is unbounded. I do not agree that it always terminates. Do you mean that the algorithm will "certainly" terminate (every outcome of coinflips will cause it to terminate), or that it will "almost certainly" terminate (the probability of termination is 1)?

  139. CyrusN says:

    Herbie: "In an infinite sequence of coin flips, you may never see a terminating result, thus the algorithm will never terminate. Am I missing something here?"

    In an infinite sequence of coin flips you *will* see a terminating result. πŸ™‚

    "Sorry for the bluntness of the previous post, and perhaps I am misunderstanding your claim. I do agree that the algorithm is unbounded. I do not agree that it always terminates. Do you mean that the algorithm will "certainly" terminate (every outcome of coinflips will cause it to terminate), or that it will "almost certainly" terminate (the probability of termination is 1)? "

    No, there is no probability going on. (well, not strictyly true. there is probability, but it’s just uninterestingly: 1). The other place where probability came in is in the *expected* number of rounds necessary for it to terminate: 4/3

    What is going on is that even in this perfect math world, it is provable (and has been done so in posts here) that the algorithm cannot take finite time to end. And, as has also been stated, a non-infinite (and thus finite) operation suffices for the term "algorithm".

    What can also be shown is that you cannot state the bound on the algorithm. I.e. if you say that it will end in N steps, one can show that there is a probability (albeit low) that the algorithm might end up taking more than N steps. However, despite being bounded, it is still finite.

    Remember, there is space between unbounded and infinite πŸ™‚

  140. herbie says:

    Hmmm, after that post I’m starting to think more and more that I am confusing your terms. This paper (pages 7 and 8) better illustrate my questions <a href="http://www.cl.cam.ac.uk/users/jeh1004/research/talks/termination-talk.pdf">http://www.cl.cam.ac.uk/users/jeh1004/research/talks/termination-talk.pdf</a&gt;.