Non-Randomness in Coin Flipping

It turns out that flipping a coin has all sorts of non-randomness:

Here are the broad strokes of their research:

  1. If the coin is tossed and caught, it has about a 51% chance of landing on the same face it was launched. (If it starts out as heads, there’s a 51% chance it will end as heads).
  2. If the coin is spun, rather than tossed, it can have a much-larger-than-50% chance of ending with the heavier side down. Spun coins can exhibit “huge bias” (some spun coins will fall tails-up 80% of the time).
  3. If the coin is tossed and allowed to clatter to the floor, this probably adds randomness.
  4. If the coin is tossed and allowed to clatter to the floor where it spins, as will sometimes happen, the above spinning bias probably comes into play.
  5. A coin will land on its edge around 1 in 6000 throws, creating a flipistic singularity.
  6. The same initial coin-flipping conditions produce the same coin flip result. That is, there’s a certain amount of determinism to the coin flip.
  7. A more robust coin toss (more revolutions) decreases the bias.

The paper.

Tags: ,

Posted on August 24, 2009 at 7:12 AM • 59 Comments

Comments

Nicholas Weaver • August 24, 2009 7:57 AM

Don’t forget that a good slight-of-hand magician can coin-flip with effectively pure determinism.

Pete Austin • August 24, 2009 8:07 AM

This is an example of how real-world digits have a bias towards low values. This is most obvious for the highest-order digits, but also exists for the others. True randomness is an illusion.

For example in “1”, consider the number of spins represented as a decimal number, and this result shows the “low value” bias of the rightmost digit.

sooth sayer • August 24, 2009 8:10 AM

I think these things are very known if not well documented.

A lot of research, in my opinion is bogus – the researchers ran out of ideas (or brains) but still had money so you get this documentational thesis

Rui Ferreira • August 24, 2009 8:26 AM

I don’t think Benford’s law applies at all. It doesn’t becomes a log distribution just because it’s biased, right? It’s still a normal distribution centered around a different mean.

Clive Robinson • August 24, 2009 8:31 AM

@ Nicholas Weaver,

“Don’t forget that a good slight-of-hand magician can coin-flip with effectively pure determinism”

It’s actually very very easy…

When you flip the coin with your right thumb into the air you let is spin a little or a lot it does not matter.

When you catch it in the palm of your left hand you can see if it is heads or tails as you bring it across to the back of your right hand it will be the other way up With about half an hours practice you can make this a very fluid action.

Obviously if you want it to be heads and it’s in your left hand as heads you will need to flip it in bringing it down on the back of your right hand.

So you know what state the coin is in before you take your hand off.

If your opponent late calls after it’s on the back of your right hand and it’s the wrong way you have two choices one easy one hard.

The hard way is to flip it with your left hand as you take it off (needs about half a day to get the feel of it). The easy way is to simply tip back onto your left hand and hold that out to your opponent. You would be surprised how few people this occurs to especially if it’s a one off toss for the begining of a game of football or some such.

If you are tossing to the floor your opponent normally calls before you flip it with your thumb. With (quite a bit) of practice you can learn to do a slow flip where you know how many times it turns in the air before hitting the floor. If the floor is soft the coin tends to land on the downwards side, Even on hard floors it still tends to stay on the downwards side but much less so than with soft floors.

There is actually some physics/mathematics behind the landing of coins (like there is for the maximum number of folds in a piece of paper) I just wish I could remember where I saw it.

Roboticus • August 24, 2009 9:28 AM

I can easily cheat a coin toss. When I flip a coin with my thumb it almost always lands with the side that was up now down. So if it was facing heads up it will land tails up nearly everytime.

Frank • August 24, 2009 10:10 AM

Given the pure physics of coin flipping – it would seem that if one has a single coin, imparts the same force at the same location, from the same height, a consistent landing can be deterministic. I think back to my days of “baseball card-flipping” as a youth. I know I could “throw-down” 20 or more face-up or face-down – on demand to “match” the opponent and collect more cards into my stash.

Jackson Madden • August 24, 2009 10:31 AM

what relevance does this have for security? none at all.

unless the DHS flips coins to find terrorists.

clvrmnky • August 24, 2009 10:44 AM

