0
$\begingroup$

This is not a homework or exam question

Greetings Community!

I am working a piece of a problem that I came up with on my own and the challenge below is a step that I can't seem to view in a way so as to solve it myself. I thought that perhaps the community may see a way to solve this that I am just not seeing. Any insights you are willing to provide are most appreciated. If you require additional information or something is not clear, please let me know.

Assume you have two binary strings $A$ and $H$ each with length $N$. The $j^{th}$ position of both strings is denoted by $a_j$ and $h_j$ respectively.

$A$ and $H$ are randomly generated with one condition: $A$ and $H$ must have a predefined and an equal number, of 1's, namely M.

We now define the variable $X$ such that if $a_j = h_j$ then $x_j = 1$ otherwise $x_j = 0$. This is the NXOR operation. An example is below:

A = 00010010101

H = 00101001011

X = 11000100001

The string for X is essentially tracking where the collisions of A and H take place. Here is where the challenge comes in.

Define $W = \sum_{j=1}^N x_j$. What is the distribution of $W$ given the parameters of $M$ and $N$?

Current (yet minimal) progress:

As I had eluded to, this problem seems to be a derivative from the problem set that deals with hash collisions in cryptography and so seems to be related to the birthday problem.

The bounds on the distribution would have to be $[|N-M|, N]$. This is because unless you have an equal number of 0's and 1's you will always have $W > 0$.

I think this would be some kind of hypergeometric distribution but I seem to be stuck on my condition that a certain number of 1's be present.

$\endgroup$
1
$\begingroup$

First of all, when you say "random," I assume you mean that each of the $\binom{N}{M}$ $n-$bit strings with exactly $M$ ones is equally likely.

Let $A$ be given. For $0 \le w \le M$ the are $\binom{M}{w}$ ways to choose $w$ positions for ones in H that will match the ones in $A$. We can match the remaining $M-w$ ones to zeroes of A in $\binom{N-M}{M-w}$ ways. Then we assign zeroes to all the remaining positions in $H$. How may matches did we get? We matched $w$ ones and $N-M-(M-w)$ zeroes, for a total of $N-2(M-w)$ matches.

To be able to assign the unmatched ones, we need $M-w \le N-M,$ that is, $w \ge 2M-N.$ Finally, the probability that we get $N-2(M-w)$ matches is $$\frac{\binom{M}{w}\binom{N-M}{M-w}}{\binom{N}{M}} \text{ for } \max(0,2M-N) \le w \le M,$$ and $0$ otherwise.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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