A sequence cannot end after an odd number of bits, because if you have 2n+1 bits ending with (n+1) 1s then you first had 2n bits ending with n 1s, and would have ended there.
Let A(n) = the number of sequences that terminate after exactly n steps, B(n) = the number of sequences of length n that haven’t terminated yet, and B(n,k) = the number of sequences of length n that haven’t terminated yet ending with exactly k 1s. Then A(2n) = B(2n-1,n-1) and A(2n+1) = 0.
For any k<n/2, B(n,k) = B(n-k-1). (The sequences counted by B(n,k) all end with a 0 and then k 1s, and didn’t terminate before that.) So, in particular, A(2n) = B(2n-1-(n-1)-1) = B(n-1).
B(n) = sum {0<=k<n/2} of B(n,k) = sum {0<=k<n/2} of B(n-k-1).
It isn’t immediately obvious to me how to get a closed form out of this, so I computed the first few terms and looked the numbers up in the Online Encyclopedia of Integer Sequences. It appears to be http://oeis.org/A002083 whose elements are conjectured to be asymptotically constant*2^n. (It’s interesting that the descriptions of this sequence in OEIS don’t mention anything trivially equivalent to what GSE has asked about here.)
The unconditional average length—which we already know is infinite—is the infinite sum {n>=1} of 2n A(2n) / 2^(2n) = the sum {n>=1} of 2n B(n-1) / 2^n. Writing b(x) = sum { n>=0 } of B(n) x^n, this equals 2b’(1/2). The information about the generating function on the OEIS page implies that b(1/2) is infinite but b(x) is finite for x<1/2, which implies that 2b’(1/2) is infinite. Check.
The average length of sequences that terminate is harder: it’s lim { N->inf } of sum { 1<=n<=N } of 2n A(2n) / (2^2N-B(2N)). Since I’m supposed to be doing the work I’m paid to do right now, I’ll leave it there for someone who may or may not be me to come back to :-).
(It’s interesting that the descriptions of this sequence in OEIS don’t mention anything trivially equivalent to what GSE has asked about here.)
Perhaps not trivially so, but this one from that page is exactly the one I worked out when I looked at the problem, and what I programmed to compute the table:
a(1)=1, else a(n) is sum of [ n/2 ] previous terms.
There’s an edge case at the very start that means that the OP’s sequence has an extra 1 at the beginning.
I was thinking of the material in the “Comment” section, which lists various examples of where the sequence arises, often (as here) of the form “a(n) = total number of objects of such-and-such a kind satisfying such-and-such conditions”. It’s true that one of the recurrence relations listed there also arises very straightforwardly from GSE’s definition of the sequence, but that’s not the same thing.
A sequence cannot end after an odd number of bits, because if you have 2n+1 bits ending with (n+1) 1s then you first had 2n bits ending with n 1s, and would have ended there.
Let A(n) = the number of sequences that terminate after exactly n steps, B(n) = the number of sequences of length n that haven’t terminated yet, and B(n,k) = the number of sequences of length n that haven’t terminated yet ending with exactly k 1s. Then A(2n) = B(2n-1,n-1) and A(2n+1) = 0.
For any k<n/2, B(n,k) = B(n-k-1). (The sequences counted by B(n,k) all end with a 0 and then k 1s, and didn’t terminate before that.) So, in particular, A(2n) = B(2n-1-(n-1)-1) = B(n-1).
B(n) = sum {0<=k<n/2} of B(n,k) = sum {0<=k<n/2} of B(n-k-1).
It isn’t immediately obvious to me how to get a closed form out of this, so I computed the first few terms and looked the numbers up in the Online Encyclopedia of Integer Sequences. It appears to be http://oeis.org/A002083 whose elements are conjectured to be asymptotically constant*2^n. (It’s interesting that the descriptions of this sequence in OEIS don’t mention anything trivially equivalent to what GSE has asked about here.)
The unconditional average length—which we already know is infinite—is the infinite sum {n>=1} of 2n A(2n) / 2^(2n) = the sum {n>=1} of 2n B(n-1) / 2^n. Writing b(x) = sum { n>=0 } of B(n) x^n, this equals 2b’(1/2). The information about the generating function on the OEIS page implies that b(1/2) is infinite but b(x) is finite for x<1/2, which implies that 2b’(1/2) is infinite. Check.
The average length of sequences that terminate is harder: it’s lim { N->inf } of sum { 1<=n<=N } of 2n A(2n) / (2^2N-B(2N)). Since I’m supposed to be doing the work I’m paid to do right now, I’ll leave it there for someone who may or may not be me to come back to :-).
Perhaps not trivially so, but this one from that page is exactly the one I worked out when I looked at the problem, and what I programmed to compute the table:
There’s an edge case at the very start that means that the OP’s sequence has an extra 1 at the beginning.
I was thinking of the material in the “Comment” section, which lists various examples of where the sequence arises, often (as here) of the form “a(n) = total number of objects of such-and-such a kind satisfying such-and-such conditions”. It’s true that one of the recurrence relations listed there also arises very straightforwardly from GSE’s definition of the sequence, but that’s not the same thing.