0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What about using the central limit theorem? $\endgroup$ – callculus Nov 20 '18 at 16:30
1
$\begingroup$

You're sampling the negative binomial distribution. Inverse transform sampling of that distribution requires numerically solving an equation involving the beta function.

$\endgroup$
  • $\begingroup$ “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 :-) $\endgroup$ – ljwobker Nov 21 '18 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.