CS 70 Discrete Mathematics and Probability Theory

Spring 2015 Vazirani Lecture 18

Chebyshevs Inequality

Problem: Estimating the Bias of a Coin

Suppose we have a biased coin, but we dont know what the bias is. To estimate the bias, we toss the coin

                                                                                         1

n times and count how many Heads we observe. Then our estimate of the bias is given by p n Sn , where

Sn is the number of Heads in the n tosses. Is this a good estimate? Let p denote the true bias of the coin,

which is unknown to us. Since E(Sn ) np, we see that the estimator p has the correct expected value:

                               ...