# Minimize average bitwise entropy with given pairwise hamming distance

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$?

• 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. – Jon Noel Jul 28 '17 at 20:46
• 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). – 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).$$