Binomial distrobution, find number of trials such that correct outcome occurs 99% of the time An algorithm gives a correct answer with prob p=0.75. The output is binary (0 or 1). How many times should this be run with the same input such that the correct output occurs with probability at least 0.99?
To the best of my understanding, this is a Bernoulli experiment. The order of outcomes however, do not matter one bit. So I believe this should make it a binomial distribution. 
$$
\begin{equation}
f(x)=\frac{n!}{x!(n-x)!}p^x(1-p)^{n-x}
\end{equation}
$$
If I am understanding this correctly, my $f(x)$ should be 0.99. And $p=0.75$. As I understand this, $x$ is the number of successes, and $n$ it the total number of trials. Clearly I have 1 equation, but two unknowns. Now if does specify that the trials are run with "the same input". Does this help, perhaps letting "x=1"? Any ideas how I go about solving for n? I should note that this is indeed a homework related question.
edit: Here's what I'm thinking
Let $E_n$ be the number of successes after 1 trial. 
Clearly, $P(E_1)=(0.75)^1(0.25)^0=0.75$ Thus we have that $P(E_1)^c=0.25$.
So as the trials are independent, $E_n=(0.75)^n$ for the bare minimum number of trials needed (I'm assuming the at least portion of the problem here). 
So $P(E_n^c)=0.01=(0.25)^n\implies \ln(0.01)=n\ln(0.25) \implies n=3.322$
So we'll need at least 4 trials to have out outcome occur correctly 99% of the time. Does this method make any sense?
 A: Let there be $n$ independent Bernoulli trials $X_1, X_2, \ldots, X_n$, each of which has probability $p$ of being correct, and $1-p$ of being incorrect; i.e., $\Pr[X_i = 1] = p$ for each $i = 1, 2, \ldots, n$.  Let $Y = \sum X_i$ be the corresponding binomial random variable that counts the number of correct trials.  If the majority rule applies to the sequence of trials, then the probability that the correct output is obtained is given by $$\Pr[Y > n/2] = \sum_{k=\lfloor n/2 \rfloor + 1}^n \binom{n}{k} p^k (1-p)^{n-k}.$$  For $p = 0.75$, we wish to find the smallest positive integer $n$ such that $\Pr[Y > n/2] \ge 0.99$.  This requires some guess-and-check or other numerical method.  We can also use a normal approximation.  Note $$Y \dot\sim W \sim \operatorname{Normal}(\mu = np, \sigma^2 = np(1-p)),$$ so we can approximate the above probability (with continuity correction) as $$\Pr[Y > n/2] \approx \Pr[W > n/2] = \Pr\left[ Z = \frac{W - \mu }{\sigma} > \frac{n/2 - np + 0.5}{\sqrt{np(1-p)}} = \frac{2-n}{\sqrt{3n}} \right],$$ where $Z$ is standard normal.  If this is equal to $0.99$, then it follows that $$\frac{n-2}{\sqrt{3n}} \approx 2.32635,$$ or $n \approx 20.036$, so we should check $n = 19$, $n = 20$ and $n = 21$.  The reason for checking below and above is because the binomial is a discrete distribution, not continuous.  By substitution, we find  $$\Pr[Y > 19/2] \approx 0.991097,$$ which is large enough.  $$\Pr[Y > 10] \approx 0.986136,$$ which is too small, so we proceed to $n = 21$ and get $$\Pr[Y > 21/2] \approx 0.993577,$$ which also works, but we want the minimum, so $n = 19$.  Note that the continuity correction is a significant benefit here, because without it, you'd start your guessing around $n = 15$, which would be more time-consuming.
