Provisional solutions by H Reuvers

11623 A fair coin is tossed n times and the results recorded as a bit string. A run is a maximal subsequence of identical tosses. Let the random variable Xn be the number of runs in the bit string not immediately followed by a longer run. Find E(Xn).

Solution:

E(Xn) = SUM(k from 1 to n: (n-1 over k-1)*(1+(k-1)*((1/2)*(1-prob)+prob)))/2n-1, where
2n-1 is the number of compositions of n,
(n-1 over k-1) is the number of compositions of n in k parts;
the term 1 counts the last part (which will never be followed by a larger part);
for the other k-1 parts holds that they either will be followed by an equal part (with a chance we denote by prob),
or in half of the cases by a smaller part.

Because SUM(k from 1 to n: (n-1 over k-1)) = 2n-1 and SUM(k from 1 to n: (k-1)*(n-1 over k-1)) = (n-1)*2n-2, we find
E(Xn) = 1 + (n-1)/4 + (1/2n)*SUM(k from 1 to n: (n-1 over k-1)*(k-1)*prob).

In this last sum, the term with k=2 is e/2n where e=1 if n is even and e=0 if n is odd. We find
E(Xn) = 1 + (n-1)/4 + e/2n + (1/2n)*SUM(k from 3 to n: SUM(m from 1 to int((n-(k-2))/2): (k-1)*(n-2m-1 over k-3))), where
(n-2m-1 over k-3) is the number of compositions of n-2m in k-2 parts.

This last doublesum can be calculated by changing the order of summation. With p:=int((n-1)/2) we get

SUM(m from 1 to p: SUM(k from 3 to n-2m+2: (k-1)*(n-2m-1 over k-3))) =
SUM(m from 1 to p: SUM(j from 0 to n-2m-1: (j+2)*(n-2m-1 over j))) =
SUM(m from 1 to p: 2n-2m + (n-2m-1)*2n-2m-2) =
(2n+(n-1)*2n-2)*(1-(1/4)p)/3 - 2n-1*SUM(m from 1 to p: m*(1/4)m), so

E(Xn) = (n+3)/4 + e/2n + ((n+3)/12)*(1-(1/4)p) -(2/9)*(1+p*(1/4)p+1-(p+1)*(1/4)p))
where p:=int((n-1)/2) and e:=1 if n is even and e:=0 if n is odd

(This outcome should be equal to 199/64 for n=7, and it is.)