Fetching the paper…

Reading the bibliography…

2019

Pairwise optimal coupling of multiple random variables

Angel, Omer, Spinka, Yinon

Original
PDF
Post on X

Understand

We generalize the optimal coupling theorem to multiple random variables: Given a collection of random variables, it is possible to couple all of them so that any two differ with probability comparable to the total-variation distance between them.

In a number of cases we show that the disagreement probability we achieve is the best possible.
The proofs of sharpness rely on new results in extremal combinatorics, which may be of independent interest.

Pairwise optimal coupling of multiple random variables · Around

Built on

W. Doeblin, 1915-1940, 1991
Torgny Lindvall · 1991
Earlier work this paper cites.
On the resemblance and containment of documents
Andrei Z Broder · 1997
Earlier work this paper cites.
Coupling, Stationarity, and Regeneration
H. Thorisson · 2000
Earlier work this paper cites.
Similarity estimation techniques from rounding algorithms
Moses S Charikar · 2002
Earlier work this paper cites.
Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields
Jon Kleinberg and Eva Tardos · 2002
Earlier work this paper cites.

Similar

Lectures on the coupling method
Torgny Lindvall · 2002
Cited alongside, same era.
Rounding parallel repetitions of unique games
Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, and David Steurer · 2008
Cited alongside, same era.
Probability theory: The coupling method
Frank den Hollander · 2012
Cited alongside, same era.
Multi-marginal optimal transport: theory and applications
Brendan Pass · 2015
Cited alongside, same era.

Then

The optimality of correlated sampling
Original
Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L Rivest, and Madhu Sudan · 2016
Later among the works it cites.
Strong functional representation lemma and applications to coding theorems
Cheuk Ting Li and Abbas El Gamal · 2018
Later among the works it cites.
Pairwise multi-marginal optimal transport and embedding for earth mover’s distance
Original
Cheuk Ting Li and Venkat Anantharam · 2019
Closest in time.
A unified framework for one-shot achievability via the poisson matching lemma
Cheuk Ting Li and Venkat Anantharam · 2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…