We study error exponents for the problem of low-rate communication over a directed graph, where each edge in the graph represents a noisy communication channel, and there is a single source and destination. We derive maxflow-based achievability and converse bounds on the error exponent that match when there are two messages and all channels satisfy a symmetry condition called pairwise reversibility. More generally, we show that the upper and lower bounds match to within a factor of 4. We also show that with three messages there are cases where the maxflow-based error exponent is strictly suboptimal, thus showing that our tightness result cannot be extended beyond two messages without further assumptions.


翻译:我们研究了在有向图上低速率通信的误差指数问题,其中图中每条边表示一个嘈杂的通信渠道,且有一个单一的源和目标。我们推导了基于最大流的可实现性和对话界限,这些界限是匹配的,当图中有两个消息且所有通道满足称为成对可逆性的对称性条件时。更一般地,我们表明上限和下限在因子4内匹配。我们还表明,当有三个消息时,有些情况下基于最大流的误差指数严格次优,因此表明我们的紧密性结果不能在没有进一步假设的情况下推广到两个消息以上。

0
下载
关闭预览

相关内容

【硬核书】树与网络上的概率,716页pdf
专知会员服务
72+阅读 · 2021年12月8日
【WWW2021】双曲图卷积网络的协同过滤
专知会员服务
39+阅读 · 2021年3月26日
专知会员服务
49+阅读 · 2020年8月27日
图节点嵌入(Node Embeddings)概述,9页pdf
专知会员服务
39+阅读 · 2020年8月22日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2023年5月19日
Arxiv
13+阅读 · 2021年5月25日
Arxiv
19+阅读 · 2020年7月13日
VIP会员
相关VIP内容
【硬核书】树与网络上的概率,716页pdf
专知会员服务
72+阅读 · 2021年12月8日
【WWW2021】双曲图卷积网络的协同过滤
专知会员服务
39+阅读 · 2021年3月26日
专知会员服务
49+阅读 · 2020年8月27日
图节点嵌入(Node Embeddings)概述,9页pdf
专知会员服务
39+阅读 · 2020年8月22日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员