Expected number of heads

Question

You flip $n$ coins and your goal is to maximize the number of heads. Your expected value is $\frac{n}{2}$. Now what if you're allowed to pick a coin and re-flip it, what does your expected value become?

I have 2 different formulas, both seem logical to me, but they can't be both correct which is why I'm confused:

1. $E[X]= \frac{1}{2^n}\cdot n + \frac{2^n-1}{2^n} \cdot \frac{n}{2}$
2. $E[X]= \frac{n}{2} + \frac{2^n-1}{2^n}\cdot \frac{1}{2}$

Which one is correct? And what's the flaw with the incorrect formula?

Answer 1

Number 1 is incorrect. Regarding the explanation you gave for it in the comments:

well, you get $n$ heads with probability $1/2^n$, in which case you don't re-flip, and with probability $\frac{2^n−1}{2^n}$ I re-flip a coin: among the first $n−1$ coins I'm expected to have $\frac{n−1}{2}$ heads, and the extra flip adds $\frac{1}{2}$ hence $\frac{n}{2}$ in total.

The main problem here is regarding the definition of the "first $n-1$ coins". Whatever way you define it, the expected number of heads in the "first $n-1$ coins" will not be $\frac{n-1}{2}$ (except in the trivial case of $n=1$ where your two choices of $E[X]$ agree)

---

The logic for number 2 is sound. In particular, we are able to define $X = X_i + X_e$ where $X_i$ is the initial number of heads and $X_e$ is the number of "extra" heads we get with our later flip. The only detail Doing it this way, we have

$$E[X] = E[X_i + X_e] = E[X_i] + E[X_e] = \frac{n}{2} + 1 \cdot P(X_e=1)$$ and $$P(X_e = 1) = P(X_e=1, X_i < n) = P(X_i < n) \cdot P(X_e = 1 | X_i < n)$$ which matches your formula given in number 2 because $X_e|(X_i<n) = X_e | (\text{We reflip a coin})$ is a simple Boolean taking value $1$ with prob. $1/2.$

Answer 2

The correct argument for your first method is:

You get $n$ heads with probability $1/2^n$, in which case you don't re-flip. With probability $(2^n−1)/2^n$ you have probability $1/2$ of increasing the number of heads by $1$.

So the new expected value is $$\frac{n}{2}+\frac{2^n-1}{2^n}\times \frac{1}{2}.$$

The problem with your argument is that you are analysing the cases (which have total probability $\frac{2^n-1}{2^n}$) where you know there were not $n$ heads and knowing this alters the probabilities and therefore alters the $\frac{n-1}{2}$ result.