The number of sequences of length 2n ending with n 1s is 2^n.
The number of sequences of length 2n+1 ending with (n+1) 1s is also 2^n.
Hence, if you generate 0s and 1s at random for ever, the expected number of stopping-points you encounter is 1/2 + 1/2 + 1/4 + 1/4 + 1/8 + 1/8 + ... = 2.
If you begin with 000 then the expected number of stopping points after that is 3/4, hence the probability of stopping at all is at most 3/4. Hence the overall probability of ever stopping is at most 1 - 1/8.1/4 = 0.96875. (It must in fact be less than that.)
So it is not true that "all of these sequences will eventually terminate", nor even that a random such sequence terminates with probability 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.
I came up with this problem the other day. I don't have nearly enough math to solve it. Do any of you wise folk have insight?
Imagine a sequence of randomly generated 0s and 1s. I start from nothing and generate this sequence one term at a time. I stop when I'm at the end of a streak of 1s which is at least one half the length of the total sequence.
For example:
01
0010110101101011111111111111
010110111111 -EDIT: Obviously, this is wrong, because it would terminate at 01. Sorry.
What is the average length of such sequences?
I know that all of these sequences will eventually terminate. I just don't know if the length diverges, and I'm not sure how to deal with the problem.