Extreme bionomal distribution, finding at least $x$ successes amongst many trials

Question

Sorry, I don't know much about advanced probabilities. I've learned most of what I know in the last few hours. So be gentle.

Essentially, I want to calculate the odds of dropping at least 80 swords in an idle RPG game. We kill 100 monsters per minute, and the drop chance of 1 is 1/20000 (0.005%). So, I want to know what the probability is for at least 80 to drop after 1 day, 10 days, 30 days and 365 days. Any of these will suffice for this question though, just to understand how it works.

As I understand it, 10 days is 1,440,000 trials:

$$10 days \times 24 hours \times 60 minutes \times 100 kills/minute$$

I've tried an online calculator which was limited to 1000 trials, and also manually calculating how likely exactly 80 swords is after 10 days:

$$\frac{n!}{x!\times(n-x)!} \times p^x \times q^{(n-x)}$$

n = number of trials
x = number of successes
p = probability of success in any one trial
q = probability of failure in any one trial (q = 1 - p)

$$\frac{1.44e6!}{80!\cdot(1.44e6-80)!} \times (1/20000)^{80} \times (19999/20000)^{(1.44e6-80)} \approx 2.9\% $$

But how do I find the chance that at least 80 drops will have occurred after $X$ minutes?

Answer 1

Let $X_n$ count the number of collected swords after $n$ minutes.

Note that $X_n$ follows a Binomial Distribution, $X_n\sim B(100n,\frac{1}{20000})$. The formula for calculating when a Binomial is lower or equal than a number is easily defined, so we will use it.

$\begin{align} P(X_n\geq 80)&=1-P(X_n\leq 79)\\ &=1-\sum_{i=0}^{79}\binom{100n}{i}\frac{1}{20000^i}\frac{19999^{n-i}}{20000^{n-i}}\\ &=1-\frac{19999^n}{20000^n}\sum_{i=0}^{79}\binom{100n}{i}\frac{1}{19999^i}\\ &=1-\frac{19999^n}{20000^n}\sum_{i=0}^{79}\frac{100n!}{i!(100n-i)!19999^i} \end{align}$

Now you simply have some calculations to do and a sumatory

Answer 2

Let $p = \frac{1}{20000},$ that is, $p$ is the probability to drop a sword in each trial. The expected value of the number of swords dropped per trial is $p$, and the variance in the number of swords dropped per trial is $p - p^2$ (since each trial is a Bernoulli random variable).

The expected value $\mu$ of a sum of random variables is the sum of their expected values, so in $N$ trials, the expected number of dropped swords is $\mu = Np$. Assuming each trial is a random variable independent of all the other trials, the variance $\sigma^2$ of the sum of the variables is the sum of their variances, so in $N$ trials the variance in the number of swords dropped is $\sigma^2 = N(p - p^2).$

The standard deviation $\sigma$ of a probability distribution is the square root of its variance. Since $p$ is so small in this case, $\sigma = \sqrt{N(p-p^2)} \approx \sqrt{Np}$.

If you add together $N$ independent Bernoulli variables, when $N$ is very large the resulting binomial distribution starts to look like a Gaussian distribution (also called a normal distribution). You can then use the mean and standard deviation of that normal distribution, along with tables that tell you what percentage of the time a normal random variable will be less than $m$ standard deviations above the mean, to estimate the probability that your binomial variable will be less than $m$ standard deviations above its mean.

$80$ is not a particularly large number in this context, so the approximation may be somewhat rough. But for $N = 1.44 \times 10^6$ trials, the expected number of dropped swords is $\mu = 72$ and the standard deviation is $\sigma = 8.485$. That is, $80$ swords is just about $\mu + 0.94 \sigma$. We look up $0.94$ in a table for area under the normal curve (such as the table on this page), or we have a computer calculate it for us, and we find that nearly $83\%$ of the area under the normal curve is to the left of that point, giving us about a $17\%$ chance to exceed $80$ swords (but recalling that that is a rough approximation, I'd just say it's somewhere around $15$ or $20$ percent).

The normal distribution tables tell us there is about a $0.01$ probability to exceed $\mu + 2.33\sigma$, so suppose $N$ is just large enough that $\mu + 2.33\sigma \approx Np + 2.33\sqrt{Np} = 80$. Letting $y = \sqrt{Np}$, this means we want to solve the quadratic equation $$y^2 + 2.33y - 80 = 0.$$ Once we find $y$, we can work backwards to find that $N = \frac{y^2}{p}$. The only positive root of the equation above is $y \approx 7.85$, so in that case $N \approx 1.23 \times 10^6.$ In other words, you have to do something like $1.23 \times 10^6$ trials in order to have at least a $1\%$ chance of dropping $80$ or more swords.

The tables also say that there is about a $0.0001$ chance to exceed $\mu + 3.73\sigma$, which implies a $0.9999$ chance to exceed $\mu - 3.73\sigma$. Solving for $y$ in $$y^2 + 3.73y - 80 = 0,$$ the only positive root is $y \approx 11.0016$, which implies $N \approx 2.42 \times 10^6$.

So the number of trials needed in order to have a $99.99\%$ chance of $80$ or more dropped swords is just about twice the number of trials that give you a $1\%$ chance of $80$ or more dropped swords. Or in other words, once you get to $1\%$, it takes only about the same amount of time again to reach $99.99\%$ probability. Is that what you meant by a "narrow timespan"?

To make this better than just an educated guess, however, you would still need to try calculating the exact binomial probabilities for each number of swords from $0$ to $79$ inclusive to find an accurate probability that you drop fewer than $80$ swords.

By the way, it may help in your calculations to use the fact that

$$\begin{eqnarray} \frac{n!}{x!(n-x)!} p^x q^{n-x} &=& \frac{n(n-1)(n-2)\cdots(n-x+1)}{x!} \left(\frac pq\right)^x q^n \\ &=& \left(\frac{n}{1}\cdot\frac pq\right) \left(\frac{n-1}{2}\cdot\frac pq\right) \left(\frac{n-2}{3}\cdot\frac pq\right)\cdots \left(\frac{n-x+1}{x}\cdot\frac pq\right) q^n. \end{eqnarray}$$

In particular, once you have the probability of dropping $x$ swords, call this $P(X = x)$, the probability of dropping $x+1$ swords is

$$\begin{eqnarray} P(X = x+1) &=& \frac{n!}{(x+1)!(n-x-1)!} p^{x+1} q^{n-x-1} \\ &=& \frac{n-x}{x+1} \cdot \frac pq \cdot \frac{n!}{x!(n-x)!} p^x q^{n-x} \\ &=& \frac{n-x}{x+1} \cdot \frac pq \cdot P(X = x). \end{eqnarray}$$

So computing all the probabilities from $x = 0$ to $x = 79$ inclusive is not terribly hard to do with the help of a computer. (If you are not using software that can deal with very large numbers, you may need to do the calculations using logarithms in order to avoid exceeding the maximum size of a floating-point number. But with that warning in mind, I think even a decent spreadsheet program can be made to do the calculation.)