Convergence of $\prod_\limits{i=0}^{m-1} 1-\frac{4i}{n(n-1)(n-2)-2i(n-2)}$

102 Views Asked by At

In the context of Random graph threshold, in particularin the Uniform Random Graph model (i.e. I am working with the probability space $G_{n,M}$ described in Erdos' paper https://users.renyi.hu/~p_erdos/1959-11.pdf), I want to prove that $m^* = \frac{1}{2}n\log n$ is sharp threshold for the property that a graph on n vertices contains at least one isolated vertex (basically proving lemma 1.11 at page 13 of https://www.math.cmu.edu/~af1p/BOOK.pdf). Note that in this context we are interested to see what happens as $n \to \infty$.

Now in equation (1.9) of that lemma, there is the following product: $$\prod_{i=0}^{m-1} 1-\frac{4i}{n(n-1)(n-2)-2i(n-2)},$$ where $m=\frac{1}{2}n(\log(n)+\omega(n))$ where $\omega(n)=o(\log n)$.

Also in what follows $m=\frac{1}{2}n(\log(n)+\omega(n))$

Now the product turn out to be $\left(1+\mathcal O\left(\frac{(\log n)^2}{n}\right)\right)$. However in this context I just get away with the fact that asymptotically as $n\to \infty$ the product goes to $1$.

I can prove that by reasoning in the following manner: $\prod_{i} (1-f(i))\leq \prod_{i} (1-h(i))$ if $\forall i:h(i)\leq f(i)$.

Now in our case $f(i)=\frac{4i}{n(n-1)(n-2)-2i(n-2)}$ while we can take $h(i)=\frac{4}{n^3+2n(\log(n)+\omega(n))+2n}$

Using the fact that $h(i) \to 0$ as $n \to 0$ I use the asymptotic approximation $(1+z)^\alpha$ valid for small $z$ to get: $$\prod_{i=0}^{m-1} (1-h(i))=\left(1-\frac{4}{n^3}\right)^{\frac{1}{2}n(\log(n)+\omega(n))}=1+\mathcal O\left(\frac{\log n}{n^2}\right)$$

I have dropped the smaller terms in the denominator and $\omega$ by our assumption that $\omega(n)=o(\log n)$.

In a similar manner I can take $g(i) \geq f(i)$ and by reasoning in the same way I get that the product is bounded below by $$\prod_{i=0}^{m-1} (1-g(i))=\left(1+\mathcal O\left(\frac{(\log n)^2}{n}\right)\right)$$

Therefore as $n \to \infty$ I can prove that the product goes to 1 by the sandwich theorem.

However is there a nicer and quicker way to prove that the product is $$\left(1+\mathcal O\left(\frac{(\log n)^2}{n}\right)\right)$$

1

There are 1 best solutions below

2
On BEST ANSWER

To begin with, as soon as I see the expression, I want to clean up the denominator before doing anything else. Since $0 \le i < m < \frac12 \binom n2$, we have $$ \frac12 n(n-1)(n-2) \le n(n-1)(n-2) - 2i(n-2) \le n(n-1)(n-2), $$ and therefore $$ \frac{4i}{n(n-1)(n-2)} \le \frac{4i}{n(n-1)(n-2) - 2i(n-2)} \le \frac{8i}{n(n-1)(n-2)}. $$ We will not care about the constant $4$ versus $8$, so both bounds are as tight as we need them to be.

For the lower bound, we simply have $$ \prod_{i=0}^{m-1} \left(1 - \frac{8i}{n(n-1)(n-2)}\right) \ge 1 - \sum_{i=0}^{m-1} \frac{8i}{n(n-1)(n-2)} = 1 - \frac{8\binom m2}{n(n-1)(n-2)} $$ and this is clearly $1 + O(\frac{(\log n)^2}{n})$. (Why the relationship between the product and the sum? Because multiplying a number less than $1$ by a factor $1-p$ decreases it by at most $p$.)

In particular, for $n$ sufficiently large, our product always stays above $\frac12$. Multiplying a number greater than $\frac12$ by a factor $1-p$ decreases it by at least $\frac p2$, so we have the upper bound $$ \prod_{i=0}^{m-1} \left(1 - \frac{4i}{n(n-1)(n-2)}\right) \le 1 - \frac12\sum_{i=0}^{m-1} \frac{4i}{n(n-1)(n-2)} = 1 - \frac{2\binom m2}{n(n-1)(n-2)} $$ and this is also clearly $1 + O(\frac{(\log n)^2}{n})$.

A more precise version of this argument (replacing the initial bound of $m < \frac12 \binom n2$ by $m < \epsilon \binom n2$, and saying that our product stays above $1-\epsilon$ rather than above $\frac12$ when $n$ is sufficiently large) actually tells us that the error term is not just $O(\frac{(\log n)^2}{n})$ but $(1+o(1)) \frac{2m^2}{n^3}$.