I’m assuming this was of interest to Bruce because it highlights an assumption we might have about things like “randomness” that may, in fact, not be true at all.

If anything, this blog is about the perception of security as much as it is about the practicalities of the same.

The basic notion of how much time a side is up vs. down while in the air was surprising to me, but so obvious when described. Even a theoretical perfect coin tossed by an honest person still appears to have some bias simply because of the mechanics of flipping.

Of more interest is that the potential bias of real-life flips might be greater than some so-called games of chance at a casino.

Michael Ash • August 24, 2009 11:08 AM

Note that if for some reason you really need an unbiased choice, there’s an easy way to do this with a biased flip.

Flip the coin twice. If the first one is heads and the second tails, take one choice. If the first is tails and the second heads, take the other choice. If you get the same face both times, start over. This last part is key: you must start over and flip two more times, and keep flipping in pairs until you get two different faces. It’s not enough to just flip in sequence until you see a change. You have to completely discard the result and begin anew.

Clive Robinson • August 24, 2009 11:11 AM

@ Jackson Madden,

“what relevance does this have for security? none at all.”

Quite a bit actually.

Most of the security theorms depend on the notion of “randomnes” in one form or another.

For security “true random” bit generation is a fundemental building block.

There has been a lose (and incorect) assumption for many years that a coin is “fair” and therfore could be used for generating true random numbers etc.

What this paper shows is that as coins are not of the quantum world they do (as expected) follow the laws of physics. Which realy means that the random elerment in coin tossing is actually the human operator not “chance” etc.

And as humans are involved perception and skill are all…

puterdude • August 24, 2009 11:16 AM

It still appears that coin-flipping is a good way to make a random choice. To begin with, the coin-flipping mechanism varies as no two hands are alike (and therefore not everyone will flip a coin at the same angle or spin); secondly, I always shake the coin in my hand and cover it prior to flipping – so, there’s really no way of knowing which side it starts out on; thirdly, the choice of coin (and coin wear on the head or tail side) depends on the random event of what happens to be in my pocket; and lastly, from now on I will flip the coin high and vigorously, and let it bounce on the ground. It seems that, as long as these three conditions are met, anyone will have a fair chance of guessing one way or the other, right? If so, this report will have had a global impact on ensuring repeatable, fair coin-tossing practices and policies! Thanks for bringing this issue to my attention.

Fred P • August 24, 2009 11:16 AM

@Jackson Madden-

Some of us still use coins for random number generation. I use them to generate my passwords. Considering the information in this paper, there’s a bit of a hole in my RNG method, then, although it’s actually less than I believed.

Clive Robinson • August 24, 2009 12:24 PM

@ Calum,

“remind me to never, ever, play a game with you.”

My 7 year old son is coming to that conclusion as well (he’s learning).

He’s not yet sure how I do it but he knows that I win when I want to 😉

In the past most of my work colleagues would not take a bet with me either, not because I’d bet for money or gain (except for the odd doughnut) but they could not figure how I did it.

Unlike a well known business person who once said,

“I’m a great beliver in luck, I make as much of it for myself as I can.”

From my point of view nearly every game has a weakness and can be “gamed” all I want to do is find it work out how to use it, then move on to the next game, ther’s no fun in just playing 😉

arthur • August 24, 2009 12:31 PM

when catching the coin I can make it land same side up at least 3/4 times. Seriously folk let it hit the floor 🙂

Pete Austin • August 24, 2009 12:31 PM

@Rui Ferreira. Benford’s law is about real-world counting: each digit starts
showing a small number (1 for the leading digit and 0 for subsequent ones) and counts upwards, resetting when it passes 9.

Whenever you stop the count, each digit will on average have spent longer showing small values than large numbers. This effect is normally only relevant for the first digit, but with small numbers it applies to them all.

The coin is the same, if you count its spins as a binary number and consider the rightmost digit (when I said decimal, above, that was a typo).

Jeff • August 24, 2009 12:50 PM

@Clive, re: coin flip manipulation: I managed to eliminate the flash-in-front-of-face by swiping my thumb across the face of the coin. Generally (with US coins) it is smooth:heads, rough:tails. It’s easy enough that in about the same amount of training time you listed, you can learn to swipe once with the thumb and then flip the coin over if it is going to come up “wrong.” So, this can all be done below eye level on the way to smacking the coin against the back of the hand.

