A tribute to Mickey
Alice is building skyscrapers at Infinity City. Bob is a science fiction monster who is toppling skyscrapers. Alice is twice as industrious as Bob. So here's what happens: Alice builds two skyscrapers. Then Bob destroys one. Alice builds two more. Then Bob destroys another. This goes on forever. At the end of forever, what is left standing?
(If you don't like the idea of "the end of forever", imagine that Alice and Bob are also getting faster and faster with each step. The first step takes a half hour, the second a quarter hour, the third an eighth of an hour... so reaching "the end of forever" just takes an hour.)
The surprising answer is that the order matters: you get different answers depending on how Bob decides which skyscraper to violently unmake next.
Say the skyscrapers that Alice builds are numbered 1, 2, 3, ...
Now say after Alice builds 1 and 2, Bob destroys building number 1. Then she builds 3 and 4, and Bob destroys number 3. Bob goes on destroying number 5, 7, 9, .... At the end of forever, all of the odd-numbered buildings are gone, and the even-numbered ones are still around. So Infinity City has infinitely many skyscrapers.
But if Bob instead destroys number 1, and then number 2, and then number 3, and so on, then at the end of forever there are no skyscrapers left at all, because every one of them is reduced to rubble.
Now here's the problem: what happens if Bob chooses the next skyscraper randomly? That is, at each step there are a finite number of buildings still standing, and Bob picks a building to destroy from a uniform distribution over all of them. When this process goes on forever, I claim (and this is cool) that the probability of any building staying upright goes to zero. Prove it.
(If you don't like the idea of "the end of forever", imagine that Alice and Bob are also getting faster and faster with each step. The first step takes a half hour, the second a quarter hour, the third an eighth of an hour... so reaching "the end of forever" just takes an hour.)
The surprising answer is that the order matters: you get different answers depending on how Bob decides which skyscraper to violently unmake next.
Say the skyscrapers that Alice builds are numbered 1, 2, 3, ...
Now say after Alice builds 1 and 2, Bob destroys building number 1. Then she builds 3 and 4, and Bob destroys number 3. Bob goes on destroying number 5, 7, 9, .... At the end of forever, all of the odd-numbered buildings are gone, and the even-numbered ones are still around. So Infinity City has infinitely many skyscrapers.
But if Bob instead destroys number 1, and then number 2, and then number 3, and so on, then at the end of forever there are no skyscrapers left at all, because every one of them is reduced to rubble.
Now here's the problem: what happens if Bob chooses the next skyscraper randomly? That is, at each step there are a finite number of buildings still standing, and Bob picks a building to destroy from a uniform distribution over all of them. When this process goes on forever, I claim (and this is cool) that the probability of any building staying upright goes to zero. Prove it.
Posted by Jeff on Tuesday, September 26, 2006
3 Comments:
forgive my ignorance - but by definition doesn't infinity mean "no end"? if there is an end - would not alice and bob both epxerience it at the same time - at which point bob would have destroyed half as many buildings as alice had built regardless of the order he destroyed them in?
i don't think that is the usual definition of "infinite", at least if we're talking about sets. let's think about some examples. think of all of the fractions that are less than or equal to 1/2. there are infinitely many of them, right? but there's also a last one (an "end"): 1/2.
but that's talking about sets, and not processes. you're right that a natural way to think about an infinite process is one that has "no end", if by that we mean "no last step". it could still have an "end", though, in the sense that there could be a time after which it's finished. (that was the point of imagining the steps getting faster and faster--after an hour, all of the steps are finished, even though there are infinitely many steps.)
as to your second point, you're totally right. if the process has an end--a last step--so the process is finite, then bob will destroy only half of the buildings, regardless of order. so the crazy result is that, even though for every finite amount of steps, there are still buildings standing, after infinitely many steps there could be nothing left at all! it is kind of mind-blowing.
dude.
Post a Comment
<< Home