Cuente la probabilidad de una cadena aleatoria de$20$ bit

Question

Considerar binario palabras de longitud $20$. Están formados de tal manera que un $1$ se produce con una probabilidad de $0.6$$0$, con una probabilidad de $0.4$ (lugares diferentes son independientes). También, un "run" es una máxima de la subcadena de sólo o sólo ceros; por ejemplo, $00110001101011111111$ $8$ pistas.

Creo que esta pregunta debe ser resuelto usando la Linealidad de la Expectativa de la Matemática Discreta II, pero es un poco difícil para mí para hacer las conexiones entre la probabilidad y el recuento de las teorías.

1) ¿Cuál es la probabilidad de que un azar cadena de bits de longitud $20$ comienza en un $0$, tiene exactamente $8$, y tiene exactamente $10$ carreras?

Me imagino que la probabilidad de "aleatorio cadena de bits de longitud $20$ comienza en un $0$, tiene exactamente $8$" es igual a $(0.6^8)\cdot(0.4^{11})$ ya que se inicia con $0$ y, a continuación, hay $19$ bits a la izquierda. Entonces quiero usar las estrellas y las barras de la teoría a contar el número de maneras en que podemos organizar $8$ queridos y $11$ ceros para hacer de él un "$10$ " de la cadena. Es como elegir a $4$ paredes de separar a $19$ ceros. Estoy atascado aquí porque no sé cómo hacer la conexión entre las carreras y la posibilidad de $o$'s y $1$s' ($0.4/0.6$).

2) ¿Cuál es la probabilidad de que un azar cadena de bits de longitud $20$ tiene exactamente $10$ carreras?

Misma idea aquí, el uso de las estrellas y las barras de la teoría a separar $4-16$ $1$'s o $0$'s el uso de $4-16$ $0$'s o $1$'s. Ah, yo no sé cómo a partir de aquí...

Answer 1

Me imagino que la probabilidad de a random bit string of length 20 starts in a 0, has exactly 8 ones es igual a (0.6^8)*(0.4^11) , ya que comienza con 0 y, a continuación, hay 19 bits a la izquierda.

Eso no es cierto: que sería la probabilidad de obtener un específico de la cadena de bits con $8$ queridos y $11$ ceros, por ejemplo, la probabilidad de obtener los $1111111100000000000$ es la probabilidad de que has indicado. También, se puede olvidar que aunque queremos que el primer bit a ser un $0$, todavía tiene una cierta probabilidad de que ocurra.

En vez de eso, se puede señalar que hay $19 \choose 8$ cadenas de bits de longitud $19$ que puede tener éxito inicial $0$, y así la probabilidad de obtener un bitstring de longitud con 20 $8$ queridos y $12$ ceros que comienza con un cero:

$${19 \choose 8} \cdot 0.6^8 \cdot 0.4 ^ {12}$$

But yes, that number does not reflect the constraint that it should have exactly $10$ se ejecuta. De hecho, no está claro que el cálculo de esta probabilidad se le ayuda un montón.

En vez de eso, vamos a concentrarnos en las pistas. Usted escribe:

Quiero usar las estrellas y las barras de la teoría a contar el número de maneras en que podemos organizar 8 queridos y 11 ceros para hacer de él un 10 ejecución de la cadena. Es como elegir las 4 paredes de separar 19 ceros.

De cerca! No separe $19$ ceros ... sólo tienes $12$ ceros. Pero eso sí, con $10$, que se ejecuta a tener una vigencia de al final, y por lo que significa que, de hecho, ha $4$ carreras de la que necesita para separar el $12$ ceros. En términos de estrellas y barras: usted tiene $11$ brechas entre los ceros, y usted necesita recoger a $4$ de los que colocar sus carreras, lo que da un total de $11 \choose 4$ maneras de colocar las pistas de entre las pistas de ceros.

Sin embargo, mientras que la colocación de las pistas de los que determina las longitudes de las pistas de ceros, de las carreras de los mismos pueden ser de diferentes longitudes sin embargo, lo que resulta en diferentes cadenas de bits. Así, tenemos que averiguar ¿de cuántas maneras podemos crear $5$ pistas de los uso de $8$.

Bueno, de nuevo, podemos utilizar las estrellas y barras para esto. Esta vez, tenemos que poner $4$ bares en cualquiera de las $7$ huecos entre las $8$ oness, y así tenemos a $7 \choose 4$ formas de crear $5$ carreras de.

OK, por lo que el número total de bitstrings de longitud $20$ $8$ queridos y $12$ ceros que comienza con un cero, y que ha $10$ carreras:

$${11 \choose 4} \cdot {7 \choose 4}$$

Now, each of these occurs with a probability of $0.6^8 \cdot 0.4 ^ {12}$, and so the probability of getting one of these is:

$${11 \choose 4} \cdot {7 \choose 4} \cdot 0.6^8 \cdot 0.4 ^ {12}$$