Theory of Computing
-------------------
Title     : Optimality of Correlated Sampling Strategies
Authors   : Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, and Madhu Sudan
Volume    : 16
Number    : 12
Pages     : 1-18
URL       : https://theoryofcomputing.org/articles/v016a012

Abstract
--------

In the _correlated sampling_ problem, two players are given
probability distributions $P$ and $Q$, respectively, over the same
finite set, with access to shared randomness. Without any
communication, the two players are each required to output an element
sampled according to their respective distributions, while trying to
minimize the probability that their outputs disagree. A well known
strategy due to Kleinberg--Tardos and Holenstein, with a close variant
(for a similar problem) due to Broder, solves this task with
disagreement probability at most $2 \delta/(1+\delta)$, where $\delta$
is the total variation distance between $P$ and $Q$. This strategy has
been used in several different contexts, including sketching
algorithms, approximation algorithms based on rounding linear
programming relaxations, the study of parallel repetition and
cryptography.

In this paper, we give a surprisingly simple proof that this strategy
is essentially optimal. Specifically, for every $\delta \in (0,1)$, we
show that any correlated sampling strategy incurs a disagreement
probability of essentially $2\delta/(1+\delta)$ on some inputs $P$ and
$Q$ with total variation distance at most $\delta$. This partially
answers a recent question of Rivest.

Our proof is based on studying a new problem that we call _constrained
agreement_. Here, the two players are given subsets $A \subseteq [n]$
and $B \subseteq [n]$, respectively, and their goal is to output an
element $i \in A$ and $j \in B$, respectively, while minimizing the
probability that $i \neq j$. We prove tight bounds for this question,
which in turn imply tight bounds for correlated sampling. Though we
settle basic questions about the two problems, our formulation leads
to more fine grained questions that remain open.