4
$\begingroup$

Consider binary words of length $20$. They are formed in such a way that a $1$ occurs with probability $0.6$, and a $0$ does with probability $0.4$ (different places are independent). Also, a “run” is a maximal substring of only ones or only zeros; e.g., $00110001101011111111$ has $8$ runs.

I think this question should be solved using Linearity of Expectation from Discrete Math II but It is kind of hard for me to make the connections between probability and counting theories.

1) What is the probability that a random bit string of length $20$ starts in a $0$, has exactly $8$ ones, and has exactly $10$ runs?

I worked out that the probability of "a random bit string of length $20$ starts in a $0$, has exactly $8$ ones" is equal to $(0.6^8)\cdot(0.4^{11})$ because it starts with $0$ and then there're $19$ bits left. Then I want to use stars and bars theory to count the number of ways we can arrange $8$ ones and $11$ zeros to make it a "$10$ run" string. It is like choosing $4$ walls of ones to separate $19$ zeros. I am stuck here because I don't know how to make the connection between runs and the possibility of $o$'s and $1$'s ($0.4/0.6$).

2) What is the probability that a random bit string of length $20$ has exactly $10$ runs?

Same idea here, to use the stars and bars theory to separate $4-16$ $1$'s or $0$'s using $4-16$ $0$'s or $1$'s. Ah, I just don't know how to start from here...

$\endgroup$
  • $\begingroup$ Welcome to MSE! Please show what you have tried and where you got stuck. $\endgroup$ – Remy Mar 21 '18 at 6:41
  • $\begingroup$ @Remy Thanks for the tips. $\endgroup$ – Ulysses Mar 21 '18 at 6:48
  • $\begingroup$ @an4s I've just updated my question. Sorry for that $\endgroup$ – Ulysses Mar 21 '18 at 6:48
3
$\begingroup$

I worked out that the probablity of a random bit string of length 20 starts in a 0, has exactly 8 ones is equal to (0.6^8)*(0.4^11) because it starts with 0 and then there're 19 bits left.

That's not quite right: that would be the probability of getting a specific bit string with $8$ ones and $11$ zeros, e.g. the probability of getting $1111111100000000000$ is the probability you indicated. Also, you forget that even though we want the first bit to be a $0$, it still takes a certain probability for that to happen.

So, instead, you can point out that there are $19 \choose 8$ bit strings of length $19$ that can succeed the initial $0$, and so the probability of getting a bitstring of length 20 with $8$ ones and $12$ zeros that starts with a zero is:

$${19 \choose 8} \cdot 0.6^8 \cdot 0.4 ^ {12}$$

But yes, that number does not reflect the constraint that it should have exactly $10$ runs. In fact, it is not clear that calculating this probability helps you a whole lot.

So, instead, let's concentrate on the runs. You write:

I want to use stars and bars theory to count the number of ways we can arrange 8 ones and 11 zeros to make it a 10 run string. It is like choosing 4 walls of ones to separate 19 zeros.

Close! You don't separate $19$ zeroes ... you only have $12$ zeroes. But yes, with $10$ runs you have a run of ones at the end, and so that means you indeed have $4$ runs of ones that need to separate the $12$ zeroes. In terms of stars and bars: you have $11$ gaps between the zeroes, and you need to pick $4$ of those to place your runs, giving a total of $11 \choose 4$ ways to place the runs of ones between the runs of zeros.

However, while the placement of the runs of ones determines the lengths of the runs of zeros, the runs of the ones themselves may be of different lengths yet, resulting in different bit strings. So, we need to figure out how in how many ways we can create $5$ runs of ones using $8$ ones.

Well, again we can use stars and bars for this. This time, we need to place $4$ bars in any of the $7$ gaps between the $8$ oness, and thus we have $7 \choose 4$ ways to create $5$ runs of ones.

OK, so the total number of bitstrings of length $20$ with $8$ ones and $12$ zeros that starts with a zero, and that has $10$ runs is:

$${11 \choose 4} \cdot {7 \choose 4}$$

Now, each of these occurs with a probability of $0.6^8 \cdot 0.4 ^ {12}$, and so the probability of getting one of these is:

$${11 \choose 4} \cdot {7 \choose 4} \cdot 0.6^8 \cdot 0.4 ^ {12}$$

$\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.