Finite-Blocklength, Channel Dispersion, and the Normal Approximation¶

Job: develop the finite-blocklength $R^*(n,\epsilon)$, the normal approximation (Polyanskiy–Poor–Verdú), the channel dispersion $V$, and the hypothesis testing converse — with the BSC normal approximation as the worked example.

Core¶

The finite-blocklength regime¶

$M^$ / $R^$ / normal approximation	Description
$M^*(n,\epsilon)$	the maximum codebook size for blocklength $n$ and error $\epsilon$
$R^*(n,\epsilon)$	$\log M^*/n$ (the finite-blocklength rate)
Normal approximation (PPV)	$R^*(n,\epsilon)=C-\sqrt{V/n}\,Q^{-1}(\epsilon)+O(\log n/n)$ (the $C$ the capacity, the $V$ the dispersion)

The channel dispersion $V$¶

Dispersion / information density	Description
$V=\mathrm{Var}[i(X;Y)]$	the variance of the information density ($i(x,y)=\log\frac{p(y
BSC dispersion	$V=p(1-p)(\log\frac{1-p}{p})^2$ (the BSC the explicit)
AWGN dispersion	$V=\frac12(1-\frac{1}{(1+P/N)^2})(\log e)^2$ (the AWGN the explicit)

The converse and the achievability (finite)¶

Converse / achievability / strong converse	Description
$\epsilon$-converse (PPV)	$R^*(n,\epsilon)\le C-\sqrt{V/n}\,Q^{-1}(\epsilon)+O(\log n/n)$
Achievability (random coding)	$R^*(n,\epsilon)\ge C-\sqrt{V/n}\,Q^{-1}(\epsilon)-O(\log n/n)$
Strong converse	$R>C$ the error $\to1$ (the strong, the $R<C$ the $\to0$)

The finite-blocklength and the hypothesis testing¶

HT converse / $\beta$ / $M^*$	Description
HT converse (PPV)	the $M^*$ the hypothesis testing ($D_{\mathrm{KL}}$ the $\beta\le\epsilon$)
$\beta\le\epsilon$	the $M^*\le e^{nD}/\beta$ (the HT converse, the PPV)
$R^*$	the $R^$ the HT (the $\beta$ the type-II, the $M^$ the codebook)

See it¶

BSC normal approximation $R^*(n,\epsilon)=C-\sqrt{V/n}\,Q^{-1}(\epsilon)+O(\log n/n)$. The BSC($p$), the $C=1-h_2(p)$, the $V=p(1-p)(\log\frac{1-p}{p})^2$ (the dispersion, the variance of the information density $i(x,y)=\log\frac{p(y|x)}{p(y)}$). The normal approximation: $R^*(n,\epsilon)=1-h_2(p)-\sqrt{V/n}\,Q^{-1}(\epsilon)+O(\log n/n)$ (the PPV, the finite-blocklength the rate the capacity minus the $\sqrt{V/n}$ the dispersion correction). The key point: the finite-blocklength the $R^*(n,\epsilon)$ the $C-\sqrt{V/n}\,Q^{-1}(\epsilon)$ (the normal approximation, the PPV), the BSC the explicit.

Check¶

Show that the BSC dispersion $V=p(1-p)(\log\frac{1-p}{p})^2$ and explain the normal approximation.

The BSC($p$): the information density $i(x,y)=\log\frac{p(y|x)}{p(y)}$. The $p(y|x)=1-p$ (correct) or $p$ (error), the $p(y)=\frac12$ (the uniform output). The $i=\log\frac{1-p}{1/2}=\log(2(1-p))$ (correct) or $\log\frac{p}{1/2}=\log(2p)$ (error). The $V=\mathrm{Var}[i]$: the $P(\text{correct})=1-p$, $P(\text{error})=p$, the $\mathbb{E}[i]=(1-p)\log(2(1-p))+p\log(2p)=I(X;Y)=C=1-h_2(p)$, the $V=(1-p)(\log(2(1-p))-C)^2+p(\log(2p)-C)^2=p(1-p)(\log\frac{1-p}{p})^2$ (the dispersion). The normal approximation: $R^*(n,\epsilon)=C-\sqrt{V/n}\,Q^{-1}(\epsilon)+O(\log n/n)$ (the PPV).

Explain the hypothesis testing converse and the $\beta\le\epsilon$.

The HT converse (PPV): the $M^*$ (the max codebook) bounded by the hypothesis testing. The $H_0$: $Y^n\sim\prod W(\cdot|x_i)$ (the codeword), the $H_1$: $Y^n\sim\prod Q(\cdot)$ (the noise). The $\beta$ (the type-II error of the optimal test at type-I $\le\epsilon$): the $M^*\le\frac{e^{nD}}{\beta}$ (the $\beta$ the type-II, the $D$ the divergence, the PPV). The $R^*=\log M^*/n\le D-\frac1n\log\beta$, the $\beta\le\epsilon$ the converse. The key: the $M^*$ the hypothesis testing (the $\beta$ the type-II, the PPV the converse).

Pitfalls¶

The $R^*(n,\epsilon)$ the finite (the $C$ the asymptotic, the $\sqrt{V/n}$ the dispersion correction) — the finite-blocklength the $C-\sqrt{V/n}Q^{-1}(\epsilon)$, the $O(\log n/n)$ the lower order.
The dispersion $V$ (the $\mathrm{Var}[i(X;Y)]$ the information density variance) — the $V$ the dispersion, the BSC / AWGN the explicit.
The HT converse (the $\beta\le\epsilon$, the $M^*\le e^{nD}/\beta$) — the HT the converse, the PPV the finite.
The strong converse (the $R>C$ the error $\to1$, the strong) — the strong converse, the $R<C$ the $\to0$.

Refs¶

Polyanskiy–Poor–Verdú, "Channel coding rate in the finite blocklength regime" (2010); the normal approximation
Polyanskiy–Poor–Verdú, "Hypothesis testing converse" (2010); the HT converse
Shannon (1948); the strong converse; the PPV the finite-blocklength

Next¶

IT index · Foundations · Network Information · Rate-Distortion & Lossy · Quantum & Large Deviations · Probability

\(M^\) / \(R^\) / normal approximation	Description
\(M^*(n,\epsilon)\)	the maximum codebook size for blocklength \(n\) and error \(\epsilon\)
\(R^*(n,\epsilon)\)	\(\log M^*/n\) (the finite-blocklength rate)
Normal approximation (PPV)	\(R^*(n,\epsilon)=C-\sqrt{V/n}\,Q^{-1}(\epsilon)+O(\log n/n)\) (the \(C\) the capacity, the \(V\) the dispersion)

HT converse / \(\beta\) / \(M^*\)	Description
HT converse (PPV)	the \(M^*\) the hypothesis testing (\(D_{\mathrm{KL}}\) the \(\beta\le\epsilon\))
\(\beta\le\epsilon\)	the \(M^*\le e^{nD}/\beta\) (the HT converse, the PPV)
\(R^*\)	the \(R^\) the HT (the \(\beta\) the type-II, the \(M^\) the codebook)