Also, the flip the coin over in your hand trick is pretty easy to master, and if you do it while bringing the catching hand down, it looks very smooth. I’ve never been caught.

And, nice note about the easy way to avoid flipping the coin in your hand–that’s totally awesome, and I don’t doubt that it works flawlessly.

HJohn • August 24, 2009 1:22 PM

Of course, there is Murphy’s Law: when there is a 50/50 chance between a desirable and an undesireable outcome, the undesirable outcome will occur 9 times out of ten.

jnc • August 24, 2009 1:29 PM

When I was a kid, and didn’t have much better to do, I got pretty good at manipulating coin flips under rule 1. I could get it to land “same side up” about 7 or 8 out of 10 times and made a little bit of money betting others on the result.

Clive Robinson • August 24, 2009 1:47 PM

@ HJohn,

“50/50 chance between a desirable and an undesireable outcome,”

Err no the results of “There pervasivnes of inanimate objects” or Murphy’s Law are, not realy understood by most people there are actually two entities involved the anamate and inanimate (A & B).

The results out of ten are,

undesireable for A 4/10
undesireable for B 4/10
undesireable for A&B 1/10
desireable for A&B 1/10

But Murphy’s Law is only invoked when another law such as “A person rises to their point of maximum incompetence” is in place.

And as factory supervisers will tell you usually the animate and inanimate objects are incorrectly clasified. In many cases it’s the operator that is inanimate.

All of which explains why your apparently contradictory empirical observations are both correct 😉

Clive Robinson • August 24, 2009 1:55 PM

@ puterdude,

“I always shake the coin in my hand and cover it prior to flipping – so, there’s really no way of knowing which side it starts out on”

Do you also have a cat in a box?

Just wondering if it’s alive or dead 😉

Vijay • August 24, 2009 4:59 PM

These results are very surprising…It is surprising also (according to the paper) that there is not much empirical data on coin flips, since it is so easy to conduct that experiments.

One of your prior posts describes a machine to that rolls dice…surely somebody must have built a machine that spins a coin!

Vijay • August 24, 2009 5:02 PM

Also, what is the difference between a tossed and a spun coin?

Is it just a difference in number of revolutions per unit time??

Clive Robinson • August 24, 2009 5:28 PM

@

“Also, what is the difference between a tossed and a spun coin?”

When you toss a coin it flips over from edge to edge in the direction of it’s trajectory.

when you spin a coin you simply put it on it’s edge on a flat level surface and spin it around it’s vertical axis. the same part of the edge of the coin remains in contact until it either stops spinning or it slows sufficiently that any irregularity causes it to topple to one side.

When a spun coin topples it starts to run on the edge of the rim and develops a different way of turning. In part the coin turns around it’s centre of gravity (turns like a wheel) and in part it oscillates around the rim with increasing frequency as it gets closer to the flat surface (a theory says it should produce an audible click as it goes through the sound barrier however that does not take into account the non linear nature of fluid dynamics of air that should occur).

Richard Feynman did some work on coin/plate spining shortly after the second world war and again more formally in the early 1960’s.

Apparently it was watching a plate spin in the air with an eccentric wobble that started him on the road to QED.

Stephanie • August 24, 2009 8:40 PM

Great story. I see the relevance to security.

I was reminded of that part at the beginning of Stoppard’s play “Rosencrantz and Guildenstern are Dead” when the strange results of 92 coin tosses make Ros win each time sort of foreshadowing that something odd is going to happen, and then it does.

AC2 • August 25, 2009 12:44 AM

So we’re OK with tosses at the start of cricketing matches as
a. The coin is produced by the referee
b. Toss is done by one captain (alternates to other captian in subsequent matches)
c. The other captain calls while it is in the air
d. Coin allowed to fall to the pitch not caught
e. Little chance, methinks, of a spin when it falls as the pitch is soft

Phew!!

hwKeitel • August 25, 2009 1:13 AM

