How many tries to get a closer number to a target when $X$ others numbers are present?

Question

I have a target number in a $2^{64}$ space.

How many random tries do I have to do to be the closest to this target number if there is $X$ other random number?

Answer 1

Let $N$ be the number of tries it takes for you to be closest. You want the expected value of $N$. After $n$ tries, your probability of being the closest is $n/(X+n)$. Thus the expected value of $N$ is

\begin{eqnarray*} \mathsf E[N] &=&\sum_{n=1}^\infty\mathsf P(N\ge n)\\ &=&\sum_{n=1}^\infty\frac X{X+n}\\ &=&\infty\;. \end{eqnarray*}

Thus, perhaps somewhat counterintuitively, the expected number of tries turns out to be infinite.

I glossed over the very low probability of ties; in order to deal with that, you'd have to specify what happens in case of ties – both ties between guesses and coincidences between a guess and the target. If “closest” is taken to mean “closer than any other number”, then the expected number of tries is infinite simply because there's a non-zero ($2^{-64}$) probability that one of the other numbers coincides with the target and you can never be closer.