## 3A Exercise 1: Lifting Markov chains to the symmetric group

Let $n \in \mathbf{N}$. Suppose that we have a probability measure $P : S_n \rightarrow \mathbf{R}$. We can use this probability measure to define a random walk on $S_n$. The walk starts at the identity. At each subsequent step, if it is currently at $t \in S_n$, then it moves to $st$ with probability $P(s)$.

If after $\tau$ steps the random walk is at $t \in S_n$, then let $L(\tau) = t(1)$. This defines a Markov chain taking values in $\{1,2,\ldots,n\}$. In any transition, the probability of moving from state $i$ to state $j$ is

$Q_{ij} = \sum_{s \in S_n : s(i) = j} P(s) \qquad (\star)$

Note that

$\sum_i Q_{ij} = \sum_i \sum_{s \in S_n : s(i) = j} P (s) = \sum_{s \in S_n} P(s) = 1.$

The transition matrix is therefore doubly stochastic. The non-trivial part of Exercise 1 asks us to prove the converse: given a doubly-stochastic $n \times n$ matrix $Q$, there is a probability distribution $P$ on $S_n$ so that $(\star)$ holds.

This result shows that any time-invariant Markov chain taking values in $\{1,2,\ldots, n\}$ can be lifted to a random walk on $S_n$, and so can be analysed using the techniques in Diaconis’ book.

For the proof, we shall reinterpret $(\star)$ as follows. Given $s \in S_n$, let $A(s)$ denote the $n \times n$ permutation matrix whose entry in position $(i,j)$ is $1$ if $s(i) = j$ and otherwise the entry is $0$. Then $(\star)$ holds if and only if

$Q = \sum_{s \in S_n} P(s) A(s).$

The converese therefore follows from Birkhoff’s Theorem, that any doubly-stochastic matrix is a non-negative linear combination of permutation matrices.