# What's the chance of $(\frac{1}{2})^x$ with $y$ iterations?

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.

• 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? – 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

• 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. – Quelklef May 25 '15 at 15:18