# An Information Theoretic Proof of the Chernoff-Hoeffding Inequality

Olivier Rioul, Patrick Solé

<figure><img src="image_1.png" /></figure>

## To cite this version:

Olivier Rioul, Patrick Solé. An Information Theoretic Proof of the Chernoff-Hoeffding Inequality. Information Processing Letters, 2025, 190, pp.106582. 10.1016/j.ipl.2025.106582. hal-05047248

HAL Id: hal-05047248

https://hal.science/hal-05047248v1

Submitted on 8 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
# An Information Theoretic Proof of the Chernoff-Hoeffding Inequality

Olivier Rioul<sup>a</sup>, Patrick Solé<sup>a,b</sup>

<sup>a</sup>LTCI, Télécom Paris, Institut Polytechnique de Paris, France

<sup>b</sup>Institut de Mathématiques de Marseille (CNRS, Aix-Marseille University), Marseilles, France

## Abstract

The Chernoff bound is a well-known upper bound on the tail of binomial distributions of parameter $1/2$ involving the binary entropy function. Hoeffding's inequality (or the Chernoff-Hoeffding inequality) is a generalization for binomial distributions of parameter $1 - 1/q$, involving the $q$-ary entropy function (with $q \ge 2$), which can be written in terms of the Kullback-Leibler divergence and is related to the bound in Fano's inequality. We give an information theoretic proof of that bound, and sketch some applications to channel and source coding. We also derive a refined bound which is always sharper.

**Keywords:** Chernoff bound, Hoeffding's inequality, Shannon Entropy, Hilbert Entropy function, Kullback-Leibler divergence

**2020 MSC:** Primary 68 P30, Secondary 94 B25

## 1. Introduction

The Chernoff bound is a concentration inequality for sums of symmetric Bernoulli random variables (of parameter $1/2$), of popular use in information theory [3, 11, 10], extremal combinatorics [1], and theoretical computer science in general [7]. It can be written as

$$ \sum_{i=0}^{d} \binom{n}{i} \le \exp(nh_2(\frac{d}{n})) \quad (1) $$

where $h_2(x)$ is the binary entropy function defined for $0 < x < 1$ as

$$ h_2(x) = -x \log x - (1-x) \log(1-x). \quad (2) $$
Hoeffding's inequality [4] for sums of Bernoulli random variables of parameter $1 - \frac{1}{q}$ is a similar inequality:

$$ \sum_{i=0}^{d} \binom{n}{i} (q-1)^i \le \exp(nh_q(\frac{d}{n})) \quad (3) $$

where $h_q(x)$ is the q-ary entropy function defined for $0 < x < \frac{q-1}{q}$ as

$$ h_q(x) = -x \log x - (1-x) \log(1-x) + x \log(q-1), \quad (4) $$

also called Hilbert entropy function in [6, § 13.5] and in [12, p. 14]—although we could not find an explanation as to why such a function is named after Hilbert.

**Remark 1** (Base of Logarithms and Exponentials). Throughout this note, logarithms and exponentials can be taken to any base. The reciprocal function of the logarithm $\log(\cdot)$ is denoted $\exp(\cdot)$ in the same base. Thus for example,

* to base 2, $\log 2 = 1$ and $\exp(x) = 2^x$;

* to base q, $\log q = 1$ and $\exp(x) = q^x$;

* to natural base e, $\log x = \ln x$ and $\exp(x) = e^x$.

It is customary, in coding theory [6, 9, 12], to use logarithms to base 2 in the expression (2) of the binary entropy, and logarithms to base q in the expression (4) of the q-ary entropy. With this convention, the upper bound in Chernoff's inequality (1) writes $2^{nh_2(\frac{d}{n})}$ while the upper bound in Hoeffding's inequality (3) writes $q^{nh_q(\frac{d}{n})}$.

In this work, we recall the classical analytic proof of Hoeffding's inequality, which is in fact a naive saddle point method [5]. Then we give an information theoretic proof, which yields a sharper inequality for a modified parameter d, hereby denoted $d'$. We give several applications of this bound, notably to combinatorial coding and source coding.

