Markov Inequality results seems too high The Markov Inequality states that
$$P(X>\alpha) \le \frac{E[X]}{\alpha}$$
If I flip a fair coin 100 times, I was trying to calculate the probability that there were at least 90 tails in order to determine whether this series of events was an outlier or not. I was expecting that this would be an outlier according to the Markov Inequality.
Since heads and tails are equally likely, I stated that $E[X] = 50$ (and that  $\alpha = 90$), which yields:
$$P(X > 90) \le \frac{50}{90} = \frac{5}{9} \approx 0.56$$
This seems absurdly high to me because it is saying that this extreme event could be more likely than not (which would imply that this is not an outlier). I do realize that this is an upper bound, but am I missing something here?
 A: Markov's inequality is answering the question "Knowing nothing except that $X \ge 0$ and $\mathbb E[X] = 50$, how unlikely is it in the worst case that $X \ge 90$?"
If this is all we know, it is possible that $X$ is a random variable equal to $90$ with probability $\frac59$ and $0$ the rest of the time. For such a random variable, $\Pr[X \ge 90]$ is exactly $\frac59$, and this turns out to be the worst case.
Your random variable $X \sim \text{Binomial}(100, \frac12)$ is much more likely to be close to its expected value. But Markov's inequality has no way of knowing that. If you want stronger bounds on $\Pr[X \ge 90]$, you should use inequalities that use more properties of $X$.

For example, one traditional trick is to take the random variable $Y = 2^X$, which turns out to have expected value $\mathbb E[Y] = (\frac32)^{100}$ (but this is tricky to compute), and use Markov's inequality to find $\Pr[Y \ge 2^{90}]$.
This works much better: we get $\Pr[Y \ge 2^{90}] \le \frac{(3/2)^{100}}{2^{90}} \approx 3.3 \times 10^{-10}$.
Why does it work much better? Because $Y$ is a random variable that's much closer to the worst case of Markov's inequality. Most of the contribution to the expected value of $Y$ is from values that are unlikely to happen, but much larger than $\mathbb E[Y]$.
If we wanted even better results, we'd replace $2^X$ with $z^X$ for a carefully chosen value of $z$ that makes values of $X$ near $90$ contribute most of $\mathbb E[z^X]$. The best choice of $z$ here is $z=9$, which gives bounds on the order of $10^{-16}$, and generalizing this logic gives the well-known Chernoff bound.
