Suppose we have $n$ strings (or vectors) $a_1, a_2, \dots, a_n \in A^m$, where $A$ is an arbitrary set satisfies $|A| \geq n$. And we limit their pairwise hamming distance by $$ d(a_i, a_j) \geq d_{ij} \mathrm{\ for\ all\ } i \neq j$$ with given $d_{ij}$. Then we define random variable $X_l$ by that it will equal to $a_{il}$ (the $l$-th character, or component, of $a_i$) for some $i$, where $i$ will be uniformly distributed in $1,2,\dots,n$.

Question: Can we give a lower bound of $$ E(H(X_l)) = \frac{1}{m}\sum_{l=1}^m H(X_m),$$ where $H(\cdot)$ is entropy function and $l$ is uniform distributed in $1,2,\dots,m$?

  • $\begingroup$ In the displayed equation in the statement of the question, what is $l$? Are you trying to define a random vector of length $m$? In that case, $X$ might be a good name for the vector. $\endgroup$ – Jon Noel Jul 28 '17 at 20:46
  • $\begingroup$ If you are defining a random vector in the way that I think you are, then it seems to me that the entropy should be basically minimised by making the range of possibilities of $X$ as small as possible (although I'm not sure how to make this rigorous). $\endgroup$ – Jon Noel Jul 28 '17 at 21:02

First decompose the total distance $D$ by component: $$D = \sum_{i,j\in [n]} d(a_i,a_j) = \sum_{l \in [m]} \sum_{i,j\in [n]} \mathbf{1}\{a_{il} \neq a_{jl}\}.$$ Let $\delta_l = \frac{1}{n^2} \sum_{i,j\in [n]} \mathbf{1}\{a_{il} \neq a_{jl}\}$. Compute the collision entropy of $X_l$: $$H_2(X_l) = - \log \left(\frac{1}{n^2}\sum_{i,j \in [n]} \mathbf{1}\{a_{il} = a_{jl}\}\right) = - \log (1-\delta_l).$$

For each $l$, $H(X_l) \geq H_2(X_l)$. Thus $\sum_{l \in [m]} H(X_l) \geq - \log \prod_{l \in [m]} (1 - \delta_l)$. $\prod_{l \in [m]} (1 - \delta_l)$ is maximized subject to $\sum_{l \in [m]} \delta_l = \frac{D}{n^2}$ by $\delta_l = \frac{D}{mn^2}$. The final lower bound is $$\frac{1}{m} \sum_{l \in [m]} H(X_l) \geq - \log \left(1 - \frac{D}{mn^2}\right).$$

| cite | improve this answer | |
  • $\begingroup$ Thanks! What should I do if I would like to cite your answer (e.g. in paper)? $\endgroup$ – Lwins Aug 7 '17 at 17:44

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.