Useful Asymptotics

1 Taylor Expansion #

Approximating $$e^x$$ #

\begin{aligned} e^x &= 1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots\\ &= 1+x+O(x^2) \end{aligned}

This Taylor expansion holds for all $$x$$, but only for small $$x$$ is $$O(x^2)$$ less significant than $$x$$.

Approximating $$\ln (1+\frac{1}{n})$$ #

For $$-1\leq x\leq 1$$

$\ln (1+x)=x-\frac{x^2}{2}+\frac{x^3}{3}-\dots$

When $$x=\frac{1}{n}$$, we have $$\ln (1+\frac{1}{n})\sim \frac{1}{n}$$.

2 Harmonic Numbers Asymptotics #

The $$n$$-th harmonic number:

$H_n = 1+\frac{1}{2}+\frac{1}{3}+ \dots +\frac{1}{n} = \sum_{k=1}^n \frac{1}{k}$

Upper bound: if $$k = \lceil \log_2(n+1)\rceil$$, then

\begin{aligned} H_n &= 1+\frac{1}{2}+\frac{1}{3}+ \dots + \frac{1}{n}\\ &\leq 1+\frac{1}{2}+\frac{1}{3}+ \dots + \frac{1}{2^k-1}\\ &= 1+ \left( \frac{1}{2} + \frac{1}{3} \right) + \left( \frac{1}{4} + \frac{1}{5} + \frac{1}{6}+\frac{1}{7} \right)+ \dots + \left( \frac{1}{2^{k-1}}+\dots + \frac{1}{2^{k}-1} \right)\\ &\leq 1+ \left( \frac{1}{2} + \frac{1}{2} \right) + \left( \frac{1}{4} + \frac{1}{4} + \frac{1}{4}+\frac{1}{4} \right)+ \dots + \left( \frac{1}{2^{k-1}}+\dots + \frac{1}{2^{k-1}} \right)\\ &=\underbrace{1+1+\dots +1}_k = k \end{aligned}

Therefore $$H_n \leq \lceil \log_2(n+1)\rceil \sim \log_2 n$$

Lower bound is similar: if $$k = \lfloor \log_2(n)\rfloor$$, then

\begin{aligned} H_n &= 1+\frac{1}{2}+\frac{1}{3}+ \dots + \frac{1}{n}\\ &\geq 1+\frac{1}{2}+\frac{1}{3}+ \dots + \frac{1}{2^k}\\ &= 1+ \frac{1}{2} + \left( \frac{1}{3} + \frac{1}{4} \right) + \left( \frac{1}{5} + \frac{1}{6}+\frac{1}{7} + \frac{1}{8}\right) + \dots + \left( \frac{1}{2^{k-1}+1}+\dots + \frac{1}{2^{k}} \right)\\ &\geq 1+ \frac{1}{2} + \left( \frac{1}{4} + \frac{1}{4} \right) + \left( \frac{1}{8} + \frac{1}{8} + \frac{1}{8}+\frac{1}{8} \right)+ \dots + \left( \frac{1}{2^{k}}+\dots + \frac{1}{2^{k}} \right)\\ &=1 + \underbrace{\frac{1}{2}+\frac{1}{2}+\dots +\frac{1}{2}}_k = 1 + \frac{1}{2}k \end{aligned}

Therefore $$H_n \geq 1+\frac{1}{2}\lfloor \log_2 n\rfloor \sim \frac{1}{2}\log_2 n$$

In summary, $H_n = \Theta(\log n)$

We can also approximate $$H_n$$ by an integral.

The integral $$\int_{1}^n \frac{1}{x} dx = \ln n -\ln 1 = \ln n$$ has lower bound $$\frac{1}{2}+\frac{1}{3}+\dots + \frac{1}{n}=H_n-1$$, and upper bound $$1+\frac{1}{2}+\dots +\frac{1}{n-1} = H_{n-1}$$, this can be easily seen by drawing the graph, so we have:

$H_n-1\leq \ln n \leq H_{n-1} \Leftrightarrow \ln (n+1) \leq H_n \leq 1+\ln n$

We can write down a slightly less accurate but prettier estimate: $$\ln n \leq H_n \leq 1+\ln n$$

Randomly put $$n$$ balls into $$m$$ bins ($$n\leq m$$). What is the probability that no two balls land in the same bin?

The probability of no collisions is:

$p_{n,m} = 1 \cdot \left( 1-\frac{1}{m} \right) \left( 1-\frac{2}{m} \right) \cdots \left( 1-\frac{n-1}{m} \right)$

Using $$e^x\geq 1+x$$, we get a supper bound:

\begin{aligned} p_{n,m} &\leq e^{-\frac{1}{m}}\cdot e^{-\frac{2}{m}} \cdots e^{-\frac{n-1}{m}} \\ &= \exp \left( -\frac{1}{m}-\frac{2}{m}- \dots -\frac{n-1}{m} \right) \\ &= \exp \left( -\frac{n(n-1)}{2m} \right) \end{aligned}

Roughly, we say $$p_{n,m}\leq \exp \left( -\frac{n^2}{2m} \right)$$. (It doesn’t follow from the above, but just believe it.)

We can answer the question “when is $$p_{n.m}\approx \frac{1}{2}$$” by solving $$n$$, obtaining $$n\sim \sqrt{2 \ln 2} \cdot \sqrt{m}$$.

For the lower bound, since the Taylor expansion:

$\ln (1+x)=x-\frac{x^2}{2}+\frac{x^3}{3}-\dots$

We have $$\ln (1+x)\geq x-\frac{x^2}{2}$$, so $$1+x \geq \exp (x-O(x^2))$$. It follows that:

\begin{aligned} p_{n,m} &\geq e^{-\frac{1}{m}-O(\frac{1}{m^2})}\cdot e^{-\frac{2}{m}-O(\frac{2^2}{m^2})} \cdots e^{-\frac{n-1}{m}-O(\frac{(n-1)^2}{m^2})} \\ &= \exp \left( -\frac{1}{m}-\frac{2}{m}- \dots -\frac{n-1}{m} \right) \exp \left( \frac{1}{m^2} O(1^2+2^2+\dots+(n-1)^2) \right) \\ &= \exp \left( -\frac{n(n-1)}{2m} \right) \exp \left( -O\left(\frac{n^3}{m^2}\right) \right) \end{aligned}

This is the same thing as the upper bound, multiplied by an error factor. When $$n=\Theta(\sqrt{m})$$, this error factor is $$\exp \left( -O \left( \frac{1}{\sqrt{m}} \right) \right)$$, which is $$1-O \left( \frac{1}{\sqrt{m}} \right)$$.

So when $$n=\Theta(\sqrt{m})$$, the error factor doesn’t matter too match. This implies that when there are $$O(\sqrt{m})$$ balls and $$m$$ bins, there is around 50% chance to get a collision.

4 Factorial Asymptotics (Stirling’s Formula) #

Stirling’s formula: $n! = \Theta(\sqrt{n})\cdot \left( \frac{n}{e} \right)^n$

A more precise variant states that: $n! = \sqrt{2\pi n} \cdot \left( \frac{n}{e} \right)^n \left( 1 \pm O \left( \frac{1}{n} \right) \right)$

5 Binomial Approximation #

Approximate powers of 1 plus a small $$x$$. When $$|x|<1$$ and $$|\alpha x|\ll 1$$, then

$(1+x)^{\alpha} \approx 1+\alpha x$