# probability to create a binary bit pattern

• Feb 24th 2010, 11:51 AM
probability to create a binary bit pattern
Hello,

I did not anderstand this exercise.

If we have created a binary bit pattern from 100 bits.

What is the probability to create another binary bit pattern from 100 bits which will have distance smaller than 10 from the already created one.

The distance is based on XOR calculation like i.e:

010101
101010
--------
111111 - > distance 6

or

010101
010100
--------
1 -> distance 1

• Feb 24th 2010, 11:57 AM
icemanfan
If the distance is less than 10, then it must be something between 0 and 9.

You can create all possible 100 bit patterns from one bit pattern A by choosing the bits from A that change.

That means that you need to choose less than 10 bits that change. More precisely, you need to choose exactly n bits that change, where $0 \leq n \leq 9$.

The number of ways to do this is
$\sum_{n=0}^9 {100 \choose n}$.

The total number of 100 bit patterns is $2^{100}$.

Hence, the required probability is

$\frac{\sum_{n=0}^9 {100 \choose n}}{2^{100}}$,

assuming that each bit pattern is chosen with equal probability.
• Feb 24th 2010, 02:44 PM