La probabilidad de una larga ocurriendo simultáneamente en dos secuencias más largas

Question

Supongamos que tengo dos secuencias de caracteres de longitud L y M, respectivamente, con los personajes elegido yo.yo.d. a partir de un alfabeto de la a a la H, cada uno con una probabilidad de p=1/8. Quiero encontrar la probabilidad de que existe una larga de longitud N que se produce simultáneamente en la longitud L y M de las secuencias. En realidad no me importa si es que ocurre exactamente una vez, o al menos una vez en cada una de las secuencias. Lo que es más fácil va a hacer.

Por ejemplo, digamos que tenemos

(L) AABBCCDDEEFFGGHH

(M) GBCCDFH

Si N=4, voy a buscar a través de M y descubrir que BCCD también se produce en L (exactamente una vez en tanto en este caso). Quiero saber que tan probable es que se haya pasado (la búsqueda de cualquier longitud de cuatro secuencia, no específicamente BCCD).

En el caso en que M=N, pensé que la respuesta sería algo como

$$\left( \begin{array}{c} L-N+1\\ 1 \end{array} \right)*(p^N)^1*(1-p^N)^{L-N}$$

dando un límite inferior, pero de esto, no estoy terriblemente confianza. En cualquier caso, M probablemente será significativamente mayor que N, por lo que sería bueno para obtener una respuesta más precisa.

Answer 1

Deje $t$ ser la longitud de los más comunes de la subcadena. A continuación, $p_H = p(t \ge H)$, por lo que el problema es equivalente a encontrar la distribución de probabilidad de $t$ Este es un problema que ha recibido bastante trabajo, pero no son simples resultados exactos - incluso para el caso especial $L=M$. Por ejemplo, ver aquí y aquí.

Tal vez si usted está interesado en un determinado rango de $L,M$ podemos obtener una aproximación o algoritmo de...

Actualización : Este es un problema complejo, y yo no estoy muy familiarizado con él. Sólo algunas notas y un salvaje estimación:

Me permitirá cambiar la notación: vamos a $n$ $n$ ser las longitudes de las cadenas, $k$, la subcadena de longitud, $a$ el alfabeto de tamaño. Entonces, se espera que el número de subcadenas es fácilmente (el único resultado fácil aquí) obtenido como $\lambda_{n,m}^k = (n-k+1)(m-k+1) a^{-k}$

La equiparación de la que a 1, se puede obtener una rápida y estimación aproximada de la espera más larga de la subcadena comunes: $k_1 = \log_a [(n-k_1+1)(m-k_1+1) ] \approx \log_a (n \, m)$ (en lugar de la última aproximación también podemos usar la primera igualdad como un interactivas de solver). Por ejemplo, para $n=5000$, $m=100$, $k_1 = 6.284$ Esto da una idea aproximada: si $k$ supera considerablemente este valor, la probabilidad será cercano a cero, si $k<k_1$ la probabilidad de quicky a 1.

Una (muy natural) estimar, para $k$ no muy lejos de $k_1$, pueden ser obtenidos mediante asumiendo una distribución de Poisson con una media de $\lambda_{n,m}^k$, por lo que la probabilidad deseada es

$$p \approx 1- \exp\left( -\lambda_{n,m}^k \right) \approx 1 - \exp\left( n \, m \, a^{-k}\right)$$

Por ejemplo, para $n=5000$,$m=100$,$k=7$,$a=8$, llego $p\approx 0.178$ (simulación: $p\approx 0.2$)