Stationary distribution of a Markov process defined on the space of permutations

Let $$S$$ be the set of $$n!$$ permutations of the first $$n$$ integers. Let $$p\in(0,1)$$. Consider the Markov Process defined on the elements of $$S$$.

1. Let $$x\in S$$. Choose $$1\le i uniformly at random.
2. If $$x_i < x_{i+1}$$, swap $$x_i$$ and $$x_{i+1}$$ with probability $$p$$, otherwise do nothing. If $$x_i > x_{i+1}$$, swap $$x_i$$ and $$x_{i+1}$$ with probability $$1-p$$, otherwise do nothing.

This process is ergodic, because there is path between any two states with non-zero probability. It has a stationary distribution. I conjecture that the stationary distribution of $$p(x)$$ depends only on $$p$$ and on the number of mis-rankings of $$x$$, defined as $$\sum_{i\le j} 1\{x_i < x_j\}$$. But am not able to prove it. I also wonder whether this simple model has been studied somewhere, maybe in Statistical Mechanics. Any literature reference is appreciated.

• Is this well-defined? Suppose $p=1/3$ and you pick $2$ and $3$. We should swap $2$ and $3$ with probability $1/3$ because $2<3$. Then again, we should swap $3$ and $2$ with probability $2/3$ because $3>2$... Jun 18 '19 at 4:38
• Of course there are $n(n-1)/2$ pairs... if it is swap $i,j$ with probability $p$, then you have a random walk on $S_n$ driven by $\nu\in M_p(G)$ given by $\nu((i\qquad j))=\frac{2p}{n(n-1)}$ on transpositions and $\nu(e)=1-p$. Random walks on groups have as stationary distributions, due to the fact that the stochastic matrix is doubly stochastic. For $p=1-1/n$ this is the random transposition shuffle. See Diaconis and Shahshahani 1981. Jun 18 '19 at 7:25
• *"... have as stationary distributions,..., the uniform distribution". Jun 18 '19 at 8:13
• @JP McCarthy: we don't swap $2$ and $3$, but instead $x_2$ and $x_3$. It seems well-defined to me. But there is a typo: there are $n(n-1)/2$ choices for $i$ and $j$, not $n(n+1)/2$. Jun 18 '19 at 10:05
• Ah I missed $i<j$ which means the pair $\{i,j\}$ is an ordered pair $(i,j)$. Take the permutation $\{(1,3),(2,1),(3,2)\}$. I take it the notation means that $x_1=3$, $x_2=1$, and $x_3=2$? Jun 18 '19 at 10:30

Your conjecture is correct. In fact, provided $$0 < p < 1$$, the Markov process is recurrent and reversible with unique stationary distribution proportional to $$\pi_\sigma = \Bigl(\frac{p}{1-p}\Bigr)^{\ell(\sigma)},$$ where $$\ell(\sigma)$$ is the Coxeter length of $$\sigma$$. (This is the number of 'misrankings' in your question.)

Proof. Suppose that $$0 < p < 1$$. Let $$p_{\sigma\tau}$$ be the probability of a step from $$\sigma \in S$$ to $$\tau\in S$$. We solve the detailed balance equations $$\pi_\sigma p_{\sigma\tau} = \pi_\tau p_{\tau\sigma}$$. Suppose that $$\tau = \sigma_1 \ldots \sigma_{i+1} \sigma_i \ldots \sigma_n$$ where $$1 \le i < \le n$$. Then we step from $$\sigma$$ to $$\tau$$ with probability either $$p/n$$ or $$(1-p)/n$$. Explicitly,

