Answer to the Friday Puzzle….

70

coverOn Friday I set this puzzle.  If you have not tried to solve it, have a go now.  For everyone else the answer is after the break.

Imagine that you have a coin that is biased – that is, in a long series of tosses it won’t come up with 50% heads and 50% tails.  Alas, you don’t know the extent of the bias.  How can you use the coin to generate a random series of zeros and ones?

The sequence Heads-Tails is as likely as Tails-Heads, no matter the extent of the bias.  And so you toss the coin twice for each trial.  You ignore the Heads Heads and Tails Tails sequences, and assign a 1 to Heads Tails, and a 0 to Tails Heads.  That way, you will generate a random sequence of 1s and 0s from a biased coin.  Did you solve it? Any other answers?

I have produced an ebook containing 101 of the previous Friday Puzzles! It is called PUZZLED and is available for the Kindle (UK here and USA here) and on the iBookstore (UK here in the USA here). You can try 101 of the puzzles for free here.

70 comments on “Answer to the Friday Puzzle….

  1. Roland says:

    If the coin is extremely biased, and e.g. only ends up with heads, this method will not work.

    You might try this: add a sign (dot/line) on the edge of the coin on both sides. Next twist the coin really hard, or throw it up sufficiently high, and when the sign ends up in the top half part, consider it a 1, when it ends up in the bottom end, consider it a 0.

    • Bob O'H says:

      No, it will still work, but it’ll take longer: if the probability of a head is p the mean number of tosses to get a number is 1/(p(1-p)).

    • Ken Haley says:

      Bob O’H: If it never lands tails then p = 1, and 1-p = 0 (p = probablility of heads), and your formula results in division by zero. Can’t really say “it will still work” in that case. However, I think this condition denies the premise. Although biased, the coin must have a non-zero probability of landing heads as well as tails in order for there to be a reasonable solution without doing something like Roland suggests (marking the coin, or whatever).

    • ctj says:

      this won’t work because you don’t know the extent of the bias of the coin. you are assuming that the weight distribution of the coin is radially symmetric.

    • Barry Goddard says:

      Saying something “will not work” is different from saying that it “will work, but only if you keep at it for a long time”. It still does work.

      To the poster about the radially symmetric weight distribution, it does not matter. The chance of a 2-toss pair coming up H-T is exactly the same as the pair coming up T-H. Go do the math, it’s simple probability.

  2. The Masked Twit says:

    Didn’t we have a similar problem a while ago featuring the black and red cards in a pack?
    5 minutes

  3. slugsie says:

    Maybe I’m missing something, but 11111111 is just as random as 00000000, which is just as random as 01101000. In a truly random system each of those outcomes is just as likely.

    Unless the bias is extreme (and as such you would really notice after a few coin tosses), or you need a very long sequence, then just tossing it would probably be good enough for most purposes.

    • Richard M says:

      Slugsie, the problem is that it is not truly random – if it was, it would be 50/50. If it’s 90/10, then getting 11111111 is 0.9^8 and 00000000 is 0.1^8 and you can appreciate the difference in probabilities.

    • One Eyed Jack says:

      Actually, slugsie is on to something that Richard overlooked, but misses just slightly.

      Randomness does not require equal probability. Simply because the frequency of heads or tales (or 1 and 0) are not equal does not make the distribution non-random. It only makes it biased.

      You cannot predict that the next toss will be heads or tails. All you can do is assign a probability. The results still remains random.

      Richard’s solution provides a method to achieve 50/50 probability, but simply flipping the biased coin still produces a random (albeit biased) distribution.

      It is a common mistake to equate random with equal distribution.

    • The Masked Twit says:

      I think Mr (or is it Mrs?) Slugsie is correct.
      Random is not the same as evenly distributed.

  4. ChrisR says:

    My solution was rather like Roland’s – spin the coin (preferably on a sheet of lined paper) and if, say, the Queen’s head or the picture ion the reverse ends up the right way (i.e. facing me) then count that as a 1 whereas if it ends up facing away, count that as a 0. And if it’s borderline ignore it.
    Or build one of those penny drop machines with pins like you get at a fairground.

    But I understand the ‘official’ solution – especially having googled it and tried it in Excel.

  5. Barry Goddard says:

    I do not wish to beat my own trumpet but there was some discussion of this over the weekend on the blog and my ideas led the way.

    This is also the way to defeat the intrusions that the NSA has built into Microsoft’s random number generator (ie the the heartbleed bug). Simply run the random generator and then every time you see 01 take it as 1 and every time you see 10 take it as 0.

    It will be half the speed but completely secure from tampering.

    • Bob O'H says:

      Um. Excuse my whilst I blow my drum…

      (a) Heartbleed isn’t in the Microsoft RNG
      (b) A deterministic rule from a RNG will only be slightly harder to crack than the original RNG: it certainly won’t be “completely secure” unless the RNG is completely secure.

    • >the intrusions that the NSA has built into Microsoft’s random number generator (ie the the heartbleed bug).
      What are you talking about? Heartbleed was nothing to do with a Microsoft random number gnerator (and indeed Microsoft-based websites were unaffected by heartbleed). And the NSA cryptographic backdoor to which I rather suspect you are referring was built in to the Dual Elliptic Curve Deterministic Random Bit Generator (Dual_EC_DRBG) which is/was an international standard, not a Microsoft one. Dual_EC_DRBG was also a component of Open SSL (one of the seed random number generators), but was not the vulnerability that led to Heartbleed (indeed, according to wikipedia, the implementation was actually flawed so that it didn’t actually work at all …)

    • Barry Goddard says:

      Thank you @Bob O’H and @Mike Strong for your compliments and support.

      Few people truely understand computer safety and how hard it is to keep the intruders from reading all your files.

      But today with my clarity and your clarifications we may have made a small step to help others understand better.

      Perhaps we could team up to start a computer safety blog that would farther inform the world. I have a great interest in this subject and am familiar with (for example) installing Norton products which is a real world skill many of the more “ivory tower” experts do not have.

      It is a sad indication of our modern world the this very blog has had to turn off comments over the weekends. This is perhaps still a collateral effect of heartbleed.

    • Larry Spoddard says:

      BG – a true legend among trolls.

  6. Alma says:

    Oh for God’s sake – just sling the coin and get another that ISN’T biased. :-))

  7. Dom says:

    I took a different approach. Start by writing out an alternating sequence of 1s and 0s of the desired length (e.g. “101010101010”). Now, for each digit in the sequence, toss the coin: if it lands heads, copy down the digit to a new sequence unmodified; if it lands tails, then first “flip” the digit, i.e. 1 becomes 0 and vice versa, before writing it into the new sequence. By the end, your second sequence will be a random sequence of equally distributed 1s and 0s.

    • Ken Haley says:

      Doesn’t work, DOM. Suppose the coin is biased 99.9% heads (only one in a thousand, tails). Your method will predictably output long series of 0101010…. Admittedly, the output will have roughly the same number of 1’s and 0’s, with no bias towards either; but it’s definitely NOT random, as the sequence is very predictable.

  8. Sockatume says:

    1) Toss the coin
    2) Toss the coin again.
    a) If it shows the same side as the previous flip, record a 0
    b) If it shows the opposite side, record a 1
    3) Return to 2)

    So a sequence:

    HTHHTTHHTHTHHTTHTHHTTTTHT

    Would become:

    Different different same different same different same different different different different same different same different different different same different same same same different different

    110101011110101110100011

    Of course this is just a hunch. I’m working figuring out whether it’s truly random.

    • Larry Spoddard says:

      Fraid not old chap. If it’s biased, it’s going to tend towards coming down on the same side time and again.

    • Ken Haley says:

      This fails. Consider a coin biased 99.9% heads. Then a sequence of HHHHHHHHHHHHHHHHHHHHTHH.. would yield an output of 000000000000000000000000110… (Forgive me if I counted H’s and 0’s wrong, but you get the idea).

    • Sockatume says:

      Thanks Ken, I had a feeling that there was something wrong with it.

  9. Matilda says:

    Or you could simply modify the way you use the coin. Rather than using it as a heads or tails indicator, you could use it like a dart on a dartboard (where the numbers you land on, tell you the points, rather than it being decided by bias)

  10. Hugh Janus says:

    I had another solution

    1. Place coin in pocket
    2. Put hand in pocket and twirl the coin few times
    3. Grab the coin, remove from pocket and slap the hand and coin palm down onto a table
    4. Lift hand and observe

    No tossing is required (“Ooer missus!”) which no doubt the pedants will point out violates the strict wording of the question but it does at least remove the effect of the coin bias.

    • ctj says:

      this is really no different than just taking it out of your pocket and gently putting it down on the table. the act of taking it out of the pocket introduces enormous bias on your part, even if you could successfully overcome the bias in the coin.

    • Stevenz says:

      Remove any chance of bias by wearing mittens.

    • Eddie says:

      Then you wouldn’t be able to get your hand into your pocket.

  11. Just invert the meaning on each toss, i.e. switch from (Heads=1 and Tails=0) to (Heads=0 and Tails=1)

  12. Major Todd says:

    I suppose “series” means that the order of results is important and should be random, else could you do e.g. 10 coin tosses and reverse the results of half of them to achieve a random set of heads and tails?

  13. Eddie says:

    This is all too difficult for me.

  14. Andy says:

    I did this by simply alternating the meaning of heads and tails. So on odd tosses, heads is 1 and on even tosses, heads is 0. This means you get an even distribution without having to double the number of throws.

    • Andy says:

      I just noticed Graham beat me to it!

    • Björn says:

      This wouldn’t work well with an extremely biased coin – the extreme case of a coin always showing heads/tails would give a series looking like …010101… Another case, almost as extreme would generate a series with a very high likelihood of looking like …010101… I’m not so great at statistics, but following this line of reasoning I assume this solution is only truely random if the coin is also truely random.

  15. Ken Haley says:

    Here’s my answer, which I haven’t proved to myself to be totally unbiased, but I don’t see how it can be biased one way or the other. I also think it improves on Richard’s answer, as it requires fewer flips in most random (although biased) series of flips.

    For each random digit do the following: Flip the coin (at least twice) counting flips until the result is different from the first flip. If the number of flips is even record 0, else record 1.

    • Bob O'H says:

      No, that doesn’t work. Your first flip sets the probability, which is either p or 1-p (with those probabilities). We’ll call this q.

      The probability that you have n subsequent flips is q^n-1(1-q). As q < 1, this must decrease as n increases. Pr(n=1) = (1-p). Then Pr(n=2) = p(1-p), which is less than Pr(n=1). Similarly, Pr(n=3) = p^2(1-p), and Pr(n=4) = p^3(1-p) < Pr(n=3). etc.

      In other words, if we pair each odd number of (subsequent) tosses with the even number above it, we see that the odd number has a higher probability. Thus, the odd numbers must have a higher probability overall. Finally, as this is the the number of subsequent tosses after the first toss, we add one and see that an even number of tosses is more likely.

    • Ken Haley says:

      Bob O’H: I’m not convinced. I think the effect you’re talking about when heads lands first is exactly reversed when tails lands first…with the complementary probablility, resulting in an overall even likelihood of either digit. If you disagree, tell me this: Say the coin is biased 75% towards heads. Which digit–1 or 0–will occur more often in the result…with what probability? Same question for 99.9%?

      I think we agree that there’s no sequence bias (that is, the series of digits up to any point has no effect on the next number in the series, since we start over after generating each digit).

    • Bob O'H says:

      The effect I’m discussing isn’t reversed. Whether the coin lands heads or tails first, and however the coin is biased (well, assuming it can land on both sides), it’s the case that the longer the sequence, the less likely it is. Thus Pr(2 tosses) >Pr(3 tosses), Pr(4 tosses) >Pr(3 tosses), etc. So, as there must be at least 2 tosses, evens must be more likely.

    • Ken Haley says:

      Bob, you’re right. I didn’t write the method exactly the way I was envisioning it. (Happens as I get older…damn!) As you pointed out, my method would always produce more 0’s than 1;s in the long run as an even number of flips is more likely, regardless of the coin’s bias. But here’s the method that I envisioned:

      Flip the coin (at least twice) counting flips until the result is different from the first flip. If the first flip is heads then record 0 for even number of flips and 1 for odd. If the first flip is tails then record 1 for even number of flips and 0 for odd.

      Now, I think you’ll agree that for a 50-50 coin there’s no bias, whereas my original method would be biased producing more 0s than 1s. Thinking about the extreme case, 99.9% bias towards heads: When heads lands first, there will be many flips before we see tails (on average) and the probability of producing a 0 is very slightly greater than producing a 1 (slight, but > 0). But if tails lands first, it’s almost certain (but not quite) that we will produce a 1, as we will see heads on the 2nd (even) flip. Getting tails first only happens 1/1000 of the the time, which I think is just enough to cancel the slight edge that 0 gets when heads lands first. Overall, the probability of getting either digit is the same, it appears.

      Agree?

    • Bob O'H says:

      I’m not sure that would work either. If p= Pr(heads), we have

      Pr(1) = p Pr(odd|heads) + (1-p) Pr(even|tails)

      I think Pr(odd|heads) = 1/(1+p) (assume we have m pairs of tosses before the sequence ends, the probability that the next toss is the final one is 1-p, and the probability that it the next but one toss is p(1-p), so Pr(odd|heads & M=m)=(1-p)/((1-p) + p(1-p)) = 1/(1+p). Similarly Pr(even|tails) = (1-p)/(2-p), so

      Pr(1) = p/(1+p) + (1-p)(1-p)/(2-p)

      which is not, in general, 0.5.

      (I think my maths is correct, but it’s worth checking)

  16. Sheldon Cooper says:

    You’ve got a brilliant mind such as I viewing this page and you want me post an answer that is so simple and straightforward? That’s like asking the Incredible Hulk to open a pickle jar.

  17. James Bailey says:

    For those wondering why comments have been turned off until Monday, consider this: Since there seems to be a large number of people who cannot understand the phrase “DO NOT post your answers”, then what better way to ensure this condition?

    • Edward Snowjob says:

      Alternatively, for those of a less self righteous nature, why not comment on the post prior to the Friday puzzle?
      That’s what the cognoscenti do.

    • Stevenz says:

      Seems to me James is just expressing frustration, a very minor reason to call someone self-righteous. Now, lumping oneself with the cognoscenti…

  18. Defining a “run” as the number of times you get the same side in a row, even if it’s only 1. Now flip away but each time a run ends write down the run count in binary. E.G. HHHHTHHH = 10 1 11 … something like that?

  19. Markus says:

    What about inverting every second turn. That would compensate for the bias, would not it.

    • Ken Haley says:

      Compensates for the bias (i.e., you’ll geat about the same number of 1’s and 0’s), but the sequence is still not random, as pointed out above, especially with a heavily biased coin.

  20. Kristian says:

    My solution uses the same principle as Richard’s, mine is just a little different.
    You count your throws. On odd throws, heads is 1. On even throws, heads is 0.
    The pingpong should produce even distribution as long as your total number of throws is even. Richard ensures the total number of throws to be even by doing throws in pairs.

  21. Simon Treves says:

    My brain hurts. Can’t we talk about cheese?

    • Gabby Bollard says:

      Be my guest ….

    • Simon Treves says:

      Thank you, Mr Bollard. I was starting to worry I was the only human being in this thread.

    • Cowardly Troll says:

      I could eat cheese all day, every day, for every meal.
      I don’t because I don’t want to balloon up like someone on the Jeremy Kyle Show.
      My favourite is Vacherin Fribougoise (might not have spelled that properly).

  22. Katrina Hill says:

    What if the answer is not important to Richard and it was the way in which we answered or spoke to each other on this comments thread that Richard was studying… Watching… Eeeek

  23. Stevenz says:

    Richard’s answer is so much simpler than any others suggested. All he is saying is that no matter what the bias of the coin, any series of *two* flips of opposite results will be random, not as is usually done, a series of each of the flips independently. It will take longer – and more callouses – to regress to the mean, but it will get there.

  24. Nathaniel says:

    Richard’s answer is incorrect, or the same reasons posted above:
    H to T really is as likely as T to H, but the two are correlated. Let’s say your sequence is like:
    HHHHHHTHHHHHHTTHHHHHTTHHHHTHHHT
    Ignoring all the repeats, you have:
    HTHTHTHTHT
    Which, according to the simplest rule above, generates 101010101. This is a 50/50 population, but not random!

    One way to fix it would be to start over after using each throw, but a highly loaded coin will almost always start a sequence with H. Nearly every sequence will be HHHHHHHT
    so the H->T transition is much more likely to see as your first than the T->H transition.. so you no longer have a 50/50 population spread.

    The only way to do it properly, I think, is some form of reweighting: you must measure the bias of the coin and use that bias to correct. (i.e. If the coin is weighted 3:1 H:T, then you throw out every other head)

    • Schmy says:

      Nathaniel, I had the same thought till I reread the solution. Richard’s idea would take your string of flips and break it up like this:
      HH HH HH TH HH HH HT TH HH HH TT HH HH TH HH T
      Knock out the pairs:
      TH HT TH TH
      Then:
      0 1 0 0
      It’s gets less efficient the more biased the coin is but no less effective.

    • Barry Goddard says:

      Schmy is right.

      How you’re supposed to go about this is to make exactly 2 coin tosses, then see if they are HT or TH. If not, throw them out.

      What you were doing was throwing out all results until you get a H-T transition, and then a T-H transition, etc. You are right in saying that this is not random, in fact it is 100% deterministic. You will DEFINITELY get an alternating HTHTHTHTHT sequence by carrying out the solution this way.

  25. mittfh says:

    Just out of curiosity, if you had a coin and you weren’t sure if it was biased or not, how many tosses would you need to do before the results were skewed enough you could be reasonably sure there was a bias? How many tosses to get an approximation of the bias?

    • Nathaniel says:

      That’s an easy statistics problem. You want to test how close p (the probability of getting heads) is to a value of 0.5. The particular distribution you’re checking is called the binomial distribution. which tells you the probability of getting N heads for a given p.

      Easy statistics problems are hard, though. In statistics terms, your question isn’t well-formed. The correct formulation of your question is: “estimate how many coin tosses I would need to make to ensure that the coin heads probability is 0.49<p<0.51 with a 95% confidence interval".

      Consider a coin that is ever so slightly loaded: p=0.5000001. You would need to flip such a coin millions of times to notice the loading, but if you flipped it billions of times the pattern would start to become obvious. The problems are: how true, and how obvious?

  26. ChrisR says:

    Derren Brown’s famous 10 heads in a row

    http://www.youtube.com/watch?v=n1SJ-Tn3bcQ (start 1min in)

  27. Anders says:

    My solution was to simply ask random people to select heads or tails.(and screw the coins)

  28. Hugh Janus says:

    Let’s take an example of a biased coin with probabilities of H = 0.6 and T = 0.4.

    If you toss a coin twice, you have 4 possible sequences, with the following odds:
    HH = 0.6 * 0.6 = 0.36
    HT = 0.6 * 0.4 = 0.24
    TH = 0.4 * 0.6 = 0.24
    TT = 0.4 * 0.4 = 0.16

    So, there are two scenarios where the odds are identical, HT and TH and you use these to create your random ‘0’ or ‘1’ sequence. So you flip the coin twice and apply the following rule set:

    HT = Score ‘1’
    TH = Score ‘0’
    HH = Ignore and retoss
    TT = Ignore and retoss

  29. I’m missing something. If we are measuring only transitions between runs of heads or tails, won’t the sequence be the nonrandom 01010101…?

    • schmy says:

      See my reply earlier.
      I thought the same as you until I reread the problem. You examine tosses 1&2 together, then 3&4, but not 2&3.

  30. Johana says:

    Extraordinarily educative thank you, I believe your trusty readers may well want even more information like this carry on the great effort.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s