Just as a piece of constructive criticism, I will note that the argument is probably a bit hard to read if you don’t already know a decent amount of combinatorics / probability. In particular you might want to cite Markov’s inequality explicitly.
Yeah, it’s a bit terse. I was writing while at work, and since regrettably “doing combinatorics on Less Wrong” isn’t part of my job description I didn’t spend much time polishing.
Also, there’s a mistake, though it doesn’t invalidate the argument.
So here’s a more leisurely and less-wrong explanation.
Imagine that you just generate 0s and 1s for ever. You don’t stop when you find a long enough run of 1s, you merely note that fact and continue generating bits. How many times, on average, will that happen?
The probability that it happens after generating exactly n bits is the fraction of n-bit strings that end with at least n/2 consecutive 1s. When n=2m is even, that means you get to choose the first m bits arbitrarily and then the remaining m are all 1s. When n=2m+1 is odd, it means you get to choose the first m bits arbitrarily and then the remaining m+1 are all 1s. So the probability that you get to call “stop!” after a given number of bits goes: 1⁄2, 1⁄2, 1⁄4, 1⁄4, 1⁄8, 1⁄8, etc.
Now, the average number of times you get to call “stop!” is just the sum of those probabilities. (“Expectations are additive”: the average number of times you get to say “stop!” equals the average number of times you get to say it after one bit, plus the average number of times you get to say it after two bits, etc., and those averages are just the probabilities.) So the average number of “stop!”s is 1/2+1/2+1/4+1/4+etc = 2.
Now, handwavily, the fact that this is finite should be enough to make you suspect that there’s a nonzero probability of never seeing a stopping-point: after all, there’s a nonzero probability of reaching (say) 100 bits without stopping, and after that the probability should look like 1/2^50+1/2^50+1/2^51+… = 1/2^48 which is very small.
That handwavy argument is actually wrong, because it’s possible that conditional on not yet having reached a stopping point the probability of stopping might get bigger. So, e.g., imagine that the process went like this: if you’ve generated a 0s and b 1s, your next bit is 1 with probability 1-1/a if b=0 and 0 otherwise; you stop when you first generate a 1. Then the expected (average) total number of stopping points is just 1 (because once you’ve generated one 1 you never generate another) but the probability of ever stopping is also 1 -- with each bit that goes past without a 1 generated, the probability that you stop on the very next turn gets closer to 1.
In our situation, though, it’s the other way about: in so far as previous stoppability makes a difference, having been unable to stop for a while makes you less likely to be entitled to stop.
To be more precise: Suppose your first three bits happen to be 0. (An event with probability 1⁄8.) Then if at any later point you’re entitled to stop, you’d have been entitled to stop whatever the first three bits were. In particular, Pr(can stop at time t | first three bits are 0) ⇐ Pr(can stop at time t). Also, Pr(can stop at time t | first three bits are 0) is 0 for t=1,2,3.
Therefore, conditional on the first three bits being 0, the expected (average) number of “stop!”s is at most what you get on replacing the first three terms of the series with 0s: 0+0+0+1/4+1/8+1/8+1/16+1/16+… = 3⁄4.
[Note: in my original much more terse explanation, I said that those two things are equal. That was the mistake I mentioned earlier.]
This implies that, conditional on starting with three 0s, there’s at least a 1⁄4 probability of never being entitled to stop. Why? Because expected number of stops ⇐ Pr(any stops), because expected number of stops ⇐ sum {all n} of Pr(exactly n stops) . n ⇐ sum {n>=1} of Pr(exactly n stops) . 1 = sum {n>=1} of Pr(exactly n stops) = Pr(at least one stop).
So. If (as happens with probability 1⁄8) the first three bits are 0, then with probability at least 1⁄4 you never get to stop. Therefore Pr(never get to stop) >= 1⁄8 . 1⁄4 = 1⁄32, and therefore Pr(ever get to stop) ⇐ 31⁄32. In particular, that last probability isn’t 1.
Upvoted for the nice argument.
Just as a piece of constructive criticism, I will note that the argument is probably a bit hard to read if you don’t already know a decent amount of combinatorics / probability. In particular you might want to cite Markov’s inequality explicitly.
Yeah, it’s a bit terse. I was writing while at work, and since regrettably “doing combinatorics on Less Wrong” isn’t part of my job description I didn’t spend much time polishing.
Also, there’s a mistake, though it doesn’t invalidate the argument.
So here’s a more leisurely and less-wrong explanation.
Imagine that you just generate 0s and 1s for ever. You don’t stop when you find a long enough run of 1s, you merely note that fact and continue generating bits. How many times, on average, will that happen?
The probability that it happens after generating exactly n bits is the fraction of n-bit strings that end with at least n/2 consecutive 1s. When n=2m is even, that means you get to choose the first m bits arbitrarily and then the remaining m are all 1s. When n=2m+1 is odd, it means you get to choose the first m bits arbitrarily and then the remaining m+1 are all 1s. So the probability that you get to call “stop!” after a given number of bits goes: 1⁄2, 1⁄2, 1⁄4, 1⁄4, 1⁄8, 1⁄8, etc.
Now, the average number of times you get to call “stop!” is just the sum of those probabilities. (“Expectations are additive”: the average number of times you get to say “stop!” equals the average number of times you get to say it after one bit, plus the average number of times you get to say it after two bits, etc., and those averages are just the probabilities.) So the average number of “stop!”s is 1/2+1/2+1/4+1/4+etc = 2.
Now, handwavily, the fact that this is finite should be enough to make you suspect that there’s a nonzero probability of never seeing a stopping-point: after all, there’s a nonzero probability of reaching (say) 100 bits without stopping, and after that the probability should look like 1/2^50+1/2^50+1/2^51+… = 1/2^48 which is very small.
That handwavy argument is actually wrong, because it’s possible that conditional on not yet having reached a stopping point the probability of stopping might get bigger. So, e.g., imagine that the process went like this: if you’ve generated a 0s and b 1s, your next bit is 1 with probability 1-1/a if b=0 and 0 otherwise; you stop when you first generate a 1. Then the expected (average) total number of stopping points is just 1 (because once you’ve generated one 1 you never generate another) but the probability of ever stopping is also 1 -- with each bit that goes past without a 1 generated, the probability that you stop on the very next turn gets closer to 1.
In our situation, though, it’s the other way about: in so far as previous stoppability makes a difference, having been unable to stop for a while makes you less likely to be entitled to stop.
To be more precise: Suppose your first three bits happen to be 0. (An event with probability 1⁄8.) Then if at any later point you’re entitled to stop, you’d have been entitled to stop whatever the first three bits were. In particular, Pr(can stop at time t | first three bits are 0) ⇐ Pr(can stop at time t). Also, Pr(can stop at time t | first three bits are 0) is 0 for t=1,2,3.
Therefore, conditional on the first three bits being 0, the expected (average) number of “stop!”s is at most what you get on replacing the first three terms of the series with 0s: 0+0+0+1/4+1/8+1/8+1/16+1/16+… = 3⁄4.
[Note: in my original much more terse explanation, I said that those two things are equal. That was the mistake I mentioned earlier.]
This implies that, conditional on starting with three 0s, there’s at least a 1⁄4 probability of never being entitled to stop. Why? Because expected number of stops ⇐ Pr(any stops), because expected number of stops ⇐ sum {all n} of Pr(exactly n stops) . n ⇐ sum {n>=1} of Pr(exactly n stops) . 1 = sum {n>=1} of Pr(exactly n stops) = Pr(at least one stop).
So. If (as happens with probability 1⁄8) the first three bits are 0, then with probability at least 1⁄4 you never get to stop. Therefore Pr(never get to stop) >= 1⁄8 . 1⁄4 = 1⁄32, and therefore Pr(ever get to stop) ⇐ 31⁄32. In particular, that last probability isn’t 1.