Limits with Asymptotics 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.
 A: 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}$.
A: 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.
A: 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.
