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.

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

    Your Answer

    By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

    Not the answer you're looking for? Browse other questions tagged or ask your own question.