Número esperado de virus de las células

Question

He encontrado esta pregunta en un pasado programación de la asignación de un curso que estoy leyendo actualmente.

Su declaración se parece a esto :

Un reciente accidente de laboratorio dio como resultado la creación de un extremadamente peligroso virus que se replica tan rápidamente que es difícil predecir exactamente cómo muchas de las células que contienen después de un período de tiempo dado. Sin embargo, un técnico de laboratorio hizo las siguientes observaciones acerca de su crecimiento por milisegundo:

$\bullet$ La probabilidad de que el número de virus de las células que crecen en un factor de $a$ $0.5$

$\bullet$ La probabilidad de que el número de virus de las células que crecen en un factor de $b$ $0.5$

Dados a, b, y sabiendo que inicialmente sólo hay una sola celda de virus, calcular el número esperado de virus de las células después de la $t$ milisegundos. Como este número puede ser muy grande, imprimir su respuesta modulo $(10^9 + 7)$ .

Como yo no tengo ninguna formación previa en la probabilidad o de la combinatoria, este problema no tiene mucho sentido para mí . He hecho un poco de investigación acerca de los valores esperados en el contexto de la probabilidad, pero no puedo ver cómo un modelo de los datos que me dan. Tal vez hay algo muy obvio que me falta, pero yo no soy capaz de ver en el momento.

¿Cómo se podría solucionar esto?

Answer 1

Este fue un problema interesante, pero creo que tengo una solución:

• En el momento $t=0$ es sin duda simplemente uno de los virus de la célula, nada que discutir aquí.
• En el momento $t=1$ hay $a$ células con probabilidad 1/2, y $b$ células con prob. 1/2. El promedio es de, a continuación,$(a+b)/2$.
• En el momento $t=2$ hay $aa$ células con prob. 1/4, $bb$ células con prob. 1/4 y $ab=ba$ células con prob. $1/4+1/4=1/2$. Promedio: (aa+bb+2ab)/4
• Et cetera...

¿Cuál es el patrón? Para generar todas las posibilidades de la próxima generación de células, tomamos las cadenas posibles de a y b de la anterior gen en dos copias, concatenar una $a$ a un conjunto de copias y un $b$ a los demás. Multiplicamos la probabilidad de cada edad cadena de 1/2 para mantener la expectativa en la verificación, y añadir cosas.

Pero no tenemos que generar real cadenas!! (Esta es buena, evita exponencial blow-up). Todo lo que tenemos que hacer, es tomar el promedio de la generación anterior, dividir por 2, y se multiplica por $(a+b)$, y somos buenos para ir.

Así que...acabamos de calcular $(\frac{a+b}{2})^{t} \mod (10^9+7)$, y esto es eficazmente (como $O(\log t)$ tiempo) el uso repetido de cuadratura. Sólo tenga cuidado de desbordamiento de enteros, y ya está :)

(Siéntase libre de pedir más detalles si es necesario, estoy escribiendo esto en el medio de la noche donde yo vivo...el de arriba puede no ser tan claramente escrito como me gustaría que fuese)

Answer 2

Deje $X$ ser el número de veces que el "virus de la célula" de la población creció por un factor $a$ $t$ milisegundos. Así, la población de 1, después de $X$ crecimientos de factor de $a$ $t-X$ crecimientos de factor de $b$ será: $$\begin{align}N_t =&~ a^X b^{t-X} \\ = &~ b^t (a/b)^{X} \end{align}$$

Ahora, como $X$ es es el número de "éxitos" en una serie de $t$ ensayos de Bernoulli independientes con tasa de éxito $0.5$, tendrá una Distribución Binomial. $X\sim\mathcal {Bin}(t, 0.5)$

Ahora se puede encontrar esta? $~\mathsf E(N_t)$

---

Sugerencia: Una útil tema de investigación es "el momento de generación de funciones".

Si $X\sim \mathcal{Bin}(n,p)$$\mathsf E(\mathsf e^{sX}) = (1-p+p\mathsf e^{s})^n$. Este es el momento de generación de la función de una Distribución Binomial.