# Reference Request for Couplings with Conditions

I have two discrete (integer-valued) random variables $A,B$, with $1\le A\le n$ and $1\le B$. A coupling is a joint distribution of $A,B$ with marginal distributions $A,B$. I know there are several ways to couple any two variables, but I am placing a restriction on the coupling $(A',B')$ (if such a coupling exists) of $A,B$ by forcing some entries to be 0: $$P(A'=i,B'=j)=0 \text{ when } \frac{i}{\gcd(i,j)} \text{ is composite}.$$.

If $A,B$ both had finite range, a computer would be able to check for the existence of such a coupling. Is there any literature on how to couple discrete variables, of which at least one has infinite range, when we require that certain probabilities in the coupling are zero?

I think the Hall Marriage Theorem will give you necessary and sufficient conditions for the existence of a coupling: Write $i\sim j$ if $i/\gcd(i,j)$ is prime or $i=j$. Define functions: \begin{align*} a\colon\mathcal P(B)\to\mathcal P(A); &\quad a(T)=\{i\in A\colon \exists j\in T\text{ with }i\sim j\}\text{; and}\\ b\colon \mathcal P(A)\to \mathcal P(B); &\quad b(S)=\{j\in B\colon \exists i\in S\text{ with }i\sim j\}. \end{align*} There are two equivalent necessary and sufficient conditions.

• For each $S\subseteq\{1,\ldots,n\}$, you require $\mathbb P(B\in b(S))\ge \mathbb P(A\in S)$; OR
• for each $T\subseteq \mathbb N$, you require $\mathbb P(A\in a(T))\ge \mathbb P(B\in T)$.

NB: In your situation, of course it's much easier to check the first condition, as there are only finitely many $S$'s to check.

EDIT (based on question in comments)

You asked whether the Hall Marriage theorem applies given that $B$ takes values in an infinite set. I guess the strict answer is no, but an extension of the theorem does apply. One very useful fact is that the collection of couplings of a pair of discrete random variables forms a compact set (in fact the result is more general than this), where the distance between a pair of couplings is just the sum of the absolute values of the difference in the probability of $(i,j)$.

First, let's show that the conditions are necessary. Suppose that there is a coupling satisfying your condition. This implies that $\mathbb P(B\in b(A))=1$. Now we have $\mathbb P(B\in b(S))\ge\mathbb P(A\in S,B\in b(S))=\mathbb P(A\in S)$. Similarly $\mathbb P(A\in a(T))\ge \mathbb P(A\in a(T),B\in T)=\mathbb P(B\in T)$.

We will use compactness for the sufficiency. Let $\epsilon>0$. Then there exists an $M$ such that $\mathbb P(B\in b(S)\cap \{1,\ldots,M\})\ge (1-\epsilon)\mathbb P(A\in S)$ for each of the finitely many subsets $S$ of $\{1,\ldots,n\}$. Hall's theorem gives a sub-coupling: a measure on $\{1,\ldots,n\}\times \{1,\ldots,M\}$ where the $i$th row sums to at least $(1-\epsilon)\mathbb P(A=i)$ satisfying the constraint. We can then use compactness to take a limit, which will be a true coupling (since each row sums to the correct thing).

If the other condition is satisfied, you have $\mathbb P(A\in a(T))\ge \mathbb P(B\in T)$ for each subset $T$ of $\{1,\ldots,M\}$. This allows you to construct a sub-coupling on $\{1,\ldots,n\}\times\{1,\ldots,M\}$ where each column sums to $\mathbb P(B=j)$. Taking a limit of these, again, you obtain a true coupling.

• Does the Hall Marriage Theorem hold when one of the sets is infinite? – The Substitute Oct 27 '17 at 22:11