9 votos

¿Cuánto falta para que una palabra aleatoria con letras "A", "B", "C" termine en el patrón "ABC"?

Digamos que tengo palabra construido a partir de letras al azar, A By C con $\mathbf{P}(A) = \mathbf{P}(B) = \mathbf{P}(C) = \frac{1}{3}$. Voy a hacer un ensayo aleatorio y registro de las cartas que tengo. El experimento se detiene la primera vez que deletrear la palabra ABC. Deje $N$ el número de ensayos hasta que yo hago de la palabra ABC de las cartas.

Aquí están algunas juicio palabras:

BBBBACCCCBABAABBBBCBCCBBBCACBCAACBABC
BBACCCCACABABC
CBBCCCABBABC
BABBBCAAAABC
CBBBCCBCCABABC
CCBCBBABC
ACCACCCCBCBBBCBACCBBAABBABBACCCBCBAABC
ABAAABBBABC
ABABC
BBCACAACCACCAABAAABBCABBBBACABACBACBAABACCCBCBCCCBCCCBAAAABC

Estoy pidiendo a la duración prevista de esta palabra. Y la varianza.

  • $\mathbb{E}[N]$ expectativa
  • $\mathbb{E}[N^2] - \mathbb{E}[N]^2$ varianza

Suena más como un libro de texto:

Nuestra variable aleatoria es $X \in \{ A,B,C\}$ donde cada letra aparece con igual probabilidad. Vamos a examinar la secuencia de $(X_1, X_2, X_3, \dots , X_n)$ donde $X_i$ son variables aleatorias iid con probabilidad, el mismo que $X$. Nuestro proceso se detiene en el tiempo $t = N$ cuando $(X_{N-2}, X_{N-1}, X_N) = (A,B,C)$. ¿Cuál es el valor esperado de $N$ ?

9voto

kg. Puntos 404

La expectativa es bastante fácil (Varianza parece más trabajo).

Tenemos cuatro estados, de acuerdo a la cantidad de $ABC$ es completa. Así, los estados se $\emptyset, A, AB, ABC$. Por supuesto, de Inicio es $\emptyset$ y el Final es $ABC$. Para un estado de $\mathscr S$ denotamos por a$E[\mathscr S]$ el número esperado de pasos, dado que a partir de $\mathscr S$. La respuesta que queremos es $E[\emptyset]$.

Tomamos nota de que $$E[AB]=1\times \frac 13+(E[A]+1)\times \frac 13+(E[\emptyset]+1)\times \frac 13$$

$$E[A]=(E[AB]+1)\times \frac 13+ (E[A]+1)\times \frac 13+(E[\emptyset]+1)\times \frac 13$$

$$E[\emptyset]=(E[A]+1)\times \frac 13+(E[\emptyset]+1)\times \frac 23$$

La solución de este sistema lineal (y confiando en que no hay aritmética que se han cometido errores) se obtiene: $$E[AB]=18\quad E[A]=24\quad \boxed {E[\emptyset]=27}$$

4voto

A. Pongrácz Puntos 301

Una vez que usted ve que esto es una cadena de Markov (como correctamente etiquetados) el problema es fácil de solucionar con el primer paso del análisis. Estados: $0, A, AB, ABC$, lo que significa que el final de la palabra que ya no es útil (equivalente a la palabra vacía), termina con $A$, termina con $AB$ y termina con $ABC$, respectivamente. El estado $ABC$ es el único estado de absorción. Transiciones:

$0\rightarrow 0$ si usted consigue $B$ o $C$, por lo que la probabilidad de transición es $2/3$.

$0\rightarrow A$ si usted consigue $A$, por lo que la probabilidad de transición es $1/3$.

$A\rightarrow 0$ si usted consigue $C$, por lo que la probabilidad de transición es $1/3$.

$A\rightarrow A$ si usted consigue $A$, por lo que la probabilidad de transición es $1/3$.

$A\rightarrow AB$ si usted consigue $B$, por lo que la probabilidad de transición es $1/3$.

$AB\rightarrow 0$ si usted consigue $B$, por lo que la probabilidad de transición es $1/3$.

$AB\rightarrow A$ si usted consigue $A$, por lo que la probabilidad de transición es $1/3$.

$AB\rightarrow ABC$ si usted consigue $C$, por lo que la probabilidad de transición es $1/3$.

Por lo que la matriz de transición es

