Suppose that $x \sim \text{Benoulli}(1/2)$ with $\bar x = 1/2$ and we have $N$ i.i.d. samples and compute $\hat x = (x_1 \dots x_N)/N$. Hoeffding's inequality says that with high probability probability:
$$|\bar x - \hat x| = O( \frac{1}{\sqrt{N}}).$$
Can we show (via a concrete example) that with a constant probability, we have $$\hat x - \bar x= \Theta( \frac{1}{\sqrt{N}})?$$
My attempt: I think this is true based on the tightness of Hoeffding's inequality. My thought is that with probability $\approx 1/2$, we sample more than $N/2$ ones so $\hat x > 1/2 = \bar x$. So we want to show that with constant probability, we sample $N/2 + c\sqrt{N}$ ones, where $c$ is a constant. It appears that I need to show that Binomial CDF with $N/2 + c\sqrt{N}$ successes has a constant lower bound. But the CDF does not have a closed form. How can I show this lower bound?