1
$\begingroup$

Imagine I asked $1000$ people to choose a number between $0$ and $999$ (both inclusive, the numbers are not biased, they will be completely random) and write that number down. Now, after that, pick a number, $x$, where $0\le x \le 1000$. What is the probability that none of people that I asked will have chosen that number?

I ran a simulation in Python to do this $10000$ times (code), and in $37.22\%$ of the cases, no one choose the $x$.

I would like to know a simple way to calculate this for any amount of people.

$\endgroup$
5
  • $\begingroup$ Total ways are $1000^{1000}$ . and specific number has $1000$ ways so its almost 0 in 1 time $\endgroup$
    – Archis Welankar
    Mar 19, 2016 at 14:52
  • $\begingroup$ @ArchisWelankar, what does "almost 0 in 1 time" mean? $\endgroup$
    – siegehalver
    Mar 19, 2016 at 14:54
  • 1
    $\begingroup$ This is not clear. First of all, you didn't mean $0≥x≥1000$. But even if we reverse the inequalities...did you mean to allow $1000$ to be chosen in the second case but not the first? $\endgroup$
    – lulu
    Mar 19, 2016 at 15:00
  • $\begingroup$ Wait, people really choose numbers in the range $[0, 999]$, but your $x$ is in the range $[0, 1000]$? Your code uses $[0, 1000]$ for both. $\endgroup$
    – alexis
    Mar 19, 2016 at 16:21
  • 1
    $\begingroup$ Your code is inconsistent with the question, and the question is inconsistent with itself and with the title. I assume you meant $0 \le x < 1000$ (rather than $0 \le x \le 1000$), and that you meant randint(0,999) in your code (rather than randint(0,1000)). $\endgroup$
    – David Hammen
    Mar 19, 2016 at 19:34

5 Answers 5

Reset to default
10
$\begingroup$

For $n$ people, the probability is $$\left(1-\frac1n\right)^n\approx \frac1e$$ To explain that, notice that the natural logarithm of $1+x$ is close to $x$ when $x$ is small. (Try it for $\ln(1.1),\ln(1.01),\ln(1.001)$).
So the log of the left-hand side is $n\log(1-\frac1n)\approx(n(-\frac1n))=-1$.
Since the log is near $-1$, the probability is near $1/e$.

$\endgroup$
3
  • $\begingroup$ I use this point of view in my probability class to try to hammer in the importance of the number $e$ from a probablistic point of view. Or, more precisely, the importance of the number $\frac{1}{e} \approx .3679...$. $\endgroup$
    – Lee Mosher
    Mar 19, 2016 at 15:52
  • $\begingroup$ There are $n+1$ numbers and $n$ people in the given problem. $\endgroup$
    – robjohn ♦
    Mar 19, 2016 at 15:59
  • 1
    $\begingroup$ The first sentence says there are 1000 people and numbers. 2 paragraphs down it is 1000 people and 1001 numbers. Doesn't really matter as lim n-> infty (1-1/n)^(n+1) = lim (1-1/n)^n(1+ 1/n) = lim (1-1/n)^n = lim(1 - 1/n)^(n-1)(1-1/n) = lim (1-1/n)^(n-1) = lim (1- 1/(n+1))^n. $\endgroup$
    – fleablood
    Mar 21, 2016 at 19:59
10
$\begingroup$

The odds that any particular person does not pick your number is $\frac{999}{1000}$, so the odds nobody picks it will be $$\left(\frac{999}{1000}\right)^{1000} \approx 0.368$$

$\endgroup$
0
1
$\begingroup$

There are 1001 numbers to choose from, so each person has a probability of 1000/1001 (just over 0.999) of not picking your chosen $x$.

Since each person chooses independently, the probability that nobody chooses $x$ is the product of the individual probabilities: $(1000/1001)^{1000}$, or more generally $(1000/1001)^N$ when $N$ people are choosing. My python interpreter is calculating this as $0.368063...$, which is a bit lower than the $0.372$ from your simulation.

$\endgroup$
3
  • $\begingroup$ There are 1000 numbers to choose from. $\endgroup$
    – David Hammen
    Mar 19, 2016 at 17:58
  • $\begingroup$ David, Not according to the way $x$ is chosen, and not according to the OP's code (see link). But the question doesn't match the code, so one of the two is wrong. Since I doubt the OP really intends $x$ to be drawn from a larger range of numbers than people can choose from, I'll assume the code is correct until the OP clears this up. $\endgroup$
    – alexis
    Mar 19, 2016 at 18:08
  • $\begingroup$ Good point. The question is inconsistent with the code. $\endgroup$
    – David Hammen
    Mar 19, 2016 at 18:24
1
$\begingroup$

I'm going to assume that the question asks for the probability that none of $N$ independent and identically distributed random variates drawn from the discrete uniform distribution $U[0,M)$ will be equal to separate random variate drawn from the same distribution.

The general case is quite easy. This is a binomial distribution, with parameter $p=\frac1M$. The probability that one given person will draw the correct number is exactly equal to $p$. The probability that that person will not draw the correct number is $1-\frac1M = \frac{M-1}M$. The probability that not a single one of the $N$ people involved in the experiment will draw the given number is $$P=\left(\frac{M-1}M\right)^N$$

In the case where $N=1000, M=1001$ (e.g. the code), this becomes $\left(\frac{1000}{1001}\right)^{1000} \approx 0.36806$. If $N=M=1000$ (the intent of the question?), this becomes $\left(\frac{999}{1000}\right)^{1000} \approx 0.36770$. Note that both are quite close to $1/e \approx 0.36788$. This is not a coincidence. Both $\left(\frac{N}{N+1}\right)^N$ and $\left(\frac{N-1}N\right)^N$ are fairly good estimates of $1/e$ for large $N$; the average of the two is an even better estimator of $1/e$.


I ran a simulation in Python to do this 10000 times, and in 37.22% of the cases, no one chose the $x$.

You are overstating the precision of your Monte Carlo simulation. It would have been much better to have said 37% rather than 37.22%. Your 10000 cases yield about two decimal places of accuracy. You would need to run that Monte Carlo simulation about one million times to get three places of accuracy, and about 100 million times to get four places of accuracy.

I'm a big fan of what I call "dumb Monte Carlo" because it's so easy to set up. That said, it is indeed "dumb" because of the logarithmic growth of precision that results. Better techniques do exist (e.g. bootstrap, jackknife, Markov chain Monte Carlo), but these are a bit trickier to set up.

$\endgroup$
1
  • $\begingroup$ I too am a fan of simple Monte Carlo :-) $\endgroup$
    – user150203
    Dec 2, 2018 at 12:10
0
$\begingroup$

Every solution can be represented by tuples from $$ A = \{0, \dotsc, M\}^N $$ where $M$ is the largest number to choose from and $N$ is the number of people asked, so you simply list their choices.

There are $$ \lvert A \rvert = (M+1)^N $$ possible choices.

The event you are interested in, is that all persons will not note down a certain number, we can use $0$ as that number. Then all such events would result in a tuple from $$ B = \{1, \dotsc, M\}^N $$ where there are $$ \lvert B \rvert = M^N $$ So the probability of such events is $$ p = \frac{\lvert B \rvert}{\lvert A \rvert} = \left( \frac{M}{M+1}\right)^N $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .