Mixing
Probability Mass Function of Number of Draws with Replacement Until N Distinct Results are Obtained
$begingroup$
Let $X$ be the discrete random variable that corresponds to the number of draws (with replacement) from a population of $k$ distinct objects required until $n$ distinct results are obtained, where $1le nle k$. Each item is equally likely to be drawn.
What is the probability mass function (PMF) of $X$? Its support is $[n,infty]capmathbb{N}$.
The only portion I'm able to derive is this:
$$P(X=n)=prod_{i=k-n+1}^{k}frac{i}{k}$$
But what about on the rest of the support? I assume it's going to involve combinatorics, but I'm not sure how to derive it.
probability combinatorics discrete-mathematics probability-distributions
asked Jan 9 at 19:33
jippyjoe4jippyjoe4
4768
$endgroup$
add a comment |
$begingroup$
Let $X$ be the discrete random variable that corresponds to the number of draws (with replacement) from a population of $k$ distinct objects required until $n$ distinct results are obtained, where $1le nle k$. Each item is equally likely to be drawn.
What is the probability mass function (PMF) of $X$? Its support is $[n,infty]capmathbb{N}$.
The only portion I'm able to derive is this:
$$P(X=n)=prod_{i=k-n+1}^{k}frac{i}{k}$$
But what about on the rest of the support? I assume it's going to involve combinatorics, but I'm not sure how to derive it.
probability combinatorics discrete-mathematics probability-distributions
asked Jan 9 at 19:33
jippyjoe4jippyjoe4
4768
$endgroup$
$begingroup$
On ${X=n+i}$ the $(n+i)^{mathsf{th}}$ draw yields the $n^{mathsf{th}}$ distinct object, so the first $(n+i-1)^{mathsf{th}}$ draws must be among $n-1$ of the $k$ objects.
$endgroup$
– Math1000
Jan 9 at 21:21
add a comment |
$begingroup$
Let $X$ be the discrete random variable that corresponds to the number of draws (with replacement) from a population of $k$ distinct objects required until $n$ distinct results are obtained, where $1le nle k$. Each item is equally likely to be drawn.
What is the probability mass function (PMF) of $X$? Its support is $[n,infty]capmathbb{N}$.
The only portion I'm able to derive is this:
$$P(X=n)=prod_{i=k-n+1}^{k}frac{i}{k}$$
But what about on the rest of the support? I assume it's going to involve combinatorics, but I'm not sure how to derive it.
probability combinatorics discrete-mathematics probability-distributions
asked Jan 9 at 19:33
jippyjoe4jippyjoe4
4768
$endgroup$
Let $X$ be the discrete random variable that corresponds to the number of draws (with replacement) from a population of $k$ distinct objects required until $n$ distinct results are obtained, where $1le nle k$. Each item is equally likely to be drawn.
What is the probability mass function (PMF) of $X$? Its support is $[n,infty]capmathbb{N}$.
The only portion I'm able to derive is this:
$$P(X=n)=prod_{i=k-n+1}^{k}frac{i}{k}$$
But what about on the rest of the support? I assume it's going to involve combinatorics, but I'm not sure how to derive it.
probability combinatorics discrete-mathematics probability-distributions
probability combinatorics discrete-mathematics probability-distributions
asked Jan 9 at 19:33
jippyjoe4jippyjoe4
4768
asked Jan 9 at 19:33
jippyjoe4jippyjoe4
4768
asked Jan 9 at 19:33
jippyjoe4jippyjoe4
4768
asked Jan 9 at 19:33
jippyjoe4jippyjoe4
4768
asked Jan 9 at 19:33
jippyjoe4jippyjoe4
4768
4768
$begingroup$
On ${X=n+i}$ the $(n+i)^{mathsf{th}}$ draw yields the $n^{mathsf{th}}$ distinct object, so the first $(n+i-1)^{mathsf{th}}$ draws must be among $n-1$ of the $k$ objects.
$endgroup$
– Math1000
Jan 9 at 21:21
add a comment |
$begingroup$
On ${X=n+i}$ the $(n+i)^{mathsf{th}}$ draw yields the $n^{mathsf{th}}$ distinct object, so the first $(n+i-1)^{mathsf{th}}$ draws must be among $n-1$ of the $k$ objects.
$endgroup$
– Math1000
Jan 9 at 21:21
$begingroup$
On ${X=n+i}$ the $(n+i)^{mathsf{th}}$ draw yields the $n^{mathsf{th}}$ distinct object, so the first $(n+i-1)^{mathsf{th}}$ draws must be among $n-1$ of the $k$ objects.
$endgroup$
– Math1000
Jan 9 at 21:21
$begingroup$
On ${X=n+i}$ the $(n+i)^{mathsf{th}}$ draw yields the $n^{mathsf{th}}$ distinct object, so the first $(n+i-1)^{mathsf{th}}$ draws must be among $n-1$ of the $k$ objects.
$endgroup$
– Math1000
Jan 9 at 21:21
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let $Y_i$ denote the $i^{th}$ sample. To choose a situation where $X=t$, you need to
- choose the value of $Y_t$ in $k$ ways.
- choose the set $S$ of $n-1$ values appearing among ${Y_1,dots,Y_{t-1}}$ in $binom{k-1}{n-1}$ ways.
partition the numbers ${1,2,dots,t-1}$ into $n-1$ sets in ${t-1brace n-1}$ ways. $^*$
assign to each part in the partition a distinct element of $S$ in $(n-1)!$ ways. The interpretation is that if a part is assigned the value $x$, then $Y_i=x$ for each $i$ in that part.
Therefore,
begin{align}
P(X=t)
&=k^{-t}cdot kcdot binom{k-1}{n-1}{t-1brace n-1}(n-1)!
\&=boxed{{t-1brace n-1}frac{k!}{(k-n)!k^{t}}}
end{align}
For example,
$$
P(X=n)=frac{(k-1)(k-2)dots(k-n+1)}{k^{n-1}}
$$
as expected. For another sanity check, you can verify the above is a probability distribution using the fourth equation in https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Generating_functions.
$^*$The notation ${m brace j}$ refers to the Stirling numbers of the second kind, which is the number of ways to partition a set of size $m$ into $j$ parts, where the order of the parts does not matter. This can be computed via $${mbrace j}=frac1{j!}sum_{i=0}^j(-1)^ibinom{j}i(j-i)^m.$$
answered Jan 9 at 22:42
Mike EarnestMike Earnest
22.3k12051
$endgroup$
$begingroup$
+1 though I might write your result as ${t-1brace n-1}dfrac{k! }{(k-n)! k^t}$. Compare this with the probability that after $t$ draws from $k$ you have exactly $n$ distinct items which is ${tbrace n}dfrac{k! }{(k-n)! k^t}$.
$endgroup$
– Henry
Jan 10 at 0:46
$begingroup$
@Henry Good point.
$endgroup$
– Mike Earnest
Jan 10 at 1:20
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%2f3067862%2fprobability-mass-function-of-number-of-draws-with-replacement-until-n-distinct-r%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let $Y_i$ denote the $i^{th}$ sample. To choose a situation where $X=t$, you need to
- choose the value of $Y_t$ in $k$ ways.
- choose the set $S$ of $n-1$ values appearing among ${Y_1,dots,Y_{t-1}}$ in $binom{k-1}{n-1}$ ways.
partition the numbers ${1,2,dots,t-1}$ into $n-1$ sets in ${t-1brace n-1}$ ways. $^*$
assign to each part in the partition a distinct element of $S$ in $(n-1)!$ ways. The interpretation is that if a part is assigned the value $x$, then $Y_i=x$ for each $i$ in that part.
Therefore,
begin{align}
P(X=t)
&=k^{-t}cdot kcdot binom{k-1}{n-1}{t-1brace n-1}(n-1)!
\&=boxed{{t-1brace n-1}frac{k!}{(k-n)!k^{t}}}
end{align}
For example,
$$
P(X=n)=frac{(k-1)(k-2)dots(k-n+1)}{k^{n-1}}
$$
as expected. For another sanity check, you can verify the above is a probability distribution using the fourth equation in https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Generating_functions.
$^*$The notation ${m brace j}$ refers to the Stirling numbers of the second kind, which is the number of ways to partition a set of size $m$ into $j$ parts, where the order of the parts does not matter. This can be computed via $${mbrace j}=frac1{j!}sum_{i=0}^j(-1)^ibinom{j}i(j-i)^m.$$
answered Jan 9 at 22:42
Mike EarnestMike Earnest
22.3k12051
$endgroup$
$begingroup$
+1 though I might write your result as ${t-1brace n-1}dfrac{k! }{(k-n)! k^t}$. Compare this with the probability that after $t$ draws from $k$ you have exactly $n$ distinct items which is ${tbrace n}dfrac{k! }{(k-n)! k^t}$.
$endgroup$
– Henry
Jan 10 at 0:46
$begingroup$
@Henry Good point.
$endgroup$
– Mike Earnest
Jan 10 at 1:20
add a comment |
$begingroup$
Let $Y_i$ denote the $i^{th}$ sample. To choose a situation where $X=t$, you need to
- choose the value of $Y_t$ in $k$ ways.
- choose the set $S$ of $n-1$ values appearing among ${Y_1,dots,Y_{t-1}}$ in $binom{k-1}{n-1}$ ways.
partition the numbers ${1,2,dots,t-1}$ into $n-1$ sets in ${t-1brace n-1}$ ways. $^*$
assign to each part in the partition a distinct element of $S$ in $(n-1)!$ ways. The interpretation is that if a part is assigned the value $x$, then $Y_i=x$ for each $i$ in that part.
Therefore,
begin{align}
P(X=t)
&=k^{-t}cdot kcdot binom{k-1}{n-1}{t-1brace n-1}(n-1)!
\&=boxed{{t-1brace n-1}frac{k!}{(k-n)!k^{t}}}
end{align}
For example,
$$
P(X=n)=frac{(k-1)(k-2)dots(k-n+1)}{k^{n-1}}
$$
as expected. For another sanity check, you can verify the above is a probability distribution using the fourth equation in https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Generating_functions.
$^*$The notation ${m brace j}$ refers to the Stirling numbers of the second kind, which is the number of ways to partition a set of size $m$ into $j$ parts, where the order of the parts does not matter. This can be computed via $${mbrace j}=frac1{j!}sum_{i=0}^j(-1)^ibinom{j}i(j-i)^m.$$
answered Jan 9 at 22:42
Mike EarnestMike Earnest
22.3k12051
$endgroup$
$begingroup$
+1 though I might write your result as ${t-1brace n-1}dfrac{k! }{(k-n)! k^t}$. Compare this with the probability that after $t$ draws from $k$ you have exactly $n$ distinct items which is ${tbrace n}dfrac{k! }{(k-n)! k^t}$.
$endgroup$
– Henry
Jan 10 at 0:46
$begingroup$
@Henry Good point.
$endgroup$
– Mike Earnest
Jan 10 at 1:20
add a comment |
$begingroup$
Let $Y_i$ denote the $i^{th}$ sample. To choose a situation where $X=t$, you need to
- choose the value of $Y_t$ in $k$ ways.
- choose the set $S$ of $n-1$ values appearing among ${Y_1,dots,Y_{t-1}}$ in $binom{k-1}{n-1}$ ways.
partition the numbers ${1,2,dots,t-1}$ into $n-1$ sets in ${t-1brace n-1}$ ways. $^*$
assign to each part in the partition a distinct element of $S$ in $(n-1)!$ ways. The interpretation is that if a part is assigned the value $x$, then $Y_i=x$ for each $i$ in that part.
Therefore,
begin{align}
P(X=t)
&=k^{-t}cdot kcdot binom{k-1}{n-1}{t-1brace n-1}(n-1)!
\&=boxed{{t-1brace n-1}frac{k!}{(k-n)!k^{t}}}
end{align}
For example,
$$
P(X=n)=frac{(k-1)(k-2)dots(k-n+1)}{k^{n-1}}
$$
as expected. For another sanity check, you can verify the above is a probability distribution using the fourth equation in https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Generating_functions.
$^*$The notation ${m brace j}$ refers to the Stirling numbers of the second kind, which is the number of ways to partition a set of size $m$ into $j$ parts, where the order of the parts does not matter. This can be computed via $${mbrace j}=frac1{j!}sum_{i=0}^j(-1)^ibinom{j}i(j-i)^m.$$
answered Jan 9 at 22:42
Mike EarnestMike Earnest
22.3k12051
$endgroup$
Let $Y_i$ denote the $i^{th}$ sample. To choose a situation where $X=t$, you need to
- choose the value of $Y_t$ in $k$ ways.
- choose the set $S$ of $n-1$ values appearing among ${Y_1,dots,Y_{t-1}}$ in $binom{k-1}{n-1}$ ways.
partition the numbers ${1,2,dots,t-1}$ into $n-1$ sets in ${t-1brace n-1}$ ways. $^*$
assign to each part in the partition a distinct element of $S$ in $(n-1)!$ ways. The interpretation is that if a part is assigned the value $x$, then $Y_i=x$ for each $i$ in that part.
Therefore,
begin{align}
P(X=t)
&=k^{-t}cdot kcdot binom{k-1}{n-1}{t-1brace n-1}(n-1)!
\&=boxed{{t-1brace n-1}frac{k!}{(k-n)!k^{t}}}
end{align}
For example,
$$
P(X=n)=frac{(k-1)(k-2)dots(k-n+1)}{k^{n-1}}
$$
as expected. For another sanity check, you can verify the above is a probability distribution using the fourth equation in https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Generating_functions.
$^*$The notation ${m brace j}$ refers to the Stirling numbers of the second kind, which is the number of ways to partition a set of size $m$ into $j$ parts, where the order of the parts does not matter. This can be computed via $${mbrace j}=frac1{j!}sum_{i=0}^j(-1)^ibinom{j}i(j-i)^m.$$
answered Jan 9 at 22:42
Mike EarnestMike Earnest
22.3k12051
edited Jan 10 at 4:09
answered Jan 9 at 22:42
Mike EarnestMike Earnest
22.3k12051
answered Jan 9 at 22:42
Mike EarnestMike Earnest
22.3k12051
answered Jan 9 at 22:42
Mike EarnestMike Earnest
22.3k12051
22.3k12051
$begingroup$
+1 though I might write your result as ${t-1brace n-1}dfrac{k! }{(k-n)! k^t}$. Compare this with the probability that after $t$ draws from $k$ you have exactly $n$ distinct items which is ${tbrace n}dfrac{k! }{(k-n)! k^t}$.
$endgroup$
– Henry
Jan 10 at 0:46
$begingroup$
@Henry Good point.
$endgroup$
– Mike Earnest
Jan 10 at 1:20
add a comment |
$begingroup$
+1 though I might write your result as ${t-1brace n-1}dfrac{k! }{(k-n)! k^t}$. Compare this with the probability that after $t$ draws from $k$ you have exactly $n$ distinct items which is ${tbrace n}dfrac{k! }{(k-n)! k^t}$.
$endgroup$
– Henry
Jan 10 at 0:46
$begingroup$
@Henry Good point.
$endgroup$
– Mike Earnest
Jan 10 at 1:20
$begingroup$
+1 though I might write your result as ${t-1brace n-1}dfrac{k! }{(k-n)! k^t}$. Compare this with the probability that after $t$ draws from $k$ you have exactly $n$ distinct items which is ${tbrace n}dfrac{k! }{(k-n)! k^t}$.
$endgroup$
– Henry
Jan 10 at 0:46
$begingroup$
+1 though I might write your result as ${t-1brace n-1}dfrac{k! }{(k-n)! k^t}$. Compare this with the probability that after $t$ draws from $k$ you have exactly $n$ distinct items which is ${tbrace n}dfrac{k! }{(k-n)! k^t}$.
$endgroup$
– Henry
Jan 10 at 0:46
$begingroup$
@Henry Good point.
$endgroup$
– Mike Earnest
Jan 10 at 1:20
$begingroup$
@Henry Good point.
$endgroup$
– Mike Earnest
Jan 10 at 1:20
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.
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%2f3067862%2fprobability-mass-function-of-number-of-draws-with-replacement-until-n-distinct-r%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
$begingroup$
On ${X=n+i}$ the $(n+i)^{mathsf{th}}$ draw yields the $n^{mathsf{th}}$ distinct object, so the first $(n+i-1)^{mathsf{th}}$ draws must be among $n-1$ of the $k$ objects.
$endgroup$
– Math1000
Jan 9 at 21:21