On 26/05/2016 22:37, James Propp wrote:
One of us miscalculated. I get
0000->(Empty): 0 0001->01: 2 0010->10: 2 0011->(Empty): 0 0100->01: 2 0101->0101: 4 0110->(Empty): 0 0111->01: 2 1000->10: 2 1001->(Empty): 0 1010->1010: 4 1011->10: 2 1100->(Empty): 0 1101->01: 2 1110->10: 2 1111->(Empty): 0
0+2+2+0+2+4+0+2+2+0+4+2+0+2+2+0=24
And 24/16=3/2, not 7/4.
Can you find my mistake (or yours)?
Originally you wrote: | what's the expected number of uneliminated bits that | remain, or equivalently, what is the expected number | of bit-runs of odd length? but those two things are not equivalent. Consider, for instance, 0110. It has two bit-runs of odd length, one at each end, but because they are separated only by even-length runs they get merged and eliminated by the "keep removing pairs" process. The same goes for 1001, and the extra four odd runs turn your 24/16=3/2 into my 28/16=7/4. My numbers are from counting bit-runs of odd length; yours are from counting bit-runs of odd length not separated only by even-length runs. Given how much simpler your numbers come out than mine, I'm thinking there is probably a simpler characterization of what you're counting... -- g