The football (real football) matches 1. FC Köln – FC Liverpool at the quarter finals of the European Champions Clubs’ Cup 1964/65 ended 0:0 (two times) and 2:2 in the deciding game. Penalty shootout was not established, so the rules said: coin flip!
What happened: the coin landed on the edge, better: the coin plunged (correct word?!?) in the mud. The referee flipped the coin again and Liverpool moved to the semi finals.
Curious story and true.

csrster • August 25, 2009 2:23 AM

Terry Pratchett fans know that a flipistic singularity is a sure sign of a strong residual magical field.

Clive Robinson • August 25, 2009 5:25 AM

@ csrster,

“Terry Pratchett fans know that a flipistic singularity is a sure sign of a strong residual magical field.”

For my sins I showed Terry and his wife how to “game” a coin flip many years ago at a weekend house party in Oxford (he had worked out one bit of how I did it from watching me on previous occasions) as well as telling him one or two jokes at least one one of which later made it into one of his books (after a little cleaning up ;).

What most people may not realise is that his main characters are based on real people who he met through such things as playing Dungeons and Dragons (not the board variety) and some of the other characters are based on “bureaucratic types” he used to work with when he was a “press officer” (or so he say’s ;).

Often they are not even composite as a young lady who had a book shop in Oxford is well aware, and (as was pointed out to me) sometimes a real person has so many interesting or useful facets to their character Terry spreads them across two or more characters (Death, Mort and Rincewind) as the characters develop over time.

I like many others hope that against the odds Terry will find a cure for his posterior cortical atrophy (early-onset Alzheimer’s).

http://www.guardian.co.uk/books/2008/mar/18/health.terrypratchett

http://en.wikipedia.org/wiki/Death_(Discworld)
http://en.wikipedia.org/wiki/Mort
http://en.wikipedia.org/wiki/Rincewind

flipistic singularity • August 25, 2009 6:19 AM

@calum “Clive remind me to never, ever, play a game with you”

with Them.

@clvrmnky highlights an assumption we might have about things like “randomness…”

It’s the difference between the real world and world of models isn’t it? In the math world one of three outcomes (heads, tails, edge).
In the world of the real there is spin bias due to variation in manufacture, manipulation by Clive, other oppourtunity and so forth.

It’s the model world that says no one can breach X security. It’s in the real world that we find keyways that can be attacked, relationships that can be exploited, misconfigured equipment, shoddy installation of controls that can be brute forced.

@Clive
Adora Belle Dearheart is real? I KNEW it!

Clive Robinson • August 25, 2009 7:11 AM

@ AC2,

“So we’re OK with tosses at the start of cricketing matches”

Not quite… If the only effect involved in the outcome of the coin was the rotational vector on the coin was that of flipping this would not be expected to make much of a difference, but there are a number of other factors….

As I noted further up,

“And as humans are involved perception and skill are all…”

It is reasonably well known that people are creatures of habit and are very bad at making random choices which can be gamed. Vinny Jones actually attributed part of Wimbeldon’s win of the FA cup to the fact that when it came to penalties the opposition goalie habitually went in a given direction. That is you can move the odds in your favour due to other peoples failings.

Thus if the ref knows that the captain of team A habitually calls heads and the captain of team B is a left hander he could provide a coin with bias and position the captains appropriately to the way the grass is rolled.

That is you have to take into account the failings of not just the humans but the surface as well. So there are several additional factors to be considered,

The first is for a high toss many people use their arm not their thumb to get the hight so less “flip” rotational force will be imparted into the coin and more “spin” rotational force as the arm vector is a lot more likely to be out of the coin centre line, so the coin is considerably less likely to flip but spin in the air (try it out).

Secondly look at how you actually flip a coin with your thumb, if you are left handed your thumb has a habit of going to the left in a slight rotation and to the right if you are right handed due to the mechanics of your hand. This will also add more “spin” rotational force to the coin.

Then there is the very significant problem of placing the coin with respect to the thumb. Due to the way most people flip a coin by curling their index finger around the end of the thumb and placing the coin on this as opposed to the thumb the coin is very much less likely to have it’s centrer line aligned with that of the thumb.

All of which means the coin is subject to both the problems of the slow flip and or spin on landing.

Then there are the smaller problems with a surface like grass, It is usually cut short and rolled and as any halfway decent seam bowler or snooker player will tell you this “nap” has a small but noticeable effect on a ball and thus you would expect a coin.

