Una discusión reciente, que puede ser encontrado aquí, examinó el problema de contar el número de acíclicos de los bigramas en $n$ etiquetado de nodos y habiendo $k$ bordes y indegree y outdegree a más de uno. Se estableció que la bivariante mixto de generación de la función de esta clase $\mathcal{G}$ de los gráficos en $n$ nodos y con $k$, de bordes $$ G(z, u) = \exp \left(\frac{z}{1-uz} \right).$$ Esto implica inmediatamente que el número esperado de los bordes de un azar gráfico de $\mathcal{G}$ es $$\epsilon_n = [z^n]\left. \frac{d}{du} G(z,u) \right|_{u=1}.$$ La evaluación de esta cantidad, obtenemos $$ \left. \exp \left(\frac{z}{1-uz} \right) z (-1)\frac{1}{(1-uz)^2} (-z)\right|_{u=1} = \left. \exp \left(\frac{z}{1-uz} \right) \frac{z^2}{(1-uz)^2} \right|_{u=1} = \exp \left(\frac{z}{1-z}\right) \left(\frac{z}{1-z}\right)^2$$ Continuando con este cálculo podemos encontrar $$ \epsilon_n = [z^n] \sum_{m\ge 0} \frac{1}{m.} \left(\frac{z}{1-z}\right)^{m+2} = \sum_{m=0}^{n-2} \frac{1}{m.} [z^n] \left(\frac{z}{1-z}\right)^{m+2} = \sum_{m=0}^{n-2} \frac{1}{m.} [z^{n-m-2}] \left(\frac{1}{1-z}\right)^{m+2} = \sum_{m=0}^{n-2} \frac{1}{m.} \binom{n-m 2+m+1}{m+1} = \sum_{m=0}^{n-2} \frac{1}{m.} \binom{n-1}{m+1}.$$ De esta forma cerrada es en realidad bastante bueno, pero no responde a la pregunta que es la más obvia para este problema, es decir, hay un asintótica de expansión de $\epsilon_n$ y si sí, ¿cuál es el primer término?
Respuestas
¿Demasiados anuncios?
Podemos ampliar el cálculo de la varianza además del valor esperado. Para ello calculamos el $$E[X(X-1)] = \frac{ [z^n] \left. \left(\frac{d}{du}\right)^2 G(z, u) \right|_{u=1}}{[z^n] G(z, 1)}$$ where $X$ es de la RV, que representa el número de aristas. Ahora, $$\left. \left(\frac{d}{du}\right)^2 G(z, u) \right|_{u=1} = \left.\left( \frac{d}{du}\right)\exp\left(\frac{z}{1-uz}\right) \left(\frac{z}{1-uz}\right)^2 \right|_{u=1} = \left.\exp\left(\frac{z}{1-uz}\right) \left(\frac{z}{1-uz}\right)^4 + 2 \exp\left(\frac{z}{1-uz}\right) \left(\frac{z}{1-uz}\right)^3 \right|_{u=1} = \exp\left(\frac{z}{1-z}\right) \left(\frac{z}{1-z}\right)^4 + 2 \exp\left(\frac{z}{1-z}\right) \left(\frac{z}{1-z}\right)^3$$ Ahora expandir los dos términos en turno. El término izquierda, $$[z^n] \exp\left(\frac{z}{1-z}\right) \left(\frac{z}{1-z}\right)^4 = [z^n] \sum_{m\ge 0} \frac{1}{m.} \left( \frac{z}{1-z}\right)^{m+4} = [z^n] \sum_{m=0}^{n-4} \frac{1}{m.} \left( \frac{z}{1-z}\right)^{m+4} $$ or $$ \sum_{m=0}^{n-4} \frac{1}{m.} [z^{n-m-4}] \left( \frac{1}{1-z}\right)^{m+4} = \sum_{m=0}^{n-4} \frac{1}{m.} \binom{n-m-4+m+3}{m+3} = \sum_{m=0}^{n-4} \frac{1}{m.} \binom{n-1}{m+3}.$$ Término derecho, $$2 [z^n] \exp\left(\frac{z}{1-z}\right) \left(\frac{z}{1-z}\right)^3 = 2 [z^n] \sum_{m\ge 0} \frac{1}{m.} \left( \frac{z}{1-z}\right)^{m+3} = 2 [z^n] \sum_{m=0}^{n-3} \frac{1}{m.} \left( \frac{z}{1-z}\right)^{m+3} $$ or $$ 2 \sum_{m=0}^{n-3} \frac{1}{m.} [z^{n-m-3}] \left( \frac{1}{1-z}\right)^{m+3} = 2 \sum_{m=0}^{n-3} \frac{1}{m.} \binom{n-m-3+m+2}{m+2} = 2 \sum_{m=0}^{n-3} \frac{1}{m.} \binom{n-1}{m+2}.$$ De ello se sigue que $$E[X(X-1)] = \frac{\sum_{m=0}^{n-4} \frac{1}{m.} \binom{n-1}{m+3} + 2 \sum_{m=0}^{n-3} \frac{1}{m.} \binom{n-1}{m+2}}{\sum_{m=1}^n \frac{1}{m.} \binom{n-1}{m-1}}.$$ La pregunta ahora es, ¿cuál es la forma asintótica de la expansión de este cociente de sumas? Que pondría la varianza dentro de alcance, dado que el $E[X^2] = E[X(X-1)] + E[X].$
Lo que se calcula es el número de aristas, pero el número total de aristas de todos los gráficos en $\mathcal G$ $n$ nodos. Para obtener el número esperado de bordes tendrías que dividir por el número de estos gráficos.
Otro método para aproximar el número esperado de bordes es encontrar el modo de que el número de gráficos como una función del número de bordes y de la estimación de cuánto la media podrían desviarse de la modalidad. El número de
$$ q_{nk}=\binom nk\binom{n-1}kk!=\frac{n!(n-1)!}{k!(n-k)!(n-1-k)!} $$
de gráficos en $n$ nodos con $k$ bordes es máxima cuando el nuevo factor de $k$ que se añade a la del denominador es igual a la de los factores de $(n-k)(n-1-k)$ ser eliminado:
$$k=(n-k)(n-1-k)\;,$$ $$k=n\pm\sqrt n\;.$$
Para ver qué tan cerca de la media es el modo en $k=n-\sqrt n$, podemos aproximar el logaritmo del número de gráficos usando la aproximación de Stirling:
$$ \begin{align} \log q_{nk}\approx&n\log n+(n-1)\log(n-1)-k\log k \\ &-(n-k)\log(n-k)-(n-1-k)\log(n-1-k)-k \end{align} $$
y así
$$ \begin{align} \frac{\mathrm d\log q_{nk}}{\mathrm dk} &\approx-\log k+\log(n-k)+\log(n-1-k)\;,\\ \frac{\mathrm d^2\log q_{nk}}{\mathrm dk^2} &\approx-\frac1k-\frac1{n-k}-\frac1{n-1-k}\;. \end{align} $$
Configuración de la primera derivada a cero rendimientos $k=(n-k)(n-1-k)$ como se esperaba, y la sustitución de $k=n-\sqrt n$ en el segundo derivado de los rendimientos de aproximadamente $-2/\sqrt n$. Por lo tanto el número de gráficos como una función de $k$ puede ser aproximada por una Gaussiana con la anchura de la orden de $\sqrt[4]n$, por lo que la diferencia entre el máximo y la media debe ser en la mayoría de las $O(\sqrt[4]n)$. De hecho, los resultados numéricos sugieren una mucho más pequeña diferencia, aparentemente $O(\log\log n)$ e incluso quizás $O(1)$:
$$ \begin{array}{r|r|r|c} \log_2n&\langle k\rangle&n-\sqrt n&\langle k\rangle-(n-\sqrt n)\\\hline 0&0.0000&0.0000&0.0000\\ 1&0.6667&0.5858&0.0809\\ 2&2.1370&2.0000&0.1370\\ 3&5.3441&5.1716&0.1725\\ 4&12.1957&12.0000&0.1957\\ 5&26.5548&26.3431&0.2116\\ 6&56.2228&56.0000&0.2228\\ 7&116.9171&116.6863&0.2308\\ 8&240.2364&240.0000&0.2364\\ 9&489.6129&489.3726&0.2404\\ 10&992.2432&992.0000&0.2432\\ 11&2002.9903&2002.7452&0.2452\\ 12&4032.2466&4032.0000&0.2466\\ 13&8101.7379&8101.4903&0.2476 \end{array} $$
Aquí está el código para producir esos números. Podría ser interesante para encontrar el siguiente término en la expansión analíticamente.
Gracias Joriki para este importante puntero corregir mi error. De hecho, el número de gráficos en $\mathcal{G}$ está dado por $$ n! [z^n] G(z, 1) .$$ Pero tenemos $$[z^n] \exp \left( \frac{z}{1-z} \right) = [z^n] \sum_{m\ge 0} \frac{1}{m.} \left( \frac{z}{1-z} \right)^m$$ que es $$ \sum_{m=1}^n \frac{1}{m.} [z^n] \left( \frac{z}{1-z} \right)^m = \sum_{m=1}^n \frac{1}{m.} [z^{n-m}] \left( \frac{1}{1-z} \right)^m = \sum_{m=1}^n \frac{1}{m.} \binom{n-m+m-1}{m-1} = \sum_{m=1}^n \frac{1}{m.} \binom{n-1}{m-1}.$$ De ello se deduce que el valor de $\epsilon_n$ está dado por $$\epsilon_n = \frac{n! \sum_{m=0}^{n-2} \frac{1}{m.} \binom{n-1}{m+1}}{n! \sum_{m=1}^n \frac{1}{m.} \binom{n-1}{m-1}} = \frac{\sum_{m=0}^{n-2} \frac{1}{m.} \binom{n-1}{m+1}}{\sum_{m=1}^n \frac{1}{m.} \binom{n-1}{m-1}} = \frac{\sum_{m=2}^n \frac{1}{(m-2)!} \binom{n-1}{m-1}}{\sum_{m=1}^n \frac{1}{m.} \binom{n-1}{m-1}}.$$ Parecería que esto implica $$\epsilon_n \sim n,$$ answering my original question. This even includes the coefficient on $n$ and it means that small components having $o(n)$ bordes no contribuyen en el límite. Voy a esperar un par de horas para darle una oportunidad de demostrar que esta última asintótica resultado, lo que no parece tan difícil.
El siguiente bastante ingenuo programa hace posible calcular el $\epsilon_n$ $n$ tan grande como $300000.$ El valor que se obtiene para el término constante de la expansión de la es $0.2496.$ Esto sugeriría la conjetura de que $$\epsilon_n \sim n - \sqrt{n} + \frac{1}{4}.$$
El código de la siguiente manera.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
long double plazo(int n, int m)
{
long double v = (long double)1;
mientras(m>1){
v *= (long double)((n-1)-(m-2));
v /= (long double)(m-1);
v /= (long double)(m);
m--;
}
return v;
}
int main(int argc, char **argv)
{
int n;
if(argc!=2 || sscanf(argv[1], "%d", &n)!=1 || n<1){
fprintf(stderr, "esperando un entero positivo\n");
exit(-1);
}
long double p = 0, q = 1;
int m;
para(m=2; m<=n; m++){
si(m%(n/10)==0) printf("%d%%\n", m*100/n);
long double t = plazo(n, m);
p += t*(long double)(m)*(long double)(m-1);
q += t;
}
long double eps = p/q;
printf("%.18Le %.18Le %.18Le\n", p, q,
eps-((long double)n-sqrtl((long double)n)));
exit(0);
}
El siguiente programa puede ser utilizado para calcular el $E[X(X-1)]$ a partir de la forma cerrada como un cociente de sumas. Parecería apoyar la conjetura de que $$ E[X(X-1)] \sim n^2 - 2 n^{3/2} + \frac{1}{2} n.$$
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
long double plazo(int n, int m)
{
long double v = (long double)1;
mientras(m>1){
v *= (long double)((n-1)-(m-2));
v /= (long double)(m-1);
v /= (long double)(m);
m--;
}
return v;
}
int main(int argc, char **argv)
{
int n;
if(argc!=2 || sscanf(argv[1], "%d", &n)!=1 || n<1){
fprintf(stderr, "esperando un entero positivo\n");
exit(-1);
}
long double p = 0, q = 0, r = 0;
int m;
para(m=1; m<=n; m++){
si(m%(n/10)==0) printf("%d%%\n", m*100/n);
long double t = plazo(n, m);
p += t*
(long double)(m)*
(long double)(m-1)*
(long double)(m-2)*
(long double)(m-3);
q += 2*t*
(long double)(m)*
(long double)(m-1)*
(long double)(m-2);
r += t;
}
long double eps = (p+q)/r;
printf("%.18Le %.18Le %.18Le\n", p, q,
(eps-(((long double)n)*((long double)n)
-(long double)2*
(long double)n*sqrtl((long double)n)))/
(long double)n);
exit(0);
}
