Why is $m(n)\approx\log_2(n)$?

46 Views Asked by At

Why is $m(n)\approx\log_2(n)$ ?

If $m(n)=\inf\{m:2^{-m}m^{-3/2}\le\frac1n\}$, taking log of $m(n)$ I get $-m(n)-\frac32\log_2(m(n))\le-\log_2(n)$

(This appears in the solution of an exercise in Rick Durret's Probability Theory and Examples)

enter image description here

1

There are 1 best solutions below

0
On

Since $2^{-m} m^{-3/2}$ is a decreasing function of $m$, $m(n)$ is approximately the value that makes the inequality into an equality, that is $$2^{-m(n)} m(n)^{-3 / 2} \approx \frac{1}{n} ,$$ or equivalently $$m(n) + \tfrac{3}{2} \log_2 m(n) \approx \log_2 n .$$ For large $m$ we have that $$m(n) \gg \tfrac{3}{2} \log_2 m(n) ,$$ so the contribution of the second term is relatively small, leaving $$m(n) \approx \log_2 n .$$