While reading an answer related to solving a problem with a geometric distribution, the following question occurred to me.
The answer gives two possibilities for replying the OP's question. In the second one (Changing number) he's actually using a geometric distribution with pobability of success $\theta$. In the first one (Fixed Number), however, the probability of success is not fixed, as it decreases for each new trial $\theta_i = \dfrac{1}{1000-i}$.
I am wondering what is the expected error one would commit if he computes $E[k]$ as in "changing number" when in fact the "fixed number" is the most adequate solution. I think it might make sense to model the distribution as a geometric one for sake of simplicity. What can you say about this error? Can you provide a bound?
Say there are $n$ numbers in total.
If the number is changing every time, then every trial is independent and the number of trials to have the correct guess follows a geometric distribution, and the expectation is $n$.
If the number is fixed, then you are equally likely to have the correct guess in each trial. Therefore the distribution in this time is a discrete uniform, and the expectation is $$ \frac {n(n + 1)} {2} \times \frac {1} {n} = \frac {n + 1} {2}$$
So what do you mean by error? Is it the difference $$ n - \frac {n + 1} {2} = \frac {n - 1} {2}$$