If you've taken a basic probability class, then you probably know the solution to this issue of obtaining a fair toss with a biased coin. Flip the coin twice. If both are heads, or both are tails, discard the pair of tosses and try again. If the first flip is a heads and the second is a tails, then count the pair as a "heads". If the first is a tails and the second is heads, count the pair as "tails". Even with a bias, the probability of getting a heads-tail pair equals the probability of getting a tails-heads pair.

Here's a blog post that explains this in more detail: http://www.billthelizard.com/2009/09/getting-fair-toss-from-...

You can be sure all future coin tosses I do will use this technique!

It's not a biased coin.

It's a biased flip.

Your solution does not help with that.

Then simply have the same side facing up each time; in that case, there would be no difference between a coin which is biased and a flip which is biased - the bias remains in the same direction, and thus the method works.

(I noprocrast'd myself out, but I couldn't stop thinking about this.)

It's still an issue, GP is very right. The problem is that you can get any desired outcome with some probability p: it's effectively a coin that changes bias depending on the flipper's preference.

I'm trying to think of a solution that resolves this... thoughts encouraged. :)

Only thing that comes to mind is to add some sort of blind element. For example having two people, one flips two coins but both remain ignorant of the actual outcome and assume that they have opposing interests (and so would not be likely to try to help the other in any way). Depending on the outcome of the preliminary flip, the one of the second person is either kept the same or inversed. Again still not perfect but removes some level of manipulation. Which is sort of interesting because you'd have to wonder should the preliminary tosser try to make the probability as even or skewed as possible. If he is likely to skew it it becomes a whole new scenario.

Since the bias is in the toss, not the coin:

Put the coin in the ref's hands, which are cupped against each other in a closed sphere. The ref shakes his hands to the satisfaction of all (and we assume an honest ref). He then places the coin on his thumb, but uses the opposite hand to cover the placing operation and the final launch configuration.

After the coin is positioned, but before it's uncovered, one of the interested parties calls it. Then the coin is tossed.

Fair, random, and evenly distributed as far as I can tell.

Edit: I think this works as well with two interested parties and an impartial ref, or only two opponents where the non-tosser calls the coin before it's tossed.

In the case of an honest 3rd party doing the toss, you can even have someone call it before the ref shakes the coin around in his cupped hands. That way you eliminate the possibility of someone seeing the coin's orientation as it's placed on the thumb. The ref doesn't even need to hide the starting position after that.

If one of the interested parties is also the coin tosser, this could offer an opportunity to game the system, though, so one might want to just use your proposal in all cases to avoid complexity.

Thinking about this a bit more, though, I wonder if this really has the desired effect.

Let's assume for a moment that the act of the ref shaking the coin around in his cupped hands actually generates a random starting position. Ok, so starting position is 50/50 heads/tails, and the caller of the coin doesn't know the starting position.

In that case, the final heads/tails probability then depends on the initial starting position -- to use the bad-case numbers from the article, say the final probability is 60/40, favoring the side that was initially facing up.

So what have we really gained here? All we've done is made sure the initial positioning of the coin is random. The bias in the toss itself is still there, but we're hiding it by making sure the caller doesn't know the initial state of the coin.

If that's the case, then why not:

a) Don't even toss the coin at all. If we're convinced that the act of the ref shaking the coin around in his cupped hands gives a random starting position, then why not use that in place of the coin toss?

... or...

b) Avoid the whole cupped-hands shake thing entirely. Just have the interested party call the toss before the ref places the coin on his thumb. Obviously then you have to have an impartial ref who won't then place the coin on his thumb in a way to benefit one of the interested parties. (You could just specify that the ref is required to reach into his pocket, pull out the coin, and place it on his thumb, all without looking at it at all or feeling its surface sufficiently to figure out which side is which.)

I guess it also depends on what we care about to make this "random." Personally I think it's random enough if the caller simply doesn't know the starting position when calling the coin, assuming the coin tosser doesn't use the call to game the toss.

Heh, or we can just admit that tossing a coin isn't sufficiently random, and use something else... like radioactive isotope decay... or even a PC's PRNG (though that of course opens a big computer security debate).

"So what have we really gained here? All we've done is made sure the initial positioning of the coin is random. The bias in the toss itself is still there, but we're hiding it by making sure the caller doesn't know the initial state of the coin."

