A random Algorithm $A$ receives input in $[n]$ it's know that when the probability is taken over input that was chosen randomly over uni-formal distribution over the algorithm randomness the probability $A$ succeeds is at least $2/3$. Prove that if we randomly pick $k \in [n]$ then with probability of at least $1/3$ we shall get such k such that the algorithm succeeds with probability of at least $1/2$ Any help\directions would be great
random Algorithm over Random input-help needed
0
$\begingroup$
probability
algorithms
probability-theory
probability-distributions
1 Answers
1
Consider the set $B$ of all inputs $b$ such that $P(\text{success}\mid b)\ge 1/2$. Then, clearly $P(\text{success}\mid \neg B)<1/2$.
Now write $\frac23 \le P(\text{success}) = P(B) P(\text{success}\mid B) + P(\neg B) P(\text{success}\mid \neg B)$ and consider what happens if $P(B)<1/3$