I'm trying to reconstruct the proof for the Erdös-Renyi Theorem from Jackson's "Social and Economic Networks" [1], chapter 4.2.3. This part I don't understand:
Let $p(n)$ be a function s.t. $\lim_{n\to \infty} \frac{p(n)}{\ln n / n} \to 0$, i.e., a function that grows slower than $\ln n / n$. Relevant for the proof are indeed choices for $p(n)$ that are close to $\ln n / n$, since we want to show that $\ln n / n$ is a threshold for this choice.
The proof then claims that $(1-p(n))^n$ can be approximated by $e^{-np(n)}$. It does not state what "approximate" should mean in this context. The relevant quote from the proof is:
Given that $p(n)/n$ converges to 0, we can approximate $(1 - p(n))^n$ by $e^{-np(n)}$.
The first thing I associate this with is $\lim_{n \to \infty}(1 + \frac{a}{n})^n = e^a$. If we say that $p(n)$ is chosen "very close" to $\ln n / n$ (say $(\ln n / n)^{1 - \epsilon}$) I could see how we can squeeze our eyes and rewrite $(1-p(n))^n$ as $(1 - \frac{\ln n}{n})^n$. If we now treated $\ln n$ as a constant (which it obviously is not), this would lead to $\lim_{n \to \infty}(1 - \frac{\ln n}{n})^n = e^{-\ln n}$. With $p(n) \approx \ln n / n$, this amounts to $e^{-p(n)n}$.
However, treating $\ln n$ as a constant feels (and is) very wrong here, right? Am I missing some way of making this approximation?
Thanks for any help.
[1] Jackson, Matthew O. Social and economic networks. Princeton university press, 2010.
That is because $\;(1 - \frac{\ln n}{n})^n=\mathrm e^{n\ln(1 - \frac{\ln n}{n})}$ and that, in a neighbourhood of $0$, we have $\ln(1-u)=-u-\frac{u^2}2+o(u^2)$, so that $$\mathrm e^{n\ln(1 - \frac{\ln n}{n})}=\mathrm e^{n\bigl(- \tfrac{\ln n}{n}-\tfrac{\ln^2n}{2n^2}+o\bigl(\tfrac{\ln^2 n}{n^2}\bigr)\bigr)}= \mathrm e^{-\ln n}\cdot\underbrace{\mathrm e^{-\tfrac{\ln^2 n}{2n}+o\bigl(\tfrac{\ln^2n} n\bigr)}}_{\substack{\downarrow\\\mathstrut 1}}\sim_\infty\mathrm e^{-\ln n}$$