Minimize average bitwise entropy with given pairwise hamming distance

Question

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

Answer 1

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).$$