Exercises

Subpacketization: $\binom{6}{2} = 15$. Coded messages: $\binom{6}{3} = 20$. Each message has size $F_{\text{file}}/15$ bits. Rate: $R = 20/15 \cdot 1 = 4/3 \approx 1.333$. Cross-check: $R = (K-t)/(t+1) = 4/3$. ✓

Subfiles per cache: $10 \cdot \binom{4}{2} = 10 \cdot 6 = 60$. Subfile size: $F/\binom{5}{3} = F/10$ bits. Total: $60 \cdot F/10 = 6F$ bits = $6$ files $\cdot F$ bits/file. Target $M = tN/K = 3 \cdot 10/5 = 6$. ✓

$\binom{K}{t+1}/\binom{K}{t} = [K!/((t+1)!(K-t-1)!)] / [K!/(t!(K-t)!)] = t!(K-t)!/[(t+1)!(K-t-1)!] = (K-t)/(t+1)$. ✓

For $\mathcal{S}' = \{1,2,3\}$: $X = W_{1,\{2,3\}} \oplus W_{1,\{1,3\}} \oplus W_{1,\{1,2\}}$. Similarly for other $\mathcal{S}'$.

When all users request $W_1$, the MAN scheme's raw transmissions are still $\binom{4}{3} = 4$ messages of size $F/6$. Total: $4F/6 = 2F/3$. Rate $R = 2/3$.

This equals the worst-case MAN rate $(K-t)/(t+1) = 2/3$. In fact the base MAN scheme sends the same messages regardless of demands when demands happen to be equal, so rate is preserved. A smarter delivery (same-demand aware) would be cheaper — but the worst-case formula already captures the right number for the default scheme.

For any demand $\mathbf{d}$, the coded message is $X_{\mathcal{S}'} = \bigoplus_{j \in \mathcal{S}'} W_{d_j, \mathcal{S}' \setminus \{j\}}$. User $k \in \mathcal{S}'$ needs $W_{d_k, \mathcal{S}' \setminus \{k\}}$ and has all other summands in its cache because every other subfile's index set $\mathcal{S}' \setminus \{j\}$ (for $j \neq k$) contains $k$. This is the structural guarantee of the placement — it does not depend on which file each user requested.

User $k$ has $N \cdot \binom{K-1}{t-1}$ subfiles in cache, each of size $F/\binom{K}{t}$ bits.

Total bits: $N \binom{K-1}{t-1} \cdot F/\binom{K}{t}$. Using the identity: $= N \cdot (t/K) \cdot F = (tN/K) \cdot F = MF$. $\blacksquare$

For all-same demand $\mathbf{d} = (n, \ldots, n)$, $X_{\mathcal{S}'} = \bigoplus_{k \in \mathcal{S}'} W_{n, \mathcal{S}' \setminus \{k\}}$. This depends only on the single file $W_n$ and the set $\mathcal{S}'$. No further simplification in general unless the user knows more about the file's structure.

The number of $(t+1)$-subsets is unchanged: $\binom{K}{t+1}$. Messages are still distinct (different XORs of different subfiles of $W_n$). So the rate is $(K-t)/(t+1) \cdot (F/F) = (K-t)/(t+1)$ — same as worst case. No savings from demand concentration under the vanilla scheme.

A smarter scheme (demand-aware delivery) could recognize that only $\binom{K-1}{t}$ distinct subfiles are missing and broadcast those directly. But that's not the MAN scheme; it is a demand-adaptive variant (Chapter 18). The MAN scheme's rate is demand-agnostic by design, trading robustness for simplicity.

$R_{\text{cont}} = 10 \cdot 0.85 / (1 + 1.5) = 8.5/2.5 = 3.4$.

At $M/N = 0.1$: $R = 10 \cdot 0.9/(1+1) = 4.5$. At $M/N = 0.2$: $R = 10 \cdot 0.8/(1+2) = 8/3 \approx 2.667$. Linear interp at $M/N = 0.15$: $R = (4.5 + 2.667)/2 = 3.583$.

Memory-shared (3.583) exceeds continuous (3.4) by about 5.4%. The piecewise-linear envelope is slightly above the continuous curve everywhere except at integer-$t$ points.

A coded message $X_{\mathcal{S}'}$ has $t+1$ summands. Each summand $W_{d_j, \mathcal{S}' \setminus \{j\}}$ is needed by exactly one user $j \in \mathcal{S}'$ (since the index $\mathcal{S}' \setminus \{j\}$ excludes $j$). Hence the message serves at most $t+1$ distinct users, with equality when demands are such that each summand is actually missing for its designated user. $\blacksquare$

The coded caching gain $1 + t$ is the maximum multicast gain attainable by XOR combining subfiles under the MAN structure. To exceed it would require a different placement (e.g., coded placement, which we explore in Ch 13) or a different algebraic structure (linear combinations, index coding, Ch 4).

$K \cdot 0.722 = \log_2(3.2 \times 10^{10}) \approx 34.9$. $K \approx 48$.

For $K > 48$, subpacketization exceeds the video file size — each "subfile" is less than one bit. This is the operational reason MAN does not scale to wireless networks with hundreds of users. Chapter 14's graph-coloring and PDA constructions handle $K = 1000$+ with polynomial $F$.

A bit of $W_n$ is cached by subset $\mathcal{S}$ with probability $(M/N)^{|\mathcal{S}|}(1-M/N)^{K-|\mathcal{S}|}$. So subfile $W_{n,\mathcal{S}}$ has expected size $F \cdot (M/N)^{|\mathcal{S}|} (1-M/N)^{K-|\mathcal{S}|}$ bits.

Mimic MAN: send XOR for each $\mathcal{S}'$ of size $t = |\mathcal{S}'| - 1$. In the limit $F \to \infty$, subfiles concentrate at their expected sizes, and the rate approaches $R_{\text{dec}} = K(1-M/N) \cdot [1/(KM/N) \cdot (1 - (1-M/N)^K)]$. For $K$ large, $R_{\text{dec}} \to (1-M/N)/M/N$, the same asymptote as centralized MAN.

Decentralized MAN eliminates the need for server-coordinated placement — each user acts independently. The asymptotic rate matches; the finite-$K$ performance is strictly worse by a small multiplicative factor.

Missing subfiles for user $k$: $W_{d_k, \mathcal{T}}$ for every $t$-subset $\mathcal{T} \not\ni k$. Such a $\mathcal{T}$ corresponds to the $(t+1)$-subset $\mathcal{S}' = \mathcal{T} \cup \{k\}$, and the message $X_{\mathcal{S}'}$ has $W_{d_k, \mathcal{T}}$ as one summand. The other summands are in user $k$'s cache (by the placement rule), so user $k$ XOR-cancels and recovers $W_{d_k, \mathcal{T}}$. Repeating across all $\mathcal{T} \not\ni k$, user $k$ collects all $\binom{K-1}{t}$ missing subfiles.

Any message $X_{\mathcal{S}'}$ with $k \notin \mathcal{S}'$ is an XOR of subfiles indexed by subsets $\mathcal{S}' \setminus \{j\}$ for $j \in \mathcal{S}'$. None of these subsets is the form $\{d_k, \ldots\}$; the file labels are $d_j \neq d_k$ for $j \in \mathcal{S}'$. Hence $X_{\mathcal{S}'}$ carries no information about $W_{d_k}$'s subfiles — irrelevant to user $k$.

$(t+1)$-subsets containing $k$: $\binom{K-1}{t}$. Missing subfiles: $\binom{K-1}{t}$. One-to-one correspondence. ✓

Fix a family $\mathcal{F}$ of subsets of $[K]$. For every $\mathcal{T} \in \mathcal{F}$, subfile $W_{n,\mathcal{T}}$ is in caches $\mathcal{T}$. Delivery: for every subset $\mathcal{S}'$ of $[K]$ such that $\mathcal{S}' \setminus \{k\} \in \mathcal{F}$ for every $k \in \mathcal{S}'$, send $X_{\mathcal{S}'} = \bigoplus_{k \in \mathcal{S}'} W_{d_k, \mathcal{S}' \setminus \{k\}}$.

