So neither of us miscalculated; we correctly calculated two different things that I overhastily and mistakenly assumed were equal! (Is there a nice "static" way to characterize "the number of bits that remain" without reference to the bit-elimination process?) Anyway, I have to retract what I said about using recurrence relations; I don't see how to solve for the nth term of the sequence using finite-state-machines technology. Jim On Thursday, May 26, 2016, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun