Repeating something with (1/n)th chance of success n times

Is there anything that can be said about how many attempts it will take to correctly guess a random number out of 1000 numbers? If the number wouldn't change the probability would just increase every guess, giving in the end a probability of 1.

If the number changes every guess tough, you just have a 1/1000th chance everytime. Can it be calculated how many attempts it would probably take, on average?

(I'm sorry, i'm not very skilled in probability maths)

Solution 1:

This concept is the foundation of the Law of Large Numbers, which is behind most concepts of probability. By definition, if given 1000 unique random trials, a particular event (result) occurs once, then the observed probability of that event occurring is 1/1000. The inverse is basically the application of the calculated probability; if an event has a probability of 1/1000, then if you performed 1000 trials, you should expect the event to occur once. For an independent event (the results of past trials do not influence the probability of future ones), it's not guaranteed to happen exactly once per 1000 trials, but as the number of trials t grows large, the number of times an event with probability $1/n$ occurs will approach $t/n$.

Now, if you started with the first trial, and continued performing trials until the event occurred, and then counted how many trials it took, the probability of it occurring for the first time on exactly the Xth trial is equal to the probability that it doesn't occur on any of the X-1 trials, and that it does occur on the Xth. The probability that it doesn't happen is $\dfrac{n-1}{n}$ (or equivalently $1-\dfrac{1}{n})$ and it must happen X-1 times, followed by the event occurring the Xth time ($1/n$ probability), so the formula for the probability of it occurring on exactly the Xth trial is

$$P(X)=(1-\dfrac{1}{n})^{X-1}(\dfrac{1}{n})$$

Plugging in our known specific value for N, we get:

$$P(X)=(\dfrac{999}{1000})^{X-1}(\dfrac{1}{1000})$$

This is an asymptotically-reducing exponential function; it approaches zero as X grows infinitely large. As such, there isn't a point at which it starts becoming more likely to happen; it just becomes increasingly less likely that it doesn't happen. However, if we consider only how likely it is that it doesn't happen in X-1 trials ($(\dfrac{999}{1000})^{X-1}$), we can find an "over-under", where it is equally likely for it to take more than that many trials than fewer. This is our "expected value" for the number of trials it should take (similar to the "expected value" of one roll of the dice; the probability that it's greater than or equal to a certain face value is 1 at 1, but only 1/6 at 6, and at the expected value of 3.5, the odds are 50-50 either way). With a little graphing magic, we see that the number of trials after which the probability of your number having not occurred so far drops below .5 is 674.

Thus, before you begin choosing numbers, you can expect it to take, on average, about 674 trials for the number you want to pop up for the first time. However, there's still a 36% chance it won't happen in 1000 trials, and a 13% chance it won't even happen once in 2000 trials, and given that it hasn't happened in 674 trials (or 1000 or even 100,000), the probability the next number will be the one you want is still 1 in 1000.

Solution 2:

Let $K$ be the number of attempts it takes. You want to compute the expected value of $K$, that is $E[K]$. Since this is a discrete distribution, we have $E[K] = \sum_{k=1}^\infty k p_k$, where $p_k$ is the probability that it takes exactly $k$ attempts to guess the correct number.

Fixed number: If the number is fixed, then the expected number is straightforward to compute. Note that $p_k = 0$ for $k > 1000$, since you must have figured out the number by then (I'm assuming that guesses are not repeated!). To compute $p_k$ for $k \leq 1000$, we need the probability of making $k-1$ incorrect guesses (without 'replacement'), multiplied by the probability of the $k$th guess being correct, ie, $p_k = \frac{1000 - 1}{1000 - 0} \frac{1000 - 2}{1000 - 1} \cdots \frac{1000-(k-1)}{1000-(k-2)} \frac{1}{1000-(k-1)} = \frac{999}{1000} \frac{998}{999} \cdots \frac{1000-k+1}{1000-k+2} \frac{1}{1000-k+1} = \frac{1}{1000}$. Consequently, $E[K] = \frac{1}{1000} \sum_{k=1}^{1000} k = \frac{1001}{2}$. That is, on average you would expect to take 500.5 attempts.

Changing number: If the number is randomly selected from 1,000 numbers each time, the expected number of attempts is straightforward to compute.

In this case $p_k = (1-\theta)^{k-1}\theta$, where $\theta = \frac{1}{1000}$. So the answer is $E[K] = \sum_{k=1}^\infty k (1-\theta)^{k-1}\theta$.

Since $\sum_{k=1}^\infty k (1-\theta)^{k-1} = \frac{1}{\theta^2}$, this gives $E[K] = \frac{1}{\theta} = 1000$. That is, on average you would expect to take 1000 attempts.

Solution 3:

As you said, if the number doesn't change while you're guessing, and you always guess a number that you haven't guessed yet, then your probability of getting the number right within $m \le n$ guesses is just $m/n$. To make the probability of getting it right reach $p$, you need $m(p)=pn$ guesses.

On the other hand, if the number changes after every guess, then your probability of getting it wrong is $1-1/n$ for each guess (independent of how many guesses you've made already), and your probability of getting it wrong $m$ consecutive times is $$\left(1-\frac{1}{n}\right)^{m} \sim \exp\left(-\frac{m}{n}\right),$$ where the approximation is asymptotically valid as $n\rightarrow\infty$. Here, to make the probability of getting it right reach $p$, you need $$ m(p)=-n\log(1-p)=pn+\frac{1}{2}p^2n+\frac{1}{3}p^3n + \ldots $$ guesses. Note that this is approximately equal to $pn$ for small $p$, but for $p$ approaching $1$ (i.e., to achieve certainty), you need a divergent number of guesses.