This note is arranged as follows. The next section collects the notions and notations needed in the rest of the paper. Section 3 recalls the analytic proof and Section 4 derives the information theoretic proof. Section 5 discusses an improvement of the information theoretic bound using the modified parameter $d'$. Finally, Section 6 gives applications to channel and source coding.
## 2. Information Theoretic Background

**Definition 2 (q-ary Entropies).** Let $q > 1$ be an integer. The q-ary entropy of a probability distribution $(p_0, p_1, \dots, p_{q-1})$ is

$$H(p_0, p_1, \dots, p_{q-1}) = \sum_{i=0}^{q-1} p_i \log \frac{1}{p_i} \qquad (5)$$

The q-ary relative entropy (a.k.a. Kullback-Leibler divergence) between two probability distributions $(p_0, p_1, \dots, p_{q-1})$ and $(r_0, r_1, \dots, r_{q-1})$ is

$$D(p_0, p_1, \dots, p_{q-1} \| r_0, r_1, \dots, r_{q-1}) = \sum_{i=0}^{q-1} p_i \log \frac{p_i}{r_i} \qquad (6)$$

In particular, the binary entropy and binary relative entropy are

$$h_2(p) \triangleq H(p, 1-p) = p \log \frac{1}{p} + (1-p) \log \frac{1}{1-p} \qquad (7)$$

$$d_2(p \| r) \triangleq D(p, 1-p \| r, 1-r) = p \log \frac{p}{r} + (1-p) \log \frac{1-p}{1-r}.$$

Note that $h_2(p)$ is defined for $0 \le p \le 1$ and increasing for $0 \le p \le 1/2$.

Maximum entropy is a classical concept (see e.g., [3, Chap. 12], [11, Chap. 4]):

**Proposition 3 (Max q-ary Entropy).**

1. The maximum q-ary entropy is attained for a uniform distribution:

$$H(p_0, p_1, \dots, p_{q-1}) \le \log q \qquad (8)$$

with equality if and only if $p_i = 1/q$ for all i.

2. The maximum q-ary entropy under the constraint $p_0 = 1 - \alpha$ is attained for the distribution $(1 - \alpha, \frac{\alpha}{q-1}, \dots, \frac{\alpha}{q-1})$:

$$H(p_0 = \alpha, p_1, \dots, p_{q-1}) \le h_q(\alpha) \triangleq h(\alpha) + \alpha \log(q-1) \qquad (9)$$

with equality if and only if $p_i = \frac{\alpha}{q-1}$ for $i \ne 0$.
Proof. We use the basic information inequality [3, 11, 10]

$$D(p_0, p_1, \dots, p_{q-1} \| r_0, r_1, \dots, r_{q-1}) \ge 0 \quad (10)$$

with equality = 0 if and only if $p_i = r_i$ for all $i$:

1. Take $r_i = 1/q$ for all $i$:

$$D(p_0, \dots, p_{q-1} \| \frac{1}{q}, \dots, \frac{1}{q}) = \log q - H(p_0, \dots, p_{q-1}) \ge 0.$$

2. Take $r_1 = p_1 = \alpha$ and $r_i = \frac{\alpha}{q-1}$ for $i \ne 0$:

$$D(p_0 \dots p_{q-1} \| \alpha, \frac{\alpha}{q-1} \dots \frac{\alpha}{q-1}) = h(\alpha) + \alpha \log(q-1) - H(p_0 \dots p_{q-1}) \ge 0.$$

□

**Remark 4** (Fano Bound). The second inequality in Proposition 3 is a particular instance of Fano's inequality for unconditional entropies, where $\alpha$ represents a probability of error (see e.g., [3, § 2.10],[11, § 4.3], and [10, § 3.6]). For instance, if $X \in \{0, 1, \dots, q-1\}$ is an error random variable having distribution $(p_0, p_1, \dots, p_{q-1})$, then $X = 0$ represents zero error, of probability $p_0 = 1 - \alpha$ while $X \ne 0$ is the error event of probability $p_1 + \dots + p_{q-1} = \alpha$. The Fano inequality writes

$$H(X) \le h_q(\alpha) = h_2(\alpha) + \alpha \log(q-1), \quad (11)$$

