2
$\begingroup$

Consider $R_1, R_2, ... R_N$, N items arranged in a sequence. With probability $p_i > 0$, item $R_i$ is moved to the front of the sequence. This defines a finite Markov Chain of $N!$ states.

What is the stationary distribution of this Markov Chain?

Note: I am looking for a solution to this problem with elementary probability that also shows how one would derive the distribution, and not just a proof by induction as is presented here: https://www.jstor.org/stable/3212655?seq=1#metadata_info_tab_contents

$\endgroup$
0

1 Answer 1

0
$\begingroup$

Let's generalize the description of the problem slightly, so that item $R_i$ has weight $w_i$, and is moved to the front with probability $p_i = \frac{w_i}{w_1 + w_2 + \dots + w_N}$. Let $f(w_1, w_2, \dots, w_N)$ be the stationary probability of state $(R_1,R_2,\dots,R_N)$: by symmetry, that's the only probability we need to find.

Start the Markov chain in the stationary distribution and then make one more step from there. This will keep the distribution stationary, but make it easy to see that item $R_1$ is in front with probability $\frac{w_1}{w_1 + w_2 + \dots + w_n}$.

Moreover, given that item $R_1$ is in front, the order of $R_2, \dots, R_N$ is distributed exactly as it was in the stationary distribution, because it did not change. If we forget about $R_1$ entirely, we get a size-$(N-1)$ problem with weights $w_2, \dots, w_N$; therefore the probability that $R_2, \dots, R_N$ appear in that order is $f(w_2, \dots, w_N)$.

Multiplying, we get $$ f(w_1, w_2, \dots, w_N) = \frac{w_1}{w_1 + \dots + w_n} f(w_2, \dots, w_N) $$ from which the formula $$ f(w_1, w_2, \dots, w_N) = \prod_{i=1}^N \frac{w_i}{w_i + \dots + w_N} $$ immediately follows.

$\endgroup$
2
  • $\begingroup$ Hi thanks for the answer. Could you maybe explain slightly more why the probability that $R_2,...R_n$ appear in that order is $f(w_2,...,w_n)$. I don’t think that is immediate from the definition of f since f was defined for n elements. I’m not able to see clearly the connection between the stationary distribution on all n elements and the stationary distribution on the subsequence of n-1 elements. $\endgroup$
    – shashvat
    Feb 23, 2021 at 8:12
  • $\begingroup$ Ok nevermind I got it! $\endgroup$
    – shashvat
    Feb 23, 2021 at 11:21

You must log in to answer this question.

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