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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .