Consider the following game: You throw a die 1000 times, and win 1 dollar for every you get a 6. You don't lose money for the other rolls. Apply both Chebyshev's and Chernoff's to bound the probability that we are $X$ or further above/below the expected value for $X = 50, 100, 150$. Simplify each answer using a calculator.

I tried solving for $X = 50$ first by using the Law of Large Numbers but I don't think I'm correct.

So $A_n$ is the average number of 6s after 50 throws.

$E[A_n] = 1000 * (1/6) = 166.667$

Since $Var(A_n) = Var(X)/n$ and $X$ has Binomial distribution (or is it Bernoulli?) we can use $Var(X) = p(1-p)n$.

$Var(A_n) = [p(1-p)n]/n = 5/36$.

The observed value of $A_n$ is $1/20$ therefore it is $1/6 - 1/20 = 7/60$ away from the expected value.

$$P(|A_n - 1/6| \geq 1/20) = Var(A_n)/(7/60)^2 = (5/36)/(7/60)^2 = 10.2$$

This answer is way off what I expected and I'm also not sure how to differentiate between above and below the observed rolls.


Let random variable $W$ be the number of sixes after $1000$ rolls. The expected value of $W$ is $1000/6$.

We want to use the Chebyshev Inequality to estimate $\Pr(|W-1000/6|\ge 50)$, also $\Pr(|W-1000/6|\ge 100)$, also $\Pr(|W-1000/6|\ge 150)$.

The variance of $W$ is $\sigma^2$, where $\sigma^2=1000(1/6)(5/6)$.

By the Chebyshev Inequality, we have $\Pr(|W-1000/6|\ge k\sigma)\le \frac{1}{k^2}$.

For $50$ dollars, we want to set $k\sigma=50$. So $k=300/\sqrt{5000}$, and therefore $\frac{1}{k^2}=\frac{5000}{90000}$. Similar calculations can be made for other values of the number of dollars.

Note that the bound we have obtained is of poor quality. One can get sharper estimates by using the normal approximation to the binomial. And with appropriate software, we can calculate $\Pr(|X-1000/6|\ge 50)$ "exactly."


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.