probability to create a binary bit pattern

Printable View

February 24th 2010, 10:51 AM
problady

probability to create a binary bit pattern

Hello,

I did not anderstand this exercise.

May you PLEASE help me?

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

Looking forward for your answer!
February 24th 2010, 10: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.
February 24th 2010, 01:44 PM
problady

I woud appreciate if you can let me know where I can read more about this kind of problems and in which category they fall in probability. Moreover could you explain what is the probability to create the same bit pattern?

Thank you...
February 24th 2010, 01:59 PM
icemanfan

This is a question of combinatorics.