Comportamiento asintótico de una Suma con los Coeficientes Binomiales

Question

El Problema:

Encontrar el comportamiento asintótico (con respecto a $n$) de la suma siguiente $$\sum\limits_{j = 3}^n \binom{n}{j} \frac{(j - 1)!}{2\cdot n^j}. $$

---

Donde el Problema Viene De: Si tenemos en cuenta el azar gráfico de $G(n,p)$, es decir, la gráfica de $n$ vértices donde cada una de las posibles borde se añade de forma independiente con una probabilidad de $p$, entonces el número esperado de ciclos es $$ \sum\limits_{j = 3}^n \binom{n}{j} \frac{(j - 1)!}{2} p^j. $$

Si tomamos $p = 1/n$, entonces obtenemos la suma mencionada anteriormente.

---

Lo que he Hecho hasta Ahora: se puede obtener un rápido-y-no-tan-grandes obligado de la siguiente manera: \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*}

Sin embargo, basado en un rápido programa que yo he escrito, parece que tal vez este en realidad debería ser $O(1)$, ya que esta suma parece permanecer por debajo de $1$, incluso cuando se $n = 130$ (casi tan grande como Python me permitirá que antes de golpear a un error de desbordamiento).

Utilizando la fórmula de Stirling (en diferentes formas) no arrojó ningún resultado. También probé: \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} que diverge como $n \to \infty$. Sin embargo, la suma de $$ \sum \frac{\alpha^j (j - 1)!}{j^j}$$ converge para todos los $|\alpha| < e$. Esto sugiere que tal vez se podría obligado $$\binom{n}{j} \leq \left(\frac{\alpha n}{j}\right)^j $$ for some $\alfa < 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$, que también funcionaría. No he sido capaz de averiguar cómo hacer que calcular el trabajo, sin embargo.

Así, es esta $O(1)$? Es $O(\log(n))$? Cualquier ayuda (o intuición) es apreciado.

Answer 1

Para cualquier $j$, tenemos \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*} Ahora supongamos, además, que $j=o(n)$. En este caso, para cada una de las $0 \leq i \leq j-1$ tenemos la expansión de Taylor $$\log\left(1-\frac{i}{n}\right) = -\frac{i}{n} +O(\frac{i^2}{n^2})=-(1+o(1))\frac{i}{n}$$ (con la constante implícita en el $o$ notación de aquí, dependiendo únicamente de la $j$). Esto significa que podemos obligado $$\binom{n}{j} = \frac{n^j}{j!} \exp\left(-(1+o(1)) \sum_{i=0}^{j-1} \frac{i}{n}\right).$$ Pero si $i=o(\sqrt{n})$, la suma dentro de la exponente es $o(1)$. En otras palabras, tenemos el (utilizadas) asintótica obligado que

Si $j$ es mucho menor que $\sqrt{n}$, $\binom{n}{j}=(1+o(1))\frac{n^j}{j!}$

Ahora vamos a ver lo que esto significa para su suma. Tenemos \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*} El $\frac{1}{3}$ aquí puede ser reemplazado por cualquier constante a menos de $1/2$. De modo que su suma crece logarítmicamente con $n$.

Si eres un poco más cuidadoso, usted probablemente puede demostrar que la suma es $(\frac{1}{4}+o(1)) \log n$. Un boceto: Para $j$ mayor que $n^{1/2+o(1)}$ la misma expansión de Taylor le da a ese $\binom{n}{j}$ es mucho menor que $\frac{n^j}{j! \log n}$. Por lo que la contribución total de $j$ mayor que $n^{1/2+o(1)}$$o(1)$, la contribución total de $j$ $n^{1/2-o(1)}$ es aproximadamente el $\frac{1}{4} \log n$, y a partir de su rápido-y-no-tan-grandes obligado. la zona entre contribuye $o(\log n)$