1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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}

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

:)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.