# Help Understanding an Approximation

I am reading a paper where there is an approximation that I don't see where it comes from. I have $$\mu=np$$ where $$p \in (0,1)$$ is a probability and $$n$$ denotes some size of a graph and $$n$$ can be made sufficiently large. The approximation used is $$1 - \left(1-\frac{\mu}{n} \right)^{\mu-1+(\mu-1)^2} \approx \frac{\mu^3}{n}.$$ It is assumed that $$p=\Theta(\frac{\log(n)}{n})>3\frac{\log(n)}{n}$$. Any help is appreciated. Thank you.

Note that $$\mu - 1 + (\mu-1)^{2} = \mu(\mu - 1).$$ Using the approximation $$(1+x)^{\alpha} \approx 1 + \alpha x$$ for small $$x$$, we obtain $$\begin{equation*} \left(1 - \frac{\mu}{n}\right)^{\mu -1 + (\mu - 1)^{2}} \approx 1 - \frac{\mu^{2}(\mu -1)}{n}. \end{equation*}$$ Hence $$\begin{equation*} 1 - \left(1 - \frac{\mu}{n}\right)^{\mu -1 + (\mu - 1)^{2}} \approx \frac{\mu^{2}(\mu -1)}{n} = \frac{\mu^{3}-\mu^{2}}{n}. \end{equation*}$$ If we can assume that $$\mu$$ is sufficiently large (and indeed we assume that $$p > 3 \frac{\log{n}}{n}$$ so that $$\mu = np > 3 \log{n}$$), then the $$\mu^{2}$$ term pales in comparison to $$\mu^{3}$$, so the approximation $$\begin{equation*} \frac{\mu^{3} - \mu^{2}}{n} \approx \frac{\mu^{3}}{n} \end{equation*}$$ can also be made. Another way to view this last approximation is to say that $$\mu -1 \approx \mu$$ for large $$\mu$$ so that $$\mu^{2}(\mu -1) \approx \mu^{2}(\mu) = \mu^{3}.$$
• Thank you. For binomial approximation we also need $|\alpha x| \ll 1$ Here this means that $\mu(\mu-1)\frac{\mu}{n} \approx \frac{\mu^3}{n}$ should be very small comparison to 1. I think that is guaranteed by the fact that $p$ is Big-$\Theta$ of $\frac{\log(n)}{n}$ and not because $p$ is just greater than $3\frac{\log(n)}{n}$. Am I correct? Apr 13, 2020 at 15:26
• This is a good point, and your reasoning seems correct to me. You can calculate $\mu^{3}/n = n^{2}p^{3}$ which is of order $\log^{3}(n)/n$. This is small for large values of $n$.