If the expected number of stopping times is finite, the probability of stopping cannot equal 1. (Because the expected number of stopping times when the first K bits are 0 must go to 0, and therefore pass below 1.)
So looking for a sequence of 1s of length no more than log (base 2) of n plus a constant should be necessary to get it to always stop.
Now I’m going to try and calculate the distribution. The only thing that matters at each step is the number of 1s at the end. This has a 50% chance of being increased by 1 and a 50% chance of falling to 0.
If you analyze this in a way that it’s not worth it to explain on this poorly-suited medium, you get my excel calculation, which gives an expected value of .93975 conditional on terminating.
This is weird because I got the same terminating probabilities as Richard, but different expected value.
What about lengths other than n/2?
If the expected number of stopping times is finite, the probability of stopping cannot equal 1. (Because the expected number of stopping times when the first K bits are 0 must go to 0, and therefore pass below 1.)
So looking for a sequence of 1s of length no more than log (base 2) of n plus a constant should be necessary to get it to always stop.
Now I’m going to try and calculate the distribution. The only thing that matters at each step is the number of 1s at the end. This has a 50% chance of being increased by 1 and a 50% chance of falling to 0.
If you analyze this in a way that it’s not worth it to explain on this poorly-suited medium, you get my excel calculation, which gives an expected value of .93975 conditional on terminating.
This is weird because I got the same terminating probabilities as Richard, but different expected value.