Mixing
Fast(er) way of computing the cumulative binomial probability?
$begingroup$
While revising for my probability test, I saw this question from one of the previous exams:
You flip a fair coin 100 times. What is the probability that you have less than 45 heads?
My question is a simple one. I know that to calculate the probability of a specific amount of $ n $ heads (or tails), we can use the binomial distribution with formula $ P(X = k) = {n choose k} p^k(1-p)^{n-k} $, with $ n = 100 $ and $ p = 0.5 $ in this case. I also know that we can compute the chance of $ P(X < k) $ as either $ P(X = 0) + P(X = 1) + ... + P(X = k - 10) $ or $ 1 - (P(X = k) + P(X = k + 1) + ... + P(X = n)) $.
However this is a simple question only worth two points out of over 60 total points. I cannot imagine that you need to compute $ P(X = n) $ 44 separate times and sum them together for such a small amount of points.
Is there any way to rewrite the formula or apply a different trick to drastically lower the amount of computations you need to do?
probability binomial-distribution
asked Jan 28 at 15:37
molenzwiebelmolenzwiebel
1153
$endgroup$
add a comment |
$begingroup$
While revising for my probability test, I saw this question from one of the previous exams:
You flip a fair coin 100 times. What is the probability that you have less than 45 heads?
My question is a simple one. I know that to calculate the probability of a specific amount of $ n $ heads (or tails), we can use the binomial distribution with formula $ P(X = k) = {n choose k} p^k(1-p)^{n-k} $, with $ n = 100 $ and $ p = 0.5 $ in this case. I also know that we can compute the chance of $ P(X < k) $ as either $ P(X = 0) + P(X = 1) + ... + P(X = k - 10) $ or $ 1 - (P(X = k) + P(X = k + 1) + ... + P(X = n)) $.
However this is a simple question only worth two points out of over 60 total points. I cannot imagine that you need to compute $ P(X = n) $ 44 separate times and sum them together for such a small amount of points.
Is there any way to rewrite the formula or apply a different trick to drastically lower the amount of computations you need to do?
probability binomial-distribution
asked Jan 28 at 15:37
molenzwiebelmolenzwiebel
1153
$endgroup$
2
$begingroup$
The normal approximation works well for things like this.
$endgroup$
– lulu
Jan 28 at 15:48
1
$begingroup$
Alternatively, it should be pointed out that in most educational settings for a first course in combinatorics or probability not only are numerical answers for problems like this unnecessary, they are often discouraged. It is far more telling whether a student understands what is going on if you can see an answer with binomial coefficients and products left unsimplified since it implies the thought process used in creating the expression. $(0.5)^{100}cdot sumlimits_{k=0}^{44}binom{100}{k}$ is a perfectly acceptable answer in my book. If multiple choice with numerical, well... yeah...
$endgroup$
– JMoravitz
Jan 28 at 15:59
$begingroup$
Completely agreed @JMoravitz. The context for this particular question is the multiple-choice section on a final for a course on both probability and statistics, so the author of the test can be fairly sure that the student knows how to use the CLT (or at least should know).
$endgroup$
– molenzwiebel
Jan 28 at 16:02
$begingroup$
As for a different trick to drastically lower, note that it is just as probable to get $k$ heads as you are $100-k$ heads with a fair coin. You can get an exact answer then as $0.5 - (0.5)^{100}left(0.5binom{100}{50} + binom{100}{49}+binom{100}{48}+dots+binom{100}{45}right)$ due to the symmetry, dropping the number of binomial coefficients you need to calculate down from $45$ to just $6$. Still too tedious to do in an exam setting, but much less so than before.
$endgroup$
– JMoravitz
Jan 28 at 16:13
add a comment |
$begingroup$
While revising for my probability test, I saw this question from one of the previous exams:
You flip a fair coin 100 times. What is the probability that you have less than 45 heads?
My question is a simple one. I know that to calculate the probability of a specific amount of $ n $ heads (or tails), we can use the binomial distribution with formula $ P(X = k) = {n choose k} p^k(1-p)^{n-k} $, with $ n = 100 $ and $ p = 0.5 $ in this case. I also know that we can compute the chance of $ P(X < k) $ as either $ P(X = 0) + P(X = 1) + ... + P(X = k - 10) $ or $ 1 - (P(X = k) + P(X = k + 1) + ... + P(X = n)) $.
However this is a simple question only worth two points out of over 60 total points. I cannot imagine that you need to compute $ P(X = n) $ 44 separate times and sum them together for such a small amount of points.
Is there any way to rewrite the formula or apply a different trick to drastically lower the amount of computations you need to do?
probability binomial-distribution
asked Jan 28 at 15:37
molenzwiebelmolenzwiebel
1153
$endgroup$
While revising for my probability test, I saw this question from one of the previous exams:
You flip a fair coin 100 times. What is the probability that you have less than 45 heads?
My question is a simple one. I know that to calculate the probability of a specific amount of $ n $ heads (or tails), we can use the binomial distribution with formula $ P(X = k) = {n choose k} p^k(1-p)^{n-k} $, with $ n = 100 $ and $ p = 0.5 $ in this case. I also know that we can compute the chance of $ P(X < k) $ as either $ P(X = 0) + P(X = 1) + ... + P(X = k - 10) $ or $ 1 - (P(X = k) + P(X = k + 1) + ... + P(X = n)) $.
However this is a simple question only worth two points out of over 60 total points. I cannot imagine that you need to compute $ P(X = n) $ 44 separate times and sum them together for such a small amount of points.
Is there any way to rewrite the formula or apply a different trick to drastically lower the amount of computations you need to do?
probability binomial-distribution
probability binomial-distribution
asked Jan 28 at 15:37
molenzwiebelmolenzwiebel
1153
asked Jan 28 at 15:37
molenzwiebelmolenzwiebel
1153
asked Jan 28 at 15:37
molenzwiebelmolenzwiebel
1153
asked Jan 28 at 15:37
molenzwiebelmolenzwiebel
1153
asked Jan 28 at 15:37
molenzwiebelmolenzwiebel
1153
1153
2
$begingroup$
The normal approximation works well for things like this.
$endgroup$
– lulu
Jan 28 at 15:48
1
$begingroup$
Alternatively, it should be pointed out that in most educational settings for a first course in combinatorics or probability not only are numerical answers for problems like this unnecessary, they are often discouraged. It is far more telling whether a student understands what is going on if you can see an answer with binomial coefficients and products left unsimplified since it implies the thought process used in creating the expression. $(0.5)^{100}cdot sumlimits_{k=0}^{44}binom{100}{k}$ is a perfectly acceptable answer in my book. If multiple choice with numerical, well... yeah...
$endgroup$
– JMoravitz
Jan 28 at 15:59
$begingroup$
Completely agreed @JMoravitz. The context for this particular question is the multiple-choice section on a final for a course on both probability and statistics, so the author of the test can be fairly sure that the student knows how to use the CLT (or at least should know).
$endgroup$
– molenzwiebel
Jan 28 at 16:02
$begingroup$
As for a different trick to drastically lower, note that it is just as probable to get $k$ heads as you are $100-k$ heads with a fair coin. You can get an exact answer then as $0.5 - (0.5)^{100}left(0.5binom{100}{50} + binom{100}{49}+binom{100}{48}+dots+binom{100}{45}right)$ due to the symmetry, dropping the number of binomial coefficients you need to calculate down from $45$ to just $6$. Still too tedious to do in an exam setting, but much less so than before.
$endgroup$
– JMoravitz
Jan 28 at 16:13
add a comment |
2
$begingroup$
The normal approximation works well for things like this.
$endgroup$
– lulu
Jan 28 at 15:48
1
$begingroup$
Alternatively, it should be pointed out that in most educational settings for a first course in combinatorics or probability not only are numerical answers for problems like this unnecessary, they are often discouraged. It is far more telling whether a student understands what is going on if you can see an answer with binomial coefficients and products left unsimplified since it implies the thought process used in creating the expression. $(0.5)^{100}cdot sumlimits_{k=0}^{44}binom{100}{k}$ is a perfectly acceptable answer in my book. If multiple choice with numerical, well... yeah...
$endgroup$
– JMoravitz
Jan 28 at 15:59
$begingroup$
Completely agreed @JMoravitz. The context for this particular question is the multiple-choice section on a final for a course on both probability and statistics, so the author of the test can be fairly sure that the student knows how to use the CLT (or at least should know).
$endgroup$
– molenzwiebel
Jan 28 at 16:02
$begingroup$
As for a different trick to drastically lower, note that it is just as probable to get $k$ heads as you are $100-k$ heads with a fair coin. You can get an exact answer then as $0.5 - (0.5)^{100}left(0.5binom{100}{50} + binom{100}{49}+binom{100}{48}+dots+binom{100}{45}right)$ due to the symmetry, dropping the number of binomial coefficients you need to calculate down from $45$ to just $6$. Still too tedious to do in an exam setting, but much less so than before.
$endgroup$
– JMoravitz
Jan 28 at 16:13
2
2
$begingroup$
The normal approximation works well for things like this.
$endgroup$
– lulu
Jan 28 at 15:48
$begingroup$
The normal approximation works well for things like this.
$endgroup$
– lulu
Jan 28 at 15:48
1
1
$begingroup$
Alternatively, it should be pointed out that in most educational settings for a first course in combinatorics or probability not only are numerical answers for problems like this unnecessary, they are often discouraged. It is far more telling whether a student understands what is going on if you can see an answer with binomial coefficients and products left unsimplified since it implies the thought process used in creating the expression. $(0.5)^{100}cdot sumlimits_{k=0}^{44}binom{100}{k}$ is a perfectly acceptable answer in my book. If multiple choice with numerical, well... yeah...
$endgroup$
– JMoravitz
Jan 28 at 15:59
$begingroup$
Alternatively, it should be pointed out that in most educational settings for a first course in combinatorics or probability not only are numerical answers for problems like this unnecessary, they are often discouraged. It is far more telling whether a student understands what is going on if you can see an answer with binomial coefficients and products left unsimplified since it implies the thought process used in creating the expression. $(0.5)^{100}cdot sumlimits_{k=0}^{44}binom{100}{k}$ is a perfectly acceptable answer in my book. If multiple choice with numerical, well... yeah...
$endgroup$
– JMoravitz
Jan 28 at 15:59
$begingroup$
Completely agreed @JMoravitz. The context for this particular question is the multiple-choice section on a final for a course on both probability and statistics, so the author of the test can be fairly sure that the student knows how to use the CLT (or at least should know).
$endgroup$
– molenzwiebel
Jan 28 at 16:02
$begingroup$
Completely agreed @JMoravitz. The context for this particular question is the multiple-choice section on a final for a course on both probability and statistics, so the author of the test can be fairly sure that the student knows how to use the CLT (or at least should know).
$endgroup$
– molenzwiebel
Jan 28 at 16:02
$begingroup$
As for a different trick to drastically lower, note that it is just as probable to get $k$ heads as you are $100-k$ heads with a fair coin. You can get an exact answer then as $0.5 - (0.5)^{100}left(0.5binom{100}{50} + binom{100}{49}+binom{100}{48}+dots+binom{100}{45}right)$ due to the symmetry, dropping the number of binomial coefficients you need to calculate down from $45$ to just $6$. Still too tedious to do in an exam setting, but much less so than before.
$endgroup$
– JMoravitz
Jan 28 at 16:13
$begingroup$
As for a different trick to drastically lower, note that it is just as probable to get $k$ heads as you are $100-k$ heads with a fair coin. You can get an exact answer then as $0.5 - (0.5)^{100}left(0.5binom{100}{50} + binom{100}{49}+binom{100}{48}+dots+binom{100}{45}right)$ due to the symmetry, dropping the number of binomial coefficients you need to calculate down from $45$ to just $6$. Still too tedious to do in an exam setting, but much less so than before.
$endgroup$
– JMoravitz
Jan 28 at 16:13
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
@lulu's comment recommending normal approximation was enough for me to solve the question myself. The trick is to indeed use the central limit theorem since we already have a large $ n $.
Since our distribution is a binomial one, we have $ E[X] = mu = 0.5 cdot 100 = 50 $ and $ Var(X) = sigma^2 = 0.5 cdot 100 (1 - 0.5) = 25 $.
Then, we can compute $ frac{45-mu}{sqrt{sigma^2}} = frac{45-50}{sqrt{25}} = -1 $. Looking this up in the Z-table gives $ 0.1587 $. This is close to the exact answer of $ 0.14 $ (and indeed, both 0.14 and 0.16 are marked as correct in the answer sheet).
answered Jan 28 at 15:55
molenzwiebelmolenzwiebel
1153
$endgroup$
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%2f3091016%2ffaster-way-of-computing-the-cumulative-binomial-probability%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$
@lulu's comment recommending normal approximation was enough for me to solve the question myself. The trick is to indeed use the central limit theorem since we already have a large $ n $.
Since our distribution is a binomial one, we have $ E[X] = mu = 0.5 cdot 100 = 50 $ and $ Var(X) = sigma^2 = 0.5 cdot 100 (1 - 0.5) = 25 $.
Then, we can compute $ frac{45-mu}{sqrt{sigma^2}} = frac{45-50}{sqrt{25}} = -1 $. Looking this up in the Z-table gives $ 0.1587 $. This is close to the exact answer of $ 0.14 $ (and indeed, both 0.14 and 0.16 are marked as correct in the answer sheet).
answered Jan 28 at 15:55
molenzwiebelmolenzwiebel
1153
$endgroup$
add a comment |
$begingroup$
@lulu's comment recommending normal approximation was enough for me to solve the question myself. The trick is to indeed use the central limit theorem since we already have a large $ n $.
Since our distribution is a binomial one, we have $ E[X] = mu = 0.5 cdot 100 = 50 $ and $ Var(X) = sigma^2 = 0.5 cdot 100 (1 - 0.5) = 25 $.
Then, we can compute $ frac{45-mu}{sqrt{sigma^2}} = frac{45-50}{sqrt{25}} = -1 $. Looking this up in the Z-table gives $ 0.1587 $. This is close to the exact answer of $ 0.14 $ (and indeed, both 0.14 and 0.16 are marked as correct in the answer sheet).
answered Jan 28 at 15:55
molenzwiebelmolenzwiebel
1153
$endgroup$
add a comment |
$begingroup$
@lulu's comment recommending normal approximation was enough for me to solve the question myself. The trick is to indeed use the central limit theorem since we already have a large $ n $.
Since our distribution is a binomial one, we have $ E[X] = mu = 0.5 cdot 100 = 50 $ and $ Var(X) = sigma^2 = 0.5 cdot 100 (1 - 0.5) = 25 $.
Then, we can compute $ frac{45-mu}{sqrt{sigma^2}} = frac{45-50}{sqrt{25}} = -1 $. Looking this up in the Z-table gives $ 0.1587 $. This is close to the exact answer of $ 0.14 $ (and indeed, both 0.14 and 0.16 are marked as correct in the answer sheet).
answered Jan 28 at 15:55
molenzwiebelmolenzwiebel
1153
$endgroup$
@lulu's comment recommending normal approximation was enough for me to solve the question myself. The trick is to indeed use the central limit theorem since we already have a large $ n $.
Since our distribution is a binomial one, we have $ E[X] = mu = 0.5 cdot 100 = 50 $ and $ Var(X) = sigma^2 = 0.5 cdot 100 (1 - 0.5) = 25 $.
Then, we can compute $ frac{45-mu}{sqrt{sigma^2}} = frac{45-50}{sqrt{25}} = -1 $. Looking this up in the Z-table gives $ 0.1587 $. This is close to the exact answer of $ 0.14 $ (and indeed, both 0.14 and 0.16 are marked as correct in the answer sheet).
answered Jan 28 at 15:55
molenzwiebelmolenzwiebel
1153
answered Jan 28 at 15:55
molenzwiebelmolenzwiebel
1153
answered Jan 28 at 15:55
molenzwiebelmolenzwiebel
1153
answered Jan 28 at 15:55
molenzwiebelmolenzwiebel
1153
1153
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.
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%2f3091016%2ffaster-way-of-computing-the-cumulative-binomial-probability%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
2
$begingroup$
The normal approximation works well for things like this.
$endgroup$
– lulu
Jan 28 at 15:48
1
$begingroup$
Alternatively, it should be pointed out that in most educational settings for a first course in combinatorics or probability not only are numerical answers for problems like this unnecessary, they are often discouraged. It is far more telling whether a student understands what is going on if you can see an answer with binomial coefficients and products left unsimplified since it implies the thought process used in creating the expression. $(0.5)^{100}cdot sumlimits_{k=0}^{44}binom{100}{k}$ is a perfectly acceptable answer in my book. If multiple choice with numerical, well... yeah...
$endgroup$
– JMoravitz
Jan 28 at 15:59
$begingroup$
Completely agreed @JMoravitz. The context for this particular question is the multiple-choice section on a final for a course on both probability and statistics, so the author of the test can be fairly sure that the student knows how to use the CLT (or at least should know).
$endgroup$
– molenzwiebel
Jan 28 at 16:02
$begingroup$
As for a different trick to drastically lower, note that it is just as probable to get $k$ heads as you are $100-k$ heads with a fair coin. You can get an exact answer then as $0.5 - (0.5)^{100}left(0.5binom{100}{50} + binom{100}{49}+binom{100}{48}+dots+binom{100}{45}right)$ due to the symmetry, dropping the number of binomial coefficients you need to calculate down from $45$ to just $6$. Still too tedious to do in an exam setting, but much less so than before.
$endgroup$
– JMoravitz
Jan 28 at 16:13