Supongamos que tenemos un brote de zombies en un $k$ -Gráfico regular de orden $n$ . Hay $n_0$ inicialmente infectaron los nodos zombies, y cada turno, cada zombi infecta a sus vecinos con probabilidad $p$ . Deje que $z(t)$ denotan el número de nodos infectados a su vez $t$ .
¿Cuál es el número esperado de turnos hasta que los zombis hayan tomado el mundo? (es decir, hasta que $z(t)=n$ ?)
¿Es cierto que $z(t)\approx \dfrac{n}{1+(n-n_0)e^{-rt}}$ ? Si es así, ¿qué es $r$ ?
Una vez $k>2$ la respuesta a la #1 depende del gráfico; incluso en el caso límite determinante de $p=1$ y tomando $n_0=1$ , el tiempo esperado hasta la zombificación completa puede variar desde aproximadamente $C \log n$ (para un gráfico de expansión) a por lo menos $n/k$ (cuando $k$ es parejo, el conjunto de nodos es ${\bf Z}/n{\bf Z}$ y cada nodo está unido a su $k$ vecinos más cercanos).
En cuanto al #2: para grandes $t$ la probabilidad de que todavía haya una nodo no infectado $-$ que es esencialmente la diferencia entre $n$ y el valor esperado de $z(t)$ $-$ decae exponencialmente con $t$ . La base del exponente es $(1-p)^{b_{\min}}$ donde $b_{\min}$ es el número mínimo $b(S)$ de los bordes que conectan $S$ y su complemento, y $S$ abarca todos los conjuntos de nodos no vacíos que no están inicialmente infectados y podría convertirse en el conjunto de nodos aún no infectados en algún momento. (Esto supone, por supuesto, que $n_0<n$ Si $n_0=n$ entonces $z(t)=n$ para todos $n$ .) Normalmente $b=k$ realizado por conjuntos de monótonos; pero $b$ puede ser más pequeño si el gráfico tiene un cuello de botella, por ejemplo, para este gráfico cúbico
la base es $1-p$ siempre y cuando los zombis estuvieran inicialmente en sólo un lado del gráfico.
Para obtener el $(1-p)^{b_{\min}}$ la fórmula, consideran el brote como un sistema dinámico en el subconjuntos $S$ del conjunto $S_0$ de nodos inicialmente no infectados. En cada $t$ el estado del sistema es el conjunto de nodos aún no infectado por el tiempo $t$ . La probabilidad de que $S$ va a sí mismo es $(1-p)^{b(S)}$ , y de otra manera $S$ va a un subconjunto apropiado. Así, el El sistema dinámico es triangular (con respecto a la orden parcial de inclusión en el conjunto), con valores propios iguales a las entradas diagonales $(1-p)^{b(S)}$ . El valor propio dominante de $1$ se produce sólo para $S=\emptyset$ porque el gráfico está conectado. El siguiente valor propio es $(1-p)^{b_{\min}}$ y ocurre para todos los no vacíos $S$ minimizando $b(S)$ ; estos son usualmente, pero no siempre, los solteros de $S_0$ . (A veces no todos los $S \subset S_0$ puede ser alcanzado desde $S_0$ pero claramente a un solo tonelada es alcanzable a menos que $n_0=n$ .)
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.
0 votos
(1) Por lo tanto, la probabilidad de que un nodo con precisamente $r$ los turnos de los vecinos zombis es $1-(1-p)^r$ ? (2) ¿Son los iniciales $n_0$ infectados extraídos con probabilidad uniforme del conjunto de todos los $n_0$ -subconjuntos del conjunto de vértices?
0 votos
@blue Sí y sí.
0 votos
¿Puede alguien explicar el voto negativo? ¿Hay alguna aclaración que pueda añadir a esta pregunta?
1 votos
Dejemos que $G=(V,E)$ sea un gráfico y para $v\in V$ dejar $N(v)$ denotan su conjunto de nodos vecinos. Codificar una configuración zombi como una función $f:V\to\{$ zombi, vivo $\}$ . Dejemos que $f,g$ sean dos funciones de este tipo, con $f^{-1}($ zombi $)\subseteq g^{-1}($ zombi $)$ y definir $T= g^{-1}($ zombi $)\setminus f^{-1}($ zombi $)$ (la vuelta), y $S=g^{-1}($ vivo $)$ los sobrevivientes. La probabilidad $f$ transiciones a $g$ viene dada por $$\prod_{t\in T}\left(1-(1-p)^{|N(t)\cap f^{-1}({\rm zombie})|}\right)\prod_{s\in S}(1-p)^{|N(s)\cap f^{-1}({\rm zombie})|}.$$ Tal vez esto podría ser un punto de partida.
0 votos
La teoría de la probabilidad es una etiqueta inapropiada, creo.
1 votos
Si $k=2$ El gráfico es sólo un ciclo, por lo que el tiempo hasta la toma de posesión depende claramente de lo dispersos o agrupados que estén los $n_0$ los zombis lo son. Si $n_0=1$ Creo que tienes $z(t)\approx2pt$ .
0 votos
No he votado a la baja, pero supongo que a algunos les parecerá que he hecho mis deberes sin mostrar mi esfuerzo.
3 votos
@Aryabhata He dado con el problema. No me gustaría estar en la clase de cualquier sádico que asignara esto.
0 votos
@AlexanderGruber: :-). Sí, de hecho había adivinado que eras el autor (de ahí la exclamación al final de mi comentario anterior).
0 votos
@AlexanderGruber "esto es casi seguro cuando n es grande". ¿Significa esto que el gráfico se elige aleatoriamente del conjunto de conexiones
k-grafos regulares de ordenn?0 votos
@Teepeemm Me refería a que un azar $k$ -grafo regular en $n$ vértices está conectado con probabilidad $1$ como $n\to \infty$ .
0 votos
Esto no puede ser cierto para una familia arbitraria de grafos conectados por k, porque se puede imaginar que los vértices están dispuestos en un círculo y cada uno está conectado a k/2 vértices en el sentido de las agujas del reloj y en sentido contrario, y la tasa de expansión sería lineal dependiendo de k. Creo que necesitamos alguna condición como "G es un grafo expansivo". ( es.wikipedia.org/wiki/Expander_graph )
0 votos
@HoldenLee ¿Por qué eso significa que debe ser lineal?
0 votos
Quiero decir "como mucho lineal". En el tiempo t, el número de zombis sería como máximo $n_0(kt+1)$ el área plausible de infección del zombi, ya que se extiende desde el zombi inicial a un ritmo de $k/2$ en cada lado en cada paso de tiempo. Si los zombis están agrupados, esto sería del orden de $kt$ en su lugar, sin el $n_0$ . La clave es que si tienes un crecimiento logístico, tienes un crecimiento aproximadamente exponencial cerca del principio, y aquí no lo tenemos.
1 votos
"cada zombi infecta a sus vecinos con probabilidad $p$ " Infecta a todo el conjunto de vecinos con prob $p$ ? O cada vecino con prob $p$ ?
0 votos
@leonbloy Cada vecino.
0 votos
Otro PSQ aquí