The Infinite Monkey Strikes Back

I've gotten some very interesting responses to my post about the Infinite Monkey Theorem, concerning the likelihood of a monkey accidentally reproducing The Hobbit by randomly generating letters. So I thought I'd write a follow-up to address some of them; also it gives me another chance to imagine a monkey typing on a typewriter. (I tried letting a monkey type this up for me, but he wrote something much more interesting than I had planned.)


Dear Dr. Math,
I believe the monkey problem makes the simplifying assumption that all the letters in the text are independent, which they're not in real English (or any other language). How does this affect the results? Real texts are sampled very narrowly from the space of possible letter sequences.
CN

Excellent question, CN; I'm glad you brought it up. In fact, the distribution of the letters in the text is irrelevant to the problem. The important assumption is that the letters being output by the monkey are equally likely and probabilistically independent of each other. Under this assumption, it doesn't matter if the text the monkey's trying to match is The Hobbit or the phone book or a sequence of all "7"s--the probability of matching any sequence of 360,000 characters will be . If you need convincing, consider the simpler example of flipping a fair coin 5 times. Any particular sequence of 5 flips, for example HHTHT, has the same probability, , of coming up. So, if we were trying to match any flip sequence, we'd have the same chance. The same is true here, just on a much larger scale (and with monkeys).

Now, many people object to this idea, because they think that a letter sequence like "a;4atg 9hviidp" is somehow more "random" than a sequence like "i heart hanson". Therefore, they reason, the first sequence would be more likely to occur by chance. But actually the two sequences have exactly the same probability of occurrence, under our assumptions. Really, the only difference between the two is what we could infer about the message source (beyond musical tastes) based on receiving such an output. I hope to discuss this in detail someday in the context of elementary hypothesis testing, but if, say, there were some doubt in our minds as to whether the source of these characters was, in fact, uniformly random, the latter message would give us considerable evidence to help support that doubt. The reason is that we could provide an alternative hypothesis that would make the observed data much more likely. For the monkey problem, however, we were assuming that we knew how the characters were being generated, so there's no doubt.


Dear Dr. Math,
Along the lines of your previous questions on large numbers and randomly generating the book The Hobbit, I'd like to ask about randomly generating images. A low res PC display is normally 640 x 480 pixels. If you randomly generated every combination of color pixels, wouldn't you have created every image imaginable at that resolution? That is, one of the screens would be the Mona Lisa, one would be your Ask Doctor Math page, one would be a picture of the Andromeda galaxy from close up, one would be a picture of you!, etc. If you only wanted to look at black & white images, you'd have a much smaller collection, but once again wouldn't you generate every B&W screen image possible?

With feature recognition software getting better all the time, one could "mine" these images for recognizable features. Similar to the way the pharmaceutical companies sequence through millions of plants to find new substances, one could sequence through these images to extract unknown info.
Mike

Dear Mike,

Absolutely, we could apply the same techniques to any form of information that can be reduced to a sequence of numbers or letters, like images, CDs, chess games, DNA sequences, etc. In fact, we needn't generate them randomly, either. As in The Library of Babel example, one could imagine a vast collection of all possible sequences, generated systematically one at a time with no repeats. Unfortunately, for any interesting form of information, the number of possibilities is simply too great to make it practical.

In your example of 640x480 pixel images, even assuming the images were 1-bit monochrome, there would still be 2 possibilities ("on" or "off") for each of the 640*480 = 307,200 pixels. Therefore, the number of possible images would be , which is about . Remember how big a googol is? Well, this number is about . So, not even all the crappy low-res monitors in the universe could possibly display them, even at their lousy maximum refresh rate of 60 images/second. And even worse, we'd have no reason to believe any of the images we did see, because they'd be indistinguishable from all the many other conflicting images.

Your comparison to pharmaceutical companies is interesting, but remember those companies are starting with a large (but manageable) collection of plants that actually exist, not searching through the space of all possible arrangements of plant cells or something. It's OK to search for a needle in a haystack sometimes, but not when the haystack is larger than the known universe.


