Questions: Network Information Theory

Question 1

In point-to-point information theory, capacity is a single number. In multi-user information theory, it becomes a 'capacity region.' Why?

• A. Multi-user channels have multiple noise sources, each contributing a capacity number
• B. With multiple users, there is a tradeoff: increasing one user's rate generally decreases what is available for others, so the set of simultaneously achievable rate tuples (R1, R2, ...) forms a region rather than a single point
• C. Multi-user capacity is undefined, so researchers use regions as approximations
• D. Capacity regions are used because multi-user channels always have infinite capacity

Answer: (B)

Consider two users sharing a channel. If user 1 transmits at the full channel capacity, user 2 gets nothing. If user 1 is silent, user 2 can transmit at full capacity. Between these extremes lie rate pairs (R1, R2) where both users transmit at reduced rates. The set of all achievable (R1, R2) pairs is the capacity region — a two-dimensional set that captures all possible tradeoffs. The sum-rate (R1 + R2) boundary is analogous to single-user capacity, but the full region gives much richer information about the tradeoffs.

Question 2

The capacity of a general multi-user network can always be determined by solving the capacity of each link independently.

• T. True
• F. False

Answer: False

This is one of the deepest differences between single-user and multi-user information theory. In networks, interactions between links create phenomena that link-by-link analysis misses: interference (one user's signal degrades another's), cooperation (users can relay for each other), and distributed compression (correlated sources can be compressed more efficiently together). The capacity of the interference channel — just two sender-receiver pairs sharing a medium — remains an open problem in general, precisely because the coupling between users cannot be decomposed into independent single-user problems.

Question 3

Describe the key difference between the multiple access channel (MAC) and the broadcast channel (BC), and explain why the MAC capacity region was characterized decades before the general BC.

Model answer: The MAC has multiple senders transmitting to one receiver; the BC has one sender transmitting to multiple receivers. The MAC capacity region is determined by successive decoding: the receiver decodes users one at a time, subtracting each decoded signal before decoding the next. The achievable rate region is a polymatroid characterized by I(X_S; Y | X_{S^c}) for all subsets S. The BC is harder because the sender must simultaneously serve receivers with different channel qualities. For degraded BCs (where one receiver's signal is a degraded version of another's), superposition coding achieves capacity (Cover, 1972). The general BC capacity region was not established until Marton's coding scheme and its converse were completed much later.

Network information theory is characterized by this asymmetry: many problems have elegant achievability schemes but the matching converse is extremely difficult. The general interference channel, relay channel, and non-degraded broadcast channel all illustrate this pattern.