Valor esperado de una tirada de una cadena de bits aleatoria

Question

Una serie máxima de unos en una cadena de bits es una subcadena consecutiva máxima de unos. Por ejemplo, la cadena de bits $1000111110100111$ tiene cuatro series máximas de unos: $1, 11111, 1,$ y $111$ .

Let n>=1 be an integer and consider a random bitstring of length n. 
Determine the random variable X to be the number of maximal runs of ones 
in this bitstring.

Determine the expected value E(X) of X. (Hint: Use indicator random variables)

Lo que he hecho hasta ahora es dejar que $S = (s_1, s_2, \ldots s_n)$ como una secuencia de cadenas de bits aleatorias de longitud $n$ y definió una variable aleatoria indicadora:

$X_i = 1$ si una subsecuencia de S es una serie de unos y $X_i = 0$ de lo contrario

pero no sé cómo continuar desde aquí. Me gustaría recibir alguna ayuda de cómo debo seguir a partir de aquí o alguna idea de cómo resolver la cuestión.

Gracias.

Answer 1

A ejecute en una cadena binaria $s\in\{0,1\}^n$ es una subcadena consecutiva máxima de unos en $s$ . Denotemos por $E_0(n)$ el número esperado de ejecuciones en una cadena aleatoria de longitud $n$ terminando en $0$ por $E_1(n)$ el número esperado de ejecuciones en una cadena aleatoria de longitud $n$ terminando en $1$ y que $$E(n):={1\over2}\bigl(E_0(n)+E_1(n)\bigr)$$ sea el número que buscamos. Condicionando el valor de $s_n$ uno tiene $$E(n+1)={1\over2}\left(E_0(n)+{1\over2}\right)+{1\over2}E_1(n)=E(n)+{1\over4}\ .$$ Desde $E(1)={1\over2}$ obtenemos $$E(n)={n+1\over4}\qquad(n\geq1)\ .$$

Answer 2

No sé si es lo que se pretendía, pero podría tener su indicador de registro si el $n-1^\text{th}$ bit es $0$ y el $n^\text{th}$ bit es $1$ .

Es posible que tenga que tomar el bit no visto antes de la primera para ser $0$ .

Entonces usa la linealidad de la expectativa.

Answer 3

Sea $p$ sea la probabilidad de que $s_i = 1$ . Sea $X_n$ es el número de series máximas de unos en una secuencia de $n$ cadenas de bits. Compare $X_n$ con $X_{n-1}$ . Imagina que la última parte está oculta. La única manera de que $X_n$ aumentará es que si el $n-1$ es 0 y el $n$ resulta ser 1. Entonces, dado $X_{n-1}$ , $X_n = X_{n-1} + 1$ con probabilidad $p(1-p)$ de lo contrario $X_n = X_{n-1}$ con probabilidad $p + (1-p)^2$ . Se puede derivar una fórmula iterativa para la expectativa de $X_n$ dada la expectativa de $X_{n-1}$ .

Answer 4

Sea $P_i=1$ si $i$ -ésimo símbolo de la cadena de bits inicia una serie máxima de unos y $P_i=0$ en caso contrario (por ejemplo, para $1000111110100111$ $P_i=1$ para $i=1,5,11,14$ y $P_i=0$ para cualquier otro $i$ ).

Tenga en cuenta que $X=\sum_{i=1}^nP_i$ .

Entonces usa la linealidad de la expectativa:

$E(X)=E\left(\sum_{i=1}^nP_i\right)=\sum_{i=1}^nE(P_i)$

Porque $P_i$ es una variable aleatoria indicadora, $E(P_i)=P(P_i=1)$ .

Para $i=1$ $P(P_i=1)=P(i\text{-th symbol is 1})=0.5$

Para otros $i$ 's $P(P_i=1)=P(i\text{-th symbol is 1 AND }(i-1)\text{-th symbol is 0})=0.5\cdot0.5=0.25$

$E(X)=\sum_{i=1}^nE(P_i)=E(P_1)+\sum_{i=2}^nE(P_i)=0.5+\sum_{i=2}^n0.25=0.5+0.25(n-1)$

$E(X)=0.25(n+1)$