Expected number of minimum of heads and tails

Question

Flip a fair coin $n$ times. Let $H$ denote the number of heads and $T$ the number of tails. What is $\mathbb{E}[\min(H,T)]$?

We know that $\mathbb{E}[H]=\mathbb{E}[T]=n/2$, and that $H$ and $T$ are distributed according to a binomial distribution, which has mean $n/2$ and variance $n/4$. Also, $T=n-H$ always. How can we find $\mathbb{E}[\min(H,n-H)]$?

Answer 1

Observe that $H$ has binomial distribution with parameters $n$ and $p=\frac12$.

So expectation $\mathbb E[\min(H,n-H)]$ is found by calculating:$$2^{-n}\sum_{k=0}^{n}\binom{n}{k}\min\left(k,n-k\right)$$

---

addendum:

Hints for special case: $n$ is odd:

$$\sum_{k=0}^{2m+1}\binom{2m+1}{k}\min\left(k,2m+1-k\right)=2\sum_{k=1}^{m}\binom{2m+1}{k}k=2\left(2m+1\right)\sum_{k=1}^{m}\binom{2m}{k-1}$$

and:

$$2\sum_{k=1}^{m}\binom{2m}{k-1}=2\sum_{k=0}^{m-1}\binom{2m}{k}=\sum_{k=0}^{2m}\binom{2m}{k}-\binom{2m}{m}=2^{2m}-\binom{2m}{m}$$

Do check me on mistakes, though. This stuff is slippery.

---

closed form for odd $n$:$$n\left[\frac{1}{2}-\binom{n-1}{\frac{1}{2}n-\frac{1}{2}}2^{-n}\right]$$

closed form for even $n$:$$n\left[\frac{1}{2}-\binom{n}{\frac{1}{2}n}2^{-n-1}\right]$$

Answer 2

Given natural $\text{n}$, it suffices to show that $$\sum_{h\ =\ 0}^{\text{n}}\ \text{min}\left(h,\text{n}-h\right)\cdot\binom{\text{n}}{h}\ =\ \text{n}\cdot\left(2^{\text{n}-1}-\binom{\text{n}-1}{\left\lfloor\tfrac{\text{n}}{2}\right\rfloor}\right)$$ (note the minor typo in the accepted answer). The claim follows from a counting argument: \begin{align*} \sum_{h\ \colon\ \text{n}+1} \text{min}\left(h,\text{n}-h\right)\cdot\binom{\text{n}}{h}\ &=\ \sum_{h\ \colon\ \text{n}+1} \sum_{\substack{H\ \subseteq\ \text{n} \\ \left|H\right|\ =\ h}}\ \sum_{\substack{i\ \colon\ \text{n} \\ i\ \colon\ H \iff \left|H\right|\ \leq\ \tfrac{\text{n}}{2}}}\ 1\\ &=\ \sum_{H\ \subseteq\ \text{n}} \sum_{\substack{i\ \colon\ \text{n} \\ i\ \colon\ H \iff \left|H\right|\ \leq\ \tfrac{\text{n}}{2}}}\ 1\\ &=\ \sum_{i\ \colon\ n} \sum_{\substack{H\ \subseteq\ \text{n} \\ i\ \colon\ H \iff \left|H\right|\ \leq\ \tfrac{\text{n}}{2}}}\ 1\\ &=\ \sum_{i\ \colon\ \text{n}}\ \left(\sum_{\substack{H\ \subseteq\ \text{n} \\ i\ \colon\ H\ \land\ \left|H\right|\ \leq\ \tfrac{\text{n}}{2}}}\ 1\ +\ \sum_{\substack{H\ \subseteq\ \text{n} \\ i\ \not\colon\ H\ \land\ \left|H\right|\ >\ \tfrac{\text{n}}{2}}}\ 1\right)\\ &=\ \sum_{i\ \colon\ \text{n}}\ \left(\sum_{\substack{H\ \subseteq\ \text{n}\setminus\left\{i\right\} \\ \left|H\right|\ \leq\ \tfrac{\text{n}}{2}-1}}\ 1\ +\ \sum_{\substack{H\ \subseteq\ \text{n}\setminus\left\{i\right\} \\ \left|H\right|\ >\ \tfrac{\text{n}}{2}}}\ 1\right)\\ &=\ \sum_{i\ \colon\ \text{n}}\ \sum_{\substack{H\ \subseteq\ \text{n}\setminus\left\{i\right\} \\ \left|H\right|\ \neq\ \left\lfloor\tfrac{\text{n}}{2}\right\rfloor}}\ 1\\ &=\ \boxed{\text{n}\cdot\left(2^{\text{n}-1}-\binom{\text{n}-1}{\left\lfloor\tfrac{\text{n}}{2}\right\rfloor}\right)} \end{align*} Where "$\text{n}$" is doubly interpreted as the natural it names and as the set $\left\{0,\dots,\text{n}-1\right\}$ and "$\colon$" serves as shorthand for "$\in$". $\blacksquare$

(If one carefully considers what each sum above is actually computing, I think they'll agree that there's essentially no algebraic manipulation involved despite the argument's presentation.)