Let's assume I have $N$ binary strings $\{T_1,T_2,\ldots,T_N\}$ of length $L$. All these strings satisfy a minimum hamming distance with respect to a reference binary string R with $\|R\|_1$ ones and the same length of $L$, i.e.,

$$d(T_i,R)\leq \left\lfloor{\frac{L-\|R\|_1}{2}}\right\rfloor+1$$

The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. For example the hamminf distance of 001 and $111$ is $2$.

What is the probability that for a single bit, e.g. the $K$th bit,

$$|N\times R[k]-\sum\limits_{i=1}^N T_i[k]|\geq\left\lfloor\frac{N}{2}\right\rfloor$$

Note: In fact we have a conditional probability conditioned on the samples satisfying the preceeding hamming distance condition)

  • $\begingroup$ "satisfy a minimum hamming distance " That should be a maximum distance, no? Further, I don't get how can you ask about probabilities when you didn't specify a probabilistic model for the strings. Are we to assume that the binaries strings are generated as uniform fair Bernoulli vars (iid bits), truncated to the distance condition? What about R? Is that fixed or also random? And if the later, is its weight fixed? $\endgroup$ – leonbloy Oct 23 '14 at 17:49
  • $\begingroup$ Thank you, Yes, it should be maximum hamming dsitance. So, the assumption is that these arrays are being generated with the Bernoulli distribution for each pixel, i.e., the 50% equal chance for 0 and 1. Here the probability means the number of cases satisfying the error condition over all the possible cases conditioned with respect to maximum hamming distance. $\endgroup$ – Hamid Oct 27 '14 at 19:05

Your Answer

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

Browse other questions tagged or ask your own question.