La probabilidad de ciclos de longitud en la mayoría de las $g$ aleatoria gráfico

Question

Estoy trabajando en una tarea problema. La esencia de esto es como sigue:

Corregir algunos entero $g$, una probabilidad de $p\in [0,1]$, y una función lineal $f(n)$ donde $n$ es el número de vértices de un azar gráfico. Si la probabilidad de tener una ventaja en una gráfica es $p$, ¿cuál es la probabilidad de que el número de ciclos de longitud en la mayoría de las $g$ aleatoria gráfico con $n$ vértices superará $f(n)$?

Me gustaría sólo algunas sugerencias en la dirección de la solución. La pregunta ha $p$ como una función de la $n$$g$, y pide que el resultado en el límite de $n\to\infty$, pero me gustaría entender la pregunta en general.

Answer 1

Dudo que encontrará una forma cerrada para el caso finito; el cálculo es complicado debido a las correlaciones entre los diferentes ciclos; creo que el problema que se planteó para el caso infinito, por una razón :-)

Para el caso infinito, se puede calcular el número esperado de ciclos, cuyo comportamiento para $n\to\infty$ dependerá de cómo se $p$ depende de $n$. También se puede calcular la varianza del número de ciclos como el valor esperado del cuadrado menos el cuadrado del valor esperado. A continuación, puede utilizar la desigualdad de Chebyshev para mostrar que la probabilidad de que el número de desviarse considerablemente de la cantidad esperada va a$0$$n\to\infty$, con lo que se puede comparar a$f(n)$, con el número esperado.