Cut-set outer bound for causal and full-feedback relay channels

Fano's inequality gives $(1-P_e)\ln \mathrm{\mid }\mathcal{M}\mathrm{\mid }\le I(M;Y^n)+\ln 2$. Apply the chain rule to write $I(M;Y^n)={\sum }_{i}I(M;Y_i\mid Y^{i-1})$.

Since conditional mutual information is nonnegative, each summand is at most $I(M,Y_r^{i-1};Y_i\mid Y^{i-1})$. Given $(M,Y^{i-1},Y_r^{i-1})$, the current inputs are fixed by causality in either model, and [F1] makes the current output depend on those variables only through $(X_i,X_{r,i})$. Thus the summand equals $I(X_i,X_{r,i};Y_i\mid Y^{i-1})$. For the fixed channel $W_Y$, the past $Y^{i-1}$ is a time-sharing variable independent of the current output once the current inputs are fixed. Applying [F5] gives $I(X_i,X_{r,i};Y_i\mid Y^{i-1})\le I(X_i,X_{r,i};Y_i)$.

For the second cut, $I(M;Y^n)\le I(M;Y^n,Y_r^n)={\sum }_{i}I(M;Y_i,Y_{r,i}\mid Y^{i-1},Y_r^{i-1})$. The relay input $X_{r,i}$ is determined by the past. Given the past and $M$, the source input is determined; memorylessness therefore reduces each term to $I(X_i;Y_i,Y_{r,i}\mid Y^{i-1},Y_r^{i-1},X_{r,i})$. Conditional on a fixed $X_{r,i}=x_r$, the past is a time-sharing variable for the fixed channel $W_{(Y,Y_r)\mathrm{\mid }X,x_r}$. Applying [F5] and averaging over $X_{r,i}$ bounds the term by $I(X_i;Y_i,Y_{r,i}\mid X_{r,i})$.

Let $Q$ be uniform on $[n]$ and conditionally draw $(X,X_r,Y_r,Y)$ according to the time-$Q$ joint law induced by the code and channel. Steps 2.1, 2.2 imply both cut inequalities with conditioning on $Q$. Dividing the Fano bound by $n$, then taking a sequence of codes with $P_e\to 0$, gives the stated outer bound after closure and convexification.