## Sampling from a maximal coupling

Hi,

In a recent work on parallel computation for MCMC, and also in another one, and in fact also in an earlier one, my co-authors and I use a simple yet very powerful object that is standard in Probability but not so well-known in Statistics: the maximal coupling. Here I’ll describe what this is and an algorithm to sample from such couplings.

Consider two distributions, and on a general (i.e. discrete or continuous) state space . A coupling refers to a joint distribution, say on , with first marginal and second marginal , i.e.

An independent coupling has a density function . A maximal coupling, on the other hand, is such that pairs have maximal probability of being identical, i.e. is maximal under the marginal constraints and .

At first, it might sound weird that there would be any possibility of and being identical since their distributions are on a continuous state space. But indeed it is possible. Intuitively, imagine that is sampled from : as long as then could also be a sample from , could it not?

The following algorithm provides samples from a maximal coupling of and .

- Sample from .
- Sample a uniform variable . If , then output .
- Otherwise, sample from and , until , and output .

It is clear that, if is produced by the above algorithm, then (from step 1). Checking that takes a few lines of calculus, similar to proving the validity of rejection sampling. It can be found e.g. in the appendix of this article. This scheme must have been known for a long time and is definitely in Thorisson’s book on coupling. I’m not quite sure who first came up with it, any tips welcome!

To understand the algorithm, let’s look at the following figure, where the density functions of and are plotted along with a shaded area under the curve . The algorithm tries to sample from the distribution represented by the shaded area first, and if it does not succeed, it samples from the remainder which has density , up to a normalizing constant.

The graph at the beginning of the article shows pairs generated by the algorithm. The red dots represent samples with . The probability of this event is precisely one minus the total variation between and , and by the coupling inequality (e.g. here, Lemma 4.9), this is the maximum probability of the event under the marginal constraints.

Sampling from a maximal coupling | A bunch of datasaid, on 6 September 2017 at 04:01[…] Source link […]

Sampling from a maximal coupling | A bunch of datasaid, on 6 September 2017 at 04:49[…] Please comment on the article here: Statistics – Statisfaction […]

Unbiased Hamiltonian Monte Carlo with couplings | Statisfactionsaid, on 17 September 2017 at 22:52[…] met. Yet this is not very clean… so instead, we mix HMC steps with coupled MH steps that use maximally coupled random walk proposals. Indeed, if two chains are already close to one another thanks to the coupled […]

Unbiased Hamiltonian Monte Carlo with couplings | A bunch of datasaid, on 18 September 2017 at 00:05[…] met. Yet this is not very clean… so instead, we mix HMC steps with coupled MH steps that use maximally coupled random walk proposals. Indeed, if two chains are already close to one another thanks to the coupled […]

xi'ansaid, on 25 December 2017 at 13:05Is there any sense in comparing the orders ($p,q)$ and $(q,p)$? I do not think so but I have been wrong in many occasions already!

Pierre Jacobsaid, on 26 December 2017 at 00:14Definitely, the procedure is not “symmetric” in p and q. But the expected cost and the probability of {X = Y} are unchanged by swapping p and q. So I’m not sure what would be reasons to prefer one over the other. Perhaps if the costs of sampling/evaluating p and q were asymmetric, and if one wanted to control the tails of the cost instead of the expectation.

correlation for maximal coupling – Cloud Data Architectsaid, on 3 January 2018 at 07:01[…] by simulation (as I could not figure out the analytical formula on Boxing Day…) led me back to Pierre Jacob’s entry on the topic on Statisfaction, where simulating the maximal coupling stems from the […]

correlation for maximal coupling – Mubashir Qasimsaid, on 3 January 2018 at 09:17[…] by simulation (as I could not figure out the analytical formula on Boxing Day…) led me back to Pierre Jacob’s entry on the topic on Statisfaction, where simulating the maximal coupling stems from the […]