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.
You're sampling the negative binomial distribution. Inverse transform sampling of that distribution requires numerically solving an equation involving the beta function.