Worst-case interactive communication I: Two messages are almost optimal
Worst-case interactive communication I: Two messages are almost optimal
复制标题
最坏情况交互通信一：两条消息几乎是最优的
DOI：
--
复制
发表时间：
1990
影响因子：
2.5
通讯作者：
A. Orlitsky
中科院分区：
文献类型：
--
作者：
A. Orlitsky
研究了通过交互可实现的通信减少。该模型假设两个通信者：具有随机变量 X 的信息提供者和具有可能相关随机变量 Y 的接收者。两个通信者都希望接收者在没有错误概率的情况下了解 X，而信息提供者可能会也可能不会了解 Y。为此，他们交替传输包含有限位序列的消息。消息通过无差错的通道传输，并由 (X,Y) 商定的确定性协议确定（即用于将 X 传输给认识 Y 的人的协议）。描述了两条消息协议，并研究了其最坏情况性能。 >
The reduction in communication achievable by interaction is investigated. The model assumes two communicators: an informant having a random variable X, and a recipient having a possibly dependent random variable Y. Both communicators want the recipient to learn X with no probability of error, whereas the informant may or may not learn Y. To that end, they alternate in transmitting messages comprising finite sequences of bits. Messages are transmitted over an error-free channel and are determined by an agreed-upon, deterministic protocol for (X,Y) (i.e. a protocol for transmitting X to a person who knows Y). A two-message protocol is described, and its worst case performance is investigated. >