1
$\begingroup$

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.

  • 0
    Ok thanks. So how would i convert that into the average number of "guesses" needed? is it 1 / (1/2)^4 ?2011-09-05

2 Answers 2

2

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

  • 0
    @Thijs Laarhoven: Wow, nice trick. 10x.2011-09-05
1

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?