where the term $h_2(\alpha)$ is the (binary) entropic uncertainty that an error occurs (or not), and the second term, weighted by the error probability $\alpha$, the remaining maximum entropy for the remaining possible $q-1$ nonzero values of $X$, which is $\log(q-1)$.

Notice that $h_q(\alpha)$ is well-defined and concave for $0 \le \alpha \le 1$ but increasing only for $0 \le \alpha \le 1 - \frac{1}{q}$. In the binary case one recovers of course the binary entropy.

By the above derivation of the maximum entropy attained by the uniform distribution when $(p_0, p_1, \dots, p_{q-1}) = (1 - \alpha, \frac{\alpha}{q-1}, \dots, \frac{\alpha}{q-1})$, one has

$$D(1-\alpha, \frac{\alpha}{q-1}, \dots, \frac{\alpha}{q-1} \| \frac{1}{q}, \dots, \frac{1}{q}) = \log q - H(1-\alpha, \frac{\alpha}{q-1}, \dots, \frac{\alpha}{q-1}) = \log q - h_q(\alpha) \quad (12)$$

This divergence is, therefore, equal to the difference $\log q - h_q(\alpha)$, which can be interpreted as the loss of the maximal $q$-ary entropy due to the error probability constraint $p_1 = 1 - \alpha$ (instead of $1/q$). We make the following trivial, but apparently not so well-known remark:
**Lemma 5 (Max Entropy Loss).** The loss of maximal q-ary entropies due to the error probability constraint $p_1 = 1 - \alpha$ (instead of $1/q$) equals the binary divergence between the probability parameters $1 - \alpha$ and $1/q$:

$$ \log q - h_q(\alpha) = d_2(1 - \alpha \|_{q}^{\frac{1}{q}}) = d_2(\alpha \|_{1 - \frac{1}{q}}) \quad (13) $$

*Direct Proof by Calculation.* $\log q - h_2(\alpha) - \alpha \log(q-1) = \alpha \log(\alpha \frac{q}{1-q}) + (1 - \alpha) \log(q(1-\alpha)) = d_2(\alpha \|_{1 - \frac{1}{q}}) = d_2(1 - \alpha \|_{\frac{1}{q}})$. $\square$

The above proof does not actually explain the fundamental reason why these two divergences $D(1-\alpha, \frac{\alpha}{q-1}, \dots, \frac{\alpha}{q-1} \|_{q}^{\frac{1}{q}}, \dots, \frac{\alpha}{q-1} \|_{q}^{\frac{1}{q}})$ and $d_2(\alpha \|_{1-\frac{1}{q}})$ coincide. The following information theoretic proof is more satisfactory in this respect, and applies to any divergence $D(P \| Q)$ between probability distributions $P$ and $Q$ satisfying the *data processing inequality* (DPI):

$$ D(W(P) \| W(Q)) \le D(P \| Q) \quad (14) $$

where $W$ is any Markov channel [3, 10, 11]. Not only does the Kullback-Leibler divergence satisfies the DPI, but more generally, any Csiszár $f$-divergence or Rényi $\alpha$-divergence also satisfies the DPI [10].

*Information Theoretic Proof of Lemma 5.* On one hand, by the DPI applied to the channel $X \in \{0, 1, \dots, q-1\} \to 1_{X \neq 0} = Y \in \{0, 1\}$ we have

$$ d_2(1 - \alpha \|_{q}^{\frac{1}{q}}) = D(1 - \alpha, \alpha \|_{q}^{\frac{1}{q}}, \frac{q-1}{q}) \le D(1 - \alpha, \frac{\alpha}{q-1}, \dots, \frac{\alpha}{q-1} \|_{q}^{\frac{1}{q}}, \dots, \frac{\alpha}{q-1} \|_{q}^{\frac{1}{q}}). \quad (15) $$

On the other hand, by the DPI applied to the channel $Y \in \{0, 1\} \to X = YU \in \{0, 1, \dots, q-1\}$ where $U$ is uniformly distributed in $\{1, \dots, q-1\}$, we obtain the opposite inequality:

