If I have a program that creates, let's say, one billion integers, with each having a pure $50 - 50$ chance to be one or zero,

what is the chance of finding $x$ zeros in a row?

for brownie points, instead of the program creating a set billion numbers, what would the equation be with $z$ numbers?


Hint: If you never had $x$ zeros in a row, then (at least) one of the first $x$ numbers must be a one.

If $n_z$ is the number of arrangements, then you can partition $n_z$ based on which digit (of the first $x$) is the first to be a one. This will give you a recurrence relation in terms of numbers $n_{z_0}$, where each $z_0<z$.

Doing this will let you come up with the probability that such an arrangement never occurs; the event that such an arrangement DOES occur is the complement of this event.

  • $\begingroup$ Not quite understanding... As for the first line, assuming $z=5$ and $x=3$, I could have 1, 1, 0, 0, 0, 1. The second paragraph, I'm not really getting -- as I understand it, your suggestion is to split the list of 1's and 0's into length $x$, which makes sense, and I can see where it's going, and then... I don't know. Can you break it down a little more? $\endgroup$ – Quelklef May 25 '15 at 15:25

consider with just 10 integers $$\large{x_1x_2x_3x_4x_5x_6x_7x_8x_9x_{10}}$$ where all $\large{x_i}$ is either $0$ or $1$.

What is the chance of finding $\large{x_1x_2x_3x_4}$ all zeros ?

It is just $\large{(\frac{1}{2})^4 = \frac{1}{16}}$. Now you just apply this to your question

  • $\begingroup$ Yes, but then you have a greater chance because there aren't four $x$'s, instead there are ten, allowing for different places for the pattern to pop up. This is the chance for 4 $x$'s total. $\endgroup$ – Quelklef May 25 '15 at 15:18

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.