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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Entropy_(information_theory)) and $l$ is uniform distributed in $1,2,\dots,m$?
> 
> 
> 



Minimize average bitwise entropy with given pairwise hamming distance
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).$$


