TCSLib

7 Entropy and Asymptotic Bounds

7.1 Overview

This chapter develops the asymptotic relationship between Hamming ball sizes and the \(q\)-ary entropy function \(H_q\), and provides the key binomial lower bound used in the Gilbert–Varshamov argument.

7.2 Asymptotic upper bound on ball size

Theorem 7.1 Entropy upper bound on Hamming balls
✓

Let \(\alpha \) be a finite alphabet with at least two symbols, write \(q = \left\lvert \alpha \right\rvert \) for its size, and let \(n\) be a natural number. Fix a real number \(p\) with \(0 \lt p \le 1 - 1/q\), and let

\[ H_q(p) \; =\; p\log _q(q-1) - p\log _q p - (1-p)\log _q(1-p) \]

be the \(q\)-ary entropy function. Then for every codeword \(c \in \alpha ^n\), the Hamming ball of radius \(\lfloor np\rfloor \) about \(c\), namely \(B_{\lfloor np\rfloor }(c) = \{ c' \in \alpha ^n : d(c',c) \le \lfloor np\rfloor \} \), satisfies

\[ \left\lvert B_{\lfloor np\rfloor }(c)\right\rvert \; \le \; q^{\, H_q(p)\, n}. \]

7.3 Entropy algebra lemmas

Lemma 7.2 Closed form for \(q^{H_q(p)}\)
✓

Let \(q \ge 2\) be an integer and let \(p\) be a real number with \(0 \lt p \lt 1\). Then the \(q\)-th power of the \(q\)-ary entropy \(H_q(p)\) is given by

\[ q^{H_q(p)} \; =\; (q-1)^{p}\, p^{-p}\, (1-p)^{-(1-p)}. \]
Lemma 7.3 Exponential form of the \(q\)-ary entropy
✓

Let \(q \ge 2\) be an integer and let \(p\) be a real number with \(0 \lt p \lt 1\). Then the base-\(q\) power of the \(q\)-ary entropy \(H_q(p)\) admits the closed form

\[ q^{\, H_q(p)} \; =\; (q-1)^{p}\, p^{-p}\, (1-p)^{-(1-p)}. \]

7.4 Analytic helpers

Lemma 7.4 Square root minus square root of floor is at most one
✓

For every real number \(x \ge 0\),

\[ \sqrt{x} - \sqrt{\lfloor x \rfloor } \le 1, \]

where \(\lfloor x \rfloor \) denotes the greatest integer not exceeding \(x\).

7.5 Stirling-based binomial lower bound

Lemma 7.5 Asymptotic lower bound on a weighted binomial coefficient
✓

Fix a real number \(p\) with \(0 \lt p \lt 1\) and an integer \(q \ge 2\), and let \(H_q\) denote the \(q\)-ary entropy function. Then there is a function \(\varepsilon \colon \mathbb {N}\to \mathbb {R}\) with \(\varepsilon (n) = o(n)\) such that, for all sufficiently large \(n\),

\[ \binom {n}{\lfloor np \rfloor }\, (q-1)^{pn} \; \ge \; q^{\, H_q(p)\, n \, -\, \varepsilon (n)}. \]

7.6 Positivity of \(q\)-ary entropy

Theorem 7.6 Positivity of the \(q\)-ary entropy
✓

Let \(\alpha \) be a finite alphabet with \(q = \left\lvert \alpha \right\rvert \) symbols, and let \(p\) be a real number with \(0 \lt p \le 1 - 1/q\). Then the \(q\)-ary entropy of \(p\) is strictly positive:

\[ H_q(p) \; =\; p\log _q(q-1) - p\log _q p - (1-p)\log _q(1-p) \; \gt \; 0. \]

7.7 Additional declarations

Lemma 7.7 Rearrangement of the \(q\)-ary entropy expression
✓

For every natural number \(q\) and every real number \(p\),

\[ p\, \log _q(q-1) - p\, \log _q p - (1-p)\, \log _q(1-p) = \log _q(q-1)\cdot p + \log _q p\cdot (-p) + \log _q(1-p)\cdot \bigl(-(1-p)\bigr), \]

where \(\log _q\) denotes the base-\(q\) logarithm. That is, the three terms of the \(q\)-ary entropy expression may be rewritten by commuting each product and absorbing the subtractions into the sign of the multiplier.

Lemma 7.8 AM–GM inequality for two nonnegative reals
✓

For any nonnegative real numbers \(a, b \ge 0\), the geometric mean is at most the arithmetic mean:

\[ \sqrt{ab} \; \le \; \frac{a+b}{2}. \]
Lemma 7.9 A Stirling square-root identity
✓

For every real number \(n \ge 0\), the three square roots \(\sqrt{2\pi n}\), \(\sqrt{\pi /2}\), and \(\sqrt{n}\) multiply to \(\pi n\); that is,

\[ \sqrt{2\pi n}\, \cdot \, \sqrt{\pi /2}\, \cdot \, \sqrt{n} \; =\; \pi n. \]
Lemma 7.10 Positivity of \(\lfloor np\rfloor \) for large \(n\)
✓
#

Let \(p\) be a real number with \(0 \lt p\) and \(0 \lt 1 - p\), and set \(N_2 = \lceil 2/(p(1-p))\rceil + 1\). Then for every natural number \(n\) with \(N_2 \le n\), the floor \(\lfloor np\rfloor \) is strictly positive, i.e. \(\lfloor np\rfloor \ge 1\).

Lemma 7.11 Stirling-type lower bound for a factorial ratio
✓

Let \(a,b,n\in \mathbb {N}\) with \(a\gt 0\), \(b\gt 0\), and \(a+b=n\), and let \(c\gt 0\) be a real number. Suppose the factorial product \(a!\, b!\) admits the Stirling-type upper bound

\[ a!\, b! \; \le \; c\cdot \Bigl(\sqrt{2}\, \sqrt{a}\, \sqrt{\pi }\, (a/e)^{a}\Bigr)\Bigl(\sqrt{2}\, \sqrt{b}\, \sqrt{\pi }\, (b/e)^{b}\Bigr). \]

Then the ratio \(n!/(a!\, b!)\) is bounded below by

\[ \frac{n^{n}}{a^{a}\, b^{b}}\cdot \frac{1}{c\, \sqrt{\pi /2}\, \sqrt{n}} \; \le \; \frac{n!}{a!\, b!}. \]