$\begin{pmatrix} 2/3 & 1/3 & 0 & 0\\ 1/3 & 1/3 & 1/3 & 0\\ 1/3 & 1/3 & 0 & 1/3\\ 0 & 0 & 0 & 1\\ \end{pmatrix}$

Se puede terminar de aquí? Hay una fórmula que calcula el número esperado de pasos de cada estado transitorio, dada la matriz de transición.

3voto

A. Pongrácz Puntos 301

Para la varianza, con un paso de análisis no es suficiente. Básicamente, usted necesita saber la probabilidad de $p_n$ que hacer exactamente $n$ pasos a partir de la palabra vacía. Es más fácil hacer por encontrar el vector $v_n$ con longitud 4, cuyas $i$-ésima representa la probabilidad de que después de la $n$ pasos que están en estado de $i$. Si usted tenía una $ABC$ en algún lugar, te quedas en el cuarto estado (ABC) para siempre.

A continuación, $v_0= (1, 0, 0, 0)$, e $v_{n+1}=v_n\cdot P$, donde $P$ es tmatrix en mi primera respuesta:

$P= \begin{pmatrix} 2/3 & 1/3 & 0 & 0\\ 1/3 & 1/3 & 1/3 & 0\\ 1/3 & 1/3 & 0 & 1/3\\ 0 & 0 & 0 & 1\\ \end{pmatrix}$

Por lo $v_n=v_0\cdot P^n$. Usted puede calcular este estándar algebraicas lineales técnicas: calcular la normal de Jordan $J=S^{-1}AS$ formulario de $P$ (junto con $S$), luego la exponenciación es fácil, y $P^n= SJ^nS^{-1}$.

Una vez que usted tiene una forma cerrada para $v_n$, agregar las tres primeras coordenadas: que es la probabilidad de que la longitud de la palabra es, al menos, $n$. Lo que denota el por $q_n$ (será una combinación lineal de series geométricas, bueno, casi...), tenemos $p_n= q_n-q_{n+1}$ (siendo una combinación lineal de series geométricas, si tienes suerte). A continuación, puede calcular la varianza de la definición, pero te sugiero que uses el momento de generación de función, en lugar. O, simplemente, utilizar las fórmulas aquí: https://en.wikipedia.org/wiki/Absorbing_Markov_chain#Variance_on_number_of_visits

2voto

dnqxt Puntos 71

Aquí hay una simulación rápida en R que resulta en la media de la distribución de longitudes de aproximadamente 27.1 (varianza 591) y confirma el resultado de @lulu.

 mc = function( state ){

  if( state == '0' ){
      if( runif(1,0,1) < 1/3 ) { return('A') } else{ return('0')}
  }

  if( state == 'A' ){
      u = runif(1,0,1)
      if( u < 1/3 ) { return('A') }
      if( u < 2/3 ) { return( 'AB') } else { return('0') }
  }

  if( state == 'AB' ){
      u = runif(1,0,1)
      if( u < 1/3 ) { return('A') }
      if( u < 2/3 ) { return('0') } else { return('ABC') }
  }
}

state = '0'; nsim = 1000000;
n.abc = 0; d.abc = NULL

for( i in 1:nsim){

   state = mc( state )
   n.abc = n.abc + 1

   if( state == 'ABC' ){
      d.abc = append( d.abc, n.abc )
      n.abc = 0
      state = '0'
   }
}

d.abc = unlist( d.abc )
print( mean( d.abc ))
hist( d.abc)
 

2voto

palehorse Puntos 8268

En lugar de utilizar el aparato de las cadenas de Markov, el resultado de la media puede ser de inmediato obtenidos mediante Kac del teorema acerca de los horarios de vuelta (un resultado importante que se utiliza a menudo, por ejemplo, para demostrar la asympotic de optimalidad de Lempel-Ziv compresión de los algoritmos - véase, por ejemplo de la Cubierta Y Thomas, 13.5).

En este caso, la probabilidad de éxito de la ergodic $0$-$1$ proceso $p=(1/3)^3=1/27$, por lo tanto la media de tiempo de retorno es $\langle T \rangle = 1/p=27$

El cálculo de la varianza parece ser mucho más difícil. Algunos trabajan en "Variaciones sobre un Tema de Mark Kac" (P. W. Kasteleyn , Revista de la Física Estadística, Vol. 46, Núms. 5/6, 1987).

i-Ciencias.com

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.

Powered by:

X