Chebyshev's inequality and CLT to approximate 1.000.000 coin tosses probability Let S be the number of heads in 1,000,000 tosses of a fair coin. Use Chebyshev’s
inequality, and the CLT to estimate the probability
that S lies between 499,500 and 500,500. Use the same two methods
to estimate the probability that S lies between 499,000 and 501,000.
S lies between 499,500 and 500,500  :  
Using CLT : $$P(499500 \leq S_{n} \leq 500500)$$
$$\vdots$$
$$\approx \Phi(3) - \Phi(-3) \approx 0.6826$$
Using Chebyshev's inequality : $$P(|X-500000| \geq 500) \leq \frac{Var(X)}{500^2} = \frac{np(1-p)}{500^2} = 1$$
S lies between 499,000 and 501,000 :  
Using CLT : $$P(499000 \leq S_{n} \leq 501000)$$
$$\vdots$$
$$\approx \Phi(2) - \Phi(-2) \approx 0.9544$$
Using Chebyshev's inequality : $$P(|X-500000| \geq 1000) \leq \frac{Var(X)}{1000^2} = \frac{np(1-p)}{1000^2} = \frac{1}{4}$$
Where am I wrong in the Chebyshev's inequality ?
 A: $P(|X-500000| \geq 500) < 1$ is trivial.
The another case
\begin{align}
P(|X-500000| \geq 1000) &= P(X \geq 501000) + P(X \leq 499000)\\
&= 1 - P(499000 \leq X \leq 501000) \\
&\approx 1-0.9544=0.0456 < 1/4
\end{align}
Everything is ok, isn't it ?
A: There are random variables with virtually all the probability distribution less than one standard deviation away from the mean, and there are random variables with all the probability distribution less than or equal to one standard deviation away from the mean; the Chebyshev inequality has to take these into account  
Here $\mu=500000$ and $\sigma=500$. The cases are one and two standard deviations from the mean
So look at the directions of the Chebyshev inequalities and the trivial bounds the other side; there are also variants altering the strictness of the inequalities 
$$0 \lt P(|X-\mu| \geq \sigma) \leq  1$$ $$0 \le P(|X-\mu| \geq 2\sigma) \leq   \frac14$$
and in the other direction 
$$0 \lt P(|X-\mu| \leq \sigma) \leq   1$$ $$\frac34 \leq P(|X-\mu| \leq 2\sigma) \leq  1$$
