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
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
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
7.3 Entropy algebra lemmas
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
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
7.4 Analytic helpers
For every real number \(x \ge 0\),
where \(\lfloor x \rfloor \) denotes the greatest integer not exceeding \(x\).
7.5 Stirling-based binomial lower bound
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\),
7.6 Positivity of \(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:
7.7 Additional declarations
For every natural number \(q\) and every real number \(p\),
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.
For any nonnegative real numbers \(a, b \ge 0\), the geometric mean is at most the arithmetic mean:
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,
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\).
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
Then the ratio \(n!/(a!\, b!)\) is bounded below by