Let $X_1,\ldots,X_n$ be i.i.d. Bernoulli with some parameter $1/2$. Let $\bar{X}_n = \frac{1}{n} \sum_{i=1}^n X_i$. I am trying to show $$\mathbb{E} \min\{\bar{X}_n,1-\bar{X}_n\} \ge \frac{1}{2} - C n^{-1/2},$$ but am having trouble.
It is clear that the left-hand side is $\le 1/2$, but it is not clear to me why the fluctuations are on the order of $n^{-1/2}$. Any hints or references would be appreciated!
I noticed that if we consider the one-dimensional random walk defined by $(2X_i-1)_{i=1}^n$, then $n(1-\min\{\bar{X}_n, 1-\bar{X}_n\})$ is the absolute distance of the random walk, but I am not sure how this could help.
You want to show that $$ \mathbb{E}[ \min\left(n\bar{X}, n(1-\bar{X})\right) ] \geq \frac{n}{2} - C\sqrt{n} $$ for some constant $C>0$, which is equivalent to $$ \mathbb{E}[ \min\left(n\bar{X} - \frac{n}{2}, \frac{n}{2}-n\bar{X})\right) ] \geq - C\sqrt{n} $$ that is $$ \mathbb{E}[ \lvert \mathbb{E}[S_n] - S_n \rvert ] \leq C\sqrt{n} $$ where $S_n = \sum_{k=1}^n X_k$ follows a $\operatorname{Bin}(n,\frac{1}{2})$ distribution. Now, observe that the variance of $S_n$ is $$ \mathbb{E}[ \left(S_n - \mathbb{E}[S_n] \right)^2 ] = \frac{n}{4} $$ and by Jensen's inequality, the square function being convex, $$ \mathbb{E}[ \lvert \mathbb{E}[S_n] - S_n \rvert ]^2 \leq \mathbb{E}[ \left(S_n - \mathbb{E}[S_n] \right)^2 ] = \frac{n}{4}. $$