Couplings and Matchings: Combinatorial notes on Strassen’s theorem

Statistics & Probability Letters, vol. 209, pp. 110089

Abstract

Some mathematical theorems represent ideas that are discovered again and again in different forms. One such theorem is Hall’s marriage theorem. This theorem is equivalent to several other theorems in combinatorics and optimization theory, in the sense that these results can easily be derived from each other. Remarkably, this equivalence extends to Strassen’s theorem, a celebrated result on couplings of probability measures. In this paper the equivalence between Strassen’s theorem and Hall’s theorem is investigated from a combinatorial perspective. A novel combinatorial lemma will be introduced that can be used to deduce both Hall’s theorem and a finite version of Strassen’s theorem, providing a simple proof of their equivalence.

Authors 1

1. Twan Koperberg corresponding Aachen Mathematical Institute

   Leiden University

   Affiliation as printed

   Leiden University, Mathematical Institute, Niels Bohrweg 1 2333 CA, Leiden, The Netherlands