# 'Permutation Coupling' for Markov Chains

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$

1. Pick permutation $\sigma$ with probability $\pi_\sigma$.
2. 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.

• Surely it’s not that hard to write a doubly stochastic matrix as a linear combination of permutations. Can’t you just be greedy about it? Having such a permutation coupling sounds awfully close to having the decomposition to me. – Anthony Quas Mar 11 '18 at 2:05
• @AnthonyQuas [1/2] Thanks for your comment. here describes a greedy procedure for doing this, which is guaranteed to find a solution made of at most $N^{2}$ permutation matrices. Finding which permutation matrix to subtract is the more expensive part here; I can describe a method where finding the $k^{th}$ permutation matrix takes $\sim N^3$ steps (which can probably be improved), and this leads to an algorithm which is $\mathcal{O}(N^5)$. – πr8 Mar 11 '18 at 9:52
• [2/2] This is of course still polynomial time, but feels suboptimal and possibly unnecessary, which is why I ask the question. It may well be that having the coupling is computationally equivalent to performing the decomposition (in the sense of having the same complexity); I still have some optimism that it might be possible to do better. – πr8 Mar 11 '18 at 9:57
• Doesn’t Hall’s theorem imply that you can find a permutation to subtract in a greedy way? I will think about this later. – Anthony Quas Mar 11 '18 at 14:41
• @AnthonyQuas Thank you for your consideration. The link I shared includes a comment that 'To turn it into a real algorithm, you still need an algorithm (...) that finds a permutation in Hall's marriage theorem. There are lots of algorithms to do this.' and then notes a connection between this task and matching problems. I believe you that this step can be made more efficient; I'm chiefly interested in whether I can accomplish my task without it. My reasoning is that I'm 'asking for less' than the decomposition (just samples from it), and so would like to find a method which costs less as well. – πr8 Mar 11 '18 at 15:12