# Solve the problem using Chebyshev inequality

The problem is the following:

The symmetric coin is tossed 1600 times. What is the probability that the head will be shown up more than 1200 times?

Attempt.

Using the formula $\mathbb{P}(|X-MX|)>e)≤ DX/e^2$ I put the numbers in it

$$\mathbb{P}(|X-800|>1200)\le 400/1200^2$$

But do not get the answer which is $\le 1/800$.

-

You did everything right, except that to find when it is greater than $1200$ you need $|X-800|>400$ not $|X-800|>1200$. Also note, that this will include cases $X>1200$ as well as $X<400$, and since the distribution is symmetric around $800$, all you need to do is divide $400/400^2$ by $2$.

-
Why should I put 400 instead of 1200? – saakian Feb 16 '14 at 18:10
Because $|X-800|>z$ is $X-800>z$ or $X-800<-z$, i.e. $X>800+z$ or $X<800-z$, and you need $X>1200$. Think about it differently: suppose you have median of $X$ equal $8$ and you are asked when $X$ is greater than $12$. Well, when $X>12$ or $X-8>4$, not $X-8>12$. – Vadim Feb 16 '14 at 18:14

Let $X$ be the number of heads. Then $X$ has mean $\mu=800$ and variance $\sigma^2=(1600)(1/2)(1/2)=400$. The Chebyshev Inequality says that $$\Pr(|X-\mu|\ge k\sigma)\le \frac{1}{k^2}.$$ In our case, we are interested in something related to the probability that $X\ge 1200$. Now $1200=\mu +k\sigma$, where $k=20$. So by the Chebyshev Inequality we have $$\Pr(|X-800|\ge 400)\le \frac{1}{20^2}.$$ But the distribution of $X$ is symmetric about $800$, since the coin is fair. It follows that $$\Pr(X\le 1200)\le \frac{1}{2}\cdot\frac{1}{20^2}=\frac{1}{800}.$$

We have shown that the probability that $X\ge 1200$ is $\le \frac{1}{800}$. So in fact $\Pr(X\gt 1200)\lt \frac{1}{800}$.

-
You used an additional step to to find the k. Could you please explain the following 1200=μ+kσ – saakian Feb 16 '14 at 18:19
We have $\sigma=20$ and $\mu=800$. to use the Chebyshev Inequality, we need to find the appropriate $k$. We want $1200=800+(k)(20)$, so $k=20$. – André Nicolas Feb 16 '14 at 18:24
(more) Basically we are interested in the right tail, from $1200$ up. Actually, the problem asks about $1201$ or more. So we could replace the $k=20$ by solving $1201=800+(k)(20)$, and get an improved (slightly!) estimate probability is $\le \frac{1}{2}\cdot\frac{1}{(20.05)^2}$. But both the earlier bound and this one are quite poor, Central Limit Theorem gives better estimates. – André Nicolas Feb 16 '14 at 18:31
Can I use other methods to solve the problem e.g. Bernoulli's theorem? I tried but none of calculators could count it – saakian Feb 16 '14 at 18:34
You can find the exact probability by using appropriate software. I think Wolfram Alpha will do it, certainly Mathematica or Maple will. Or you can use the normal approximation to the binomial. But your problem asks you to use Chebyshev, as an exercise with working with that inequality. – André Nicolas Feb 16 '14 at 18:40