On 26/05/2016 16:14, James Propp wrote:
One question that comes to mind is, if you randomly pick an integer between 2^(n-1) and 2^n-1, what's the expected number of uneliminated bits that remain, or equivalently, what is the expected number of bit-runs of odd length? (If you prefer, you can look at all bit strings of length n, whether they begin with a 1 or a 0; the answer is the same.)
I get the sequence of answers 1, 1, 3/2, 3/2, ...; I'm guessing the pattern continues as 2, 2, 5/2, 5/2, etc.
I get a different answer. Using the alternative formulation (all length-n bit-strings) and starting at length 0, I get 0, 1, 1, 3/2, 7/4, 17/8, 39/16, 89/32, ... which doesn't seem especially beautiful. (The corresponding integer sequence 0, 2, 4, 12, 28, 68, ... doesn't appear to be in OEIS.) Have I miscalculated? -- g