2 votes 2 votes 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? Probability probability expectation + – Manu Madhavan asked Nov 17, 2016 Manu Madhavan 696 views answer comment Share Follow See 1 comment See all 1 1 comment reply air1 commented Nov 17, 2016 reply Follow Share Is the answer 1? 0 votes 0 votes Please log in or register to add a comment.
Best answer 3 votes 3 votes 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$ air1 answered Nov 17, 2016 selected Nov 17, 2016 by Arjun air1 comment Share Follow See 1 comment See all 1 1 comment reply papesh commented Nov 19, 2016 reply Follow Share very nice explanation... thanks.. 0 votes 0 votes Please log in or register to add a comment.