If $\lim_{n \to \infty} np-\log n = c$ then why $\lim_{n \to \infty} n(1-p)^{(n-1)} = e^{-c}$?

72 Views Asked by At

If $p$ is a function of $n$ such that $\lim_{n \to \infty} np-\log n = c$ for some constant $c$, then why does $\lim_{n \to \infty} n(1-p)^{(n-1)} = e^{-c}$ hold?

I see that we would have $\lim_{n \to \infty} ne^{-np} = e^{-c}$ in this case, but why the stated limit?

1

There are 1 best solutions below

5
On BEST ANSWER

A good way to be sure asymptotic estimates like $1-p \sim e^{-p}$ hold up to the abuses your limits demand of them is to write them as inequalities. In this case, a useful pair of two-sided inequalities (valid for all $x>1$) is: $$\left(1-\frac1x\right)^{x} < \frac1e < \left(1-\frac1x\right)^{x-1}, \qquad \left(1 + \frac1x\right)^x < e < \left(1 + \frac1x\right)^{x+1}.$$ (We'll only need the first one, but I've included both for completeness. These are a few algebra steps removed from the most basic inequality: $e^x \ge x+1$.)

In this case, this tells us that $(1-p)^{1/p} < e^{-1} < (1-p)^{1/p-1}$, or $$1-p < e^{-p} < (1-p)^{1-p}.$$

Plugging this into the expression in our limit, we get $$n (1-p)^n < n e^{-pn} < n (1-p)^{n-pn}$$ or $$(1-p)^{pn} \cdot n e^{-pn} < n (1-p)^n < n e^{-pn}.$$ The correction factor of $(1-p)^{pn}$ is easily shown to approach $1$: for example, it is between $1 -p^2n$ and $1$ by Bernoulli's inequality. After that, we are done by the squeeze theorem.

Asymptotic calculations are the tedious part of studying random graphs, and I suggest that you just learn to replace $1-p$ by $e^{-p}$ whenever it occurs, as soon as it occurs; it will generally be valid by a computation similar to the one above, but you don't want to go through that justification every time.

Of course, you probably want to learn some of the tricks for doing the justification correctly, so you don't land in hot water like I did earlier.