Dear Dr. Math,
Unless I misunderstand (and that's quite possible), I think you've introduced a major flaw here... The "second chunk" begins at character number 2, not character number 360,001. There is no reason why these should be considered discrete chunks and so just because the first character isn't "I" doesn't affect the fact that the second and subsequent characters may spell out the work. Thusly, your monkeys are producing over 17 million "blocks" a day, not just 48...
A. Nonymous

Well, A, that all depends on how we set up our assumptions. The way I had pictured things, the monkey was typing out a whole manuscript of 360,000 characters at a time and then having someone (perhaps J.R.R. Tolkien himself!) check it over and see if it was exactly the same as The Hobbit. If not, the monkey tries again and, with very high probability, fails.

However, your idea is more interesting and perhaps more "realistic". That is, we could have Prof. Tolkien just watch over the monkey's shoulder as it typed and see if any string of 360,000 consecutive characters were The Hobbit. So, if the monkey started by typing a preamble of gibberish and then typed the correct text in its entirety, we'd still count it as correct. As you say, this means that the possible "chunks" we'd need to consider have a lot of overlap to them--we might find the text in characters 1 through 360,000 or 2 through 360,001, etc. But unfortunately, it's not just the number of chunks being produced we need to reconsider; because of the way they overlap, we've now introduced relationships between the chunks that mean our assumption of independence no longer holds. For example, if we knew the first block of characters was incorrect, we could determine whether it was even possible for the second block to be correct based on the particular way the first block was wrong. In fact, we'd know it was impossible unless the first block was something like "xin a hole in the ground there lived a hobbit...".

Actually, if we thought about things in this way, then CN's question above would be relevant, because the codependency of the overlapping chunks would depend heavily on the particular text we were trying to match. Consider the example of coin-flipping again: assume we were flipping the coin until we got the string TH. There are 3 possible ways we could fail on the first pair of flips, all equally likely: TT, HT, and HH. If we got TT or HT, then we could succeed on the third try by flipping an H. If we started with HH, there's no way we could get TH on the third flip. The number of ways of succeeding would be 2, out of a possible 6. So the probability of succeeding in the second block given that we failed in the first would be .

Now, if we were trying to match HH and we knew we failed on the first 2 flips, there would still be 3 equally likely possibilities. Either we flipped TT, TH, or HT. If we started off with TT or HT, we can't possibly win on the third flip. But if we got TH first, we'd have a chance of flipping H on the third flip and matching. Thus, our probability of matching in the second block given that we failed in the first would only be . Here's a chart showing all of the possibilities:

The two probabilities are different because TH can overlap in more ways with the wrong texts, whereas HH can only overlap with TH.

Therefore, our previous strategy of multiplying probabilities, which rested on the assumption of independence, won't work here. In order to explain how long it would take the monkey to produce The Hobbit with high probability under your scheme, I'd have to go into some fairly heavy-duty math involving Markov chains and their transition probabilities. The relevant probabilities can be found by raising a 360,000 x 360,000 matrix to the nth power--not generally an easy thing to do. But it turns out that the expected (i.e., average) number of characters the monkey would have to type before finishing would still be on the order of , similar to the the previous setup.

Either way, you and J.R.R. would have probably given up by that point.

-DrM

What "mean" means

Dear Dr. Math,
My parents live about 200 miles away from me, so I make the drive back and forth a lot, with no stops. Almost exactly halfway in between the speed limit changes, so instead of driving 55 mph I drive 80 mph. Since my average speed is 67.5 mph, shouldn't it take me 200/67.5 = 2.96 hours to get there? I've noticed it always takes a little longer, but I don't get it. I've even set the cruise control and kept the speeds exactly constant.
Chuck

Dear Chuck,

I'm going to go ahead and assume that you live in one of those places in Utah or west Texas where the speed limit actually is 80 mph. Otherwise, you've been speeding, and I can't endorse that kind of behavior. OK? OK. Don't make me write a post about the correlation between speeding and traffic fatalities. I swear I will turn this blog around.

Here's why your numbers didn't add up: while it's true that the average, in the sense of arithmetic mean, of 55 and 80 is mph, that's actually the wrong kind of average to be using in this circumstance. "Kinds of averages?" Oh yes. Allow me to explain:

In the course of your trip, you drive half the distance, 100 miles, at 55 mph. So that leg takes you hours. On the second half, you're going the legal speed limit of 80 mph, so that half should take you hours. Altogether, then, your driving time is 1.81 + 1.25 = 3.06 hours, a little more than you expected.

Rather than the arithmetic mean here, you should have been calculating your harmonic mean, which for two numbers A and B is defined as . To see why that's the right quantity, let's denote by S your real average speed for the trip, that is, the total distance you traveled divided by your total time. If T is the total time you spent driving, then ; equivalently, . If A is the speed you went for the first half and B is the speed for the second half, then another way you could calculate the total time is as , just like we did previously. As usual, in math when we compute the same thing two different ways we end up with an interesting equation. In this case, since the times are equal, we get:
.
Dividing through by 100 on both sides gives us

which, if you take reciprocals of both sides and multiply by 2, yields the formula for the harmonic mean. In this particular example, mph, so your guess of 67.5 mph was only off by a little bit.

So, when is the arithmetic mean the right one? If you had gone on a trip and spent an equal amount of time driving 55 mph and 80 mph, then your average speed would be the arithmetic mean of the two. To see that, let's just assume you drove 1 hour at each speed. Thus, your total distance traveled would be miles, and your total time is 2 hours, so the average speed is mph. Voilà! If you look at that calculation closely, you can pretty clearly see why it should always give you the arithmetic mean--you're just adding the two speeds together and dividing by 2. Similarly, another way to see that the arithmetic mean is inappropriate for the equal distance problem is to notice that by driving the same distance at each speed, you spend more time at the slower speed and less time at the faster one.

There's actually yet another kind of mean, called the geometric mean, which shows up when you're computing ratios, percents, interest rates, and other things that are typically multiplied together. For two numbers A and B, it's defined as . For example, let's say you were a rabbit farmer and your population of rabbits grew by 50% one year and only 10% the next. The combined effect at the end of two years would be that the population had increased by a factor of , for an increase of 65%. To achieve that same growth at a constant rate, say a factor of R for each year, you'd need , so . So in a sense the "average" growth rate was 28% per year. Many people in this kind of situation would be tempted to guess that the average was 30%, splitting the difference between 50% and 10%. You can see that it's not far off from the truth, but it's not quite right. And why be almost right when you can be exactly right?

The point of all these means is to replace the net effect of two different values with the effect of just a single value repeated. But you have to be careful to consider exactly how those quantities are interacting to produce that combined effect. When they simply add together, the relevant type of mean is the arithmetic one, when they multiply, the correct mean is geometric, and when they do that weird thing of combining via their reciprocals, you use the harmonic mean. Interestingly enough, for any two numbers, if M is their arithmetic mean, G is the geometric mean,and H is the harmonic mean, it's always the case that . In fact, there are other means, too, but these three are the major players.

Other situations where the harmonic mean might come up include: calculating average fuel economy of a car given an equal amount of city and highway driving, computing the total length of time it takes two people working together to complete a task, figuring out the net resistance of two electrical resistors in parallel, finding a pleasant harmonic note (hence the name) between two other musical notes, calculating the height of the intersection between two crossed wires, and answering questions about the uses of the harmonic mean!

-DrM

Let's Make a Deal or No Deal

Dear Dr. Math,
On the show Deal or No Deal, if the contestant gets to the point of only having two cases left they have the option to switch cases. Should they switch or not? Is this the same as the Monty Hall problem?
Daniel G.


As Scott Bakula would say, Oh boy. I guess there was no way I was going to get away with writing a math advice blog and not having to explain the Monty Hall Problem at some point. For those of you out there who may be unfamiliar with the MHP, here's the way it goes:

You are presented with three doors and told that behind one door is a car and behind the other two are goats. (Here we're assuming you want the car and not the goats, but in these tough economic times maybe they should be reversed.) You pick a door and then the host, the venerable Monty Hall, always opens one of the other two doors to reveal a goat. He then offers you the chance to switch to the remaining third door. It turns out that it's always in your best interests to switch, given the available information. Doing so improves your chance of winning from to .

Now, I see some of you reaching for that email button, getting ready to fire off an angry letter about how it just can't be true that switching is better than not switching. After all, there are two remaining doors and you don't know which has the car, so aren't your odds 50-50? It's impossible! Believe me, I sympathize, but hold it right there. Plenty of people, even professional mathematicians, have said the same thing as you. Whole books and websites have been devoted to this topic, people have written simulators that you can try out for yourself, the advice columnist Marilyn vos Savant essentially made her career by being right about this problem and explaining why. The MHP is math's version of an optical illusion--you can stare at it and stare at it, but until you actually get the ruler out and measure, you won't be convinced. The sad truth is: Ellen Tigh's a cylon, Darth Vader built C3PO, and switching doors in the Monty Hall Problem improves your chance of winning from to .

Instead of opening up all the old wounds the MHP has inflicted over the years, let me try to offer my own perspective on how I think about the problem (inflicting all-new wounds!), and then maybe we can take those same ideas and apply them to the Deal or No Deal question to show why it's different.

Let's back the train up all the way to the station and talk a little about what probability is--what it means. Warning: Heavy Philosophy-Type Stuff Ahead. As I've mentioned previously, my opinion is that probability is a way to quantify the uncertainty we have about the state of the world. Therefore, it's highly dependent on what information we feel that we possess about the things we observe and what consequences the information may have. For example, everyone's favorite "random" activity is flipping a coin--assuming it's a "fair coin", the probability is that it will come up heads and that it will come up tails. But what does that really mean? Physically, we can model all the variables that go into the action of flipping a coin--weight distribution of the coin, air resistance, amount and location of force applied to the coin, the direction the coin is tossed, elasticity of the landing surface, etc. If somehow we could measure all of these things between the time the coin was tossed and the time it landed, and if we had access to a powerful enough computing device, we could predict whether the coin would come up heads. At the very least, we could guess ("calling it in the air") and improve our chances to more than . Going back a step, the only parts of this system unknown to us ahead of time are the variables due to the tossing itself--the human element of thumb against coin. If, for example, we knew that the person tossing the coin were an amazingly skilled athlete who could control his hand and arm motions with extreme precision and who had practiced the technique of tossing a coin enough that he could reliably make it come up heads, we again could improve upon our 50-50 guess. As a third possibility, consider the case where the coin has already been flipped but we haven't seen the outcome yet (the referee's still holding it); if somebody could sneak a peek at part of the coin and tell us what they saw, we could update our information and make a better guess.

So, what is the "real" probability? In my view, and this might be hard to swallow at first, the answer is there isn't one--the question itself is flawed. "Wait a minute," I can hear you objecting, "Can't we just perform experiments and measure the frequency of heads? Flip a coin a hundred times and about 50 of those will be heads, etc.?" The problem there is that you're observing a different event each time. You can never step in the river twice, nor flip the same coin. All the repetition does is validate the predictive power of your mental model that says that the factors that go into flipping coins are beyond your comprehension and result in the heads side and the tails side being equally likely. As an alternative, say, you could have the mental model (shared by many people) that those hundred coin flips were predestined to occur the way they did and that through meditation/prayer/drugs/etc. you can actually see into the future and predict the outcome of the next flip. It happens that the first model tends to be more successful than the second (or any others) in this instance, but we should be careful to separate the things we're assuming from the things we observe. As E.T. Jaynes wrote in Probability Theory: The Logic of Science, trying to verify the probability of an event by performing experiments "would be like trying to verify a boy's love for his dog by performing experiments on the dog."

See, part of the problem with the way we humans interpret the world is that the physical laws we rely on--for example, that two colliding objects obey the law of conservation of momentum--can quickly outpace our abilities to calculate their consequences--say, the motions of every molecule of a balloon-full of air. We use probability as a way of approximating the behavior of these complex systems instead of having to understand them completely, but that doesn't mean that the events "are" random. A more powerful being might see things differently, the way adults see tic-tac-toe differently from the way little kids do. But we seem to be stuck with this uncertainty about complex systems. And there's really no system on Earth more complex than a human, which brings us back to the MHP.

In the setup to the Monty Hall Problem, we've assumed some things, all of which pertain to the actions of other people. First, there is the assumption that the car is equally likely to be behind any of the three doors (actually, assumption zero is that there even is a car at all). Presumably, some producer or somebody chose which door to put it behind--it's possible they might have had a preference for door #1, for example, because it's closer to the loading dock or looks better on TV. If we had records of thousands of shows, we might gain some insight into their decision process and detect some bias. But we're assuming otherwise. Secondly, and this is the real key, we have the assumption that Monty Hall knows which door has the car behind it. As a consequence, we can deduce that by opening up the remaining door (or one of the two remaining doors, if we initially chose the one with the car), he has added information to the set of things we know about the game. Namely, we know that if the car had been behind one of the other two doors, he would have been forced to open the door he did--that's essentially why switching gives us a chance of winning. If the other door had opened by chance, say a gust of wind blew it open and we happened to see the goat, then we'd have no reason to conclude anything about whether we should switch, because we just as easily could have seen the car. So, by knowing what Monty knows, we can improve our chances. In coin terms, it's as though we had a prearranged deal with the referee where if the coin is tails, he just tells us half the time and stays quiet the other half, and if the coin is heads he always stays quiet--so if he doesn't speak, we know there's a chance the coin is heads.

Now, on Deal or No Deal, hosted by the incomparable Howie Mandel, the situation is somewhat different. For those who haven't seen the show, it works like this: a contestant picks one of 26 briefcases, each containing a different dollar amount. He/she then opens some or all of the remaining briefcases and decides whether to keep going or sell the initial case. In the extreme situation in which he/she keeps going all the way to the end and there are only two cases left, the contestant has the option to keep the original case or switch. Let's you and I pretend that we were on the show. For simplicity, let's assume that initially 25 of the 26 cases had $0, and the one remaining case had $1 million. Also, let's assume that we opened 24 cases and inside each one was a big fat $0 (we got to say "NO DEAL!" a bunch of times, which was fun; also, they brought out Ellen Degeneres at some point). What does that mean about our prospects? Should we switch? Well, our assumptions, again, were (1) all cases were equally likely to contain the million dollars, and (2) nobody on the show knew which case was which. Under those assumptions, it doesn't matter if we switch or not, since the probability is of each case having the million. It's just like the Monty Hall Problem if Monty didn't know which door had the car behind it--nobody has given us any additional information with which to prefer one case over the other. If, however, we knew that Howie knew which case had the winner, and he had started the show by opening all the other cases, then we should absolutely switch in a heartbeat, because it would improve our chance of winning from to . It's all about what information Howie gives us. Also, if he could give us Anya's phone number while he's at it, that would help us out, too.

-DrM

Trig or Treat

Dear Dr. Math,
This is a question I thought of while pondering the air intake of a wood stove. The air intake is a series of holes, covered or uncovered by a sliding metal plate with equal sized holes.
Imagine 2 circles with equal radius, R. Slide one circle over the other. Express, in terms of R, how far one circle has to occlude the other such that half of the area is covered.
Bob H., Ashland, OR

Dear Bob,

Here's a picture of the problem, if I understand it correctly:

For legal reasons, before we get to the solution, I feel I should warn all you readers out there: what follows may involve some high-school level trigonometry, which I understand many of you have intentionally purged from your brains to make room for Grey's Anatomy plots. Part of the reason I like this question so much is that it shows that these concepts may very well have some relevance (outside of the very important pursuit of measuring the heights of buildings using a sextant) despite your high school math teacher's best attempts to convince you otherwise. Those readers who are subject to trigonometry-induced seizures should turn back now.

OK, with that out of the way, let's blow up part of the picture and label some of the relevant objects. The goal is to get a handle on this shady part of town:



First, there's the radius, R, which we've assumed is the same for the two circles. Let's call the angle formed by the center and two points of intersection . Note: this has nothing to do with thetans (or does it?). Splitting this angle down the middle forms two right triangles with an angle of . According to the rules of trigonometry, the height of each triangle is and the width is , as I've labeled here:

Now, the strategy I'd like to employ to compute the area of that funny little almond-shaped region, which I'll call C, is to think of it as consisting of two pieces, each of which is the difference between a pie-slice of the circle, A, and a triangle, B. In pictures:



The reason this helps is that circles and triangles are shapes whose areas we know how to compute. "Funny little almond shapes," not so much.

The area of the circular slice is in proportion to the whole area of the circle as the angle is to the whole angle of a circle, 360° (a quarter of a circle takes up 90°, for example). So in terms of R and , that's and so .
Now, the area of the whole triangle is , which in this case is . So, . By a sneaky trick I learned in trigonometry class, I can rewrite this as .

If we throw all these things into the hopper, we get that the area of the almond-shaped piece, C, is , and so . I can feel some of you starting to panic out there, but just take a deep breath and try to relax. Put on some Enya or something--maybe that song she wrote about trigonometry.

What were we doing? Oh yeah, right; now we have a formula for computing the area of the overlapping part of the two circles, which only depends on the angle . The question was, When is this area equal to half the area of the circle?, so we need to solve for . Half the area of the circle is ; therefore, the equation we need to solve is:



which, after we divide through by and clean up a bit leaves us with:

.

It's interesting to pause here and note that R completely vanished from the equation. This means whatever configuration we come up with as an answer must have the same angle, independent of the radius.

OK. So, how do we solve this equation?

Actually... we don't.

The problem is that we have a and a , and the thing about those two is that they're like Sydney and Cristina on Grey's Anatomy; they just don't mix well. Unfortunately, there's no way to get any further with this equation using the rules of algebra. So, here's where we cheat and approximate the solution with a calculator (in my case, a TI-89). Maybe someday I'll tell you all about what goes on inside a calculator when it does these approximations, or about how we could use calculus to solve the problem if the shape were something else. But anyway, for now, the answer is .

Lastly, we should translate this answer into a more meaningful form, for example by figuring out what the distance is between the two centers of the circles. Using trigonometry one last time, we can write this distance as , which for the magic above is . The final picture, then, is:






Put that in your wood stove and smoke it.

-DrM