weaksourcev20

{Towards Weak Source Coding} {Aman Chawla IIT Delhi and REAL Institute, Gurugram, India} {December 31, 2025}

Introduction

In this paper we will attempt to lower the upper bound $$ on the source coding probability of error. The paper assumes readers' familiarity with source coding. Consider that in traditional source coding^†A very simply described - and hence accessible - version of Shannon's source coding theorem can be found in [1]., the probability of error of the encoder is bounded above by a small positive constant $$. This means that the error-exponent, which captures the rate of decay of the probability of error with block length, is bounded below by $-{}{N}$. So if we change ${}{2}$, say, and so reduce the upper bound, it is equivalent to adding ${2}{N}$ to the lower bound. A larger lower bound means that the rate of decay of the probability of error with blocklength is higher. In this work, we will thus aim for a reduction in the upper bound.

In the traditional source coding procedure, if the input sequence doesn't lie in the typical set, the encoder outputs an arbitrary $n(H(X)+)$ bit number which represents the error condition. In this paper we will ask the question whether we can do better in a specific sense.

Figure [fig:The-space-of] shows the space of all sequences divided into the typical and atypical subsets. The typical sequences are encoded according to their position in a numbered list. They constitute a high probability set. The atypical sequences lead to the error declaration.

Innovation and its Analysis

Let $A_{}^{n}$ denote the typical set and let $B_{}^{n}$ be the associated non-typical set. Their union is the space of all sequences, ${X}^{n}$. If the sequence $x^{n}$ does not belong to the typical set, instead of declaring an error, we classify the sequence into one of $k$ classes or clusters within $B_{}^{n}$. Suppose we classify it into the $j^{th}$ class where $j{ 1,...,k} $. Further, suppose the classification obeys the rule that $d(x^{n},_{j})$ is the lowest amongst choices of $j{ 1,...,k} $, $$ standing for the mean of a cluster.

