Limits with Asymptotics

Question

I am currently stuck on how to solve this problem I'm having while doing a reading on random graph models. Given that I have function $p(n) = o \left( \frac{\log n}{n} \right)$, how do I evaluate the limit: $$ \lim_{n \to \infty} \left[1- p(n) \right]^{n-1} $$ I was told I can change the exponent from $n-1$ to $n$ since $p(n) \rightarrow 0$ as $n \rightarrow \infty$. Aside from that, I have been confused as to how to simplify using the asymptotic bound.

Answer 1

In the case $p = o(\frac{\log n}{n})$, you do not have enough information to find the limit. For example, if $p = \frac1n$, the limit is $\frac1e$; if $p = \frac1{n^2}$, the limit is $1$; if $p = \frac{\log \log n}{n}$, the limit is $0$.

However, we can say that $$1 - np \le (1-p)^n \le e^{-pn},$$ so if $np \to 0$ as $n \to \infty$, then the limit is $1$ by the squeeze theorem. Also, $$0 \le (1-p)^n \le e^{-pn},$$ so if $np \to \infty$ as $n \to \infty$, then the limit is $0$ by the squeeze theorem.

The only remaining case, in some sense, is that $np$ approaches a constant $c$ as $n \to \infty$. (Of course, we could also consider ill-behaved $p$ for which $np$ does not approach a limit at all, but nobody does this when studying random graphs.) In this case, you find a $q$ such that $(1-p) = (1-q)(1-c/n)$, use the above argument to show that $(1-q)^n \to 1$, and use the well-known result that as $n \to \infty$, $(1-c/n)^n \to e^{-c}$.

Answer 2

We have

$$p(n) = o \left(\frac{\log n}{n} \right)\iff p(n)=\omega(n)\frac{\log n}{n}\quad \omega(n)\to 0$$

then

$$\left[1- p(n) \right]^{n-1}=e^{(n-1)\log \left(1-\omega(n)\frac{\log n}{n}\right)}$$

and

$$(n-1)\log \left(1-\omega(n)\frac{\log n}{n}\right)\sim-\frac{n-1}{n}\omega(n)\log n$$

thus it seems not possible conclude.

Answer 3

Since $p(n) =o(\frac{\log n}{n}) $, for any $c > 0$, for large enough $n$, $p(n) \lt c\frac{\log n}{n} $, assuming that $p(n) > 0$.

Taking the log of your expression, $\log((1-p(n))^n) =n\log(1-p(n)) =-n(p(n)+p^2(n)/2+...) $ or $-\log((1-p(n))^n) =n(p(n)+p^2(n)/2+...) $ so $-\log((1-p(n))^n) \lt n(c\frac{log n}{n}+c^2\frac{\log^2 n}{n^2}+...) = c\log n+c^2\frac{\log^2 n}{n}+... = \log n^c+o(1) $.

Therefore, for any $c > 0$, for large enough $n$, $\dfrac1{(1-p(n))^n} \lt n^c $ or $(1-p(n))^n \gt n^{-c}$.

If we knew more about $p(n)$, we might be able to replace that $n^c$ with $\log(n)$, but I don't think that we can do that here.