Improving on the Cut-Set Bound via Geometric Analysis of Typical Sets
Xiugang Wu, Ayfer Ozgiur, Liang‐Liang Xie · IEEE Transactions on Information Theory · 2017
We consider the discrete memoryless symmetric primitive relay channel, where, a source$X$wants to send information to a destination$Y$with the help of a relay$Z$and the relay can communicate to the destination via an error-free digital link of rate$R_{0}$, while$Y$and$Z$are conditionally independent and identically distributed given$X$. We develop two new upper bounds on the capacity of this channel that are tighter than existing bounds, including the celebrated cut-set bound. Our approach significantly deviates from the standard information-theoretic approach for proving upper bounds on the capacity of multi-user channels. We build on the blowing-up lemma to analyze the probabilistic geometric relations between the typical sets of the$n$-letter random variables associated with a reliable code for communicating over this channel. These relations translate to new entropy inequalities between the$n$-letter random variables involved. As an application of our bounds, we study an open question posed by (Cover, 1987), namely, what is the minimum rate$R_{0}^{*}$needed for the$Z$–$Y$link in order for the capacity of the relay channel to be equal to that of the broadcast cut. We consider the special case when the$X$–$Y$and$X$–$Z$links are both binary symmetric channels. Our tighter bounds on the capacity of the relay channel immediately translate to tighter lower bounds for$R_{0}^{*}$. More interestingly, we show that when$p\to 1/2$,$R_{0}^{*}\geq 0.1803$; even though the broadcast channel becomes completely noisy as$p\to 1/2$and its capacity, and therefore the capacity of the relay channel, goes to zero, a strictly positive rate$R_{0}$is required for the relay channel capacity to be equal to the broadcast bound. Existing upper bounds on the capacity of the relay channel, and the cut-set bound in particular, would rather imply$R_{0}^{*}\to 0$, while achievability schemes require$R_{0}^{*}\to 1$. We conjecture that$R_{0}^{*}\to 1$as$p\to 1/2$.