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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: