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

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?

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 Now, add these together. We have $$(n/2)\sum_{kn/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}

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.

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

:)