Also the surface of the grass is effectively a cross between spiky and corrugated and this is likely to increase any “coin edge effect”.

Therefore the coin can inherit some of the properties of the grass nap and bias of a spun coin as it makes the “coin edge effect” more likely and therefore the coin will be more likely to topple with respect to it’s bias.

Therefore the significant bias effect from spinning is slightly more likely to predominate in a high toss onto grass.

The question then is can the ref or the captain flipping the coin “game the toss” to any significant degree. And this would depend on if the factors above added or reduced to the predictability of the coin landing and which predominated.

It used to be thought that a roulette wheel could not be gamed but physicists have shown otherwise so…

Therefore it is not an easy problem to answer.

Which means that the real question is,

“Who’s going to apply for a grant to test this idea?”

(and if you do get the money please send me a couple of bottles of “micro brewery” beer via Bruce as payment 8)

Harry • August 25, 2009 7:24 AM

@AC2 describes how a coin is tossed for cricket.

American football uses the same procedure, with the added feature that the “coin” is a large commemorative item rather than a standard US Mint coin.

It’s pure show. The teams agree in advance who will start at offence.

I don’t know how it is decided in advance – maybe a real coin toss? Sometimes there is one real coin toss. If the score is tied, the game goes to sudden death overtime with positions decided by another coin toss. AFAIK, this toss is for real.

Clive Robinson • August 25, 2009 10:29 AM

@ flipistic singularity

“Adora Belle Dearheart is real? I KNEW it!”

Try,

http://adorablespike.livejournal.com/

Personally I think she’s a phoney but hey what the heck.

Oh and if you work in news and media believe me you will meet a few “Spike’s” as you will in the rag trade.

Ward S. Denker • August 25, 2009 8:11 PM

Use Von Neumann’s algorithm. Have both people flip a coin. One person selects whose coin takes precedence (instead of whether it’s heads or tails), which is very similar to the cut-and-choose technique on Bruce’s recent “Self-Enforcing Protocols” entry, discouraging cheaters.

If both coins come up heads or tails, discard the result and flip again (reducing some of the bias imparted by the irregularities of the coins themselves). When a result is achieved where each has a different face, the selector’s choice (again, called before the result is known) is what goes.

Bruce Schneier • August 25, 2009 9:05 PM

“If both coins come up heads or tails, discard the result and flip again (reducing some of the bias imparted by the irregularities of the coins themselves). When a result is achieved where each has a different face, the selector’s choice (again, called before the result is known) is what goes.”

Easier is for one person to flip two coins, and for the other person to call out “same” or “different.”

thomas • August 25, 2009 9:36 PM

@sooth sayer

Yes, a lot of this stuff is well-known as folklore. Persi Diaconis would know perfectly well about that — he was a professional magician before he became a leading mathematical statistician. He has certainly written about the distribution of spun coins before, probably twenty years ago now. The point of this research would be to nail down some of the folklore more precisely. The diagnosis that the researchers ran out of ideas or brains in this particular instance is a pretty implausible one.

I’m a bit surprised to see this story popping up again without any note as to vintage. I remember hearing about it on NPR, years ago (Google informs me that it was in 2004, which corresponds to the creation date in the PDF file. )

Clive Robinson • August 26, 2009 2:01 AM

@ Ward S. Denker, Bruce Schneier,

“Use Von Neumann’s algorithm. Have both people flip a coin. One person selects whose coin takes precedence”

Err which Von Neumann algorithm and how many coins?

The unbias algorithm I remember only worked for a single coin.

However the XOR/add mod2 approach can still be gamed if not done properly.

Hmm I think this is not an easy problem…

Clive Robinson • August 26, 2009 4:47 AM

@Ward S. Denker,

“If both coins come up heads or tails, discard the result and flip again (reducing some of the bias imparted by the irregularities of the coins themselves).”

I’ve had time to think about it over a cup of coffee and sorry it does not work with two coins.

You have two independent throws with independent probabilities. The Von Neumann algorithm only works with to independent throws of the same probability. In fact you can show that when the coins have independent probabilities you can actually end up with a worse case of bias than a single coin.

