Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 58 / 4 / b

With one marked input, after $r$ distinct failed guesses it is uniformly distributed among the $N-r$ untested inputs. Therefore the conditional chance of success on the next guess is $1/(N-r)$. One further failure raises it byor by a multiplicative factor $(N-r)/(N-r-1)$. There is a different unconditional statement: the marked position is uniform, so $\mathbb{P}(K=k)=1/N$ and $\mathbb{P}(K\le k)=k/N$. Thus each additional distinct guess increases cumulative success by $1/N$, even though the conditional next-guess probability increases after each failure. These distinguish the two possible meanings of a probability boost.