1
$\begingroup$

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

$\endgroup$
2
  • $\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, 2017 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, 2017 at 21:02

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks! What should I do if I would like to cite your answer (e.g. in paper)? $\endgroup$
    – Lwins
    Aug 7, 2017 at 17:44
  • $\begingroup$ @Lwins Check the 'cite' link between 'share' and 'edit'. $\endgroup$ Sep 1, 2020 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.