A simple example as there are two throws we have a 2 dimensional space, and I will show the Von Neuman de-bias with a coin that’s heads two times out of three,

HH,HH,HT
HH,HH,HT
TH.TH.TT

In nine throws you get HH=4, TH=2, HT=2, TT=1

Von Neuman says discard HH and TT and HT and TT should be equal ie unbiased which they are.

Now with two coins both with a bias of 2 out of three but one to heads and one to tails,

HH,HH,HT
TH.TH.TT
TH.TH.TT

In nine throws you get HH=2, TH=4, HT=1, TT=2

As Von Neuman says discard HH and TT, you end up with TH=4 and HT=1

With just a single coin the bias was 66.6% with two coins of the same but opposite bias you end up with 80% bias…

@ Bruce Schneier,

From the above it can be seen that,

“Easier is for one person to flip two coins, and for the other person to call out “same” or “different.”

is not going to work either if there is any bias.

Clive Robinson • August 26, 2009 5:04 AM

One thing needs to be noted about real coins,

Their design is often changed on one or both faces and no attempt is made to balance the designs, only to keep the coin the same outer dimensions, weight and material for vending machines.

In the UK we have some new designs of both copper and silver coins, that have a very sparse design on the tails side whilst having a fairly full head design. Thus I would expect their to be a greater bias to the head side of the coin than the tail.

Thus if you see your opponent pull out a new coin you can pull out either a new coin or an old coin depending on which gives you a marginal advantage.

Is it worth it, I don’t know but I do know there was quite an outcry about tampering with the seam on the ball a few years ago in cricket.

Tonka Tom • August 26, 2009 6:10 AM

@Harry I don’t know how it is decided in advance

The tackles flip the waterboy. Heads I win tails you win.

Ward S. Denker • August 28, 2009 3:03 PM

“Easier is for one person to flip two coins, and for the other person to call out ‘same’ or ‘different.'”

Clever. It’s still harder to game this using some of the same techniques which have been discussed here (most people don’t possess a malfunctioning or severed corpus collosum and can’t independently control each hand). It’s also harder for the individual to catch the coins in each hand, increasing the likelihood that they’ll let both coins hit the ground (possibly contributing to randomness per #3).

#5 becomes a less interesting outcome, since it is probably fair to say that it falls under ‘different’ and a 1/6000 bias is simply not enough for anyone to seriously consider saying ‘different’ every time.

Clive,

“The Von Neumann algorithm only works with to independent throws of the same probability. In fact you can show that when the coins have independent probabilities you can actually end up with a worse case of bias than a single coin.”

I’m not entirely sure your argument is particularly watertight. If we’re talking about using the same two coins (i.e. both of them are quarters, as opposed to using one dime and one quarter), I’m guessing that the mechanical process which creates coins is consistent enough that the variations are just not enough to create such a perturbation in the randomness of the outcome that the VN algorithm or Bruce’s method would not help to smooth out the overall bias of the head side of the coin having more metal than the tail side. The mechanical tolerances in play at a government mint are pretty tight, and they have to be, otherwise vending machines would have a difficult time discerning fake coins from real ones. As an anecdote, I came across a silver dime for exactly this reason – a vending machine would not accept it, and upon closer examination I was able to quickly discover why that was.

Of course, the same coin could simply be flipped by each person and the second person calls whichever the outcome could be (same or different). This is still more open to being gamed, assuming the second person can affect the outcome using any of the techniques that commenters have suggested above. I don’t know if I can still do it, but I used to be able to so consistently flip a coin that whatever side was facing up at the start of the flip was the same side I’d get as an outcome well over 50% of the time. I simply practiced to get the amount of force I imparted to the coin and the height I allowed it to reach to be very consistent. Physics does the rest (after all, there’s only so many flips a coin can undergo in a given space over a given time).

That kind of intentional biasing is probably why it’s a matter of convention that the second party to the flip is the one who gets to call the outcome with it in the air. If they can observe that their opponent is very good at gaming the outcome, they can use it against that opponent for their own gain.

Another possibility is for the two parties to flip at the same time and a third, individual calls it in the air (or flips a coin himself, where a heads outcome means that the results will be the same and a tails outcome means the results will be different – as a suggestion) whether the outcome will be the same or different. This may really discourage cheating because there is no real way to know which way the third party will call it and it probably upsets the scenario where one or both parties to the flip may attempt to cheat.

Of course, this discussion is academic. It would be interesting if the authors at Stanford attempted some of these techniques to attempt to unbias the data. Perhaps that’s what they’ll study next, if there will be any continuing research on the topic using the same apparatus that was constructed for this paper (and comparing the results in real life scenarios between two people, where one may attempt to cheat intentionally, both are not trying to cheat at all, or both are trying to cheat).

It’s definitely an interesting discussion, and all we’re talking about is something as mundane as coin flipping.

ross • August 28, 2009 3:56 PM

Speaking of landing on edge. It wasn’t a coin flip, but I had this happen to me once. Was picking up a handful of change, a penny fell out of my hand, dropped at least a foot to the table, and stuck firm dead on edge. It was a VERY unsettling moment, like watching something freeze in midair, to see normal physics apparently stymied. I actually looked around for a moment, trying to figure out if there was a trick, but no, it was just a very rare occurrence.

Ward S. Denker • August 28, 2009 4:17 PM

Ross,

Your anecdote actually provided insight into another suggestion which incorporates the observations Clive made about the individual biases in each coin.

Each party to a “flip” contributes a few coins from his/her pocket to a pool of coins. All of the coins are tossed into the air and allowed to hit the ground. Prior to the “flip” each party agrees to the following conventions:

A) Heads are a value of 1.
B) Tails are a value of 0.
C) All of the values per A and B will be XORed together.
D) Each party will agree upon a different outcome (one selects 1 and the other 0).
E) Cut and choose is is employed for each party to the flip, whereby each individual puts an equal number of coins on the table and the other party selects which of the coins the opposing party contributes to the communal pot.