Total delivery: (number of valid $\mathcal{S}'$) × (subfile size). This depends on $\mathcal{F}$ — the base MAN corresponds to $\mathcal{F} = \binom{[K]}{t}$, and yields the rate formula $(K-t)/(t+1)$ with subpacketization $\binom{K}{t}$.

Smaller $\mathcal{F}$ yields fewer valid $\mathcal{S}'$ (shorter delivery) but also fewer subfiles (larger subfiles, same cache budget). There is an optimization: the base MAN maximizes multicast gain; PDAs (Chapter 14) shrink $\mathcal{F}$ to polynomial size at a rate cost. The result here is the blueprint for PDA constructions.

$R = K(1-\mu)/(1+K\mu)$. Divide top and bottom by $K$: $R = (1-\mu)/(1/K + \mu) \to (1-\mu)/\mu$ as $K \to \infty$.

The shared-link load per delivery round is bounded by a constant $(1-\mu)/\mu$ — independent of $K$. Equivalently, the link-load per user is $R/K = (1-\mu)/(K\mu + 1) \to 0$: the marginal cost of adding a user vanishes. This is the killer scaling feature of coded caching, and is why it is regarded as fundamental for future CDN architectures.

At $\mu = 0$: $R \to \infty$ (no caching, no gain). At $\mu \to 1$: $R \to 0$ (all files cached). The limit $(1-\mu)/\mu$ interpolates these two extremes smoothly.

Both users want $W_n$. User 1 is missing $W_{n, \mathcal{T}}$ for $\mathcal{T}$ with $1 \notin \mathcal{T}$. User 2 is missing $W_{n, \mathcal{T}}$ for $\mathcal{T}$ with $2 \notin \mathcal{T}$. Some missing subfiles overlap (those with $\{1, 2\} \cap \mathcal{T} = \emptyset$), some are user-specific.

For a missing subfile $W_{n, \mathcal{T}}$ with $1 \notin \mathcal{T}$: Let $\mathcal{S}' = \mathcal{T} \cup \{1\}$. Message $X_{\mathcal{S}'} = \bigoplus_{j \in \mathcal{S}'} W_{d_j, \mathcal{S}' \setminus \{j\}}$. For $j = 1$: summand is $W_{n, \mathcal{T}}$ (the target). For $j \in \mathcal{T}$: summand is $W_{d_j, \mathcal{T} \cup \{1\} \setminus \{j\}}$. This summand is in user 1's cache iff $1 \in \mathcal{T} \cup \{1\} \setminus \{j\} = \mathcal{T} \setminus \{j\} \cup \{1\}$, which is true since $1$ is in the set. ✓ User 1 decodes the target.

If $2 \in \mathcal{T}$ (so $\mathcal{T}$ contains 2 but not 1), then $d_2 = n$ means the summand for $j = 2$ in $X_{\mathcal{S}'}$ is $W_{d_2, \mathcal{S}' \setminus \{2\}} = W_{n, \{1\} \cup \mathcal{T} \setminus \{2\}}$. This is user 2's cache iff $2 \in \{1\} \cup \mathcal{T} \setminus \{2\}$, which is false. So user 2 does not cache this summand — but user 2 also does not need $W_{n, \mathcal{T}}$ (since $2 \in \mathcal{T}$), so user 2 doesn't use this message. Both users successfully collect the subfiles they need. ✓