Probability

Question

Let there be a string of 10 bits generated uniformly at random (each bit could be 0 or 1 with equal probability). What is the expected number of appearances of a substring 011 in this string?

Comments

Is the answer 1?

Answer 1

In cases where calculating expected value by definition is not easy, you can use indicator random variables. You can study this technique from here https://mikespivey.wordpress.com/2011/12/01/indicator-variables/

Let us have an indicator random variable $X_i$, such that $X_i = 1$ if $011$ occurs at $ith$ position in the random binary string and $X_i = 0$ otherwise. Then $E[Xi] = P(Xi) = 1/8$ (There are 8 binary strings of length 3. Favorable case is string $011$) Now we want to calculate expected value of number of appearances of $011$, call this $E[Z]$. $E[Z] = E[X1] + E[X2] + E[X3] + ... + E[X8]$ (011 can not start from index 9 or 10 in a string of length 10). So $E[Z] = 8 * 1/8 = 1$

Comments

very nice explanation... thanks..