This would use the biases of individual coins against one another and probably increase the randomness of the final outcome, especially considering that it’s really unlikely that either party has taken the time to determine the bias for every coin in his pocket, and he can’t determine the content of his opponent’s pocket.

Clive Robinson • August 28, 2009 5:29 PM

@ Ward S. Denker,

“If we’re talking about using the same two coins (i.e. both of them are quarters, as opposed to using one dime and one quarter),”

If they are the same type and vintage then yes I would assume the bias diference to be less than 1%.

So rule zero,

Each team captain brings a “ten pence piece of the current design”.

At this rate the toss is going to have more rules than the game 8)

Clive Robinson • August 28, 2009 5:45 PM

@ Ross, Ward S. Denker,

I’ve changed my mind make that rule 1.

Rule zero should be,

If either coin lands on it’s edge the result of the game will be decided by a drinking contest of “last man standing” rules.

Though I’m not certain landing on the edge is as rare as 1 in 6000 I’ve seen it happen several times most often when a coin lands and rolls and hits an object and bounces back a little.

The first time it happened to me was when we where at school doing probability in maths some joker had asked the teacher what we should do if it landed on it’s edge. The teacher (a Mr Pearson) assured him in a sarcastic way that it was not going to happen, well on my 26th flip it hit the top of the table and stoped dead on it’s edge as it did with Ross.

It was witnessed by the two other students in the group however Mr Pearson for whatever reason did not believe it.

Oh and for those that think finding a 4 leaf clover is lucky I told my son that I had found quite a few when I was his age (seven). He did not believe me but I sat him down on the lawn and within about ten minutes of carefull looking had found two very much to his surprise.

Jay • August 30, 2009 9:55 PM

With experience in cricket .. If you want heads you normally put the tale side up and flip… 99.9% of the time I got head 🙂

Dave • August 30, 2009 10:16 PM

Just FYI this is actually a somewhat older result, it appeared in SIAM Review about two or three years ago. There used to be a video of a freeze-frame series of shots of some of the flips floating around somewhere…

Seth Breidbart • August 31, 2009 3:44 PM

Back when they were first introduced (late 1960’s), I discovered that the “new” (non-silver) quarters spun to tails about 75% of the time.

If I pull two coins out and you call “same” or “differ”, you can easily guarantee a minimum of 50% by choosing randomly. I can guarantee 50% by using at least one fair coin.

