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.
Add a comment |
2 Answers
$\begingroup$ $\endgroup$
2 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}.$
- 1$\begingroup$ 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? $\endgroup$GA-Student– GA-Student2020-04-13 15:26:07 +00:00Commented Apr 13, 2020 at 15:26
- 1$\begingroup$ 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$. $\endgroup$Zac– Zac2020-04-13 15:36:11 +00:00Commented Apr 13, 2020 at 15:36
$\begingroup$ $\endgroup$
I have attached the detailed solution as an image in the link with this post. Your doubt is nothing but a problem of limit as n tends to infinity which can be easily solved using binomial approximation. Link: https://drive.google.com/file/d/1C1d1PcpLiv0AN00BFHGlA8s0J8GXi8yO/view?usp=drivesdk
