Prerequisites & Notation

Before You Begin

This chapter proves converse bounds complementary to the MAN scheme of Chapter 2. The proofs use Fano's inequality and the information- theoretic toolkit from ITA Chapter 1.

The MAN scheme and the rate formula $R = K(1-M/N)/(1+KM/N)$ (Ch 2)(Review ch02)
Self-check: Can you state the rate formula and sketch why each XOR message serves $t+1$ users?
Fano's inequality and converse arguments(Review ch01)
Self-check: Can you use $\mathrm{H}(X|Y) \leq h_b(P_e) + P_e \log |\mathcal{X}|$ to bound a decoding error probability?
Chain rule for entropy $\mathrm{H}(X,Y) = \mathrm{H}(X) + \mathrm{H}(Y|X)$ (Review ch01)
Self-check: Can you apply this to a sum of conditional entropies over a set of demand rounds?
Random variables over demand vectors and uniform placements
Self-check: Can you compute $\mathbb{E}[|\mathcal{Z}_k|]$ under a symmetric placement?
Convex envelopes and piecewise-linear rate-memory curves(Review ch02)
Self-check: Can you interpolate the MAN rate at non-integer $t$ via memory sharing?

Notation for This Chapter

Symbols introduced in Chapter 3. The converse notation mostly uses subsets and entropies; the YMA '18 proof uses demand types.

Symbol	Meaning	Introduced
$R^*(M)$	Optimal worst-case delivery rate at cache size $M$	s01
$R_{\text{unc}}^*(M)$	Optimal rate under uncoded placement restriction	s03
$s$	Cut-set parameter: number of users in the cut $s \in \{1, \ldots, \min(K, N)\}$	s01
$\mathcal{F}$	Subset of the library used in the cut-set bound	s01
$\rho$	File-correlation coefficient in the CommIT WTJC correlated-files model	s04
$\mathbf{d}^{(\ell)}$	$\ell$ -th demand vector in an ensemble	s01
$N_e(\mathbf{d})$	Number of distinct demands in vector $\mathbf{d}$	s02

← Ch 2 The Cut-Set Converse Bound