15 Nov 2015

A Fair Toss?

“Heads or tails?” The next time you’re asked that as a coin flips through the air, perhaps your reply shouldn’t be as simple as “heads” or “tails”. We explain more.

Quizzical Goat Humans have been deliberately using randomness for thousands of years. Besides fun and games, it’s widely used to allocate tasks and resources in ways that affect us all – from being selected for jury duty to drawing the short straw on doing the chores at home. Some have even used it to attempt to divine the will of the gods – though in modern times such cleromancy has itself spawned games and amusements, including notably the Magic 8 Ball. We all have an intuition about how randomness “works” (though our intuitions can often be wrong – as with Monty Hall’s goats) and most of us study at least the basics of probability at school. But how much do we think about how fair a random event is – even something as simple as tossing a coin? And how does that relate to the (quite literally) laser-powered electronic random number generators we use at Geonomics?

Quantis BoxesTo generate the random outcomes in our games we use Swiss “Quantis” random number generators. These are pretty well-regarded pieces of equipment. Lots of people – including the Swiss Federal Office of Metrology (metrology being the science of measurement, but you knew that, right?) – have put the boxes through their paces to check that they really work as advertised. (We also test them ourselves using the “diehard tests” created by an American professor of statistics called George Marsaglia. Those tests are not to be confused with any films featuring Bruce Willis.)

So how do they work? Inside each Quantis box is a laser. It fires a single photon at a time at a half-silvered mirror. There’s a detector on the other side of the mirror. So there’s a 50% chance the photon will pass through the mirror and be detected. Quantum mechanics tells us – by which of course we mean “people who understand quantum mechanics tell us” – that this is a fundamentally random event. In other words, there’s no way of knowing in advance whether any given photon fired at the mirror will pass through to the detector. Put simply, the box performs a quantum mechanical electronic coin toss.

By firing lots of photons in succession, we can generate a random sequence of “photon” “no photon” (or “heads” and “tails”, or “0”s and “1”s or anything else you want to call the results). From such sequences we can obtain larger random numbers. (Of course, when we say “larger random numbers” what we really mean is “a randomly generated integer within the range from 0 to N – 1 inclusive, where N is some integer chosen according to our needs and larger than 1”. But if you go around saying things like that too much, you stop getting invited to parties. And, in any case, you know what we mean.)

Lab LaserSome readers will by now be getting excited about an inherent flaw in any laser photon quantum coin tossing device. Such readers will be jumping up and down saying “There’s no such thing as a perfectly half-silvered mirror. Your two possible outcomes will not have exactly the same probability.” And some of these readers – which is to say a subset of the first set of readers who were getting so excited – will already be saying “And I know how to fix it”. In other words, they know what’s coming, and can skip the next few paragraphs.

For the rest of us, the thing that some of the people who aren’t reading this paragraph were getting so excited about is what’s often known as “the biased coin problem”. The name comes from the glib way of phrasing the issue as a brain-teaser to annoy your friends with over dinner. (Or down the pub or wherever it is you go to annoy your friends.) Anyway, the brain teaser goes as follows: “Imagine you have a coin which, when you toss it, has a very slightly different chance of landing ‘heads’ than ‘tails’. You don’t know which outcome is more likely, or how much more likely it is. You just know that it’s constant difference. It could, for example, be 51% likely to land ‘heads’ and 49% likely to land ‘tails’. Or, to take another example, it could be 50.002% ‘tails’ and 49.998% ‘heads’. How can you use this biased coin to make an exactly 50:50 random decision?”

Often people will start from wanting to measure the probabilities of each outcome of the coin toss. This approach will give you an approximation of the probabilities. And if you toss the coin a few million or even a few billion times, then your approximation should be pretty accurate. But even then, how do you use what you’ve measured to generate two possible outcomes, each of which has exactly the same probability as the other? (See how we reworded the question slightly?)

MagpieThere’s actually a simple answer. You don’t need to know the probability of “heads” or “tails” (or “lands on its edge” or “falls down a drain” or “is plucked out of the air by a quick-witted magpie”). Imagine tossing the coin twice in a row. The probability that you get “heads then tails” is exactly the same as the probability you get “tails then heads”. If you get anything else, eg “two heads” or “two tails”, you just toss the coin twice more – keep doing pairs of tosses until you get “heads then tails” or “tails then heads”.

Maths TeacherIf your friends don’t mind doing a little more maths (or “having a bit more fun” as your maths teacher might have put it), you can now pose a supplementary question: On average, how many times will we have to toss the coin to get an outcome that we can use? (Mathematicians, including your teacher, would call this the “expected number” of coin tosses.) In principle, this is the sum of an infinite number of things: “two times the probability that we need just two tosses” plus “four times the probability we need exactly four tosses” plus “six times the probability we need exactly six tosses” plus etc etc etc, with each extra term getting smaller and smaller. (It’s astonishingly unlikely that we’d need to toss the coin 100 times for instance unless it’s very biased.) But, with a little bit of algebra, we can work out an exact answer to this infinitely long sum.

Let’s use “p” for the probability that the coin lands “heads” and “q” for the probability it lands “tails”. (If it’s never going to land on its edge or be eaten by a magpie then q = 1 – p, but that’s not important at this stage.) Let’s use “t” for the expected total number of coin tosses to get a result we can use. The probability we need just two tosses is pq + qp = 2pq. The probability that we need more than two tosses is then 1 – 2pq. If we do need more than two tosses then, after the first two tosses, the expected number of additional tosses we need is also t – because we’re “starting again”. (This neat insight comes to us courtesy of a paper by Harvard Professor of Computer Science, Michael Mitzenmacher.) So now we can write a formula for t:

t = 2 . 2pq + (1 – 2pq) . (2 + t)

Expanding this out we get:

t = 4pq + 2 – 4pq + t – 2pqt

Which simplifies to:

2pqt = 2

Which we can further simplify and rearrange to:

t = 1/pq

This simplified formula enables us to answer the supplementary bit of the brain-teaser. If the probability of “heads” and the probability of “tails” are both “about a half” then, on average, we expect to need only about four coin tosses to get fair 50:50 outcome using the “pairs of tosses” strategy above. In other words, if you were using this method with a laser randomness generator, then, as long as your mirror is approximately half-silvered, you’re typically not going to require too many photons to be fired at it to generate each “electronic coin toss” outcome. And, since photons travel at, well, the speed of light, you can each generate literally millions of such binary outcomes per second. (Quantis actually do their statistical norming in a slightly different way for various reasons, but we’ll leave the details for a future blog post.)

Coin TossSo, now we know about de-biasing photon detection in laser-powered quantum-mechanical electronic coin-toss boxes, what’s our new answer to the original question “heads or tails?” Well, as long as the person asking isn’t likely to be moved to physical violence by a harmless bit of pedantry, we might say “Since your coin hasn’t been tested for bias by an independent metrologist, I propose paired tossings with only different outcomes for each toss being deemed valid. And I call ‘heads then tails’.”

Having a fast and reliable generator of random numbers is a key part of how we ensure our games are fair for all players. If you’re interested in probability then you might like working at Geonomics. Check out our careers page.

One response to “A Fair Toss?”

Leave a Reply

Your email address will not be published. Required fields are marked *