Probabilidad exacta de gráfico al azar estar conectado

Question

El problema: estoy tratando de encontrar la probabilidad de que un azar grafo no dirigido estar conectado. Estoy utilizando el modelo de $G(n,p)$, donde hay en la mayoría de las $n(n-1) \over 2$ bordes (no auto-bucles o duplicar los bordes) y cada arista tiene una probabilidad de $p$ de los existentes. He encontrado una fórmula simple en línea donde $f(n)$ es la probabilidad de $G(n,p)$ está conectado. Pero al parecer es demasiado trivial para el escritor para explicar la fórmula (que se acaba de decir brevemente).

El deseado fórmula: $f(n) = 1-\sum\limits_{i=1}^{n-1}f(i){n-1 \choose i-1}(1-p)^{i(n-i)}$

Mi método es el siguiente: Considere la posibilidad de cualquier vértice $v$. Entonces hay una probabilidad de ${n-1 \choose i}p^i(1-p)^{n-1-i}$ que tendrá $i$ vecinos. Después de conectar $v$ estos $i$ vecinos, tenemos un contrato con ellos ($v$ y sus vecinos) en un único componente conectado, así que nos quedamos con el problema de la $n-i$ vértices (el componente conectado plus $n-i-1$ otros "normal" de los vértices.

Excepto que ahora la probabilidad de que el vértice que representa el componente conectado, estar conectado a cualquier otro vértice es $1-(1-p)^i$. Así que me introdujo otro parámetro $s$ en la fórmula, lo que nos da:

$g(n,s)=\sum\limits_{i=1}^{n-1}g(n-i,i){n-1 \choose i}q^i(1-q)^{n-1-i}$,

donde $q=1-(1-p)^s$. A continuación,$f(n)=g(n,1)$. Pero esto de ninguna manera es tan simple como la mencionada fórmula, ya que tiene un parámetro adicional...

Puede alguien explicar cómo la fórmula $f(n)$ se obtiene? Gracias!

Answer 1

Aquí es una manera de ver la fórmula. En primer lugar, tenga en cuenta que esto es suficiente para mostrar que $$ \sum_{i=1}^n {n-1 \elegir i-1} f(i) (1-p)^{i(n-i)} = 1, $$ desde ${n-1 \choose n-1}f(n)(1-p)^{n(n-n)}=f(n).$ Deje $v_1, v_2, \ldots, v_n$ $n$ vértices. Trivialmente, $$ 1= \sum_{i=1}^n P(v_1 \text{ es en un componente de tamaño }i). $$ Ahora vamos a considerar el porqué $$P(v_1 \text{ is in a component of size }i)={n-1\choose i-1}P(G(i,p) \text{ is connected}) (1-p)^{i(n-i)}.$$ Si $\mathcal{A}$ es el conjunto de todos los $i-1$ subconjuntos de a $\{v_2, v_3, \ldots, v_n\}$, luego \begin{align*} P(v_1 \text{ in comp of size }i)&=\sum_{A \in \mathcal{A}}P(\text{the comp of }v_1\text{ is }\{v_1\}\cup A)\\&=\sum_{A \in \mathcal{A}}P(\{v_1\}\cup A \text{ is conn'd})P(\text{no edge btwn }A\cup\{v_1\} \& \ (A\cup \{v_1\})^c). \end{align*} Esta última igualdad se debe al hecho de que los bordes dentro de los $\{v_1\}\cup A$ son independientes de los bordes de$A$$A^c$. Hay exactamente ${n-1 \choose i-1}$ elementos en $\mathcal{A}$. La probabilidad de que $\{v_1\}\cup A$ está conectado es igual a la probabilidad de que $G(1+|A|,p)$ está conectado, que es $f(i)$. Hay $i(n-i)$ faltan los bordes de$\{v_1\}\cup A$$(\{v_1\}\cup A)^c$.

Answer 2

Lo que pasa es que él/ella las sumas de todos los cortes de la gráfica. Para evitar el recuento de nada dos veces, se centran específicamente uno específicos vértice, llame a 1.

Si el gráfico está desconectado, no va a ser un componente conectado de algún tamaño, que contiene $1$.

Así que suma sobre el tamaño de este componente podría tener, y con multiplicidad $n-1 \choose i-1$ que es el número de formas de elegir los $1$'s de compañeros de los miembros del conjunto. Desea que el componente que contenga $1$ a estar conectados, de manera que multiplicar por $f(i)$, pero no hay nada en el componente puede estar conectado a algo que no existe, por lo que se multiplica por $p^(i*(n-i))$. El $(n-1)$ parte de la gráfica puede ser conectado o no, no importa.

Un ligero problema con la fórmula, que no es estable para las pequeñas $p$s y un gran $n$s.