Not sure what this problem would be called....

[Povilas M]

Hi,

I am trying to write a function which would take two arguments:
-> number of bits (which are a binary 0 or 1 value) N
-> and acceptable number of mismatching bits M
The function would statistically determine the probability of having M or less mismatching bits when randomly generating two N long bit arrays and comparing them. Difference between 1001 and 1011 would be 1 for example as only the third bit differs. My testing indicates a bell curve is formed around N/2, but I've not done maths for years, it's hard for me to figure the formula out...

Thanks a lot

 

[Buzz Bloom]

My testing indicates a bell curve is formed around N/2

Hi Povilas:

Your problem statement confuses me a bit.
1. You did not mention what the the probability of generating a "1" is with the bit generator you are using. In the above quote the "N/2" suggests the probability is exactly 1/2, but you did not say that explicitly.
2. You say that your experiments produce a "bell curve", but your description says you want a curve for "M or less mismatching bits". That seems wrong to me since a curve for that result would not be bell shaped. What would be approximately bell shaped is a curve for exactly M matches.

If the "bell curve" you want is for exactly M matches, the answer is a binomial distribution curve. Take a look at

https://en.wikipedia.org/wiki/Binomial_distribution.​

Hope this helps.

Regards,
Buzz

 

[jedishrfu]

Can you provide a context of where you might use this function?

I was thinking that you could simplify the problem by considering the first N bit array as all zeros and
now you only need to count all the N bit arrays with <=M bits as ones:

Basically its a binomial distribution problem ala pascal's triangle kind of problem:

https://en.wikipedia.org/wiki/Pascal's_triangle

so for a five bit string you'd have:
- 1 string of zeros
- 5 strings with 1 one bit
- 10 strings with 2 one bits
- 10 strings with 3 one bits
- 5 strings with 4 one bitys
- 1 string with all one bits

 

[Buzz Bloom]

Can you provide a context of where you might use this function?

Hi @jedishrfu:

I am not sure you were asking the question for me to answer, but here it is.

The binomial distribution has many uses. A common example is to calculate the probability of getting M heads when flipping "an honest coin" N times.
This is exactly the same probability of getting M matches (heads and heads or tails and tails) when flipping two "honest coins" M times.

Basically its a binomial distribution problem ala pascal's triangle kind of problem:

Pascals triangle is a way of calculating the number of combinations of N things when M are of one kind and N-M are of a different kind. This usually noted as

(N over M).​

(Sorry about the awkwardness of the way I show the notation. The Wikipedia citation in post #2 shows it correctly.)
In the quote above I am not sure what "ala" means exactly, but

P(N,M) = (N over M) × (1/2)^N,​

where P is the binomial distribution probability when P(1,1) = 1/2, the probability of heads for an "honest coin".

Regards,
Buzz

 

[Povilas M]

Thanks all! Binomial distribution curve was exactly what I needed, I figured out the rest from there. Jedishrfu, simplifying the problem was a very useful point as well!
Thanks again!

 

[jedishrfu]

My context question was for the original poster.

Hopefully, he can tell us more about the problem he's trying to solve.

 

[jedishrfu]

Thanks all! Binomial distribution curve was exactly what I needed, I figured out the rest from there. Jedishrfu, simplifying the problem was a very useful point as well!
Thanks again!

So i guess youre not going to tell us the context.