0
$\begingroup$

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

1 Answers 1