Assume I have all possible $2^N$ binary strings of length $N$ as rows in a matrix $M$, i.e., $M \in \{0,1\}^{{2^N}\times N}$. I'm interested in the column-wise Hamming distances of $M$ and its properties.

Obviously, for all $N > 1$, the hamming distance $d_h$ of any two selected columns of $M$ is $>0$, i.e., $d_h(a,b) > 0$ where $a, b$ are two distinct columns of $M$.

Also, if $N = 3$ then $d_h(a,b) = 4$. Similary, if $N = 4$ then $d_h(a,b) = 8$. In general is it the case that for $N>1$, $d_h(a,b) = 2^{N-1}~\forall a \neq b$?

Also, what if in an iterative manner I start selecting a row randomly and removing it from $M$. Hence at iteration $t$, I have randomly selected and removed $t$ binary strings from $M$. I'm trying to show that as $t$ increases $d_h$ decreases at the worst case scenario.

Will the following statement be precise in explaning this: $\exists a,b$ such that $lim_{t\to N} d_h(a,b)=0$. Also, it may be obvious, but how can I approach to prove the above statement more formally?


If you take any two columns, half their entries will match and half will not match. So since you have $2^N$ strings, that means hamming distance is $2^{N-1}$.

Similarly remove the half of strings that have a '0' in one fixed position. Then the hamming distance will be $2^{N-2}$.

| cite | improve this answer | |
  • $\begingroup$ I see! Thanks! Can I derive a bound (a worst case scenario) on $d_h$ if I randomly remove $T$ strings? $\endgroup$ – Kenshin Mar 18 '15 at 22:16

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.