Capacity of the binary skew-symmetric broadcast channel
A transmitter sends a bit $X$ to two receivers, which observe bits $Y$ and $Z$. The binary skew-symmetric broadcast channel is the memoryless channel with $W(y, z \mid x) = P_{Y \mid X}(y \mid x)\, P_{Z \mid X}(z \mid x)$, where $$P_{Y \mid X} = \begin{pmatrix} 1 & 0 \\ 1/2 & 1/2 \end{pmatrix}, \qquad P_{Z \mid X} = \begin{pmatrix} 1/2 & 1/2 \\ 0 & 1 \end{pmatrix},$$ rows indexed by $x = 0, 1$ and columns by the output values $0, 1$. For each block length $n$, independent uniform messages $W_1, W_2$ with message sets of sizes $M_{1,n}, M_{2,n}$ are mapped by an arbitrary encoder to $X^n \in \{0,1\}^n$, without feedback; receiver one estimates $W_1$ from $Y^n$ and receiver two estimates $W_2$ from $Z^n$. A pair $(R_1, R_2)$ of nonnegative rates, in bits per channel use, is achievable if some sequence of such codes has $$\liminf_{n \to \infty} \frac{\log_2 M_{i,n}}{n} \ge R_i \quad (i = 1, 2), \qquad \Pr\bigl\{\widehat{W}_1 \ne W_1 \text{ or } \widehat{W}_2 \ne W_2\bigr\} \to 0,$$ and the capacity region $\mathcal{C}_{\mathrm{BSSC}}$ is the closure of the set of achievable pairs. Geng, Jog, Nair and Wang proved that the largest sum rate in Marton's inner bound for this channel is $0.36164288\ldots$, while the outer bound of Nair and El Gamal gives $0.3725562\ldots$, so the two bounds differ (2013).
Problem. Determine $\mathcal{C}_{\mathrm{BSSC}}$ exactly.
Source: Hajek and Pursley (1979), who used the channel in evaluating the Cover–van der Meulen achievable region; its capacity region was singled out as a test case by Nair and Wang (2008). Stated by AIM — Open Applied Problems after Dou, Liu, Niu, Bai, Han and Geng (2024), §5.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- IT — Information Theory
- Secondary
- PR
- Keywords
- AIM Open Applied Problems, broadcast channels, channel capacity, Marton's inner bound
References
@article{hajek1979,
author = {Hajek, Bruce E. and Pursley, Michael B.},
title = {Evaluation of an achievable rate region for the broadcast channel},
journal = {IEEE Trans. Inform. Theory},
volume = {25},
number = {1},
year = {1979},
pages = {36--46},
doi = {10.1109/TIT.1979.1055989},
}
@inproceedings{nair2008,
author = {Nair, Chandra and Wang, Zizhou Vincent},
title = {On the inner and outer bounds for 2-receiver discrete memoryless broadcast channels},
booktitle = {Proceedings of the Information Theory and Applications Workshop (ITA)},
address = {San Diego, CA},
year = {2008},
eprint = {0804.3825},
archivePrefix = {arXiv},
}
@article{dou2024,
author = {Dou, Yanan and Liu, Yanqing and Niu, Xueyan and Bai, Bo and Han, Wei and Geng, Yanlin},
title = {{B}lahut--{A}rimoto algorithms for inner and outer bounds on capacity regions of broadcast channels},
journal = {Entropy},
volume = {26},
number = {3},
year = {2024},
pages = {178},
doi = {10.3390/e26030178},
}
@article{marton1979,
author = {Marton, Katalin},
title = {A coding theorem for the discrete memoryless broadcast channel},
journal = {IEEE Trans. Inform. Theory},
volume = {25},
number = {3},
year = {1979},
pages = {306--311},
doi = {10.1109/TIT.1979.1056046},
}
@article{nair2007,
author = {Nair, Chandra and El Gamal, Abbas},
title = {An outer bound to the capacity region of the broadcast channel},
journal = {IEEE Trans. Inform. Theory},
volume = {53},
number = {1},
year = {2007},
pages = {350--355},
doi = {10.1109/TIT.2006.887492},
eprint = {cs/0605105},
archivePrefix = {arXiv},
}
@article{geng2013,
author = {Geng, Yanlin and Jog, Varun and Nair, Chandra and Wang, Zizhou Vincent},
title = {An information inequality and evaluation of {M}arton's inner bound for binary input broadcast channels},
journal = {IEEE Trans. Inform. Theory},
volume = {59},
number = {7},
year = {2013},
pages = {4095--4105},
doi = {10.1109/TIT.2013.2253511},
}
@misc{aim-binary-skew-symmetric-broadcast,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Capacity of the binary skew-symmetric broadcast channel}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/336-binary-skew-symmetric-broadcast.md},
note = {Entry 336 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00504, "Capacity of the binary skew-symmetric broadcast channel", clopen.solutions.