<p>This is called &quot;output entropy&quot;. Suppose you have a communications channel that takes a string and then outputs a random string within a relative <span class="math-container">$\delta$</span> radius of it. If you use the input distribution <span class="math-container">$X$</span> for communicating over this channel, the entropy of the output distribution would be the quantity you are after.</p>

CC BY-SA 4.0
2021-07-22T20:34:06.757Z
2021-07-22T20:34:06.757Z
Mahdi Cheraghchi
<p>Recently I stumbled upon the following notion of entropy which seems quite natural to me. I am looking for its &quot;real&quot; 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.</p>
<p>For <span class="math-container">$\delta \in [0,1]$</span> and <span class="math-container">$x \in \{0,1\}^n$</span>, let <span class="math-container">$B_\delta(x) = \{y \in \{0,1\}^n \mid d_H(x,y) \le \delta \}$</span> be the (closed) <span class="math-container">$\delta$</span>-Hamming ball around <span class="math-container">$x$</span>, where <span class="math-container">$d_H$</span> is the relative Hamming distance. For a random variable <span class="math-container">$X$</span>, define
<span class="math-container">$$H_\delta(X) = \mathbb{E}_{x \gets X}\left[ \log \frac{|B_\delta(x)|}{\Pr[X \in B_\delta(x)]} \right]$$</span>
as the &quot;<em><span class="math-container">$\delta$</span>-ball entropy</em>&quot; of <span class="math-container">$X$</span>.</p>
<p>This is the same as the standard (i.e., Shannon) entropy <span class="math-container">$H(Y_X)$</span> of the random variable <span class="math-container">$Y_X$</span> obtained by first sampling a value <span class="math-container">$x$</span> according to <span class="math-container">$X$</span> and then uniformly picking a random element of <span class="math-container">$B_\delta(x)$</span>. It seems interesting in that it &quot;evens out&quot; the entropy around each point <span class="math-container">$x$</span>. Also, <span class="math-container">$H_0(X) = H(X)$</span> is the standard entropy and <span class="math-container">$H_1(X) = H(U_n) = n$</span>.</p>

CC BY-SA 4.0
2021-07-22T10:26:05.243Z
Finally, the operation of sampling from a ball around x is vaguely reminiscent of convolution https://math.stackexchange.com/questions/999236/entropy-of-convolution-of-measures
Aryeh
CC BY-SA 4.0
2021-07-22T15:19:11.413Z
@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.)
dkaeae
CC BY-SA 4.0
2021-07-22T15:23:12.343Z
@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.
dkaeae
CC BY-SA 4.0
2021-07-22T16:31:43.410Z
Convolution can be defined over groups, see that link in my comment.
Aryeh
CC BY-SA 4.0
2021-07-23T11:58:07.483Z
@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)$.
dkaeae
<reference-request><it.information-theory><shannon-entropy>
Does this notion of entropy have a name?
dkaeae
# Does this notion of entropy have a name?

(Asked by: username_0 on 2021-07-22)

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

**Tags:** reference-request, it.information-theory, shannon-entropy
> **Comments:**
> **username_1**: Finally, the operation of sampling from a ball around x is vaguely reminiscent of convolution https://math.stackexchange.com/questions/999236/entropy-of-convolution-of-measures  
> **username_0**: @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.)  
> **username_0**: @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.  
> **username_1**: Convolution can be defined over groups, see that link in my comment.  
> **username_0**: @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)$.  

---

## 1 answers

### Answer by username_2 on 2021-07-22. Score: 1

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.


---

