Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 53 / 4 / 1 / Solution

For independent attempts, measuring after each application of $A$ produces a success with probability $p$. Recognize the answer with the verifier and restart on failure. The number $T$ of attempts has a geometric distribution, with $\mathrm{Pr}(T=k)=(1-p{)}^{k-1}p$. Summing the tail probabilities givesThis counts applications of $A$; it presumes $p>0$ and a fresh preparation for each attempt. If $p=0$, neither repetition nor the amplification construction can create a good component from this input.