Broadcasting on trees near criticality
© 2020 IEEE. We revisit the problem of broadcasting on d-ary trees: starting from a Bernoulli(1/2) random variable X 0 at a root vertex, each vertex forwards its value across binary symmetric channels BSC δ to d descendants. The goal is to reconstruct X 0 given the vector X Lh of values of all varia...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137601 |
| _version_ | 1811080203510743040 |
|---|---|
| author | Gu, Yuzhou Roozbehani, Hajir Polyanskiy, Yury |
| author_facet | Gu, Yuzhou Roozbehani, Hajir Polyanskiy, Yury |
| author_sort | Gu, Yuzhou |
| collection | MIT |
| description | © 2020 IEEE. We revisit the problem of broadcasting on d-ary trees: starting from a Bernoulli(1/2) random variable X 0 at a root vertex, each vertex forwards its value across binary symmetric channels BSC δ to d descendants. The goal is to reconstruct X 0 given the vector X Lh of values of all variables at depth h. It is well known that reconstruction (better than a random guess) is possible as h →∞ if and only if δ < δ c (d). In this paper, we study the behavior of the mutual information and the probability of error when δ is slightly subcritical. The innovation of our work is application of the recently introduced less-noisy channel comparison techniques. For example, we are able to derive the positive part of the phase transition (reconstructability when δ < δ c ) using purely information-theoretic ideas. This is in contrast with previous derivations, which explicitly analyze distribution of the Hamming weight of X Lh (a so-called Kesten-Stigum bound). |
| first_indexed | 2024-09-23T11:27:30Z |
| format | Article |
| id | mit-1721.1/137601 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:27:30Z |
| publishDate | 2021 |
| publisher | IEEE |
| record_format | dspace |
| spelling | mit-1721.1/1376012021-11-06T03:27:14Z Broadcasting on trees near criticality Gu, Yuzhou Roozbehani, Hajir Polyanskiy, Yury © 2020 IEEE. We revisit the problem of broadcasting on d-ary trees: starting from a Bernoulli(1/2) random variable X 0 at a root vertex, each vertex forwards its value across binary symmetric channels BSC δ to d descendants. The goal is to reconstruct X 0 given the vector X Lh of values of all variables at depth h. It is well known that reconstruction (better than a random guess) is possible as h →∞ if and only if δ < δ c (d). In this paper, we study the behavior of the mutual information and the probability of error when δ is slightly subcritical. The innovation of our work is application of the recently introduced less-noisy channel comparison techniques. For example, we are able to derive the positive part of the phase transition (reconstructability when δ < δ c ) using purely information-theoretic ideas. This is in contrast with previous derivations, which explicitly analyze distribution of the Hamming weight of X Lh (a so-called Kesten-Stigum bound). 2021-11-05T19:37:54Z 2021-11-05T19:37:54Z 2020-06 2021-03-10T14:14:25Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137601 Gu, Yuzhou, Roozbehani, Hajir and Polyanskiy, Yury. 2020. "Broadcasting on trees near criticality." IEEE International Symposium on Information Theory - Proceedings, 2020-June. en 10.1109/isit44484.2020.9174464 IEEE International Symposium on Information Theory - Proceedings Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf IEEE arXiv |
| spellingShingle | Gu, Yuzhou Roozbehani, Hajir Polyanskiy, Yury Broadcasting on trees near criticality |
| title | Broadcasting on trees near criticality |
| title_full | Broadcasting on trees near criticality |
| title_fullStr | Broadcasting on trees near criticality |
| title_full_unstemmed | Broadcasting on trees near criticality |
| title_short | Broadcasting on trees near criticality |
| title_sort | broadcasting on trees near criticality |
| url | https://hdl.handle.net/1721.1/137601 |
| work_keys_str_mv | AT guyuzhou broadcastingontreesnearcriticality AT roozbehanihajir broadcastingontreesnearcriticality AT polyanskiyyury broadcastingontreesnearcriticality |