Arithmetic mean of error of N coin flips from N/2

Question

When flipping $N$ fair coins, there is obviously an expected output of $\frac{N}{2}$ heads, but there will be some error from that value for individual runs. What I want is the arithmetic mean of error over all possible runs is, as a function $E$ on $N$

I can do this if I have a particular $N$

For $N=1$, the possible outcomes are {<1>,<0>} with sums of {1,0} and an expected value of $\frac12$, so $E(1) = \frac12$

For $N=2$, the possible outcomes are {<0,0>,<0,1>,<1,0>,<1,1>} with sums of {0,1,1,2} and an expected value of $1$, so $E(2) = \frac12$

For $N=3$, the possible outcomes are {<0,0,0>,<0,0,1>,<0,1,0>,<0,1,1>,<1,0,0>,<1,0,1>,<1,1,0>,<1,1,1>} with sums of {0,1,1,2,1,2,2,3} and an expected value of $\frac32$, so $E(2) = \frac34$

I continued this pattern (with the help of a computer) and got

1 / 2
1 / 2
3 / 4
3 / 4
15 / 16
15 / 16
35 / 32
35 / 32
315 / 256
315 / 256
693 / 512
693 / 512
3003 / 2048
3003 / 2048
6435 / 4096
6435 / 4096
109395 / 65536
109395 / 65536
230945 / 131072
230945 / 131072
969969 / 524288
969969 / 524288
2028117 / 1048576
2028117 / 1048576
16900975 / 8388608
16900975 / 8388608
35102025 / 16777216

At this point the program crashed (probably because I was creating a giant list of the possible outputs which was pretty inefficient).

I'm having a hard time figuring this out inductively, though perhaps that is not the best approach. How should I go about solving this?

Answer 1

You want $$ E(n)=2^{-n}\sum_{k=0}^n|k-n/2|\binom{n}k $$ Let us split this sum into two halves: \begin{align} \sum_{k>n/2}(k-n/2)\binom{n}k &=\sum_{k>n/2}k\binom{n}{k}&-&&(n/2)\sum_{k>n/2}\binom{n}{k} \\&=n\sum_{k>n/2}\binom{n-1}{k-1}&-&&(n/2)\sum_{k>n/2}\binom{n}{k} \end{align} For the other half, \begin{align} \sum_{k<n/2}(n/2-k)\binom{n}k &=(n/2)\sum_{k<n/2}\binom{n}{k}&-&&\sum_{k<n/2}k\binom{n}{k} \\&=(n/2)\sum_{k<n/2}\binom{n}{k}&-&&n\sum_{k<n/2}\binom{n-1}{k-1} \end{align} Now, add these together. We have $(n/2)\sum_{k<n/2}\binom{n}{k}-(n/2)\sum_{k>n/2}\binom{n}{k}=0$, and all but one terms cancel in the difference between the other sums, so the result is $$ E(n)= \begin{cases} \displaystyle 2^{-n}n\binom{n-1}{n/2-1} & \text{if $n$ is even,}\\\\ \displaystyle 2^{-n}n\binom{n-1}{(n-1)/2} & \text{if $n$ is odd.} \end{cases} $$ To see prove the pattern you noticed, note that when $n$ is odd, we have \begin{align} E(n) &=2^{-n}n\binom{n-1}{(n-1)/2} \\&=2^{-n}(n+1)/2\cdot \frac{n}{(n+1)/2}\binom{n-1}{(n-1)/2} \\&=2^{-(n+1)}(n+1)\binom{n}{(n+1)/2} \\&=2^{-(n+1)}(n+1)\binom{n}{(n-1)/2} \\&=E(n+1). \end{align}

Answer 2

It seems to be that $$E(2N)=E(2N-1)=\frac{(2N-1)!}{2^{2N-1}\cdot ((N-1)!)^2}$$ I used the OEIS to find a similar sequence from which I found this formula.

Answer 3

Since $E(2n-1)=E(2n)$ as we can see, we'll solve only the case in which $N$ is even. Notice that the number of possible output sequences is:

$$2^N$$

Notice now that if we consider all of the sequences with $i<\frac N2$ heads, we'll have that the sum of errors is:

$$\sum_{i=0}^{\frac N2} \left(\frac N2-i\right) {N \choose i} $$

In fact the error $\left(\frac N2-i\right)$ is repeated for all of the sequences with $i$ tails that are ${N \choose i}$. If $i=\frac N2$ the error is zero. If $i>\frac N2$ the procedure is symmetrical to the first one so the sum of all the errors is:

$$2\sum_{i=0}^{\frac N2} \left(\frac N2-i\right) {N \choose i}=\frac{N+2}{2} {N \choose \frac N2+1} $$

Dividing it by $2^N$ as said:

$$\frac{N+2}{2^{N+1}} {N \choose \frac N2+1} $$

Since this function is valid only for $N$ even we can make a substitution $N \to 2\lceil \frac N2 \rceil $ . So the general formula is:

$$E(N)=\frac{\lceil \frac N2 \rceil+1}{2^{2\lceil \frac N2 \rceil}} {2\lceil \frac N2 \rceil \choose \lceil \frac N2 \rceil +1}$$

Where $\lceil . \rceil$ is the ceiling function

:)