7 votos

asymptotics de la previsión del número de bordes de un azar acíclicos dígrafo con indegree y outdegree a más de uno

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?

5voto

Marko Riedel Puntos 19255

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].$

4voto

JiminyCricket Puntos 143

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.

0voto

Marko Riedel Puntos 19255

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.

0voto

Marko Riedel Puntos 19255

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);
}

0voto

Marko Riedel Puntos 19255

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);
}

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X