Assuming the cupped hands shake produces a random starting position, you've evenly distributed the toss bias, so the result of a series of tosses should be evenly distributed.

"If that's the case, then why not: a) Don't even toss the coin at all. If we're convinced that the act of the ref shaking the coin around in his cupped hands gives a random starting position, then why not use that in place of the coin toss?"

That's an excellent simplification, but it just doesn't feel as dramatic and traditional to decide on shaking cupped hands. You need the toss for effect.

Flip the coin twice with the same side starting face-up each time; one party calls 'same' or 'different'.

Sorry, make that "with opposite sides starting face-up".

Have the other party call it in the air.

Then the other dude lowers his hand 1 inch. And yeah, same type of thing I was going for, preferably in that case it should land on a table unaffected by either party. Preferably the guy calling it shouldn't see the trajectory, he might be an alien who could calculate it. lol. Generally though you want both parties to be ignorant towards what is happening in my opinion.

This means it becomes an issue of trust. You have to trust whoever is flipping (yourself or otherwise) to flip consistently.

According to the article, you could still bias the toss. For example, let's say you're trying to get heads, which in your system is "first heads, then tails". You would hold the coin heads up on the first toss, and tails up on the second toss.

Well, you can prevent that by stipulating that the orientation should be same on both flips.

The issue is that if probability will still vary between flips, if the adversary is good enough. Say heads is up both times. Flip one could be done so that p(heads) = .6, but flip two could be done so that p(heads) = .4. It's up to the person who flips.

Then perhaps there will soon be a market for automated coin-flipping machines that impart a consistent, if unknown, bias into every flip!

I wonder if you've seen this: The automatic dice-roller

http://gamesbyemail.com/News/DiceOMatic

It can generate 1.5 million dice rolls per day.

Just go quantum and measure single difracted photons.

For the record, that technique was developed by Jon von Neumann. It's called a randomness extractor.

Obligatory wikipedia link: http://en.wikipedia.org/wiki/Randomness_extractor#Von_Neuman...

Or toss the coin twice, the first toss to decide which side starts face up for the second toss and the second toss to determine the result. If the bias is 60% in favour of the side intitially facing up on a single toss, then it will have been reduced to 52% for the side facing up on the first of the two tosses with this method. Not perfect but only two tosses are ever needed.

The claim is that it's not uniformly random - all outcomes don't have equal probability. But it's still a random process.

Two coins flipped at equal velocity and trajectory in vacuum will flip an equal number of times. Thus, the process of a coin flip is completely deterministic since it depends on newtonian physics. So, the probability is defined by the randomness of the conditions, not the process itself.

When the conditions are controlled then so is the probability. The results of this research should not be surprising despite the tone of the article.

You also could have air motions, electric fields and so on passing through the trajectories of the coins. Unless you account for everything on atomic level, you have all that uncertainty as random noise in you measured outcome. So indeed it is a random variable. Biased, yes, but random.

Actually, even if you can have data at atomic level you still have chaos theory and butterfly effect preventing you from making prediction. Then even some small fluctuation born by the Plank's "uncertainty principle" can grow up in time to big enough error.

I consider the act of flipping the coin part of the process.

Not correct.

If it was random, the output does not depend on the input (or there is no meaningful input).

But they showed that the output depends on the input. So it's NOT random.

Biased random means the result is not uniform, but it does not depends on the input.

No so here. Here it's not biased - it simply depends on the input.

(Obviously pseudo random number generators depend on the input - but those explicitly are not random, they are simply useful.)

It's not a completely deterministic process, and I have no other way to characterize non-determinism. While the initial conditions bias the result, the result is not determined by the initial conditions. The result is still probabilistic.

Let's assume we have a function true_random() that returns a true random value between 0 and 1. Now let's define f(x) as:

  def f(x):
    r = true_random()
    if r < 0.5: return r
    else: return x

Half the time, it returns a random value between 0 and 1. The other half, it returns its input. This is still a random process.

Half the time it returns a value between 0 and .5 ...

I upvoted, but between .5 is still less than 1. He just over estimated :)

There is a nice way to define randomness by determining if given a string generated by the process (i.e. 010101011110101)can you write a program smaller than the string that will output that string for any string generated by the process.

This is called Kolmogorov randomness and has nothing to do with how input effects the output. In this instance, any string generated by a million coin tosses couldn't be reproduced by an algorithm that is smaller than the string, in general. By this metric I'd argue that the process is still random.