$$ D(1 - \alpha, \frac{\alpha}{q-1}, \dots, \frac{\alpha}{q-1} \|_{q}^{\frac{1}{q}}, \dots, \frac{\alpha}{q-1} \|_{q}^{\frac{1}{q}}) \le D(1 - \alpha, \alpha \|_{q}^{\frac{1}{q}}, \frac{q-1}{q}) = d_2(1 - \alpha \|_{q}^{\frac{1}{q}}). \quad (16) $$

This shows the desired equality of divergences for any type of divergence satisfying the data processing inequality. $\square$

### 3. Hoeffding's Inequality: Classical Proof

**Theorem 6 (Hoeffding's Inequality [4]).** Let $d$ be a natural integer such that $\frac{d}{n} \le 1 - \frac{1}{q}$. Then

$$ \sum_{i=0}^{d} \binom{n}{i} (q-1)^i \le \exp(n h_q(\frac{d}{n})). \quad (17) $$
**Remark 7.** The classical form of Hoeffding's inequality is rather an upper bound on the cumulative binomial distribution of parameter p:

$$ \sum_{i=0}^{d} \binom{n}{i} p^i (1-p)^{n-i} \le \exp(-n d_2(\frac{d}{n} \|p\)) \quad (18) $$

but this amounts the same for $p = 1 - \frac{1}{q}$ since then $p^i(1-p)^{n-i} = (q-1)^i q^{-n}$ and by Lemma 5,

$$ q^n \exp(-n d_2(\frac{d}{n} \|1 - \frac{1}{q}\)) = \exp(n(\log q - d_2(\frac{d}{n} \|1 - \frac{1}{q}\))) = \exp(n h_q(\frac{d}{n})). \quad (19) $$

The classical proof of Hoeffding's inequality uses a (generalized) Chernoff inequality for sum of i.i.d. Bernoulli variables, but it can be rewritten as a simple proof as follows.

“Classical Proof”. Let $\alpha = \frac{d}{n}$ and $x \in (0, 1]$. Since for $i \le d$, $x^{i-d} \ge 1$, we have the following Markov inequality:

$$ \sum_{i=0}^{d} \binom{n}{i} (q-1)^i \le \sum_{i=0}^{n} \binom{n}{i} (q-1)^i x^{i-d} = (1+(q-1)x)^n x^{-d} = \exp(n \varphi(x)) \quad (20) $$

where

$$ \varphi(x) = -\alpha \log x + \log(1 + (q-1)x) \quad (21) $$

has derivative

$$ \varphi'(x) = -\frac{\alpha}{x} + \frac{q-1}{1+(q-1)x} \ge 0 \iff x \ge \frac{1}{q-1} \cdot \frac{\alpha}{1-\alpha} \quad (22) $$

Thus $x^* = \frac{1}{q-1} \cdot \frac{\alpha}{1-\alpha}$, which lies in $(0, 1]$ since $\alpha \le 1 - \frac{1}{q}$, achieves the minimum

$$ \phi(x^*) = -\alpha \log\left(\frac{1}{q-1} \cdot \frac{\alpha}{1-\alpha}\right) + \log\frac{1}{1-\alpha} = h_q(\alpha). \quad (23) $$

**Remark 8 (Saddle Point Method).** In hindsight, $x^*$ is a saddle point in the sense of [5] for the generating functions $f(z) = (1 + (q-1)z)$ and $g(z) = 1$. Using the techniques in [5] it is possible to derive an asymptotic equivalent for $n \to \infty$ and fixed $q$ of the left-hand side of Hoeffding's inequality. This equivalent coincides with the right-hand side up to subexponential terms as is already clear from [6, Lemma 2.10.3 p. 91].
### 4. Hoeffding's Inequality: Information Theoretic Proof

The above classical proof works for any real $q > 1$ but does not explain why this particular $q$-ary entropy $h_q(\cdot)$ comes into play. The following proof of Hoeffding's inequality is in this respect much more satisfactory.

*Information Theoretic Proof.* The l.h.s. of Hoeffding's inequality is the number of words $x$ in $(\mathbb{F}_q)^n$ of Hamming weight $w_H(x) \le d$ and length $n$. Let $X = (X_1, X_2, \dots, X_n)$ be chosen uniformly at random from this set, where each $X_k \in \mathbb{F}_q$. Since $X$ is uniformly distributed, its entropy equals

$$H(X) = \log \sum_{i=0}^{d} \binom{n}{i} (q-1)^i. \qquad (24)$$

By symmetry, the $X_k$'s are identically distributed, and we have the following well-known entropic inequality [3, 11, 10]

$$H(X) = H(X_1, X_2, \dots, X_n) \le H(X_1) + H(X_2) + \dots + H(X_n) = nH(X_1). \qquad (25)$$

Again by symmetry, conditioned on fixed Hamming weight $w_H(X) = i$, the probability that $X_1 \ne 0$ is $\frac{i}{n}$. Thus

$$\mathbb{P}(X_1 = 0 | w_H(X) = i) = 1 - \frac{i}{n}. \qquad (26)$$

It follows from Proposition 3 (part 2) that, conditioned on $w_H(X) = i$,

$$H(X_1 | w_H(X) = i) \le h_q\left(\frac{i}{n}\right). \qquad (27)$$

(In fact equality holds, but this is not needed in the proof). Since $h_q(\alpha)$ is increasing for $\alpha \le 1 - \frac{1}{q}$,

$$H(X_1 | w_H(X) = i) \le h_q\left(\frac{d}{n}\right) \qquad (28)$$

where the r.h.s. does not depend on $i = w_H(X)$. Therefore, taking the expectation over $w_H(X) \in \{0, 1, \dots, d\}$ we obtain

$$H(X_1) \le h_q\left(\frac{d}{n}\right) \qquad (29)$$

which ends the proof. □
**Remark 9** (Reduction from the $q$-ary to the Binary Case). Hoeffding's inequality in the $q$-ary case may also be easily deduced from the corresponding inequality in the binary case, but only provided that $\frac{d}{n} \le \frac{1}{2}$:

$$ \sum_{i=0}^{d} \binom{n}{i} \le \exp(nh_2(\frac{d}{n})) \quad (30) $$

Indeed, if the latter inequality holds, then

$$ \sum_{i=0}^{d} \binom{n}{i} (q-1)^i \le (q-1)^d \sum_{i=0}^{d} \binom{n}{i} \le (q-1)^d \exp(nh_2(\frac{d}{n})) = \exp(nh_q(\frac{d}{n})) \quad (31) $$

Thus, if $\frac{d}{n} \le \frac{1}{2}$, we may use the same information theoretic proof as above, simplified to the binary case $q = 2$, where part 2 of Proposition 3 is not even needed. Note, however, that this simplified proof does not extend to values of $d$ such that $\frac{1}{2} < \frac{d}{n} \le 1 - \frac{1}{q}$.

## 5. Improved Bound

As a consequence of the above information theoretic proof in the preceding section, we have the following refined bound.

**Corollary 10.** For any $d \le n$ define

$$ d' = \frac{\sum_{i=0}^{d} i \binom{n}{i} (q-1)^i}{\sum_{i=0}^{d} \binom{n}{i} (q-1)^i} \le d, \quad (32) $$

Then the following bound improves (17) with a smaller exponent $d' \le d$:

$$ \sum_{i=0}^{d} \binom{n}{i} (q-1)^i \le \exp(n h_q(\frac{d'}{n})). \quad (33) $$

*Proof.* A closer look at the above information theoretic proof in the preceding section shows in fact the inequality

$$ \sum_{i=0}^{d} \binom{n}{i} (q-1)^i \le \exp(n \sum_{i=0}^{d} p_i h_q(\frac{i}{n})), \quad (34) $$
where

$$p_i = \mathbb{P}(w_H(X) = i | w_H(X) \le d) = \frac{\binom{n}{i} (q-1)^i}{\sum_{i=0}^{d} \binom{n}{i} (q-1)^i} \quad (35)$$

Since $h_q(\alpha)$ is concave,

$$\sum_{i=0}^{d} p_i h_q\left(\frac{i}{n}\right) \le h_q\left(\sum_{i=0}^{d} p_i \frac{i}{n}\right), \quad (36)$$

and, combining with (34) we obtain

$$\sum_{i=0}^{d} \binom{n}{i} (q-1)^i \le \exp(n h_q(\frac{d'}{n})) \quad (37)$$

where

$$d' = \mathbb{E}(w_H(X) | w_H(X) \le d) = \sum_{i=0}^{d} ip_i \quad (38)$$

is given by (32). □

<table><caption>Table 1: Bounds for $n = 20$, $q = 3$</caption><thead><tr><th>d</th><th>Σ<sup>d</sup><sub>i=0</sub> (n/i) (q-1)<sup>i</sup></th><th>exp(n h<sub>q</sub>(d'/n)) (33)</th><th>exp(n h<sub>q</sub>(d/n)) (Hoeffding)</th></tr></thead><tbody><tr><td>1</td><td>41</td><td>96</td><td>106</td></tr><tr><td>2</td><td>801</td><td>2,288</td><td>2,664</td></tr><tr><td>3</td><td>99,201</td><td>30,512</td><td>37,557</td></tr><tr><td>5</td><td>583,569</td><td>1,806,877</td><td>2,452,059</td></tr><tr><td>6</td><td>3,064,209</td><td>9,133,781</td><td>12,944,339</td></tr><tr><td>7</td><td>12,986,769</td><td>36,516,145</td><td>53,809,632</td></tr><tr><td>8</td><td>45,235,089</td><td>117,823,292</td><td>179,450,647</td></tr><tr><td>9</td><td>131,230,609</td><td>311,350,993</td><td>485,699,607</td></tr><tr><td>10</td><td>320,420,753</td><td>681,702,205</td><td>1,073,741,823</td></tr></tbody></table>

**Remark 11.** From (38) we may interpret $d'$ as the average Hamming weight in the Hamming ball of radius $d$, whose volume $V_d$ is the denominator in the expression (32).

The numerics like those of Table 1 show that (33) is significantly tighter than Hoeffding's inequality.
Some elementary properties of the $d \mapsto d'$ transformation are as follows.

**Proposition 12.** Consider the mapping $\Phi : d \mapsto d'$ for any $d \in \{0, 1, \dots, n\}$. Then

1. The map $d \mapsto d'$ is strictly increasing;

2. $n' = n^{\frac{q-1}{q}}$, where $n' = \Phi(n)$;

3. $\frac{d'}{n} \le \frac{q-1}{q}$ (even when $\frac{d}{n}$ does not satisfy this inequality);

4. If $\frac{d}{n} \to \alpha \in (0, 1 - \frac{1}{q}]$ when $n \to \infty$ then $h_q(\frac{d'}{n}) \to h_q(\alpha)$;

5. $d' \ge \sqrt{\frac{d}{8(1-d/n)}}$;

6. for any $0 \le k \le d$, $d' \le d - k \frac{V_{d-k}}{V_d}$ where $V_k$ denotes the volume of the Hamming ball of radius $k$. In particular, letting $\epsilon_k = \frac{\binom{n}{k} (q-1)^k}{V_d} \ll 1$ be the proportion of words of weight $k$ in the Hamming ball of radius $d$, we have

$$d' \le \min\left(d - 1 + \epsilon_d, d - 2 + 2(\epsilon_{d-1} + \epsilon_d)\right). \quad (39)$$

*Proof.*

1. Let $V = \sum_{i=0}^{d} \binom{n}{i} (q-1)^i$ be the volume of the Hamming ball of radius $d$, $N = \sum_{i=0}^{d} i \binom{n}{i} (q-1)^i$, and $h = \binom{n}{d+1} (q-1)^{d+1}$. We need to check that $d' < (d+1)'$, that is,

$$\frac{N}{V} < \frac{N + (d + 1)h}{V + h}, \quad (40)$$

that is, $Nh < (d+1)Vh$ by clearing denominators. Now we have, by definition, $N \le dV < (d+1)V$. The result follows.

2. Here $n'$ is the average of a binomial law of parameter $p = 1 - 1/q$, which equals $np = n^{\frac{q-1}{q}}$.

3. Immediate by 1 and 2.

4. Since $d' \le d$, by the monotonicity of the $q$-ary entropy we have $h_q(\frac{d'}{n}) \le h_q(\frac{d}{n})$, and therefore

$$\limsup_{n \to \infty} h_q(\frac{d'}{n}) \le h_q(\alpha).$$

The inequality

$$\liminf_{n \to \infty} h_q(\frac{d'}{n}) \ge h_q(\alpha)$$
is obtained by taking logs and dividing by $n$ the inequality (33), upon letting $n \to \infty$ and invoking [6, 5]

$$ \lim_{n \to \infty} \frac{1}{n} \log\left(\sum_{i=0}^{d} \binom{n}{i} (q-1)^i\right) = h_q(\alpha). $$

The result follows by combining the inequalities of superior and inferior limits.

5. Writing the definition $d' = \frac{N}{V}$. We know by Hoeffding's inequality that $V \le \exp(n h_q(\alpha))$ where $\alpha = \frac{d}{n}$. Bounding below the sum $N$ by its last term yields $N \ge d \binom{n}{d} (q-1)^d$. By [9, Chapter 10, Lemma 7 p. 309] we get $\binom{n}{d} \ge \frac{2^{nh_2(\alpha)}}{\sqrt{8n\alpha(1-\alpha)}}$. The result follows then upon noticing that like in Remark 9 (Equation (31)) we have $(q-1)^d \exp(nh_2(\frac{d}{n})) = \exp(nh_q(\frac{d}{n}))$.

6. By splitting the sum $N_d = \sum_{i=0}^{d} i \binom{n}{i} (q-1)^i$ for $i \le d-k$ and $i > d-k$,

$$ N_d \le (d-k)V_{d-k} + d(V_d - V_{d-k}) = dV_d - kV_{d-k}. \quad (41) $$

Dividing by $V_d$ gives the announced inequality $d' \le d-k \frac{V_{d-k}}{V_d}$. Numerical calculations show that the optimal value of $k$ is typically $k=1$ or $2$ for reasonable values of $q, n$ and $d$. Since $\frac{V_{d-1}}{V_d} = 1-\epsilon_d$ and $\frac{V_{d-2}}{V_d} = 1-\epsilon_{d-1}$ this yields (39). $\square$

# 6. Applications

## 6.1. Improvement of Liu et al.'s Cover Metric Bound

In [8, Lemma 2], Liu et al. proved a cover metric bound of the form

$$ |\mathcal{B}_C(A, d)| \le (d+1) \exp\left((m+n)h_2\left(\frac{d}{m+n}\right)\right) q^{md} \quad (42) $$

where $\mathcal{B}_C(A, d)$ is the cover metric ball of center $A$ (a $m \times n$ matrix with entries in $\mathbb{F}_q$) with radius $d$ of a cover metric code $C$. Their proof is based on the simple inequality

$$ \binom{m+n}{d} \le 2^{(m+n)h_2(\frac{d}{m+n})} \quad (43) $$

but as seen in the following, Hoeffding's inequality is stronger. The following lemma was also proved in [13].
**Lemma 13** (Improved Lemma of Liu et al.).

$$|\mathcal{B}_C(A, d)| \leq \exp\left((m+n)h_2\left(\frac{d}{m+n}\right)\right)q^{md} \quad (44)$$

*Proof.* Proceed as in the proof of [8, Lemma 2] to show that

$$|\mathcal{B}_C(A, d)| \leq \sum_{r=0}^{d} \binom{m+n}{r} q^{mr} \quad (45)$$

then apply Hoeffding's inequality with $m+n$ in place of $n$ and $q^m$ in place of $(q-1)$ gives

$$|\mathcal{B}_C(A, d)| \leq \exp\left((m+n)h_{q^m+1}\left(\frac{d}{m+n}\right)\right) \quad (46)$$

where

$$h_{q^m+1}\left(\frac{d}{m+n}\right) = h_2\left(\frac{d}{m+n}\right) + \frac{d}{m+n}\log(q^m) \quad (47)$$

which gives the announced inequality. □

## 6.2. Rate-Distorsion Theory

When a block code is used as a codebook for data compression an important parameter is the *covering radius*, which measures the largest possible distorsion [2]. A lower bound on the covering radius $\rho$ of a $q$-ary $[n, k]$ code is the sphere covering bound

$$q^{n-k} \leq \sum_{i=0}^{\rho} \binom{n}{i} (q-1)^i \quad (48)$$

Upon using Hoeffding's inequality on the r.h.s. this bound entails, after taking logarithms on both sides,

$$1 - R \leq h_q\left(\frac{\rho}{n}\right) \quad (49)$$

where $R = \frac{k}{n}$ is the code rate. This finite bound is formally the same as the asymptotic version of the sphere covering bound

$$1 - R \leq H_q(\rho), \quad (50)$$

where $R = \limsup_{n \to \infty} \frac{k_n}{n}$, and $\rho = \liminf_{n \to \infty} \frac{\rho_n}{n}$ for a series of $[n, k_n]$ codes of covering radii $\rho_n$.
### 6.3. Gilbert-Varshamov bound

The Gilbert-Varshamov (GV) bound states that there are unrestricted codes of length $n$ over an alphabet of size $q$ with a minimum distance $d$ as good as

$$|C| \geq \frac{q^n}{\sum_{i=0}^{d-1} \binom{n}{i} (q-1)^i}.$$

It can actually be regarded as a consequence of the sphere covering bound of the previous paragraph for optimal codes [2]. Upon using Hoeffding's inequality on the r.h.s. this bound entails, after taking logarithms on both sides,

$$1 - R \leq h_q\left(\frac{d-1}{n}\right), \qquad (51)$$

where $R = \frac{k}{n}$ is the code rate. This finite bound is formally the same as the asymptotic version of GV bound

$$1 - R \leq H_q(\delta), \qquad (52)$$

where $R = \limsup_{n \to \infty} \frac{k_n}{n}$, and $\delta = \liminf_{n \to \infty} \frac{d_n}{n}$ for a series of length $n$ codes of minimum distances $d_n$, and sizes $|C_n| = q^{k_n}$.

## References

[1] Alon N., and Spencer J. H., *The probabilistic method*, John Wiley & Sons, 2016.

[2] Cohen G., Honkala I., Litsyn S., Lobstein A., *Covering Codes*, North Holland, Amsterdam, 1997.

[3] Cover, T.M., Thomas, J.A.: *Elements of Information Theory*. John Wiley & Sons, Hoboken (1st Ed. 1990, 2nd Ed. 2006).

[4] Hoeffding, W. (1963). "Probability Inequalities for Sums of Bounded Random Variables," *Journal of the American Statistical Association*, 58 (301): 13–30.

[5] Gardy D., Solé P., "Saddle Point Techniques in Asymptotic Coding Theory," *Algebraic Coding 1991*, Springer Lect. Not. 573: 75–81 (1991).
[6] Huffman W. C. and V. Pless V., *Fundamentals of Error-Correcting Codes*, Cambridge Univ. Press, Cambridge (2003).

[7] Jukna S., *Extremal Combinatorics With Applications in Computer Science*, Springer, Berlin, 2011.

[8] Liu S., Xing C., Yuan C., “List Decoding of Cover Metric Codes Up to the Singleton Bound,” *IEEE Transactions on Information Theory*, vol. 64, no. 4, pp. 2410-2416, April 2018

[9] MacWilliams F.J., Sloane N.J.A., *The Theory of Error Correcting Codes*, North Holland, Amsterdam (1977)

[10] Polyanskiy Y. and Wu, Y. *Information Theory: From Coding to Learning*. Cambridge university press, 2024.

[11] Rioul, O. (2007) *Théorie de l'information et du codage*, Hermes Science - Lavoisier: Paris, 286 pp., Sept. 2007.

[12] Walker, J. L. *Codes and Curves*, Student Mathematical Library IAS/Park City Mathematics Subseries, Vol. 7, American Mathematical Society, June 2000.

[13] Shi M., Wang P., Solé P., “The Exact Value for the Volume of the Balls of Radius $d$ in the Cover Metric,” submitted to *Advances in Mathematics of Communications*.