July 2008

Two posts ago I showed how many coin flips it would take in order to have a 98% confidence of getting 92 heads in a row (à la Rosencratz and Guildenstern Are Dead). The answer turns out to be 3.874\times 10^{28} coin flips, which if you tried to do by yourself, it would take 100 billion times longer than the current age of the universe. Since I mentioned that only Wowbagger, the Infinitely Prolonged could pull off such a stunt, I think it’s only fair that any other solution also be Adamsian, at least in practicality if nothing else.

My friend Spencer proposed a Dyson sphere to power a huge number of coin-flipping robots. I think he’s on the right track and I had similar thoughts, however my ideas are a bit larger in scale and less detailed. I won’t go into detail on what kind of Dyson Sphere is best or such, since even simplistic models are fraught with difficulties and instabilities (a nice page talking about Dyson Spheres and some simple analysis is here). Instead, let’s just say that we can build some kind of large Dyson network in order to capture a significant portion of the Sun’s energy. We’ll be conservative and say that after light capture, conversion to useful energy, and then maintenance, etc. we can use 10% of the Sun’s radiant energy to power an array of coin-flipping robots.

Spencer also mentioned the concern that once you have good enough robots, that coin flipping is no longer random: exactly precise robots flipping exactly precise coins in the exactly precise way will give the exact same result every time. That may be the case, but we’ll assume that the robots and coins are made imprecise enough that there will be enough random variance in between all the robots to make the system truly random and fair (this is in all reality probably impossible, but we’re in Adam’s universe so we’ll assume it can be done anyway).

Since the robots don’t have to do anything but flip coins and report the outcome, we’ll say each robot consumes about as much power as a toaster oven, or 1000 W. The sun’s luminosity is 3.846\times 10^{23} W, so assuming we can use 10% of the sun’s energy we have:
\displaystyle{(0.1)\left (3.846\times 10^{26} W \right)\left (\frac {1\;\text {robot}} {1000\;W} \right) = 3.846\times 10^{22}\;\text {robots}}
This many robots would give us the same number of flips every second, so that will give us the required number of flips in:
\displaystyle{\frac{\displaystyle{3.874\times 10^{28}\text{flips}}}{\displaystyle{3.846\times 10^{22}}\textstyle{\frac{\text{flips}}{s}}}=1.007\times 10^6s\approx 11\; \text{days and}\;14\; \text{hours}}.
Now that is a considerable improvement.

This potential solution does have some problems though, the most obvious being whether there is enough useful material in the entire solar system to build 3.846\times 10^{22} robots, plus the Dyson power grid to run the whole thing, plus a maintenance system to keep it all in good working order, etc. If we limit ourselves to just the easy to use material, like just the asteroid belt, that limits us to about \small{2\times 10^{21}} kg of mass. Assuming a total of 10 kg for each robot (including Dyson network power generation, infrastructure, maintenance, etc.), that limits us to just 2\times 10^{20} robots. This number of coin-flipping robots would then take 6.14 years to get the required \approx 3.874\times 10^{28} coin flips, which still isn’t bad at all. It might take several millenia to build the coin-flipping robot Dyson network, but once it was up and running you’d have your 92 heads in a row in just a few short years!

So lets say we let our coin flipping Dyson array keep running, say, until the Sun becomes a red giant in about 5 billion years, destroying our Dyson array. We would have

\displaystyle{\begin{array}{c}\left( 2\times 10^{20}\text{robots}\right) \left( \frac{\displaystyle { 1\;\text{flip}}}{\displaystyle { \text{robot}\;s}}\right) \left( \frac{\displaystyle { 3.1557\times 10^{7}\; s}}{\displaystyle {1\; \text{yr}}} \right) \left( 5\times 10^{9}\; \text{yr} \right) \\ \approx 3.2 \times 10^{32} \text{coin flips} \end{array}}

From this can we calculate how many coin heads in a row we can expect to get during this time? Our initial equation is
\displaystyle{F = 1-\left( 1-2^{-n}\right)^{0.5\,f}}
where F the confidence probability we we desire (we’ve been using 0.98, or 98%), n is the number of heads in a row, and f is the number of coin flips. Rearranging this for n we have:
\displaystyle{n = \frac{1}{\text{ln}\,2}\: \text{ln} \left( \frac{-0.5\,f}{\text{ln}(1-F)} \right)}