There are interesting techniques to generate any desired probability given only a single coin with unknown bias (that isn’t 0 or 1).

Ward, I don’t trust your choice of third party.

Robert • May 21, 2010 9:42 PM

I’m currently working on a product using Elliptic curve cryptography. Each independent device has its own TRNG. I have done exhaustive tests on individual devices to prove that they pass all known “randomness” tests. However when I assemble a large number of devices and randomly sub-sample, in both time and device space, I find a noticeable bias in the raw TRNG data.

What is more interesting is that I would have expected this bias to disappear when the data exchanges are encrypted (using a form of Elliptic curve cryptography) however, the bias is completely unchanged, i.e. No cryptographic “whitening”

I think this might be a form of Benford’s / Zif law or maybe a direct result of Central Limit Theorem

Before I tear up a months work and repeat the whole test, I thought I’d check with the knowledgeable folks here. does anyone know whats happening?

Clive Robinson • May 24, 2010 4:30 AM

@ Robert,

You say you are having RNG problems.

There’s not enough information in you post so I’ll tread carefully.

1, You say you are using TRNG’s but don’t say what type.

2, You say you have tested individual TRNG’s and they do not show problems individualy.

Which on the face of it would normaly suggest the TRNG’s are ok.

However you go on to say that you are using multiple devices but not how and you allude to them being independent of each other.

I would be extreamly carefull of this view point. Many TRNG’s are like very high gain very high input impedence wide band amplifiers, because effectivly that’s what they have after the electrical noise source and prior to the signal limiting and squaring. As such they are prone to feedback that can cause oscillation and the band limiting filter prior to the signal limiter can be prone to ringing effects.

TRNG’s are very very susceptible to electrical noise both conducted and radiated. Like oscillators the are susceptible to “injection locking” or “lose locked oscilation” effects.

Ordinary low level analog and RF PCB design do not “cut the mustard” with TRNG’s, they need to be designed by people with very good instrumentation, low level audio and RF design for use in high level noise environment experiance. And as witnessed by the number of supposadly high spec audio cards for PC’s that fail to meet expectation don’t make the mistake of believing that a “bought in item” irrespective of it’s price is going to do the job…

You go on to mention,

“Cryptographic whitening”

When it comes to raw entropy no amount of static whitening can give you more entropy than you have already got, it is not “magic pixie” dust that you sprinkle on.

There are many types of bias a TRNG can have and the simple von Neuman “unbias” idea only deals with “static” bias in the 0’s to 1’s. There are dynamic biasis where low level oscillation causes the bias point to change. When you view a single TRNG this may not be easily visable, however with two or more TRNG’s these oscillations effectivly “hetrodyne” together and the two difference frequencies (f1+f2, f1-f2) may well be of a frequency that shows up in your tests or causes a static bias to get transported through the system.

A similar problem can be caused by the noise frequency limiting filter if it does not have a maximally flat response in the passband, or if the band stop edges have ripple or are to steep (have a look at what “windowing” functions do to the outputs of FFT’s or other sampled signal).

Thus you need to examine the raw TRNG outputs after filtering but prior to “squaring” with an appropriate waterfall analysis of it’s spectrum to look for issues with the TNG’s both singly and when operated together.

Then you need to consider the effects of sampling in the noise signal “squarer”. This can have several effects depending on how it works, one is Amplitude noise to phase noise convertion, another is “high frequency foldback” where another signal considerably outside the design bandwidth gets folded back into the design bandwidth by the sampling process.

An example of the latter is your CPU clock noise getting onto the signal and power lines and getting back into the TRNG prior to the “squaring” process. The difference between the closest harmonic multiple of the sampling frequency and CPU (or other digital signal) will be present in the “base band” signal out of the squarer…

Michael Kater • March 29, 2011 8:55 AM

Years ago when I was about 10 years old my mother and I were in a local department store when she dropped a one cent (Australian) coin onto the marble tile floor. The coin bounced around a bit then settled on its edge. It was dropped from around a metre onto the hard floor. Quite amazing and still stunned by this. Has anyone seen this sort of thing themselves?

jamon • April 15, 2011 5:35 PM

i reached in my pocket pulled out some change a dime fell out bouced once and landed on edge what does this mean?

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.