Just because the input has an effect on the output, doesn't make the output less random. "F(x) = x + rand()" is still a random function.

This is still random. Random just means the outcome is unpredictable, not that all outcomes are equally likely. If a coin flip is 60% to be heads, 40% to be tails, the results are still random.

Or, looked at another way, it's not random at all. It's a very simple function of the coin's initial state and the forces applied to it. If you knew all of those, you would be able to predict the results ahead of time.

Link fails for me - it goes to a registration check page or some such?

try this?

http://www.mercurynews.com/search/ci_13579962?nclick_check=1...

Oh, sorry - don't know why, it works fine in Chrome and I have no registration there. Try this instead: http://www.mercurynews.com/top-stories/ci_13579962

To make sure you get past the registration system on MercuryNews.com (I know this because I'm quite familiar with their CMS), append a variable named source with any value to the end of the URL, like this:

http://mercurynews.com/ci_13579962?source=hoops

Looks like there's some sort of javascript on the article page that redirects you for some reason...

It seems to direct me back to a registration check page at ycombinator, which Firefox refuses to load because of SSL issues. XSS attack?

and the paper in question: http://comptop.stanford.edu/preprints/heads.pdf

Check out "CoinFlipper" [0] - a series of machines designed to flip coins to land on the side you specify. They're so brilliantly delightful. After months of testing, experimenting and usage the coin only once landed on it's edge with the machines.

[0] http://www.dotmancando.info/index.php?/projects/coin-flipper...

Jaynes discusses this in Chapter 10 of Probability Theory: The Logic of Science. His real aim is to seperate the concepts of having to take a decision without knowing all the facts versus having to take a decision in the face of some kind of intrinsic randomness. Having seperated the two concepts he then argues that probability theory is about the former, with the later something of a red herring.

So he emphasises that coin tosses obey the laws of physics and are not random, but we use them anyway because we don't know the facts that we need to know in order to call the toss. He included experimental results of successful cheating, but with a jam jar lid instead of a coin. Clearly we call a coin toss "random" because of the practical difficulties involved in predicting the motion of a disk much smaller than a jam jar lid.

Those football players who reject the paper out of hand without considering its merits are the ones who are "ridiculous". One of the authors is Persi Diaconis. If he says something about statistics, you don't get to just reject it.

yeah, what did those football players do their entire college careers, play games?

This can also be theoretically proven:

If we view a coin flip as a random variable X that describes the number of revolutions, then X has a value of 0 to infinity.

Before the coin is flipped, lets say H faces up. Then as X marks the number of revolutions, R will describe the result:

  X: 0 1 2 3 4 5 6 ..
  R: H T H T H T H ..

As you can see for any value of X, the number of times H was up is always equal or once more then T. This shows a clear bias for the side facing up.

Uhhh, careful with "once more" in the context of infinity.

The way to model this would be to come up with a probability distribution for the number of revolutions. If the distribution is skewed towards few revolutions, (something like a poisson distribution, say) then it's very likely that the outcomes have probabilities ≠50% due to the discretisation.

In practical terms, I guess the person flipping the coin should be required to flip it such that it rotates very fast, which ought to provide a gaussian distribution around a high number of revolutions.

Anybody who's deliberately "fumbled" a coin toss before knows that it's all in the flick. Especially if you were to, say, put more emphasis on the side of a coin, giving it a lopsided spin so as to make it /look/ as if it's flipping at a casual glance.

Craps players have long known about controlling the outcome of a dice toss.

Any statistical significance results? Without them I am not buying it.

btw Boston was not the loser in the Portland Oregon coin toss, it was Stumptown.

man I am glad the football is the "important" example they gave.

I thought it was an entertaining and effective way to show something mathematical to the general public, in a way that most people can relate to.

I was especially tickled near the end of the article where they described discussions on changing the overtime rules. When they mentioned the players' reaction, I thought it would turn on something related to winning, and I was surprised to learn that their objection was more playing time and more chance of injury.

Yeah, I was struck by that as well. It's true that a lot of money is riding on the outcome of sporting events, but the fact that that's so, and that society (or at least the Mercury News) has placed that in the category of "important" is... pretty sad, IMO.

Coin spin instead?

Spinning coins tends to introduce considerably more bias than tossing them.