4
$\begingroup$

Recently I stumbled upon the following notion of entropy which seems quite natural to me. I am looking for its "real" name and/or any references where it might come up. I tried searching online for, e.g., generalized versions of entropy but could not find anything like it.

For $\delta \in [0,1]$ and $x \in \{0,1\}^n$, let $B_\delta(x) = \{y \in \{0,1\}^n \mid d_H(x,y) \le \delta \}$ be the (closed) $\delta$-Hamming ball around $x$, where $d_H$ is the relative Hamming distance. For a random variable $X$, define $$H_\delta(X) = \mathbb{E}_{x \gets X}\left[ \log \frac{|B_\delta(x)|}{\Pr[X \in B_\delta(x)]} \right]$$ as the "$\delta$-ball entropy" of $X$.

This is the same as the standard (i.e., Shannon) entropy $H(Y_X)$ of the random variable $Y_X$ obtained by first sampling a value $x$ according to $X$ and then uniformly picking a random element of $B_\delta(x)$. It seems interesting in that it "evens out" the entropy around each point $x$. Also, $H_0(X) = H(X)$ is the standard entropy and $H_1(X) = H(U_n) = n$.

$\endgroup$
5
  • $\begingroup$ Finally, the operation of sampling from a ball around x is vaguely reminiscent of convolution math.stackexchange.com/questions/999236/… $\endgroup$
    – Aryeh
    Jul 22 at 10:26
  • $\begingroup$ @Aryeh Off the top of my head, one possible motivation is in coding theory: Say $X = U_C$ is uniformly distributed over some subset $C$ of $\{ 0,1 \}^n$. Then it is easy to see that $H_\delta(U_C)$ is maximized (for subsets of $\{0,1\}^n$ of the same size) iff $C$ is a code of minimum distance $> \delta$. So in this case $H_\delta(U_D)$ gives a measure for how far a subset $D$ is from such an ideal code $C$. (Of course, in this example $X$ is always uniform but I am sure there is something interesting to be said about general distributions too.) $\endgroup$
    – dkaeae
    Jul 22 at 15:19
  • $\begingroup$ @Aryeh Also, I am asking about random variables taking values in the Hamming space $\{0,1\}^n$. AFAICT convolution is defined for real-valued variables. I am not sure how that would carry over. $\endgroup$
    – dkaeae
    Jul 22 at 15:23
  • $\begingroup$ Convolution can be defined over groups, see that link in my comment. $\endgroup$
    – Aryeh
    Jul 22 at 16:31
  • 1
    $\begingroup$ @Aryeh Aha, so another perspective is $H_\delta(X) = H(Z)$ with $Z = X \oplus U_\delta$, where $\oplus$ is the XOR operation and $U_\delta$ is the uniform distribution on $B_\delta(0)$. $\endgroup$
    – dkaeae
    Jul 23 at 11:58
1
$\begingroup$

This is called "output entropy". Suppose you have a communications channel that takes a string and then outputs a random string within a relative $\delta$ radius of it. If you use the input distribution $X$ for communicating over this channel, the entropy of the output distribution would be the quantity you are after.

$\endgroup$
0

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.