Expected value of a run of a random bitstring

Question

A maximal run of ones in a bitstring is a maximal consecutive substring of ones. For example, the bitstring $1000111110100111$ has four maximal runs of ones: $1, 11111, 1,$ and $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)

What I have done so far is let $S = (s_1, s_2, \ldots s_n)$ to be sequence of random bitstrings of length $n$ and defined an indicator random variable:

$X_i = 1$ if a subsequence of S is a run of ones and $X_i = 0$ otherwise

but I don't know how to continue from here. I would like to get some help of how I should go from there or any ideas on how to solve the question.

Thanks.

Answer 1

I do not know if it is what was intended, but you could have your indicator registering if the $n-1^\text{th}$ bit is $0$ and the $n^\text{th}$ bit is $1$.

You may need to take the unseen bit before the first to be $0$.

Then use linearity of expectation.

Answer 2

Let $p$ be the probability that $s_i = 1$. Let $X_n$ be the number of maximal runs of ones in a sequence of $n$ bitstrings. Compare $X_n$ with $X_{n-1}$. Imagine the last bit is hidden. The only way that $X_n$ will increase is that if the $n-1$ bit is 0 and the $n$ bit turns out to be 1. So, given $X_{n-1}$, $X_n = X_{n-1} + 1$ with probability $p(1-p)$, otherwise $X_n = X_{n-1}$ with probability $p + (1-p)^2$. You can derive an iterative formula for the expectation of $X_n$ given the expectation of $X_{n-1}$.

Answer 3

Let $P_i=1$ if $i$-th symbol in bitstring starts a maximal run of ones and $P_i=0$ otherwise (for example, for $1000111110100111$ $P_i=1$ for $i=1,5,11,14$ and $P_i=0$ for any other $i$).

Note that $X=\sum_{i=1}^nP_i$.

Then use linearity of expectation:

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

Because $P_i$ is indicator random variable, $E(P_i)=P(P_i=1)$.

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

For other $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)$

Answer 4

A run in a binary string $s\in\{0,1\}^n$ is a maximal consecutive substring of ones in $s$. Denote by $E_0(n)$ the expected number of runs in a random string of length $n$ ending in $0$, by $E_1(n)$ the expected number of runs in a random string of length $n$ ending in $1$, and let $$E(n):={1\over2}\bigl(E_0(n)+E_1(n)\bigr)$$ be the number we are after. Conditioning on the value of $s_n$ one has $$E(n+1)={1\over2}\left(E_0(n)+{1\over2}\right)+{1\over2}E_1(n)=E(n)+{1\over4}\ .$$ Since $E(1)={1\over2}$ we obtain $$E(n)={n+1\over4}\qquad(n\geq1)\ .$$