论文标题
如何使用一个位发送实际号码（以及一些共享随机性）
How to send a real number using a single bit (and some shared randomness)
论文作者
论文摘要
我们考虑使用一个位在[0,1] $中传达实际数字$ x \的估计值的基本问题。知道$ x $的发件人选择一个值$ x \ in \ set {0,1} $传输。反过来，一个接收器根据$ x $的值估计$ x $。我们考虑偏见和公正的估计问题，并旨在最大程度地降低成本。对于有偏见的情况，成本是预期平方误差（超过$ x $的选择），如果要求该算法是公正的，则与差异相吻合。 我们首先概述了常见的偏见和公正的估计方法，并在不允许共享随机性时证明它们的最佳性。然后，我们展示少量共享的随机性如何低至一位，在两种情况下都可以降低成本。具体而言，我们在不受限制地使用共享随机性的任何算法中得出了可实现的成本的下限，并提出了使用少量共享随机位的近乎最佳的解决方案。最后，我们讨论开放问题和未来的方向。
We consider the fundamental problem of communicating an estimate of a real number $x\in[0,1]$ using a single bit. A sender that knows $x$ chooses a value $X\in\set{0,1}$ to transmit. In turn, a receiver estimates $x$ based on the value of $X$. We consider both the biased and unbiased estimation problems and aim to minimize the cost. For the biased case, the cost is the worst-case (over the choice of $x$) expected squared error, which coincides with the variance if the algorithm is required to be unbiased. We first overview common biased and unbiased estimation approaches and prove their optimality when no shared randomness is allowed. We then show how a small amount of shared randomness, which can be as low as a single bit, reduces the cost in both cases. Specifically, we derive lower bounds on the cost attainable by any algorithm with unrestricted use of shared randomness and propose near-optimal solutions that use a small number of shared random bits. Finally, we discuss open problems and future directions.
