For binary vectors, x = (x1,x2,...,xn) and y=(y1,y2,...,yn), the Hammond distance between them is defined by

d(x,y) = |x1 - y1| + |x2 - y2| + ... + |xn - yn|.

Let A be a finite set of such vectors and let X1, X2, ..., Xn be independent random variables that are each equally likely to be either 0 or 1. Set

D = min {d(x,y): (X,y) in A}. Find an upper bound for P(D >= b) in terms of E[D], when b > E[D].

I think we have to use Azuma's inequality but can't seem to figure out how..

  • $\begingroup$ It looks like you meant to refer to Hamming distance. A (simple) analysis of this distance distribution is at the heart of proofs of Shannon's Source Coding Theorem, so perhaps you can get some ideas from studying those. Out of curiosity, could you briefly say why you tagged this post with martingale? $\endgroup$ – whuber Nov 30 '17 at 14:20

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.