Si se forma una palabra con 15 cartas al azar usando las letras P, T, I, N,
hallar la probabilidad que no contiene la secuencia de TINTE.
(Acabo de hacer este problema.)
Respuestas
¿Demasiados anuncios?
EDIT: yo creo que esta respuesta es una ligera simplificación de la primera respuesta, donde usamos el hecho de que no necesitamos para seguir la pista de las palabras que contienen el TINTE cuando estamos tratando de ver cómo un $n+1$letras de la palabra que no contiene el TINTE puede ser obtenida a partir de un $n$-carta de uno.
Deje $a_n$ el número de $n$letra no contiene TINTE y terminando con ESTAÑO. Deje $b_n$ el número de $n$letra no contiene TINTE y terminando con TI. Y deje $c_n$ el número de $n$letra no contiene TINTE terminando con T. Finalmente dejó $d_n$ el número de $n$letra no contiene el MATIZ de que no caiga en ninguna de las categorías anteriores. Entonces tenemos \begin{align*} a_n = b_{n-1}, \quad b_n = c_{n-1}, \quad c_n = b_{n-1} + c_{n-1} + d_{n-1} \end{align*} y \begin{align*} d_n = 3a_{n-1} + 2b_{n-1} + 2c_{n-1} + 3d_{n-1} \end{align*} Así que si tenemos el vector columna $(a_{n-1},b_{n-1},c_{n-1},d_{n-1})^T$, el vector columna de los nuevos hombres $(a_n,b_n,c_n,d_n)^T$ se obtiene multiplicando por la izquierda por la matriz \begin{align*} A= \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 3 & 2 & 2 & 3 \end{pmatrix} \end{align*} Para $n=1$, el vector es $v=(0,0,1,3)^T$. Así que tenemos que calcular la suma de las entradas de $A^{14}v$, lo que nos da la respuesta de otros, ya han dado en los comentarios.
rjb
Puntos
5050
Dejar el nombre de nuestro alfabeto $A := \{P, T, I, N\}$.
Veamos el conjunto de $L := A^*$ de todas las posibles palabras utilizando las letras $P, T, I, N$. En primer lugar, vamos a diseccionar en cinco sets:
$$L_5 := \{w \in L : TINT\text{ is a substring of }w\},$$ $$L_4 := \{w \in L \smallsetminus L_5 : w\text{ ends with } TIN\},$$ $$L_3 := \{w \in L \smallsetminus L_5 : w\text{ ends with } TI\},$$ $$L_2 := \{w \in L \smallsetminus L_5 : w\text{ ends with } T\},$$ $$L_1 := L \setminus (L_1 \cup L_2 \cup L_3 \cup L_4).$$
Ejemplo: La palabra $PTTPTIN$$L_4$.
La cosa agradable sobre nuestros cinco conjuntos de $L_1, \ldots, L_5$ es que para cualquier $a \in A$, $w \in L_i$, la clase $L_j \ni wa$ está totalmente determinado por $i$$a$. Por ejemplo: Si $w \in L_3$, $wN$ es siempre en $L_4$.
Damos a cada estado un estado correspondiente vector de $$s_1=\begin{pmatrix}1\\ 0 \\0 \\0 \\0\end{pmatrix}, s_2=\begin{pmatrix}0\\ 1 \\0 \\0 \\0\end{pmatrix}, s_3=\begin{pmatrix}0\\ 0 \\1 \\0 \\0\end{pmatrix}, s_4=\begin{pmatrix}0\\ 0 \\0 \\1 \\0\end{pmatrix}, s_5=\begin{pmatrix}0\\ 0 \\0 \\0 \\1\end{pmatrix}$$
y denotan por $s(w)$ el vector de estado del estado $w$. Por ejemplo,$s(TPTI) = s_3$.
Supongamos ahora que tenemos una palabra al azar $W$$L$. Podemos describir el estado esperado de $W$$S(W) := \mathbb{E}(s(W))$, que es una combinación convexa de los vectores de estado, un vector cuyas $i$-ésima denota la probabilidad de $W$$L_i$. Ahora supongamos $l$ es una carta al azar independiente de $W$, de manera uniforme elegido de $A$.
A continuación,$S(Wl) = B \cdot S(W)$, donde
$$B ~:=~ \frac{1}{4}\begin{pmatrix}3 & 2 & 2 & 3 & \\ 1 & 1 & 1 & & \\ & 1 & & & \\ & & 1 & & \\ & & & 1 & 4\end{pmatrix}$$
Supongamos que usted ha $w \in L_3$, $wl$ $L_2$ con una probabilidad de $\frac{1}{4}$ (en el caso de $l = T$), en $L_4$ con una probabilidad de $\frac{1}{4}$ (en el caso de $l = N$) y en $L_1$ con una probabilidad de $\frac{1}{2}$ (en el caso de $l = I$ o $l = P$). Esto corresponde a la tercera columna de $B$. El resto de las columnas se construyen de la misma manera.
Lo que hemos hecho aquí se construye la matriz de transición de una cadena de Markov con $5$ estados. Cada entrada de $b_{ji}$ $B$ corresponde a la probabilidad de ir del estado $L_i$ estado $L_j$ después de la adición de una carta al azar.
Ahora consideremos lo que sucede cuando agregamos 15 letras aleatorias $l_1, \ldots, l_{15}$ a la palabra vacía $\epsilon$. Sabemos que $S(\epsilon) = s_1$, y ahora sabemos que $S(\epsilon l_1\cdots l_{15}) = B^{15}S(\epsilon) = B^{15}s_1$. Ahora la probabilidad de que $\epsilon l_1\cdots l_{15}$ contiene $TINT$ es exactamente la quinta entrada de $S(\epsilon l_1\cdots l_{15})$,$s_5^\top B^{15}s_1$, que es la parte inferior izquierda de la entrada de $B^{15}$. La parte inferior izquierda de la entrada corresponde a la probabilidad de ir del estado $L_1$ estado $L_5$ después de la adición de 15 letras al azar.
La probabilidad de que un elegido al azar de 15 letras de la palabra $W \in A^{15}$ contiene la subcadena $TINT$ es exactamente la parte inferior izquierda de la entrada de $B^{15}$.
Wolfram Alpha dice que este número es exactamente
$$\frac{49167017}{1073741824}.$$
La probabilidad de que $W$ ¿ no contener $TINT$ es por lo tanto
$$ 1 - \frac{49167017}{1073741824} = \frac{1024574807}{1073741824}.$$
barak manos
Puntos
17078
El siguiente script de Python confirma la respuesta dada por @McFry:
LENGTH = 15
LETTERS = 'PTIN'
SEQUENCE = 'TINT'
def func(word):
if len(word) < LENGTH:
return sum(func(word+letter) for letter in LETTERS)
else:
return SEQUENCE not in word
count = func('')
total = len(LETTERS)**LENGTH
print '{}/{}={}%'.format(count,total,100.0*count/total)
El resultado es $1024574807/1073741824\approx95.42\%$.
JiminyCricket
Puntos
143
Si "TINTE" se produce en posiciones particulares del #% de #% % y $k\gt0$ solapamientos entre ellos, hay maneras de $j$ elegir los solapes, $\binom{k-1}j$ formas de elegir las posiciones y $\binom{15-3k}{15-4k+j}$ formas de elegir las letras restantes. Por lo tanto por la inclusión-exclusión la probabilidad deseada es
$$ 1 + \sum_ {k = 1} ^ 4(-1) ^ k\sum_ {j = 0} ^ {k-1} \binom {k-1} j\binom {15-3 k} {15-4 k + j} 4 ^ {j-4_k} = \frac {1024574807} {1073741824} \approx95.42\%\;. $$