For some various confidence probabilities we have these results:

 \begin{array}{ l l } \textbf{\textit{F}} & \textbf{\textit{n}} \\ 0.9999 & 120 \\ 0.999 & 120 \\ 0.99 & 121 \\ 0.9 & 122 \\ 0.75 & 123 \\ 0.5 & 124 \end{array}

So what does this mean? You have a 99.99% chance of getting at least 120 heads in a row, pretty much guaranteed. However, you only have a 50% chance of getting up to 124 heads in a row. What gives? We go from flipping coins for 6 years to 5 billion years, and the only improvement we get is an additional 28 heads in a row? That’s because each additional head in a row has half the probability of occuring, so the probability decreases exponentially with a linear increase in number of heads required. Conversely, for an exponential increase in the number of coin flips, we see only a modest linear increase in number of expected heads in a row.

Last Wednesday my family and I returned to Austin from our (so far) annual trip to Japan to see Ryoko’s family. Since Ryoko’s mother passed away last year, this year is one of the important anniversaries of her death where a special memorial service needs to be held. So we went to Ryoko’s home for two weeks to attend the ceremony and then to spend some time with her family.

The afternoon after the ceremony (held in the morning), all of Ryoko’s family was gathered together and chatting, and the subject turned to exotic foods. When asked for my two cents, I said that I’m always willing to try something at least once, and that I like new culinary experiences. Then Ryoko’s cousin Akihiro chimed in: “I know a place not far from here where you can eat deer meat and wild boar! I’ll take you there this evening!

So that’s how I ended up going here to eat:
wild boar restaurant!
That’s Ryoko’s father and older sister about to go inside. It’s a tiny little place that I can most easily describe as ‘seedy’. The outside looks a little run-down, and inside a little more so. Here’s the front of the restaurant:
front sign
Basically the large white sign says, “All natural: Wild boar stew, game fowl dishes, wild deer dishes.”
I didn’t bother taking any pictures of the interior of the restaurant, but it isn’t hard to describe: low light and dingy, old faded posters of actresses and Enka (basically, Japanese country music) stars. There was even a calendar with a nude woman on it hanging on the wall. (I took it down, rolled it up and set it behind the old dusty karaoke machine when the cook was back in the kitchen. He never noticed.)

The first dish was some wild fowl fried with some onions. I didn’t even take a picture of it because at the time I didn’t realize it was anything but ordinary chicken. Neither the taste nor texture disabused me of that notion. It was pretty good though.

The second dish was grilled deer meat with onions:
deer meat
It had a slightly gamy flavor to it, but it was pretty heavily salted and peppered so it didn’t stand out much. It wasn’t very tough, and I thought it was quite tasty!

The third dish was none other than roasted wild boar with salad:
wild boar!!!!!
This meat was really, really tough. It was hard to chew, and there was tons of fat on every cut. The flavor wasn’t too bad though. Sort of a cross between pork and something really really gamy. I don’t mind gamy flavor so once I could chew it until it was soft enough I had no trouble eating it, but someone without a high tolerance for gamy tastes might have trouble getting it down.

Overall it wasn’t too bad, but the atmosphere definitely left a lot to be desired.

A couple of posts ago I talked about how laughably improbable it would be to get 92 heads in a row on a fair coin. To sum up, the probability is:

\displaystyle\left(\frac{1}{2}\right)\left(\frac{1}{2}\right)\left(\frac{1}{2}\right)\cdots\left[\text{92 times}\right]\cdots\left(\frac{1}{2}\right)=2^{-92}=2.017\times 10^{-28}

The probability of this happening is so abysmally low that you could flip coins your entire life and never expect to see this happen. Or could you? How many times would you need to flip a coin to see a reasonable chance of this happening?

A pointless question? Most certainly. But trying to answer pointless questions that can be solved by math is one of the trademarks of a geek. So a quick review of probability and statistics lead me to the Geometric Distribution, which gives the probability of an event occurring after a given number of trials.