\begin{align*} n \pi_\sigma p_{\sigma\tau} &= \Bigl(\frac{p}{1-p}\Bigr)^{\ell(\sigma)} \begin{cases} p & \text{if \sigma_i < \sigma_j} \\ 1-p & \text{if \sigma_i > \sigma_j} \end{cases}\\ &= \Bigl(\frac{p}{1-p}\Bigr)^{\ell(\sigma)} \begin{cases} \frac{p}{1-p} (1-p) &\text{if \sigma_i < \sigma_j} \\ \frac{1-p}{p} p & \text{if \sigma_i > \sigma_j} \end{cases} \\ &= \Bigl(\frac{p}{1-p}\Bigr)^{\ell(\tau)} \begin{cases} 1-p & \text{if \tau_i > \tau_j} \\ p & \text{if \tau_i < \tau_j} \end{cases} \\ &= n\pi_\tau p_{\tau\sigma}. \end{align*} If $$\tau$$ is not of this form and $$\tau \not= \sigma$$ then $$p_{\sigma\tau} = p_{\tau\sigma} = 0$$. Hence the detailed balance equations hold. You observed in your question that there is a single communicating class of states. The walk is aperiodic because there is a positive chance of staying put at each step. Hence the invariant distribution is unique. $$\quad \Box$$

For completeness, suppose that $$p=0$$ or $$p=1$$ and that the walk starts at $$\sigma \in S$$. It is clear that if $$p=0$$ then after $$\ell(\sigma)$$ steps the walk reaches the identity permutation; if $$p = 1$$ then after $$\binom{n}{2} - \ell(\sigma)$$ steps the walk reaches the order reversing permutation $$1 \mapsto n$$, $$2 \mapsto n-1$$, $$\ldots$$, $$n\mapsto 1$$ of maximum Coxeter length. The only randomness arises from the order in which inversions are removed/added.

Remark In another version of the problem, we step according to a general transposition $$(i,j)$$ chosen uniformly at random. In this case the process is not reversible. When $$n \le 3$$ the invariant distribution depends only on the Coxeter length: for example if $$n=3$$ then, ordering permutations $$123,213,132,312,231,321$$, the transition matrix is

$$\frac{1}{3} \left( \begin{matrix} 3(1-p) & p & p & 0 & 0 & p \\ 1-p & 2-p & 0 & p & p & 0 \\ 1-p & 0 & 2-p & p & p & 0 \\ 0 & 1-p & 1-p & 1+p & 0 & p \\ 0 & 1-p & 1-p & 0 & 1+p & p \\ 1-p & 0 & 0 & 1-p & 1-p & 3p \end{matrix} \right).$$

A computer algebra calculation shows that the invariant distribution is proportional to $$(\alpha,\beta,\beta,\gamma,\gamma,\delta)$$ where $$\alpha = (1-p)(6-11p+7p^2)$$, $$\beta = (1-p)p(8-7p)$$, $$\gamma = (1-p)p(1+7p)$$ and $$\delta = p(2-3p+7p^2)$$. For $$n=4$$ the invariant distribution is more complicated. For example, if $$p=3/4$$ then the invariant probabilities for $$2134$$ and $$1324$$ are $$5325/485760$$ and $$8749/485760$$, respectively.

• Thank you Mark! Jun 18 '19 at 19:43
• I have two questions: 1. What is in the interpretation of $n\choose 2$ in the balance equation? 2. It seems that the third equality requires that $\ell(\tau)=\ell(\sigma)\pm 1$. This is always the case when $i$ and $j$ are adjacent, but not in general. Jun 21 '19 at 5:16
• I'm sorry: my answer is wrong because I wrongly assumed the Coxeter length goes up by 1 on every swap. As you noticed, it would be correct for the similarly defined random walk where $i$ and $j$ are required to be adjacent. Please could you unaccept my answer so that I can delete it. Jun 21 '19 at 10:11
• Mark, I think I am going to restate the formulation of my problem by restricting the assumption so that your answer is correct (just change the i, j to i, i+1). It's a special case, and it's still interesting. It's now interpretable as a noisy bubble-sort algorithm. Also, it is useful because I think now that my original conjecture was wrong! Jun 22 '19 at 1:33
• Okay! In that case I will edit the answer above so I can delete my second answer. Jun 22 '19 at 10:45

This stationary distribution is known as the Mallows measure, see e.g. the references in http://www.sc.ehu.es/ccwbayes/members/ekhine/tutorial_ranking/data/slides.pdf

For the Markov chain connection, see e.g.