# Calculating probability question

If I have a random byte which consists of 8 bits.

e.g 11011101

I want to calculate the probability that the first x number of bits of any random byte will be zero.

For example: calculate the average number of guesses it would take to find a random byte with 4 leading zero bits.

Any help appreciated.

-
Yes uniformly random. So the size of of the "byte" doesn't need to be taken into account? For example if I have a SHA 256 hash (256 bits) the probability of generating a hash with 4 leading zeros is the same as generating a byte with 4 leading zeros? –  Ben Reeves Sep 5 '11 at 13:19
Ok thanks. So how would i convert that into the average number of "guesses" needed? is it 1 / (1/2)^4 ? –  Ben Reeves Sep 5 '11 at 13:32

Assuming a random byte has all its bits 0 or 1 with probability $\frac{1}{2}$, independent of each other, the answer to the probability seems to be pretty simple.

The probability that the first x bits of such a number will be zero (or whatever) is $\frac{1}{2^x}$.

About your second question: what is the average number of guesses to find such a number. Actually it's a more general question: what is the number of guesses to find something probability of which is $\tilde{p}$.

Le't calculate this.

$$\langle N \rangle = 1 \cdot \tilde{p} + 2 \cdot (1-\tilde{p}) \cdot \tilde{p} + 3 \cdot (1-\tilde{p})^2 \cdot \tilde{p} + \ldots$$

Means you need 1 guess with probability $\tilde{p}$. The probability it doesn't happen on the first guess is $1-\tilde{p}$, hence you need 2 guesses with probability $2 \cdot (1-\tilde{p}) \cdot \tilde{p}$. And so on.

We'll use the following known fact:

$$1 + (1-\tilde{p}) + (1-\tilde{p})^2 + (1-\tilde{p})^3 + \ldots = \frac{1}{\tilde{p}}$$

$$\begin{eqnarray} \langle N \rangle &=& 1 \cdot \tilde{p} + 2 \cdot (1-\tilde{p}) \cdot \tilde{p} + 3 \cdot (1-\tilde{p})^2 \cdot \tilde{p} + \ldots = \\ &=& \tilde{p} \cdot \left[ 1 + 2 \cdot (1-\tilde{p}) + 3 \cdot (1-\tilde{p})^2 + \ldots \right] = \\ &=& \tilde{p} \cdot \left[ 1 + (1-\tilde{p}) + (1-\tilde{p})^2 + \ldots + (1-\tilde{p}) + (1-\tilde{p})^2 + ... + (1-\tilde{p})^2 + (1-\tilde{p})^3 \ldots \right] = \\ &=& \tilde{p} \cdot \left[ \frac{1}{\tilde{p}} + (1-\tilde{p}) \cdot \frac{1}{\tilde{p}} + (1-\tilde{p})^2 \cdot \frac{1}{\tilde{p}} + \ldots \right] = \\ &=& 1 + (1-\tilde{p}) + (1-\tilde{p})^2 + ... = \frac{1}{\tilde{p}} \end{eqnarray}$$

$$\langle N \rangle = \frac{1}{\tilde{p}}$$

Hence the answer to your question is $\langle N \rangle = 2^x$.

-
I have edit your post to write formulas using TeX, I hope you agree it looks nicer than HTML. –  Sasha Sep 5 '11 at 14:16
@Sasha: yeah, 10x. Hope I'll learn TeX one day –  valdo Sep 5 '11 at 14:26
@Thijs Laarhoven: Wow, nice trick. 10x. –  valdo Sep 5 '11 at 21:10

There is another nice trick to find the expected value of a geometric($p$) variable; that is, the expected number of tosses until the first sucess. It goes as follows: Note that $E[X] = 1 + (1-p) E[X]$. This is because you have to look at the first toss anyways. If the first toss is not a success (with probability $1-p$) you start all over again from the the second toss. If the first toss is a success, you stop. Solving this equation we get $E[X]=1/p$.

Here is a related question that might be of interest. If you are looking at the byte bit-by-bit, how many bits do you expect to look at until you see a string of $4$ zeroes?

-