In more detail, we output an error, but specify that it is of the $j^{th}$ type. Since we want to encode the source, we attempt to do unsupervised learning within $B_{}^{n}$. We keep building up $k$ clusters whenever $x^{n}$ lies in $B_{}^{n}$. After a while of `training,' the cluster-formation will more or less represent the part of the source that generates $B_{}^{n}$ members.

We will extend the encoding scheme in such a way that $(k)$ bits will be appended to the $n(H(X)+)$ bits previously created for the typical sequences. If we include another bit to specify that we are now beginning to index from the atypical set, then the net length of the encoding becomes $1+n(H(X)+)$+$(k)$ bits.

At the same time, the error will be constrained by the size of the largest of the $k$ clusters. Since $k2$, the size of the largest cluster belongs to the closed interval $[1,|B_{}^{n}|-k+1]$. In other words, the ambiguity is constrained by $|B_{}^{n}|-k+1$ as opposed to $|B_{}^{n}|$. These $(k-1)$ fewer sequences are the means of the unity-sized (non-largest) clusters. Let $B'$ denote the set with the size $|B_{}^{n}|-k+1$. Since $B_{}^{n}$ is the atypical set, the probability of lying in it is upper-bounded (strictly) by $$. In this section, we are interested in saying something about the probability of lying in $B'$.

Note that $B_{}^{n}$ contains such sequences $x^{n}$ as having $p(x_{1},...,x_{n})<2^{-n(H(X)+)}$ or $p(x_{1},...,x_{n})>2^{-n(H(X)-)}$. Denote the former inequality as specifying a VLPZ or Very Low Probability Zone and the latter inequality as specifying a VHPZ or Very High Probability Zone. The typical sequences lie in MPZ or the Medium Probability Zone between these two extremes. Also note that sequences within a cluster are "close" to each other, i.e., they are separated by a few bit flips only. Thus, their probabilities are alike. Hence, a cluster will lie either completely in VHPZ or completely in VLPZ.

Suppose the largest cluster lies in VLPZ and the other $k-1$ mean sequences are in VHPZ. Then the probability of $B'$ is approximately $0$. On the other hand, suppose the largest cluster lies in VHPZ and the other $k-1$ mean sequences are in VLPZ. Then the probability of $B'$ is the probability of the largest cluster. Denote this probability as PLC. Clearly PLC is strictly less than the probability of $B_{}^{n}$ which in turn is strictly less than $$.

Conclusion

To summarize, if PoE1 is strictly less than $$, and requires $n(H(X)+)$ bits for operationalization^†By operationalization, we refer to the process of enumerating the members of the set whose probability we are discussing. This enumeration requires a certain number of bits for the description of the enumerated sequences., and additionally, if PoE2 is equal to PLC which is strictly less than PoE1, and requires $1+n(H(X)+)+(k)$ bits for operationalization, it is easy to show, as is done in the Appendix, that the exponent corresponding to the second situation can possibly be better in some similar settings.

To conclude, we have demonstrated that there may be room for improvement in the traditional source coding error exponent by making use of a simple $k$-means clustering approach to the atypical sequences. Thus machine learning might be of aid in generating (marginal) improvements to the source coding reliability function. In upcoming work, the authors will focus on a quantum information theoretic version of the present paper. We will also utilize MATLAB simulations to concretely see the gains from using machine learning, as was done in the channel coding case [2].

Appendix 1

Consider two cases:

Case 1

The error exponent is $e_{1}$. The PoE is PoE1. The blocklength of sequences is $N_{1}$. Thus, we can write:

Case 2

The error exponent is $e_{2}$. The PoE is PoE2. The blocklength of sequences is $N_{2}$. Thus, we can write:

From Section [sec:Conclusion], we have

and

We ask the question: when is $e_{2}>e_{1}$? Expanding the LHS and the RHS in this question, we obtain the relation

from the definitions. This implies that

Upon multiplying throughout by negative unity, we get

Utilizing the bound on $PoE1$ we get

Upon rearranging we get

This can be simplified to

For large $n$, the second term on the RHS vanishes, but the third term can linger if the number of clusters formed within the atypical set also increases. Denote,

Thus, for large $n$,

where $>0$. These considerations imply that $e_{2}

We next study the other extreme case wherein there were exactly $k$ sequences in $B_{}^{n}$, each forming its own cluster. Here suppose that the largest cluster is in VLPZ. Then $P(B')<2^{-n(H(X)+)}$. On the other hand, if the largest cluster is in VHPZ, then $P(B')>2^{-n(H(X)-)}$. Since the error depends upon the size of the largest cluster, we can quantify it exactly as $PoE2=P({{Cluster}1mean}) P({Cluster1})+...+P({Clusterkmean}) P({Clusterk})$. This gives the upper bound $PoE2<2^{-n(H(X)+)}$.

We use the just obtained bound. We have

and

We again ask the question: when is $e_{2}>e_{1}$? Expanding the LHS and the RHS in this question, we obtain the relation

which implies that

Upon multiplying throughout by negative unity we get

Utilizing the bound (Equation ([eq:poe1bound])) on $PoE1$ we get

Upon rearranging we get

This can be simplified to

For large $n$, the second term on the RHS vanishes, but the third term can linger if the number of clusters formed within the atypical set also increases. Denote,

Thus, for large $n$,

where $>0$. Compare Equation ([eq:poe2secondextreme]) with,

which is the inequality one obtains based on Equation ([eq:poe2bound]). The comparison yields that both inequalities can be satisfied if

which, being a non-integer-logarithmic lower bound that involves the number of clusters $k$ on the LHS, shows that there is a region wherein having $k$-means clustering in the atypical set can improve the reliability function in this extreme setting. Since the usual setting will possibly lie somewhere in between the two extreme regimes studied in Section [sec:Analysis-of-Innovation] and the present Appendix, we may conclude that a gain (i.e. $e_{2}>e_{1}$) from machine learning is not ruled out.