{'fraction_non_alphanumeric': 0.06544502617801047, 'fraction_numerical': 0.009363672976238422, 'mean_word_length': 3.770893371757925, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Tight Uniform Continuity Bound for Equivocation

We prove a tight uniform continuity bound for the conditional Shannon entropy of discrete finitely supported random variables in terms of total variation distance.


I. INTRODUCTION
There has been significant work towards understanding the interplay between the Shannon entropy and various distance measures on the probability simplex [1], [2], [3]. In conjunction, remarkable progress has been made in the study of the continuity of the von Neumann entropy, or matrix entropy, versus trace distance [4], [5], [6]. In both cases, several proofs of a tight uniform continuity bound have been presented [1], [2], [7], [5], [8], [9]. On the other hand, uniform bounds, which are not tight but are independent of the size of the conditioning system, were proven for the conditional Shannon and von Neumann entropies in [10], [8]. In this note, We present a proof of a tight uniform continuity bound for the conditional Shannon entropy of discrete finitely supported random variables in terms of total variation distance.
Let X := {1, 2,..., |X |} and Y := {1, 2,..., |Y|}. Let P X ×Y denote the probability simplex with |X ||Y| atoms. The Shannon entropy of a random variable X ∼ p X is defined as [11] H(X) := − i∈X p X (i) log p X (i). (1) All logarithms are meant in base 2. Similarly, for two jointly distributed variables (X, Y ) ∼ p XY , the joint Shannon entropy is given by and the conditional Shannon entropy H(X|Y ), also known as the equivocation in X given Y , is defined as Given two probability distributions p XY , q X ′ Y ′ ∈ P X ×Y , the total variation distance between them is defined as A bona fide metric on the probability simplex, it captures the distinguishability of any two probability distributions [12]. There are at least two reasons to want the sharpest estimates of variation for entropic quantities in terms of relevant distance measures. The first reason is that in practice we only have access to estimates of distributions, never the true distribution, of any given random variable. Second, in settings where communication rates can be evaluated only for a special class of distributions, it pays to have tight bounds on the error incurred by approximating the rates of arbitrary distributions by the ones of the closest members of said special class [13], [14], [15].
Main Result: Let ǫ ∈ (0, 1 − 1 |X | ] and p XY , q X ′ Y ′ ∈ P X ×Y be such that TV(p XY , q X ′ Y ′ ) ≤ ǫ. The following inequality holds where h(·) is the binary entropy function. Moreover, the inequality is tight. This means that for all ǫ ∈ (0, 1 − 1 |X | ], there exists a pair of probability distributions on X × Y such that the total variation distance between them is ǫ and (7) is saturated.
The mechanics of the proof are based on G-majorization, which refers to a group-induced preordering on a vector space [16], [17]. It is a generalization of Schur majorization, where the group in question is the symmetric group. That is, we say that the vector q X ′ Y ′ majorizes the vector p XY whenever p XY is in the convex hull of the orbit of q X ′ Y ′ under the action of the symmetric group, where the action is thought of in terms of the natural permutation representation. Since the Shannon entropy is strictly concave and invariant under the action of the symmetric group, this implies H(XY ) ≥ H(X ′ Y ′ ), i.e., the Shannon entropy is strictly Schur-concave.
Equivocation is not Schur-concave. While it is strictly concave, it is not invariant under the action of the symmetric group. It is, however, invariant under the action of a proper subgroup of the symmetric group. We use this invariance to prove the present result.

II. PROOF
Consider the bivariate probability distribution p XY = {p XY (i, j) | i ∈ X ; j ∈ Y}. The conditional entropy H(X|Y ) associated with p XY is invariant under permutations of j indices, as can be seen from (4). Furthermore, it is invariant under exchanges of the form (i 1 , j) ⇆ (i 2 , j) ∀ i 1 , i 2 ∈ X and j ∈ Y. These are the symmetries of the equivocation in X given Y. Denote this subgroup of the symmetric group by S X |Y .
Since the bound is monotonic in ǫ, we are free to take TV(p XY , q X ′ Y ′ ) = ǫ. Moreover, we assume without loss of generality that H(X|Y ) ≥ H(X ′ |Y ′ ). We proceed in three steps.

A. Reordering
First, we order the components of the bivariate probability distributions in a suggestive way. We arrange the components to be in blocks of |X | components that share the same Y label. We order the |Y| blocks such that q Y ′ (j) − p Y (j) is in a non-increasing order. For the block labeled by j, we define the two sets: Remark that either of the two sets could be empty, but not both. Within the jth block, if both I j and I c j are nonempty, put the elements of I j ahead of those in I c j . That is, we relabel the components so that i < i ′ for all i ∈ I j and i ′ ∈ I c j . Next, we order the elements of I j such that q X ′ Y ′ (i, j) is non-increasing in i. We do the same for the elements of I c j .

B. Walking
The second step involves an optimized form of a proof technique due to Pinelis [7]. We walk the two probability distributions across the probability simplex until H(X ′ |Y ′ ) = 0. In the process, we take care that the difference of equivocations does not decrease and that the total variation distance does not increase.
We start by zooming into the jth block. If I j is not empty, then we make the following replacements: for each i ∈ I j \ {1}. If I j consists of a single element, then such replacements need not be done. By design, these replacements do not affect total variation distance. To see that H(X ′ |Y ′ ) did not increase, we note that the old probability vector is in the convex hull of the orbit of the new vector under the action of S X |Y . Put another way, the probability weights, conditional on j, are now more concentrated than before. After these replacements are made, the following inequalities will hold: for each i ∈ X \ {1}. Next, we make H(X ′ |Y ′ = j) zero by transferring probability weights in the block from the bottom to the top. Specifically, we make the following transfers: for each i ∈ X \ {1}. To ensure that the total variation distance remains constant, we make the same transfers in p XY . Observe what happens when a probability weight s, suitably small and non-negative, is taken from outcome (i, j) and given to outcome (1, j) in both probability distributions. The difference of entropies changes by the following amount: where η(x) = x log x. Since it is convex and inequalities (12) and (13) hold, the two differences in curly brackets are not negative. Hence, we can set q X ′ Y ′ (1, j) = q Y ′ (j) and q X ′ Y ′ (i, j) = 0 for i = 1. This implies that H(X ′ |Y ′ = j) vanishes. Now, say I j is empty. Then it holds that q X ′ Y ′ (i, j)−p XY (i, j) < 0, for all i ∈ X . It also holds that q X ′ Y ′ (1, j) ≥ q X ′ Y ′ (2, j) ≥ ... ≥ q X ′ Y ′ (|X |, j). Our goal is still to take H(X ′ |Y ′ = j) to zero. To do this, we increase q X ′ Y ′ (1, j) by transferring in probability weights from the rest of the outcomes in the block. As explained before, such transfers can only decrease H(X ′ |Y ′ ). Furthermore, as long as q X ′ Y ′ (1, j) − p XY (1, j) < 0, these transfers can be done without affecting the total variation distance. If at any point q X ′ Y ′ (1, j) − p XY (1, j) = 0, we stop as (12) and (13) now hold for this block. In such a case, we start the process mentioned in the previous paragraph. Otherwise, we After all blocks have been processed, we can assume without any loss of generality that q X ′ Y ′ (i, j) = 0 for all i = 1. With this in mind, we subject both probability distributions to a stochastic process that averages over all the blocks. Specifically, The stochastic map E is a convex combination of elements in S X |Y . This implies that H(X|Y ) will not decrease. Of course this processing does not change the fact that H(X ′ |Y ′ ) = 0 since only q X ′ Y ′ (1, j) are nonzero. Recall that total variation distance is contractive under stochastic maps [18]. Therefore, we are free to take p Y (j) = q Y ′ (j) = 1 |Y| for all j ∈ Y.

C. Estimating
The arguments in the preceding step give us license to assume the following: for all j ∈ Y and i ∈ X \ {1}. Denote ǫ (i,j) := p XY (i, j) for i = 1 and let Note that p XY (1, j) = 1 |Y| − δ j and that j∈Y δ j = ǫ. Since we wish to upper-bound H(X|Y ), we proceed by upper-bounding each term in the expectation: where the inequality follows because the vector ( Observe that the last expression is concave in δ j |Y|. We can overestimate as follows.
This completes the proof of the bound. To see that it is tight, let ǫ ∈ (0, 1 − 1 |X | ] be given and consider the following probability distributions.
for i ∈ X \ {1}. Evidently, the two are separated by ǫ in total variation distance and the associated equivocations saturate the bound.

III. CONCLUDING REMARKS
We have presented a proof of a tight uniform continuity bound for the conditional Shannon entropy. The bound is independent of the alphabet size of the conditioning system. However, we have assumed in the proof that the conditioning system has finite support. It would be interesting to prove the bound without such an assumption, but we leave that as an open problem.
The proof depends crucially on the invariance of H(X|Y ) under the action of S X |Y . Various forms of conditional Rényi entropies share this invariance [19], [20]. More generally, entropic quantities of interest are invariant under the action of some subgroup of the symmetric group. For example, the mutual information I(X; Y ) = H(X) + H(Y ) − H(XY ) is invariant under "local" permutations of indices, i.e., tensor products of permutations of X and Y labels. We believe such symmetries provide a path towards a better understanding of the behaviors of the corresponding quantities in terms of continuity and beyond.