Mixing
Straight route to coupon collection
$begingroup$
Consider again the coupon collector's problem:
There are $c$ different types of coupon, and each coupon obtained is
equally likely to be any one of the $c$ types. Find the probability that
the first $n$ coupons which you collect do not form a complete set, and
deduce an expression for the mean number of coupons you will need to
collect before you have a complete set.
For the probability that the first $n$ coupons do not form a complete set, it will be the complementary probability that the first $n$ coupons do form a complete set, thus:
$$
mathbb{P}(ntext{ coupons, not complete set}) = 1 - {n choose c} left(frac{1}{c}right)^c.
$$
The idea for this expression is that the sequences of length $n$ that have at least the $c$ coupons are equal to the number of ways that $c$ elements can be disposed on a sequence of length $n$, thus ${n choose c}$. The sequence of $c$ distinct coupons has probability $c^{-c}$, and as I do not care about the remaining $n-c$ spots in the sequence, these can be anything.
For the mean number of coupons needed to collect before having a complete set, I would say:
$$
sum_{m=c}^infty m {m-1 choose c-1} left(frac{1}{c}right)^{c-1}left(frac{c-1}{c}right)^{m-c-1}frac{1}{c},
$$
as in this case for every length $m$ we need to count the number of sequences which contain all the $c$ distinct coupons, but the last coupon of the collection must be in the $m$-th place, so we need to dispose $c-1$ coupons in $m-1$ places. In the remaining $m-c$ places we can allow any coupon except for the last one we need, so the probability is $frac{c-1}{c}$.
What do you think? If I am correct, is there a way to compute the summation?
probability summation
asked Jan 25 at 18:19
J. D.J. D.
1898
$endgroup$
add a comment |
$begingroup$
Consider again the coupon collector's problem:
There are $c$ different types of coupon, and each coupon obtained is
equally likely to be any one of the $c$ types. Find the probability that
the first $n$ coupons which you collect do not form a complete set, and
deduce an expression for the mean number of coupons you will need to
collect before you have a complete set.
For the probability that the first $n$ coupons do not form a complete set, it will be the complementary probability that the first $n$ coupons do form a complete set, thus:
$$
mathbb{P}(ntext{ coupons, not complete set}) = 1 - {n choose c} left(frac{1}{c}right)^c.
$$
The idea for this expression is that the sequences of length $n$ that have at least the $c$ coupons are equal to the number of ways that $c$ elements can be disposed on a sequence of length $n$, thus ${n choose c}$. The sequence of $c$ distinct coupons has probability $c^{-c}$, and as I do not care about the remaining $n-c$ spots in the sequence, these can be anything.
For the mean number of coupons needed to collect before having a complete set, I would say:
$$
sum_{m=c}^infty m {m-1 choose c-1} left(frac{1}{c}right)^{c-1}left(frac{c-1}{c}right)^{m-c-1}frac{1}{c},
$$
as in this case for every length $m$ we need to count the number of sequences which contain all the $c$ distinct coupons, but the last coupon of the collection must be in the $m$-th place, so we need to dispose $c-1$ coupons in $m-1$ places. In the remaining $m-c$ places we can allow any coupon except for the last one we need, so the probability is $frac{c-1}{c}$.
What do you think? If I am correct, is there a way to compute the summation?
probability summation
asked Jan 25 at 18:19
J. D.J. D.
1898
$endgroup$
add a comment |
$begingroup$
Consider again the coupon collector's problem:
There are $c$ different types of coupon, and each coupon obtained is
equally likely to be any one of the $c$ types. Find the probability that
the first $n$ coupons which you collect do not form a complete set, and
deduce an expression for the mean number of coupons you will need to
collect before you have a complete set.
For the probability that the first $n$ coupons do not form a complete set, it will be the complementary probability that the first $n$ coupons do form a complete set, thus:
$$
mathbb{P}(ntext{ coupons, not complete set}) = 1 - {n choose c} left(frac{1}{c}right)^c.
$$
The idea for this expression is that the sequences of length $n$ that have at least the $c$ coupons are equal to the number of ways that $c$ elements can be disposed on a sequence of length $n$, thus ${n choose c}$. The sequence of $c$ distinct coupons has probability $c^{-c}$, and as I do not care about the remaining $n-c$ spots in the sequence, these can be anything.
For the mean number of coupons needed to collect before having a complete set, I would say:
$$
sum_{m=c}^infty m {m-1 choose c-1} left(frac{1}{c}right)^{c-1}left(frac{c-1}{c}right)^{m-c-1}frac{1}{c},
$$
as in this case for every length $m$ we need to count the number of sequences which contain all the $c$ distinct coupons, but the last coupon of the collection must be in the $m$-th place, so we need to dispose $c-1$ coupons in $m-1$ places. In the remaining $m-c$ places we can allow any coupon except for the last one we need, so the probability is $frac{c-1}{c}$.
What do you think? If I am correct, is there a way to compute the summation?
probability summation
asked Jan 25 at 18:19
J. D.J. D.
1898
$endgroup$
Consider again the coupon collector's problem:
There are $c$ different types of coupon, and each coupon obtained is
equally likely to be any one of the $c$ types. Find the probability that
the first $n$ coupons which you collect do not form a complete set, and
deduce an expression for the mean number of coupons you will need to
collect before you have a complete set.
For the probability that the first $n$ coupons do not form a complete set, it will be the complementary probability that the first $n$ coupons do form a complete set, thus:
$$
mathbb{P}(ntext{ coupons, not complete set}) = 1 - {n choose c} left(frac{1}{c}right)^c.
$$
The idea for this expression is that the sequences of length $n$ that have at least the $c$ coupons are equal to the number of ways that $c$ elements can be disposed on a sequence of length $n$, thus ${n choose c}$. The sequence of $c$ distinct coupons has probability $c^{-c}$, and as I do not care about the remaining $n-c$ spots in the sequence, these can be anything.
For the mean number of coupons needed to collect before having a complete set, I would say:
$$
sum_{m=c}^infty m {m-1 choose c-1} left(frac{1}{c}right)^{c-1}left(frac{c-1}{c}right)^{m-c-1}frac{1}{c},
$$
as in this case for every length $m$ we need to count the number of sequences which contain all the $c$ distinct coupons, but the last coupon of the collection must be in the $m$-th place, so we need to dispose $c-1$ coupons in $m-1$ places. In the remaining $m-c$ places we can allow any coupon except for the last one we need, so the probability is $frac{c-1}{c}$.
What do you think? If I am correct, is there a way to compute the summation?
probability summation
probability summation
asked Jan 25 at 18:19
J. D.J. D.
1898
asked Jan 25 at 18:19
J. D.J. D.
1898
asked Jan 25 at 18:19
J. D.J. D.
1898
asked Jan 25 at 18:19
J. D.J. D.
1898
asked Jan 25 at 18:19
J. D.J. D.
1898
1898
add a comment |
add a comment |
0
active
oldest
votes
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%2f3087435%2fstraight-route-to-coupon-collection%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3087435%2fstraight-route-to-coupon-collection%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
