How do I measure the statistical significance of a boolean value? Let's say I have a function simulate() that returns True with some probability $p$ and False otherwise.
After calling simulate() $N$ times, I get True $x$ times and False $N - x$ times. I then compute $p' = \frac{x}{N}$. How do I measure my error on $p'$? My ultimate goal is to figure out whether $p > 0.5$ for my simulate() function, and I want to know how many trials I have to conduct to be confident in my result.
 A: By virtue of the fact that $X$ has a binomial distribution, we know that the standard error for $p'$ is $p(1-p)/N$.  Now $p$ is the unknown variable we wish to estimate so we get an estimate by replacing $p$ with $p'$. If $N$ is large enough we can use a normal approximation for $p'$ and take $\pm 2$ estimated standard deviations around $p'$ as an approximate 95% confidence interval for $p'$. This would be a two-sided interval. Since you only want to know if $p>0.5$, you might prefer using a one-sided interval.
A: Your data are independent binary variables with a fixed probability, so the count value you are seeking is a binomial random variable.  You already have a point estimate, so the next step is to use an appropriate interval estimator, such as a confidence interval.  This is a very well-known problem, so I recommend you start by reading some textbook presentations of binomial confidence intervals.  You can also read Brown et al (2001) for an overview of available methods, and comparison between methods.
A: You are working with a binomial distribution. Its variance for a sample of n observations with a "p" chance of getting a "true result" is np(1-p)
Therefore its standard deviation will be the square root of np(1-p) (use the results you got before to estimate p, ie: use the sample p as "kind-of-the-true-p") You can now calculate confidence intervals and all those cool things you can do with normal distributions (for a large enough sample, it will behaive similarly)
