Abstract
We study a problem related to coin flipping, coding theory, and noise sensitivity. Consider a source of truly random bits $x \in \{0,1\}^n$, and $k$ parties who have noisy versions of the source bits $y^i \in \{0,1\}^n$. For all $i$ and $j$, it holds that $\Pr[y^i_j = x_j] = 1 - \epsilon$, independently for all bits and all parties. The parties, who cannot communicate, wish to agree beforehand on balanced functions $f_i : \{0,1\}^n \to \{0,1\}$ such that the probability $\Pr[f_1(y^1) = ... = f_k(y^k)]$ is maximized. While for $k=2,3$ no error correction is possible and the optimal protocol is a simple dictatorship ($f_i(x^i) = y^i_1$), for large values of $k$, better protocols exist. We analyze the optimal protocols and the asymptotic behavior of the problem using tools from discrete Fourier analysis, convexity, and discrete symmetrization.
Introduction
Imagine a "cosmic source"—perhaps a satellite or a pulsar—broadcasting a stream of truly random bits. Multiple parties across the globe wish to use this stream to agree on a single shared random bit (a "fair coin") to facilitate a cryptographic key exchange or a distributed protocol.
The challenge lies in the transmission noise. Every party receives a slightly different version of the stream, where each bit has a small probability $\epsilon$ of being flipped. Crucially, the parties cannot communicate with each other to reconcile these differences. They must decide on a function $f$ beforehand, apply it to their local noisy data, and hope that everyone outputs the same bit. This research seeks to identify the optimal "balanced" functions—those that output 0 or 1 with equal probability—to maximize the chance of total agreement among $k$ parties.
The Mathematical Framework
To solve this, the study employs several sophisticated tools from theoretical computer science and probability:
- Discrete Fourier Analysis: Boolean functions are represented as Fourier expansions. The authors utilize the Bonami-Beckner operator ($T_\epsilon$), a standard tool in noise sensitivity, to model how noise affects the output of these functions.
- Steiner Symmetrization and Convexity: To narrow the search for optimal functions, the authors use symmetrization techniques to prove that the best functions must be "monotone" (flipping an input bit from 0 to 1 should not flip the output from 1 to 0) and "left-monotone" (prioritizing earlier bits in the sequence).
- Coupling Arguments: To analyze the behavior of the Majority function (MAJ), the authors use coupling to demonstrate how the distribution of noisy bits relates back to the original source.
- Computer-Assisted Proofs: For small values of $n$ (the number of bits), the authors performed exhaustive checks of all 2,470 antisymmetric left-monotone functions for $n=8$ to validate their conjectures and observe strategy transitions.
Key Insights: From Dictatorship to Majority
The Dictatorship of Small Groups
One of the paper's most striking results is that for very small groups ($k=2$ or $k=3$), error correction is essentially impossible. The optimal strategy is a "dictatorship" ($f(x) = x_1$), where everyone simply looks at the very first bit and ignores the rest. In these cases, any attempt to "smooth out" the noise by considering more bits actually increases the statistical likelihood that at least one person will disagree.
The Rise of the Majority
As the group size $k$ grows, the "First Bit" strategy eventually fails. When $k$ is large enough, the Majority function (taking the majority value of all $n$ bits) becomes the superior protocol. By aggregating many bits, the parties can leverage the Law of Large Numbers to "wash out" the individual bit errors.
Polynomial vs. Exponential Decay
Intuitively, one might expect the probability of $k$ people agreeing to drop off exponentially as $k$ increases. However, the authors prove that if the number of bits $n$ is allowed to increase alongside $k$, the success probability only decays polynomially (specifically, $k^{-\nu}$ for some constant $\nu$). This suggests that shared randomness is more robust than it initially appears, provided the parties have access to a sufficiently long stream of bits.
Threshold Effects and Transitions
Through computer analysis, the researchers identified specific transition points where strategies shift. For example, when $n=5$:
- The "First Bit" strategy is optimal for up to $k=9$ parties.
- At $k=10$, the "Majority-of-3" strategy (ignoring 2 bits and taking the majority of the other 3) becomes more effective.
- At $k=12$, the "Majority-of-5" strategy becomes the best possible approach.
Conclusion and Future Directions
The paper establishes that while simple strategies suffice for small groups, complex majority-based rules are required for large-scale agreement. However, several questions remain. The authors propose the "Majority Conjecture," suggesting that the optimal function is always a Majority function of some subset of bits, though this remains unproven for all cases.
Furthermore, while this study assumes a "star" configuration (one source, many receivers), future work is exploring different network topologies, such as "line" graphs, where the decay in agreement probability is significantly harsher. Expanding the scope to include biased coins (non-balanced functions) may also reveal different optimal structures in the pursuit of cosmic consensus.
Summary updated