Mixing
is there a formula to “invert” the binomial distribution - for simulation purposes
My apologies if this should be in one of the programming sites rather than the mathematics one... I decided it was theoretical enough to post here. Feel free to move if someone with authority disagrees strongly. ;-)
So the layman's version of the question I'm asking is: I want to simulate flipping a coin until I get 75 'heads'. How many times did I flip the coin? In reality I'm trying to monte-carlo an algorithm that statistically counts events over a long period of time with very large (> 10^15) numbers of events.
The brute force approach here is obvious: I just write some code that loops over flipping a coin until I get my 75th head, then return the number of times I flipped it. But this is O(n) and gets really expensive/slow for large numbers of flips.
I can use the probability mass function and/or the cumulative distribution of binomial events to answer related questions, but I can't seem to find something that will "invert" this function (if that's even the right term?) and give me a single statistical answer to the direction I'm trying to do it ... obviously each iteration of this will result in a different number of flips, but the results of a lot of these trials will look binomial.
probability-distributions binomial-distribution simulation
asked Nov 20 '18 at 16:06
ljwobker
1034
add a comment |
My apologies if this should be in one of the programming sites rather than the mathematics one... I decided it was theoretical enough to post here. Feel free to move if someone with authority disagrees strongly. ;-)
So the layman's version of the question I'm asking is: I want to simulate flipping a coin until I get 75 'heads'. How many times did I flip the coin? In reality I'm trying to monte-carlo an algorithm that statistically counts events over a long period of time with very large (> 10^15) numbers of events.
The brute force approach here is obvious: I just write some code that loops over flipping a coin until I get my 75th head, then return the number of times I flipped it. But this is O(n) and gets really expensive/slow for large numbers of flips.
I can use the probability mass function and/or the cumulative distribution of binomial events to answer related questions, but I can't seem to find something that will "invert" this function (if that's even the right term?) and give me a single statistical answer to the direction I'm trying to do it ... obviously each iteration of this will result in a different number of flips, but the results of a lot of these trials will look binomial.
probability-distributions binomial-distribution simulation
asked Nov 20 '18 at 16:06
ljwobker
1034
What about using the central limit theorem?
– callculus
Nov 20 '18 at 16:30
add a comment |
My apologies if this should be in one of the programming sites rather than the mathematics one... I decided it was theoretical enough to post here. Feel free to move if someone with authority disagrees strongly. ;-)
So the layman's version of the question I'm asking is: I want to simulate flipping a coin until I get 75 'heads'. How many times did I flip the coin? In reality I'm trying to monte-carlo an algorithm that statistically counts events over a long period of time with very large (> 10^15) numbers of events.
The brute force approach here is obvious: I just write some code that loops over flipping a coin until I get my 75th head, then return the number of times I flipped it. But this is O(n) and gets really expensive/slow for large numbers of flips.
I can use the probability mass function and/or the cumulative distribution of binomial events to answer related questions, but I can't seem to find something that will "invert" this function (if that's even the right term?) and give me a single statistical answer to the direction I'm trying to do it ... obviously each iteration of this will result in a different number of flips, but the results of a lot of these trials will look binomial.
probability-distributions binomial-distribution simulation
asked Nov 20 '18 at 16:06
ljwobker
1034
My apologies if this should be in one of the programming sites rather than the mathematics one... I decided it was theoretical enough to post here. Feel free to move if someone with authority disagrees strongly. ;-)
So the layman's version of the question I'm asking is: I want to simulate flipping a coin until I get 75 'heads'. How many times did I flip the coin? In reality I'm trying to monte-carlo an algorithm that statistically counts events over a long period of time with very large (> 10^15) numbers of events.
The brute force approach here is obvious: I just write some code that loops over flipping a coin until I get my 75th head, then return the number of times I flipped it. But this is O(n) and gets really expensive/slow for large numbers of flips.
I can use the probability mass function and/or the cumulative distribution of binomial events to answer related questions, but I can't seem to find something that will "invert" this function (if that's even the right term?) and give me a single statistical answer to the direction I'm trying to do it ... obviously each iteration of this will result in a different number of flips, but the results of a lot of these trials will look binomial.
probability-distributions binomial-distribution simulation
probability-distributions binomial-distribution simulation
asked Nov 20 '18 at 16:06
ljwobker
1034
asked Nov 20 '18 at 16:06
ljwobker
1034
edited Dec 30 '18 at 5:22
asked Nov 20 '18 at 16:06
ljwobker
1034
asked Nov 20 '18 at 16:06
ljwobker
1034
asked Nov 20 '18 at 16:06
ljwobker
1034
1034
What about using the central limit theorem?
– callculus
Nov 20 '18 at 16:30
add a comment |
What about using the central limit theorem?
– callculus
Nov 20 '18 at 16:30
What about using the central limit theorem?
– callculus
Nov 20 '18 at 16:30
What about using the central limit theorem?
– callculus
Nov 20 '18 at 16:30
add a comment |
1 Answer
1
active
oldest
votes
You're sampling the negative binomial distribution. Inverse transform sampling of that distribution requires numerically solving an equation involving the beta function.
answered Nov 20 '18 at 17:42
J.G.
23k22137
“Negative” rather than “inverse” is exactly what I needed. Thanks. With that O(1) function I can sample any point along that distribution, then binary search for the number of failures and do that in O(log(n)) rather than having to monte-Carlo the whole thing at O(n). Thanks :-)
– ljwobker
Nov 21 '18 at 17:07
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%2f3006505%2fis-there-a-formula-to-invert-the-binomial-distribution-for-simulation-purpos%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
You're sampling the negative binomial distribution. Inverse transform sampling of that distribution requires numerically solving an equation involving the beta function.
answered Nov 20 '18 at 17:42
J.G.
23k22137
“Negative” rather than “inverse” is exactly what I needed. Thanks. With that O(1) function I can sample any point along that distribution, then binary search for the number of failures and do that in O(log(n)) rather than having to monte-Carlo the whole thing at O(n). Thanks :-)
– ljwobker
Nov 21 '18 at 17:07
add a comment |
You're sampling the negative binomial distribution. Inverse transform sampling of that distribution requires numerically solving an equation involving the beta function.
answered Nov 20 '18 at 17:42
J.G.
23k22137
“Negative” rather than “inverse” is exactly what I needed. Thanks. With that O(1) function I can sample any point along that distribution, then binary search for the number of failures and do that in O(log(n)) rather than having to monte-Carlo the whole thing at O(n). Thanks :-)
– ljwobker
Nov 21 '18 at 17:07
add a comment |
You're sampling the negative binomial distribution. Inverse transform sampling of that distribution requires numerically solving an equation involving the beta function.
answered Nov 20 '18 at 17:42
J.G.
23k22137
You're sampling the negative binomial distribution. Inverse transform sampling of that distribution requires numerically solving an equation involving the beta function.
answered Nov 20 '18 at 17:42
J.G.
23k22137
answered Nov 20 '18 at 17:42
J.G.
23k22137
answered Nov 20 '18 at 17:42
J.G.
23k22137
answered Nov 20 '18 at 17:42
J.G.
23k22137
23k22137
“Negative” rather than “inverse” is exactly what I needed. Thanks. With that O(1) function I can sample any point along that distribution, then binary search for the number of failures and do that in O(log(n)) rather than having to monte-Carlo the whole thing at O(n). Thanks :-)
– ljwobker
Nov 21 '18 at 17:07
add a comment |
“Negative” rather than “inverse” is exactly what I needed. Thanks. With that O(1) function I can sample any point along that distribution, then binary search for the number of failures and do that in O(log(n)) rather than having to monte-Carlo the whole thing at O(n). Thanks :-)
– ljwobker
Nov 21 '18 at 17:07
“Negative” rather than “inverse” is exactly what I needed. Thanks. With that O(1) function I can sample any point along that distribution, then binary search for the number of failures and do that in O(log(n)) rather than having to monte-Carlo the whole thing at O(n). Thanks :-)
– ljwobker
Nov 21 '18 at 17:07
“Negative” rather than “inverse” is exactly what I needed. Thanks. With that O(1) function I can sample any point along that distribution, then binary search for the number of failures and do that in O(log(n)) rather than having to monte-Carlo the whole thing at O(n). Thanks :-)
– ljwobker
Nov 21 '18 at 17:07
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%2f3006505%2fis-there-a-formula-to-invert-the-binomial-distribution-for-simulation-purpos%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
What about using the central limit theorem?
– callculus
Nov 20 '18 at 16:30