Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
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
add comment

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?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.