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.