The probability of mistake of randomized program. Consider this program to detect odd and even numbers:

*

*If the input number is even, it prints $even$.

*If the number is odd, it has a $4/5$ probability of printing $odd$ and $1/5$ probability of printing $even$.

How many times must the program run so that the probability of getting the correct answer is 0.99 (confidence).
My solution
If the program prints $odd$ then the number is certainly odd, because if it was even the program would print $even$. But if program prints $even$ there is a probability that the number is actually odd. So the probability of error is when it prints $even$ but the number is odd.
So using Bayes rule we have:
$$ P(odd | print\ even ) = \frac{P(odd \wedge print\ even) }{P (odd \wedge print\ even) + P(even \wedge print\ even)} $$
In this case we repeat the program until we either get an $odd$ or repeating $even$ for $K$ times. Is it correct? However I then don't know how to continue and what is the value for each of these components. You can assume the probability of a number is odd or even equal to 0.5
 A: You are definitely on the right track. This formula is correct:
$$ P(odd | print\ even ) = \frac{P(odd \cap print\ even) }{P (odd \cap print\ even) + P(even \cap print\ even)} $$
$P(odd \cap print\ even)$ would be mean that the input was odd, and mistakenly got switched to even. Since these events are mutually exclusive: $\frac{1}{2} * \frac{1}{5} = \frac{1}{10}$
$P(even \cap print\ even)$ would just be $\frac{1}{2}$. If the input is even, it's guaranteed to be even.
Plugging these in we get: $$\frac{1/10}{1/10+1/2}$$
$ P(odd | print\ even ) = \frac{1}{6}$. As for the last step it's very unclear what you mean. What defines "correct answer"? The was I see it there's a chance at every step that the answer is correct or incorrect, but what would make it "correct" after running 10 times? If you respond I'll update this and give you an answer.
Edit: The 0.99 figure is how many times we need to repeat an even output until we have a 99% confidence that the number is even. We can state that: $P(\text{even after $n$ repeats}) = 1 - P(\text{odd after $n$ repeats})$ As we just calculated, the probability of it being odd when printing even is $\frac{1}{6}$. We can make a quick table changing the value of $n$, and finding $P(\text{even after $n$ repeats})$:
$n=1$ :  $1 - \frac{1}{6} \approx 0.8333$
$n=2$ : $1 - (\frac{1}{6})^2 \approx 0.9722$
$n=3$ : $1 - (\frac{1}{6})^3 \approx 0.9954$
So after 3 repeats we can be over 99% confident that it truly is an even number.
A: if it's even (.5 probability) then prob of success is 1  (an even number always prints even, so if we enter an even number, the result of even is correct with a probability of 1.  Half of numbers are even
if it is odd then prob of success is 4/5.  (in 1/5 of runs we will get the answer 'even', and not have seen the correct result)
If the number is odd then after n runs the prob of a success is $1 - (\frac{1}{5})^n$
after n runs, P of seeing correct answer is
P = $\frac{1}{2} + \frac{1}{2}(1-(\frac{1}{5})^n)$
to get P = .99, rearrange
$(\frac{1}{5})^n = 1-.99 $
$n \log(\frac{1}{5}) = \log(.01)$
$n = -\log(.01) / \log(5) = 2.9$
so 3 times, since 2.9 times is not possible, you have to exceed this
