Suppose I have a Markov chain (discrete time, finite state space) on $[N] = \{1, 2, \cdots, N\}$, with Markov kernel given by a **doubly stochastic** matrix $P$. The double-stochasticity guarantees that the uniform distribution is a stationary measure for this chain, though not necessarily ergodicity (for example, a priori, we are not guaranteed aperiodicity). This will not be important.

Say I now want to define a coupling on a collection of Markov chains with this kernel, $\{ X^{(i)}_k \}_{i=1}^N$, such that

- $ X^{(i)}_0 = i$ for each $i$, i.e. each of the chains starts at a separate location, and
- The chains
*remain*at different locations throughout, i.e. for $i \neq j, k \geqslant 0, X^{(i)}_k \neq X^{(j)}_k$.

By the Birkhoff-von Neumann theorem, this is possible: $P$ can be written as a convex combination of permutation matrices, and so one approach (in principle) would be (abusing notation slightly and writing $\sigma$ for the permutation matrix associated to the permutation $\sigma \in S_N$), if $P = \sum_\sigma \pi_\sigma \sigma$

- Pick permutation $\sigma$ with probability $\pi_\sigma$.
- Apply this permutation to $\{X^{(i)}_k\}_{i=1}^N$ to obtain $\{X^{(i)}_{k+1}\}_{i=1}^N$

In practice, however, this requires knowing the decomposition of $P$ into these permutations, which is a) time-consuming (for large $N$ - I am told), b) not necessarily unique, and c) in my opinion, hopefully not necessary.

As such, my question is: does anybody know of / can anybody come up with a constructive, practical coupling which accomplishes the above task? i.e.

Given only the entries of the matrix $P$, and performing minimal additional processing, can one construct a '

permutation coupling' as described above?

Most of the facts stated above can be retrieved at Wikipedia.