Some very sharp bounds for questions like these are provided by something called a Chernoff bound. 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.