## Flip Worse

Here is a story about being wrong. Lots of times. You know, like a new puppy when it’s trying to guess where it’s okay to pee.

A couple days ago I posted about flipping an unfair coin of a special type. This coin does not favor heads or tails. Instead, it favors its previous toss. If it was heads this time, it has a 51% chance to be heads again next time, and likewise for tails.

In the previous post, I said that if you flip and take the best 2-out-of-3, you cut the bias down by a factor of four. That is, if the coin is heads before you flip, it would have only a 50.25% chance (roughly, since this was a first-order calculation) of heads winning two-out-of-three. I posted that solution, but thought I needed a follow up because although I calculated the answer, it still wasn’t clear to me. I thought there ought to be some nice way to visualize it, so I was trying to draw some different sorts of trees that illustrated the flips and their probabilities.

What I found was that my original answer was plain wrong. In addition to the tree, or hopefully with its help, I was curious about what happens when you play 3-of-5, 4-of-7, etc. I hadn’t calculated these yet, but not having an obvious method at hand I figured the fastest way to get started was to find the answer using my computer to simulate coin tosses, then figure out why it worked.

Once I wrote such a simulation, I was shocked to find that it said that when I do best 2-out-of-3, heads won roughly 51% of the time. I thought something must be wrong with the simulation, but I didn’t see anything. So I plugged in the exact expression for the odds of heads winning into the google toolbar (you know google is a fast and easy calculator, right?) and found 51% precisely. Then I wrote my expression down on paper to see why it should work. I factored out a 51%, and saw I had the square of (.51 + .49) looking at me, confirming without long multiplications that the answer should be 51%.

Now I started thinking about the binomial theorem and how I could use induction to prove this was always going to work, but I was distracted by the thoughts of what an idiot I was.

“Oh man,” I thought. “I was an idiot not to check up a little bit on my other calculation before I posted them on the blog.” For a moment I thought the second- and higher-order corrections were somehow canceling things out, but that makes no sense. So I went back to my original post and found the mistake. I had written that if you stay on the same side when flipping with probability $1/2 + \epsilon$ and flip to the other with probability $1/2 - \epsilon$, then the probability of a given sequence of tosses that switches $n$ times and doesn’t switch $m$ times to first order in $\epsilon$ is

$\frac{1}{2^{m+n}} + \frac{m-n}{2^{m+n}}*\epsilon$,

which is wrong. It’s actually

$\frac{1}{2^{m+n}} + \frac{m-n}{2^{m+n-1}}*\epsilon$.

I felt really stupid about this one, because it wasn’t wrong due to a simple calculation error. It was wrong because the first time I did it I just wrote it down based on what I thought it ought to be, and didn’t even bother to do the calculation (which I snidely left “as an exercise to the reader”).

Still, even with this correction, it means that playing 2-out-of-3 should cut the bias in half, not leave it alone the way my simulation and google calculation said.

Still confused, I went back to the simulation, and now saw the error. I was giving tails at 49% chance all the time, not giving the coin a 49% chance to flip as I had thought. So I fixed that, and the program still didn’t seem to work. It still said 51% for 2-out-of-3, and for longer games.

I went back to google toolbar and plugged in the exact expression one more time. There are four ways for heads to win 2-out-of-3, and their probabilities are

$P(HHH) = .51*.51*.51$

$P(HHT) = .51*.51*.49$

$P(HTH) = .51*.49*.49$

$P(THH) = .49*.49*.51$

The sum is $.505002$. Okay, great. That confirms the revised first-order estimate. I just wrote down the probabilities wrong before.

I still had the simulation to take care of, since it was predicting something different than my calculations, but at this point I realized that the entire process was completely useless. There’s in fact a much better way of achieving what I wanted – a more fair coin toss. Just toss the coin twice, and take the second toss.

The first toss is a little unfair. It’s biased by something like 1%. That means that after you flip the coin, it has a little bit of memory of where it was the previous toss. What I mean is, flip the coin a million times. go to some flip in the middle, and see that it’s heads. Was the previous toss heads or tails? You don’t know, but heads is just a little bit more likely than tails for the previous toss. How about two tosses ago? Well, if you remember your father, but just barely, your memory of your grandfather will be even dimmer than that.

Specifically, if coin starts out heads with this 51% bias we’ve been talking about, flip it twice and the second toss has a 50.02% chance of being heads. The third toss is 50.0004%. Flipping two or three times and taking that last toss easier and better; the the stuff about best-2-of-3 is pointless. Still, it bugged me that I wasn’t very clear on my the answer to my original question.

Back to the simulation. Knowing it had to be in there, I finally saw another error. I was only generating one random number for three coin flips. My second and third flips were the same as my first flip every single time I ran the simulation. Fortunately, computers can’t get mad at you. If they could, I’m pretty sure my netbook would be pissed at being asked to use its limited resources to generate several million completely useless random (kind of) numbers. So I fixed the code. Finally the simulation, exact calculation, and approximate calculation converged. It appeared I had the answer.

Does it seem strange that throughout this process of being repeatedly wrong, I was readily willing to turn my back on the answer I had been sure of just a few moments before? Maybe this means I’m sure of things too easily. No, not “maybe”. I’m sure it does.