\displaystyle{P=p\left( 1-p\right)^{k-1}}

Here p is the probability of the event occurring once in one trial, i.e. 2.017\times 10^{-28}. k is the number of trials, and P is the probability of the event occurring once within k trials. However, this equation doesn’t quite give us the probability distribution we need. This function will give us the probability of getting exactly one event (heads 92 times in a row) out of k trials (flipping a coin 92 times in a row k times). We’re not interested in the probability of exactly one success, we’re interested in the probability of one or more successes. For that, we need the related Cumulative Distribution Function. Basically it’s the sum of the probabilities of 1, 2, 3,… up to k successes out of k trials. It’s actually pretty easy to derive without performing sums for arbitrarily large values of k. Since we want one or more successes, that means the only thing we don’t want is a failure for every trial. The probability of a single failure is simply 1-p, so the probability of k failures is \left( 1-p\right)^{k}. Since we want every possible combination except every trial a failure, we just subtract this from 1 (the sum of all possible combinations is of course equal to one). This function comes out to be:
\displaystyle{F=1- \left( 1-p \right)^k}

Choosing a reasonable number for F, we’ll select 0.98. Solving the above equation for k we get:
\displaystyle{k=\frac{\text{ln}\left( 1-F\right)}{\text{ln}\left( 1-p\right)}}

This equation is exact, but it has a big problem. No normal calculator or computer is going to be able to calculate the answer because of the denominator. The logarithm of one is zero, so the logarithm of a number very very close to one is a very very small number. But no normal calculator is going to be able to handle \text{ln}\left( 1-2^{-92}\right)\approx\text{ln}\left( 0.999999999999999999999999999798\right)
(Note I said no normal calculator. I used Mathematica for this and it works fine. But anything limited to double-precision arithmetic isn’t going to get you there.) Fortunately there is a convenient Taylor series expansion for \text{ln}\left( 1-x\right). It is

\displaystyle{\text{ln}\left( 1-x\right)=\sum_{i=1}^{\infty}\frac{x^i}{i}}

The first term in the series will give more than sufficient precision in this case, so we have
\displaystyle{k=-\frac{\text{ln}\left( 1-F\right)}{p}}

This tells us how many trials we we will need to to have a 98% confidence of getting 92 heads in a row, but it doesn’t tell us how many coin flips we will need. Now a trial is defined as 92 coin flips, and if all 92 are heads it is a success, otherwise it is a failure. However, we don’t need to do all 92 flips each time, as soon as we get our first tails, we already know that the trial is a failure and we can start over. Since a fair coin is going to result in tails half of the time, then that means on average we will have two flips for every trial. So if f is the total number of coin flips we will need to get a 98% confidence, then:
\displaystyle{f=-\frac{2\;\text{ln}\left( 1-0.98\right)}{2^{-92}}=3.874\times 10^{28}}

This is a very very big number. If we flipped a coin once a second, how long would it take us to get this number of flips?
\displaystyle{3.874\times 10^{28}\,\text{flips}\left( \frac{1\;\text{s}}{1\;\text{flip}}\right)\left( \frac{1\;\text{yr}}{3.1557\times 10^{7}\;\text{s}}\right)=1.22\times 10^{21}\;\text{yr}}

And how long is this? This is really, really long. Astronomers estimate the current age of the universe to be 1.373\times 10^{10} years old. That puts it as 100 billion times longer than the current age of the universe. This is a feat that could only be pulled off by, say, Wowbagger, the Infinitely Prolonged. According to this fascinating article on the eventual heat death of the universe, at this point there will be no matter left in the universe but white and black dwarfs (and black holes, but I don’t know if they’re considered to be matter within our universe or not), and they will be flung from their orbits due to gravitational radiation.

So is all lost? Is there no way to get 92 heads in a row? For all practical purposes, yes, there is no way. As for impractical purposes though, in a subsequent post I’ll detail a way that we could accomplish it long before the death of the universe using a scheme that in all reality would only make sense in a Douglas Adams’ universe.