If I ask $1000$ people to choose a random number between $0$ and $999$, what is the probability that no one...
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 $0le 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.
probability statistics random
add a comment |
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 $0le 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.
probability statistics random
Total ways are $1000^{1000}$ . and specific number has $1000$ ways so its almost 0 in 1 time
– Archis Welankar
Mar 19 '16 at 14:52
@ArchisWelankar, what does "almost 0 in 1 time" mean?
– siegehalver
Mar 19 '16 at 14:54
1
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?
– lulu
Mar 19 '16 at 15:00
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.
– alexis
Mar 19 '16 at 16:21
1
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 meantrandint(0,999)
in your code (rather thanrandint(0,1000)
).
– David Hammen
Mar 19 '16 at 19:34
add a comment |
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 $0le 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.
probability statistics random
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 $0le 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.
probability statistics random
probability statistics random
edited Mar 19 '16 at 15:51
Pichi Wuana
658425
658425
asked Mar 19 '16 at 14:47
Loovjo
12415
12415
Total ways are $1000^{1000}$ . and specific number has $1000$ ways so its almost 0 in 1 time
– Archis Welankar
Mar 19 '16 at 14:52
@ArchisWelankar, what does "almost 0 in 1 time" mean?
– siegehalver
Mar 19 '16 at 14:54
1
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?
– lulu
Mar 19 '16 at 15:00
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.
– alexis
Mar 19 '16 at 16:21
1
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 meantrandint(0,999)
in your code (rather thanrandint(0,1000)
).
– David Hammen
Mar 19 '16 at 19:34
add a comment |
Total ways are $1000^{1000}$ . and specific number has $1000$ ways so its almost 0 in 1 time
– Archis Welankar
Mar 19 '16 at 14:52
@ArchisWelankar, what does "almost 0 in 1 time" mean?
– siegehalver
Mar 19 '16 at 14:54
1
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?
– lulu
Mar 19 '16 at 15:00
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.
– alexis
Mar 19 '16 at 16:21
1
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 meantrandint(0,999)
in your code (rather thanrandint(0,1000)
).
– David Hammen
Mar 19 '16 at 19:34
Total ways are $1000^{1000}$ . and specific number has $1000$ ways so its almost 0 in 1 time
– Archis Welankar
Mar 19 '16 at 14:52
Total ways are $1000^{1000}$ . and specific number has $1000$ ways so its almost 0 in 1 time
– Archis Welankar
Mar 19 '16 at 14:52
@ArchisWelankar, what does "almost 0 in 1 time" mean?
– siegehalver
Mar 19 '16 at 14:54
@ArchisWelankar, what does "almost 0 in 1 time" mean?
– siegehalver
Mar 19 '16 at 14:54
1
1
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?
– lulu
Mar 19 '16 at 15:00
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?
– lulu
Mar 19 '16 at 15:00
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.
– alexis
Mar 19 '16 at 16:21
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.
– alexis
Mar 19 '16 at 16:21
1
1
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)
).– David Hammen
Mar 19 '16 at 19:34
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)
).– David Hammen
Mar 19 '16 at 19:34
add a comment |
5 Answers
5
active
oldest
votes
For $n$ people, the probability is $$left(1-frac1nright)^napprox 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 $nlog(1-frac1n)approx(n(-frac1n))=-1$.
Since the log is near $-1$, the probability is near $1/e$.
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...$.
– Lee Mosher
Mar 19 '16 at 15:52
There are $n+1$ numbers and $n$ people in the given problem.
– robjohn♦
Mar 19 '16 at 15:59
1
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.
– fleablood
Mar 21 '16 at 19:59
add a comment |
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$$
add a comment |
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}Mright)^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}Nright)^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.
I too am a fan of simple Monte Carlo :-)
– DavidG
Dec 2 at 12:10
add a comment |
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.
There are 1000 numbers to choose from.
– David Hammen
Mar 19 '16 at 17:58
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.
– alexis
Mar 19 '16 at 18:08
Good point. The question is inconsistent with the code.
– David Hammen
Mar 19 '16 at 18:24
add a comment |
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
$$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1704393%2fif-i-ask-1000-people-to-choose-a-random-number-between-0-and-999-what-is%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
For $n$ people, the probability is $$left(1-frac1nright)^napprox 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 $nlog(1-frac1n)approx(n(-frac1n))=-1$.
Since the log is near $-1$, the probability is near $1/e$.
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...$.
– Lee Mosher
Mar 19 '16 at 15:52
There are $n+1$ numbers and $n$ people in the given problem.
– robjohn♦
Mar 19 '16 at 15:59
1
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.
– fleablood
Mar 21 '16 at 19:59
add a comment |
For $n$ people, the probability is $$left(1-frac1nright)^napprox 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 $nlog(1-frac1n)approx(n(-frac1n))=-1$.
Since the log is near $-1$, the probability is near $1/e$.
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...$.
– Lee Mosher
Mar 19 '16 at 15:52
There are $n+1$ numbers and $n$ people in the given problem.
– robjohn♦
Mar 19 '16 at 15:59
1
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.
– fleablood
Mar 21 '16 at 19:59
add a comment |
For $n$ people, the probability is $$left(1-frac1nright)^napprox 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 $nlog(1-frac1n)approx(n(-frac1n))=-1$.
Since the log is near $-1$, the probability is near $1/e$.
For $n$ people, the probability is $$left(1-frac1nright)^napprox 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 $nlog(1-frac1n)approx(n(-frac1n))=-1$.
Since the log is near $-1$, the probability is near $1/e$.
answered Mar 19 '16 at 14:55
Empy2
33.4k12261
33.4k12261
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...$.
– Lee Mosher
Mar 19 '16 at 15:52
There are $n+1$ numbers and $n$ people in the given problem.
– robjohn♦
Mar 19 '16 at 15:59
1
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.
– fleablood
Mar 21 '16 at 19:59
add a comment |
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...$.
– Lee Mosher
Mar 19 '16 at 15:52
There are $n+1$ numbers and $n$ people in the given problem.
– robjohn♦
Mar 19 '16 at 15:59
1
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.
– fleablood
Mar 21 '16 at 19:59
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...$.
– Lee Mosher
Mar 19 '16 at 15:52
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...$.
– Lee Mosher
Mar 19 '16 at 15:52
There are $n+1$ numbers and $n$ people in the given problem.
– robjohn♦
Mar 19 '16 at 15:59
There are $n+1$ numbers and $n$ people in the given problem.
– robjohn♦
Mar 19 '16 at 15:59
1
1
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.
– fleablood
Mar 21 '16 at 19:59
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.
– fleablood
Mar 21 '16 at 19:59
add a comment |
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$$
add a comment |
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$$
add a comment |
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$$
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$$
edited Mar 21 '16 at 19:48
Kamil Jarosz
4,47831230
4,47831230
answered Mar 19 '16 at 14:53
siegehalver
1,190312
1,190312
add a comment |
add a comment |
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}Mright)^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}Nright)^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.
I too am a fan of simple Monte Carlo :-)
– DavidG
Dec 2 at 12:10
add a comment |
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}Mright)^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}Nright)^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.
I too am a fan of simple Monte Carlo :-)
– DavidG
Dec 2 at 12:10
add a comment |
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}Mright)^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}Nright)^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.
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}Mright)^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}Nright)^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.
edited Dec 2 at 10:02
answered Mar 19 '16 at 22:36
David Hammen
1766
1766
I too am a fan of simple Monte Carlo :-)
– DavidG
Dec 2 at 12:10
add a comment |
I too am a fan of simple Monte Carlo :-)
– DavidG
Dec 2 at 12:10
I too am a fan of simple Monte Carlo :-)
– DavidG
Dec 2 at 12:10
I too am a fan of simple Monte Carlo :-)
– DavidG
Dec 2 at 12:10
add a comment |
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.
There are 1000 numbers to choose from.
– David Hammen
Mar 19 '16 at 17:58
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.
– alexis
Mar 19 '16 at 18:08
Good point. The question is inconsistent with the code.
– David Hammen
Mar 19 '16 at 18:24
add a comment |
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.
There are 1000 numbers to choose from.
– David Hammen
Mar 19 '16 at 17:58
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.
– alexis
Mar 19 '16 at 18:08
Good point. The question is inconsistent with the code.
– David Hammen
Mar 19 '16 at 18:24
add a comment |
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.
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.
edited Mar 19 '16 at 15:54
answered Mar 19 '16 at 15:38
alexis
1,823710
1,823710
There are 1000 numbers to choose from.
– David Hammen
Mar 19 '16 at 17:58
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.
– alexis
Mar 19 '16 at 18:08
Good point. The question is inconsistent with the code.
– David Hammen
Mar 19 '16 at 18:24
add a comment |
There are 1000 numbers to choose from.
– David Hammen
Mar 19 '16 at 17:58
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.
– alexis
Mar 19 '16 at 18:08
Good point. The question is inconsistent with the code.
– David Hammen
Mar 19 '16 at 18:24
There are 1000 numbers to choose from.
– David Hammen
Mar 19 '16 at 17:58
There are 1000 numbers to choose from.
– David Hammen
Mar 19 '16 at 17:58
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.
– alexis
Mar 19 '16 at 18:08
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.
– alexis
Mar 19 '16 at 18:08
Good point. The question is inconsistent with the code.
– David Hammen
Mar 19 '16 at 18:24
Good point. The question is inconsistent with the code.
– David Hammen
Mar 19 '16 at 18:24
add a comment |
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
$$
add a comment |
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
$$
add a comment |
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
$$
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
$$
answered Mar 19 '16 at 15:31
mvw
31.3k22252
31.3k22252
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1704393%2fif-i-ask-1000-people-to-choose-a-random-number-between-0-and-999-what-is%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Total ways are $1000^{1000}$ . and specific number has $1000$ ways so its almost 0 in 1 time
– Archis Welankar
Mar 19 '16 at 14:52
@ArchisWelankar, what does "almost 0 in 1 time" mean?
– siegehalver
Mar 19 '16 at 14:54
1
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?
– lulu
Mar 19 '16 at 15:00
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.
– alexis
Mar 19 '16 at 16:21
1
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 thanrandint(0,1000)
).– David Hammen
Mar 19 '16 at 19:34