Stationary Distribution of Tsetlin Library/Move to Front Markov chain 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
 A: 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.
