1
$\begingroup$

What is the number of times the string "011" will appear as a substring in a randomly generated binary string of length 10. All the bits of the random binary string have equal probability of being 0 or 1. My solution uses indicator random 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$ Is this solution correct?

$\endgroup$
2
$\begingroup$

Yes, that looks correct. Additivity of expectations helps you avoid what could otherwise have been a rather complex calculation.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.