I've solved my problem: the first key was to look at the whole distribution instead of just its mean (and to notice binomial coefficients), and the second key was to think inductively (if you prepend a bit to an already-reduced bit-string, and then reduce the result, what happens?). Here's the array you get when you count the number of bit strings of length n that reduce to a bit string of length k: 0 1 2 3 4 5 6 7 8 1: 1 2: 1 1 3: 3 1 4: 3 4 1 5: 10 5 1 6: 10 15 6 1 7: 35 21 7 1 8: 35 56 28 8 1 See the pattern? It's a bisected Pascal triangle, where numbers that are to the left of the symmetry line are omitted, numbers to the right of the line are included, and numbers ON the line get HALVED. (Oh, and also, the zeroeth row gets omitted.) A fun way to generate this table is with stacks of chips on {0,1,2,3,...}. To derive a new row, double the number of chips at each site and then "fire" each stack, where firing means sending half the chips to the left and half to the right, unless the stack is at 0, in which case firing means sending all the chips to the right (from 0 to 1). The sequence of expected values goes 1/1, 2/2, 6/4, 12/8, 30/16, 60/32, 140/64, 280/128, ... where the numerators are terms of OEIS sequence A100071 and the denominators are powers of two. Indeed, I'm not the first person to notice this: Apparently also the count of 'unmatched symbols' in the binary strings of length n (see A008314 <http://oeis.org/A008314>). - Wouter Meeussen <http://oeis.org/wiki/User:Wouter_Meeussen>, May 26 2013 Hi, Wouter! :-) Entry A008314 gives a variant of my triangular array in the form of a sequence, namely 1 1 1 1 1 3 1 4 3 1 5 10 1 6 15 10 1 7 21 35 1 8 28 56 35 ... and says: Row k also counts the binary strings of length k that have 0, 2 up to 2*floor(k/2) 'unmatched symbols'. See contributions by Marc van Leeuwen in Math StackExchange link. [Wouter Meeussen <http://oeis.org/wiki/User:Wouter_Meeussen>, Apr 17 2013] The text of entry A008314 never mentions that the entries are given by binomial coefficients. But they are, aren't they? Jim On Thursday, May 26, 2016, James Propp <jamespropp@gmail.com> wrote:
Also, I now think my original conjecture was wrong:
10000->1: 1 10001->101: 3 10010->0: 1 10011->1: 1 10100->101: 3 10101->10101: 5 10110->1: 1 10111->101: 3 11000->0: 1 11001->1: 1 11010->010: 3 11011->0: 1 11100->1: 1 11101->101: 3 11110->0: 1 11111->1: 1
1+3+1+1+3+5+1+3+1+1+3+1+1+3+1+1=30, not 32.
So the sequence of averages goes 1,1,3/2,3/2,15/16,...
Anyone care to write some code to compute more terms?
Jim
On Thursday, May 26, 2016, James Propp <jamespropp@gmail.com> wrote:
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