4

I'm playing a game called Stardew Valley where each day, an ungrown tree has a $20\%$ chance of growing. So far I've figured out how to calculate what the odds of my tree growing at least once in d days is with the formula:

$$1 - 0.8^d$$

So for example if $d = 5$ that's a probably of $0.672$ that my tree will grow at least once in that time.

I want to be able to calculate the odds that it will grow at least $2, 3$ or $4$ times in d days.

Blue
  • 75,673
user3169700
  • 55
  • 1
    This can be modeled by what we call a Binomial random variable. The general formula for $k$ times of growth in $d$ days is $P(X=k)={d \choose k} p^k (1-p)^{d-k}$ where $p=0.2$ is the chance of growing per day. To get at least $k$ times of growth, we compute $P(X\geq k)=1-P(X\leq k-1)=1-\sum_{j=0}^{k-1} P(X=j)$. This can be readily computed in most programming languages or wolfram alpha and for small $k$ by hand. – Nap D. Lover Jul 28 '19 at 18:14
  • 1
    You probably can compute $P(X\geq k)$ by hand if $k$ is near $d$: $P(X\geq k)=\sum\limits_{j=k}^{d} \binom{d}{k}\cdot p^j\cdot (1-p)^{d-j}$. For instance if $k=d-1$ we have $P(X\geq k)=\sum\limits_{j=d-1}^{d} \binom{d}{d-1}\cdot p^j\cdot (1-p)^{d-(j)}$ $=\binom{d}{d-1}\cdot p^{d-1}\cdot (1-p)^{d-(d-1)}+\binom{d}{d}\cdot p^{d}\cdot (1-p)^{d-d}=d\cdot p^{d-1}\cdot (1-p)+1\cdot p^{d}\cdot 1$ – callculus42 Jul 28 '19 at 19:16

1 Answers1

5

If the probability of the tree growing on any given day is $p$, then the probability of the tree growing exactly $i$ times in $d$ days is given by the useful binomial distribution: $$P_d(X = i) = {d \choose i} p^i (1 - p)^{d - i} .$$ Here, ${n \choose i} := \frac{d!}{i! (d - i)!}$.

Thus, the probability $P_d(X \geq j)$ of growing at least $j$ times in $d$ days is the probability that it grows $j$ times or $j + 1$ times or... or $n - 1$ or $n$ times, that is, $$\color{#df0000}{\boxed{P_d(X \geq j) = \sum_{i = j}^n P_d(X = k) = \sum_{i = j}^n {d \choose i} p^i (1 - p)^{d - i}}} .$$ If $j$ is small, it is convenient to write instead $$P_d(X \geq j) = 1 - P_d(X < j) = 1 - \sum_{i = 1}^{j - 1} {d \choose i} p^i (1 - p)^{d - i},$$ because the sum that appears on the right-hand side then has few terms. For the first few values of $j$ we have (assuming in each case $0 \leq j \leq d$---otherwise the probability is zero): \begin{align*} P_d(X \geq 0) &= 1 \\ P_d(X \geq 1) &= 1 - (1 - p)^d \\ P_d(X \geq 2) &= 1 - (1 - p)^d - d p (1 - p)^{d - 1} \\ P_d(X \geq 3) &= 1 - (1 - p)^d - d p (1 - p)^{d - 1} - \frac{1}{2} d (d - 1) p^2 (1 - p)^{d - 2} \\ & \,\,\,\vdots \end{align*} As we'd expect, the formula for $P_d(X \geq 1)$ coincides with your formula for the particular value $p = \frac{1}{5}$.

For large values of $j$ it might be more practical to use an approximation that exploits the relationship between the binomial and normal distributions. For large enough $d$ (for the probability $p = \frac{1}{5}$, probably $d > 25$ is sufficient), the binomial distribution is well-approximated by the normal distribution with mean $d p$ and variance $d p (1 - p)$, giving the asymptotic approximation $$P_d(X \geq j) \approx \frac{1}{\sqrt{2 \pi d p (1 - p)}} \int_{j - \frac{1}{2}}^\infty \exp \left[ -\frac{(t - d p)^2}{2 d p (1 - p)} \right] dt = \frac{1}{2} \left[ 1 - \operatorname{erf} \left( \frac{-d p + j - \frac{1}{2}}{\sqrt{2 d p (1 - p)}}\right)\right] ,$$ where $\operatorname{erf}$ denotes the error function.

Travis Willse
  • 99,363