Some very sharp bounds for questions like these are provided by something called a [Chernoff bound][1].  The example in the wikipedia article will give you what you need.

Edit: Oh, I forgot to say that you need an estimator for the "true" probability, but I guess that the one you are using is just the average over the samples.  

  [1]: http://en.wikipedia.org/wiki/Chernoff_bound