12
$\begingroup$

The Problem:

Find the asymptotic behavior (with respect to $n$) of the following sum $$\sum\limits_{j = 3}^n \binom{n}{j} \frac{(j - 1)!}{2\cdot n^j}. $$


Where the Problem Comes From: If we consider the random graph $G(n,p)$, i.e. the graph on $n$ vertices where each possible edge is added independently with probability $p$, then the expected number of cycles is $$ \sum\limits_{j = 3}^n \binom{n}{j} \frac{(j - 1)!}{2} p^j. $$

If we take $p = 1/n$, then we get the sum mentioned above.


What I've Done So Far: We can get a quick-and-not-so-great bound as follows: \begin{align*} \sum\limits_{j = 3}^n \binom{n}{j} \frac{(j - 1)!}{2\cdot n^j} &= \sum\limits_{j = 3}^n \frac{n!}{j\cdot(n - j)!} \frac{1}{2\cdot n^j} \\ &\leq \sum\limits_{j = 3}^n \frac{n^j}{j} \frac{1}{2\cdot n^j} \\ &= \sum\limits_{j = 3}^n \frac{1}{2\cdot j} \\ &=O(\log(n)). \end{align*}

However, based on a quick program I wrote, it seems that maybe this should actually be $O(1)$, as this sum appears to stay below $1$, even when $n = 130$ (about as large as Python will allow me before hitting an overflow error).

Using Stirling's formula (in various different ways) yielded no result. I also tried: \begin{align} \sum \binom{n}{j}\frac{(j-1)!}{2 n^j} &\leq \sum \left( \frac{e n}{j}\right)^j \frac{(j-1)!}{2 \cdot n^j} \\ &= \sum \frac{e^j (j - 1)!}{2\cdot j^j} \end{align} which diverges as $n \to \infty$. However, the sum $$ \sum \frac{\alpha^j (j - 1)!}{j^j}$$ converges for all $|\alpha| < e$. This suggests that maybe one could bound $$\binom{n}{j} \leq \left(\frac{\alpha n}{j}\right)^j $$ for some $\alpha < e$ (not depending on $n$) for all but $\log(n)$ terms; then we could break the terms up into those bounded with the constant $\alpha$ (which would converge) and the $\log(n)$ terms bounded with the constant $e$, which would also work. I haven't been able to figure out how to make that estimate work, though.

So, is this $O(1)$? Is it $O(\log(n))$? Any help (or intuition) is appreciated.

$\endgroup$
  • 3
    $\begingroup$ @Did, Sorry, but I don't see how $S_n$ satisfies that; could you show that in more detail? $\endgroup$ – Marcus M Jul 28 '15 at 18:26
  • 1
    $\begingroup$ Sorry I read $n!$ instead of $n^j$ in the denominator. $\endgroup$ – Did Jul 28 '15 at 20:13
2
$\begingroup$

For any $j$, we have \begin{eqnarray*} \binom{n}{j} &=& \frac{1}{j!} \prod_{i=0}^{j-1} (n-i) \\ &=& \frac{n^j}{j!} \prod_{i=0}^{j-1} \left(1-\frac{i}{n}\right) \end{eqnarray*} Now suppose further that $j=o(n)$. In this case for each $0 \leq i \leq j-1$ we have the Taylor expansion $$\log\left(1-\frac{i}{n}\right) = -\frac{i}{n} +O(\frac{i^2}{n^2})=-(1+o(1))\frac{i}{n}$$ (with the constant implicit in the $o$ notation here depending only on $j$). This means we can bound $$\binom{n}{j} = \frac{n^j}{j!} \exp\left(-(1+o(1)) \sum_{i=0}^{j-1} \frac{i}{n}\right).$$ But if $i=o(\sqrt{n})$, the sum inside the exponent is $o(1)$. In other words, we have the (commonly used) asymptotic bound that

If $j$ is much smaller than $\sqrt{n}$, then $\binom{n}{j}=(1+o(1))\frac{n^j}{j!}$

Now let's see what this means for your sum. We have \begin{eqnarray*} \sum_{j=3}^{n-1} \binom{n}{j} \frac{(j-1)!}{2 n^j} &\geq& \sum_{j=3}^{n^{1/3}} \binom{n}{j} \frac{(j-1)!}{2n^j} \\ &=& (1+o(1)) \sum_{j=3}^{n^{1/3}} \frac{n^j}{j!} \frac{(j-1)!}{2 n^j} \\ &=& (\frac{1}{2}+o(1)) \sum_{j=3}^{n^{1/3}} \frac{1}{j} \\ &=& (\frac{1}{2}+o(1)) (\frac{1}{3} \log n + O(1)) \end{eqnarray*} The $\frac{1}{3}$ here can be replaced by any constant less than $1/2$. So your sum grows logarithmically with $n$.

If you're a little more careful, you can probably actually show that the sum is $(\frac{1}{4}+o(1)) \log n$. A rough sketch: For $j$ larger than $n^{1/2+o(1)}$ the same Taylor expansion gives that $\binom{n}{j}$ is much smaller than $\frac{n^j}{j! \log n}$. So the total contribution from $j$ larger than $n^{1/2+o(1)}$ is $o(1)$, the total contribution from $j$ up to $n^{1/2-o(1)}$ is roughly $\frac{1}{4} \log n$, and from your quick-and-not-so-great bound. the zone in between contributes $o(\log n)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.