4
$\begingroup$

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 <i+1 < n$ 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.

$\endgroup$
7
  • $\begingroup$ 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$... $\endgroup$ Jun 18, 2019 at 4:38
  • $\begingroup$ 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. $\endgroup$ Jun 18, 2019 at 7:25
  • $\begingroup$ *"... have as stationary distributions,..., the uniform distribution". $\endgroup$ Jun 18, 2019 at 8:13
  • $\begingroup$ @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$. $\endgroup$ Jun 18, 2019 at 10:05
  • 1
    $\begingroup$ 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$? $\endgroup$ Jun 18, 2019 at 10:30

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thank you Mark! $\endgroup$
    – gappy3000
    Jun 18, 2019 at 19:43
  • 1
    $\begingroup$ 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. $\endgroup$
    – gappy3000
    Jun 21, 2019 at 5:16
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 21, 2019 at 10:11
  • 1
    $\begingroup$ 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! $\endgroup$
    – gappy3000
    Jun 22, 2019 at 1:33
  • $\begingroup$ Okay! In that case I will edit the answer above so I can delete my second answer. $\endgroup$ Jun 22, 2019 at 10:45
2
$\begingroup$

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.

https://math.uchicago.edu/~shmuel/Network-course-readings/MCMCRev.pdf

and "Sampling and Learning Mallows and Generalized Mallows Models Under the Cayley Distance" Methodology and Computing in Applied Probability March 2018, Volume 20, Issue 1, pp 1–35 |

$\endgroup$
1
  • 2
    $\begingroup$ Why on earth has this been downvoted? Searching for 'Mallows measure' I found Section 5.2 of tinyurl.com/y4wcnnn4 as another reference. $\endgroup$ Jul 3, 2019 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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