A Stochastic Processes Primer

Scattered notes from Prof. Joe Chang’s stochastic processes book, intended for a first undergraduate course. Brownian motion and stochastic integration largely omitted; some sections left incomplete and proofs largely reference the book. See other posts for more details on stochastic calculus.

1 – Markov Chains

1.1 Specifying and Simulating a Markov Chain

to specify a Markov chain, we need to know its

• state space $S$, a finite or countable set of states—values the random variables $X_i$ may take on
• initial distribution $\pi_0$, the probability distribution of the Markov chain at time $0$.
  • for each state $i$, $\pi_0(i) := \mathbb{P}\{X_0=i\}$, the probability the Markov chain starts in state $i$ we can also think of $\pi_0$ are a vector whose $i$-th entry is $\pi_0(i)$
• probability transition matrix $P = (P_{ij})$
  • if $S$ has $N$ states, then $P$ is $N \times N$
  • $P_{ij}$ or $P(i,j)$ is the probability that the chain will transition to $j$ from $i$: $P_{ij} = \mathbb{P}\{X_{n+1} = j | X_n = i \}$.
  • rows sum to 1 (think: from state $i$, we are in row $i$, and there must be probability 1 of going to any next state $j$)

1.2 The Markov Property

a process $X_0, X_1, …$ satisfies the Markov property if

$$\mathbb{P}\{X_{n+1} = i_{n+1} | X_n=i_n, X_{n-1} = i_{n-1}, ..., X_0 = i_0 \} \newline = \mathbb{P}\{X_{n+1} = i_{n+1} | X_n = i_n\}$$

for all $n$ and all $i_0, …, i_{n+1} \in S$.

The Markov property implies a simple expression for the probability of our Markov chain taking any specified path, as follows:

$$\begin{align*} &\P\{X_0 = i_0, X_1 = i_1, ..., X_n = i_n\} \\ &= \P\{X_o = i_0\}\P\{X_1 = i_1 | X_0 = i_0\}\P\{X_2=i_2 | X_1 = i_1, X_0 = i_0\}\times \\ & \text{ }... \times \P\{X_n = i_n | X_{n-1}=i_{n-1}, ..., X_0 = i_0\} \\ &= \pi_0(i_0)P(i_0, i_1)P(i_1, i_2)...)(i_{n-1}, i_n). \end{align*}$$

We say that a process $X_0, X_1, ...$ is $r$-th order Markov if

$$\begin{align*} \P\{X_{n+1} = i_{n+1}| X_n = i_n, X_{n-1} = i_{n-1}, ..., X_0 = i_0 \}\\ = \P\{X_{n+1} = i_{n+1} | X_n = i_n, ..., X_{n-r+1} = i_{n-r+1}\} \\ \forall n \geq r \text{ and all } i_0, ..., i_{n+1} \in S. \end{align*}$$

1.3 Matrices

recall $\pi_0$ from 1.1. let $\pi_n$ denote the distribution of the chain at time $n$ analogously, $\pi_n(i) = \mathbb{P}\{X_n = i\}$. consider both as row vectors.

suppose that the state space is finite: $S = \{1, …, N\}$. by LOTP,

$$\pi_{n+1}(j) = \mathbb{P}\{X_{n+1} = j\} \newline = \sum_{i=1}^{N}\mathbb{P}\{X_n=i\}\mathbb{P}\{X_{n+1} = j | X_n=1\} \newline \sum_{i=1}^{N} \pi_n(i)P(i,j) = \pi_{n+1} = \pi_nP.$$

Then we have

$$\begin{align*} &\pi_1 = \pi_0 P \\ &\pi_2 = \pi_1 P = \pi_0 P^2 \\ &\pi_3 = \pi_2P = \pi_0 P^3 \end{align*}$$

and so on, so that by induction $\pi_n = \pi_0 P^n.$

1.4 Basic Limit Theorem of Markov Chains

Let’s define “irreducible,” “aperiodic,” and “stationary distribution” so this makes sense.

1.5 Stationary Distribution

stationary distribution amounts to saying $\pi = \pi P$ is satisfied, i.e.,

$$\pi(j) = \sum_{i \in S} \pi(i) P(i,j)$$

for all $j \in S$.

a Markov chain might have no stationary distribution, one stationary distribution, or infinitely many stationary distributions.

for subsets $A, B$ of the state space, define the probability flux from set $A$ into $B$ as

$$\text{flux}(A, B) = \sum_{i \in A} \sum_{j\in B} \pi(i) P(i,j)$$

1.6 Irreducibility, Periodicity, Recurrence

Use $\mathbb{P}_i(A)$ as shorthand for $\mathbb{P}\{A | X_0 = i\}$, and same for $\E_i$.

Accessibility: for two states $i, j$, we say that $j$ is accessible from $i$ if it is possible for the chain ever to visit state $j$ if the chain starts in state $i$:

$$\P_i \{\cup_{n=0}^{\infty} \{X_n = j\} \} > 0.$$

Equivalently,

$$\sum_{n=0}^{\infty}P^n (i, j) = \sum_{n=0}^{\infty}\{X_n = j \} > 0.$$

Communication: we say $i$ communicates with $j$ if $i$ is accessible from $j$ and $j$ is accessible from $i$.

Irreducibility: the Markov chain is irreducible if all pairs of states communicate.

The relation “communicates with” is an equivalence relation; hence, the states space $S$ can be partitioned into “communicating classes” or “classes.”

–

The Basic Limit Theorem requires irreducibility and aperiodicity (see 1.5). Trivial examples why:

• Irreducibility: takes $S = \{0,1\}, P = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$. Then $\pi_n = \pi_0$ holds for all $n$, i.e., $\pi_n$ does not approach a limit independent of $\pi_0$.
• Aperiodicity: same $S$, take $P = \begin{pmatrix} 0&1 \\ 1&0 \end{pmatrix}$. If, for example, $\pi_0 = (1,0),$ $\pi_n$ alternates with even and odd $n$, and does not converge to anything.

–

Period: Given a Markov chain $\{ X_0, X_1, ... \}$, define the period of a state $i$ to be the greatest common divisor

$$d_i = \text{gcd} \{n : P^n (i, i) > 0 \}.$$

The period of a state is a “class property.” In particular, all states in an irreducible Markov chain have the same period. Thus, we can speak of the period of a Markov chain if the Markov chain is irreducible.

An irreducible Markov chain is aperiodic if its period is $1$, and periodic otherwise. (A sufficient but not necessary condition for an irreducible chain to be aperiodic is that there exists a state $i$ such that $P(i,i) > 0$.)

–

One more concept for the Basic Limit Theorem: recurrence. We will begin with showing recurrence, then showing that it is a class property. In particular, in an irreducible Markov chain, etiher all states are recurrent OR all states are transient.

The idea of recurrence: a state $i$ is recurrent if, starting from the state $i$ at time 0, the chain is sure to return to $i$ eventually. More precisely, define the first hitting time $T_i$ of the state i by

$$T_i = \inf \{n>0 : X_n = i \}.$$

Recurrence: the state $i$ is recurrent if $\P_i \{ T_i < \infty \} = 1$. If $i$ is not recurrent, it is called transient.

(note that accessibility could be defined: for distinct states $i \neq j$, $j$ is accessible from $i$ iff $\P_i \{ T_j < \infty \} > 0$.)

–

We use the notation $N_i$ for the total number of visits of the Markov chain to the state $i$:

$$N_i = \sum_{n=0}^{\infty} I \{X_n = i \}.$$

–

Introducing stationary distributions.

Note that the converse for the above is not true. There are irreducible, recurrent Markov chains that do not have stationary distributions. For example, the simple symmetric random walk on the integers in one dimension is irreducible and recurrent but does not have a stationary distribution. By recurrence we have $\P_0 \{T_0 < \infty \} = 1$, but also $\E_0 \{T_0 \} = \infty$. The name for this kind of recurrence is null recurrence, i.e., a state $i$ is null recurrent if it is recurrent and $\E_i(T_i) = \infty$. Otherwise, a recurrent state is positive recurrent, where $\E_i (T_i) < \infty$.

Positive recurrence is also a class property: if a chain is irreducible, the chain is either transient, null recurrent, or positive recurrent. In fact, an irreducible chain has a stationary distribution iff it is positive recurrent.

1.7 Coupling

Example of coupling technique: consider a random graph on a given finite set of nodes, in which each pair of nodes is joined by an edge independently with probability $p$. We could simulate a random graph as follows: for each pair of nodes $i, j$ generate a random number $U_{ij} \sim U[0,1]$, and join nodes $i$ and $j$ with an edge if $U_{ij} \leq p$.

How do we show that the probability of the resulting graph being connected is nondecreasing in $p$, i.e., show that for $p_1 < p_2$,

$$\P_{p1} \{ \text{graph connected}\} \leq \P_{p2} \{ \text{graph connected} \}.$$

We could try to find an explicit function for the probability in terms of $p$, which seems inefficient. How to formalize the intuition that this seems obvious?

An idea: show that corresponding events are ordered, i.e., if $A \subset B$ then $\P A \leq \P B$.

Let’s make 2 events by making 2 random graphs, $G_1, G_2$ on the same set of nodes. $G_1$ is constructed by having each possible edge appear with prob $p_1$, and for $G_2$, each edge present with prob $p_2.$ We can do this by using two sets of $U[0,1]$ random variables: $\{U_{ij}\}, \{V_{ij}\}$ for the first and second graph, respectively. Is it true that

$$\{G_1 \text{ connected}\} \subset \{G_2 \text{ connected} \}?$$

No, since the two sets of r.v.s are independently generated.

A change: use the same random numbers for each graph. Then

$$\{G_1 \text{ connected}\} \subset \{G_2 \text{ connected} \}$$

becomes true. This establishes monotonicity of the probability being connected.

Conclusion: what characterizes a coupling argument? Generally, we show that the same set of random variables can be used to construct two different objects about which we want to make a probabilistic statement.

1.8 Proof of Basic Limit Theorem

The Basic Limit Theorem says that if an irreducible, aperiodic Markov chain has a stationary distribution $\pi$, then for each initial distirbution $\pi_0$, as $n \rightarrow \infty$ we have $\pi_n (i) \rightarrow \pi(i)$ for all states $i$.

(Note the wording “a stationary distribution”: assuming BLT true implies that an irreducible and aperiodic Markov chain cannot have two different stationary distributions)

Equivalently, let’s define a distance between probability distributions, called “total variation distance:”

We now introduce the coupling method. Let $Y_0, Y_1, ...$ be a Markov chain with the same probability transition matrix as $X_0, X_1, ...$, but let $Y_0$ have the initial distribution $\pi$ and $X_0$ have the initial distribution $\pi_0$. Note that $\{ Y_n \}$ is a stationary Markov chain with distribution $\pi$ for all $n$. Let the $Y$ chain be independent of the $X$ chain.

We want to show that, for large $n$, the probabilistic behavior of $X_n$ is close to that of $Y_n$.

Define the coupling time $T$ to be the first time at which $X_n = Y_n$:

$$T = \inf \{ n : X_n = Y_n \}.$$

Hence we need only show that $\P \{T > n \} \rightarrow 0$, or equivalently, that $\P \{ T < \infty \} = 1.$

Consider the bivariate chain $\{ Z_n = (X_n, Y_n) : n \geq 0 \}.$ $Z_0, Z_1, ...$ is clearly a Markov chain on the state space $S \times S$. Since the $X$ and $Y$ chains are independent, the probability transition matrix $P_Z$ of chain $Z$ can be written

$$P_Z (i_x i_y, j_x j_y) = P(i_x , j_x) P(i_y, j_y).$$

$Z$ has stationary distribution

$$\pi_Z (i_xy i_y) = \pi(i_x) \pi(i_y).$$

We want to show $\P \{ T \leq \infty \}.$ So, in terms of the $Z$ chain, we want to show that with probability one, the $Z$ chain hits the “diagonal” $\{ (j,j) : j \in S\}$ in $S \times S$ in finite time. To do this, it is sufficient to show that the $Z$ chain is irreducible and recurrent.

This is where we use aperiodicity.

Let $i \in S$ and recall the assumption that the chain is aperiodic. Since the set $\{ n : P^n (i,i) > 0 \}$ is closed under addition, and, from aperiodicity, has greatest common divisor $1$, we can use the previous lemma. So $P^n (i,i) > 0$ for all sufficiently large $n$. From this, for any $i,j \in S$, since irreducibility implies $P^m (i,j) > 0$ for some m, it follows that $P^n(i,j) > 0$ for all sufficiently large $n$.

Now we show irreducibility. Let $i_x, i_y, j_x, j_y \in S$. It is sufficient to show that $P^n_Z (i_x i_y, j_x j_y) > 0$ for some $n$. By the assumed independence of $\{X_n\}$ and $\{Y_n\}$, we have

$$P^n_Z (i_x i_y, j_x j_y) = P^n(i_x, j_x)P^n(i_y, j_y),$$

which (by the previous argument) is positive for all sufficiently large $n$, so we are done.

1.9 SLLN for Markov Chains

The usual Strong Law of Large Numbers for iid random variables says that if $X_1, X_2, ...$ are iid with mean $\mu$, then

$$\P \{ (1/n) \sum^n_{t=1} X_t \rightarrow \mu \} = 1 \text{ as } n \rightarrow \infty.$$

We will do a generalization of this result for Markov chains: the fraction of times a Markov chain occupies state $i$ converges to a limit.

Although the successive states of a Markov chain are not independent, certain features of a Markov chain are independent of each other. Here we will use the idea that the path of the chain consists of a succession of independent “cycles,” the segments of the path between successive visits to a recurrent state. This independence allows us to use the LLN that we already know.

In the proof of the previous theorem, we define $V_n(j)$ as the number of visits made to state $j$ made by $X_1, ..., X_n$, i.e.,

$$V_n(j) = \sum^{n}_{t=1} \{X_t = j\}.$$

Using the Bounded Convergence Theorem,

we have the following:

Consider an irreducible, aperiodic Markov chain haing a stationary distribution $\pi$. From the Basic Limit Theorem, we know that $P^n (i,j) \rightarrow \pi(j)$ as $n \rightarrow \infty$. Notice also that if a sequence of numbers converges to a limit, then the sequence of Cesaro averages converges to the same limit, i.e., if $a_t \rightarrow a$ as $t \rightarrow \infty$, then $(1/n) \sum^{n}_{t=1}a_t \rightarrow a$ as $n \rightarrow \infty$. However, the previous Corollary shows the Cesaro averages of $P^t (i,j)$'s converge to $1 / \E_j T_j$. So, we must have

$$\pi(j) = \frac{1}{E_j T_j}.$$

In fact, aperiodicity is not needed for this conclusion:

2 – Markov Chains: Examples & Applications

2.1 Branching Processes

Motivating example: the branching process model was formulated by Galton, who was interested in the survival and extinction of family names.

Suppose children inherit their fathers’ names, so we need only to keep track of fathers and sons. Consider a male who is the only member of his generation to have a given family name, so that the responsibility of keeping the family name alive falls upon him–if his line of male descendants terminates, so does the family name.

Suppose for simplicity that each male has probability $f(0)$ of producing no sons, $f(1)$ of producing 1 son, and so on.

What is the probability that the family name eventually becomes extinct?

To formalize this, let:

• $G_t$ the number of males in generation $t$
  • Start with $G_0 = 1$
  • If $G_t = i$, write $G_{t+1} = X_{t1} + X_{t2} + ... + X_{ti}$, where $X_{tj}$ is the number of sons fathered by the $j$-th man in generation $t$
• Assume the r.v.s $\{ X_{tj} : t \geq 0, j \geq 1 \}$ are iid with probability mass function $f$
  • Hence $\P \{ X_{tj} = k \} = f(k)$ for $k = 0, 1, ...$.
• To avoid trivial cases, assume $f(0) > 0$ and $f(0) + f(1) < 1$.

We are interested in the extinction probability $\rho = \P_1 \{ G_t = 0 \text{ for some t} \}$.

$\{ G_t : t \geq 0 \}$ is a Markov chain. State 0 is absorbing. So, for each $i > 0$, since $\P_i \{ G_1 = 0 \} = (f(0))^i >0$, the state $i$ must be transient.

Consequently, with probability 1, each state $i > 0$ is visited only a finite number of times. So, with probability 1, the chain must get absorbed at 0 or approach $\infty$.

We can obtain an equation for $\rho$ by conditioning on what happens at the first step of the chain:

$$\rho = \sum^{\infty}_{k=0} \P \{ G_1 = k | G_0 = 1 \} \P \{\text{eventual extinction} | G_1 = k \}.$$

Since the males all have sons independently,

$$\P \{ \text{eventual extinction} | G_1 = k \} = \rho^k.$$

Thus, we have

$$\rho = \sum^{\infty}_{k=0} f(k) \rho^k = \psi (\rho).$$

For each distribution $f$ there is a corresponding function of $\rho$ denoted $\psi$. So the extinction probability $\rho$ is a fixed point of $\psi$.

$\psi$ is the probability generating function of the probability mass funcion $f$. The first two derivatives are

$$\psi' (z) = \sum^{\infty}_{k=1} kf(k) z^{k-1}, \psi '' (z) = \sum^{\infty}_{k = 2} k (k-1) f(k) z^{k-2}.$$

for $z \in (0,1).$ Since these are positive, the function $\psi$ is strictly increasing and convex on $z \in (0,1).$ Also note that $\psi(0) = f(0), \psi(1) = 1$. Finally, $\psi'(1) = \sum k f(k) = \mu$, where $\mu = E(X)$, the expected number of sons for each male.

Since $\psi(1) = 1$, there is always a trivial solution at $\rho = 1$. When $\mu \leq 1$, this trivial solution is the only solution, so $\rho = 1$.

When $\mu > 1$, we define $r$ to be the smaller solution of $\psi(r) = r$. Since $\psi(\rho) = \rho$, we know that $\rho$ must be either $r$ or 1. We want to show that $\rho = r$.

Defining $p_t = \P_1 \{ G_t = 0 \}$, observe that as $t \rightarrow \infty$,

$$p_t \uparrow \P_1 \left[ \bigcup_{n=1}^{\infty} \{ G_n = 0 \} \right] = \rho.$$

Therefore, to rule out $\rho = 1$, it is sufficient to prove that

$$p_t \leq r \text{ for all }t.$$

By induction, observe $p_0 = 0$. Next,

$$p_{t+1} = \P_1 \{ G_{t+1} = 0 \} = \sum_{i=0}^{\infty}\P_1 \{ G_1 = i \} \P_1 \{G_{t+1} = 0 | G_1 = i \} = \sum^{\infty}_{i=0} f(i) (p_t)^i.$$

i.e., $p_{t+1} = \psi(p_t).$ Since $\psi$ is increasing and by the induction hypothesis $p_t \leq r$, we have that

$$p_{t+1} = \psi(p_t) \leq \psi(r) = r.$$

So $p_0, p_{t+1}$ is bounded by $r$ for all non negative $t$, which proves $\rho = r$. Hence there is a non negative probability that the family name goes on forever.

2.2 Time Reversibility

2.3 More on Time Reversibility: A Tandem Queue Model

2.4 The Metropolis Method

2.5 Simulated Annealing

2.6 Ergodicity Concepts

In this section we focus on a time-inhomogeneous Markov chain $\{X_n\}$ on a countably infinite state space $S$.

Let $P_n$ denote the probability transition matrix governing the transition from $X_n$ to $X_{n+1}$, i.e.,

$$P_n(i,j) = \P \{X_{n+1} = j | X_n = i \}.$$

For $m < n$, define $P^{(m,n)} = \prod^{n-1}_{k=m} P_k,$ s.t.

$$P^{(m,n)}(i,j) = \P \{ X_n = j | X_m = i \}.$$

We can understand weak ergodicity somewhat as a “loss of memory concept.” It says that at a large enough time $n$, the chain has nearly forgotten its state at time $m$, in the sense that the distribution at time $n$ would be nearly the same no matter waht the state was at time $m$. However, there is no requirement that the distribution be converging to anything as $n \rightarrow \infty$. The concept that incorporates convergence in addition to loss of memory is strong ergodicity.

2.6.1 The Ergodic Coefficient

For a probability transition matrix $P = P((i,j)),$ the ergodic coefficient $\delta(P)$ of $P$ is defined to be the maximum total variation distance between pairs of rows of $P$, that is,

The basic idea is that $\delta(P)$ being small is “good” for ergodicity. For example, in the extreme case of $\delta(P) = 0$, all the rows of $P$ are identical, so $P$ would cause a Markov chain to lose its memory completely in just one step: $v_1 = v_0 P$ does not depend on $v_0$.

2.6.2 Sufficient Conditions for Weak and Strong Ergodicity

Sufficient conditions are given in the next two propositions:

2.7 Proof of Main Theorem of Simulated Annealing

See book…

2.8 Card Shuffling

We have seen that for an irreducible, aperiodic Markov chain $\{ X_n \}$ having stationary distribution $\pi$, the distribution $\pi_n$ of $\{X_n\}$ converges to $\pi$ in the total variation distance. An example of using this would be generating a nearly uniformly distributed $4 \times 4$ table with given row and column sums by simulating a certain Markov chain for a long enough time. The question is: how long is long enough?

In certain simple Markov chain examples, it is easy to figure out the rate of convergence of $\pi_n$ to $\pi$. In this section we will concentrate on a simple shuffling example considered by Aldous and Diaconis in their article “Shuffling cards and stopping times.” The basic question is: How close is the deck to being “random” (uniformly distributed over the $52!$ possible permutation) after $n$ shuffles? For the riffle shuffle model, the answer is “about 7.”

2.8.1 “Top in at random” Shuffle

The “top in at random” method consists of taking the top card off the deck and then inserting is back into the deck at a random position (this includes back on top). So, altogether, there are 52 equally likely positions. Repeated performance of this shuffle on a deck of cards produces a sequence of “states” of the deck. This sequence of states forms a Markov chain with state space $S_{52}$, the group of permutations of the cards. This Markov chain is irreducible, aperiodic, and has stationary distribution $\pi = \text{ Uniform }$ on $S_{52}$ (i.e., probability $1/52!$ for each permutation). Therefore, by the Basic Limit Theorem, we may conclude that $|| \pi_n - \pi || \rightarrow 0$ as $n \rightarrow \infty$.

2.8.2 Threshold Phenomenon

Suppose we are working with a fresh deck of $d$ cards in the original order (card 1 on top, card 2 under, etc.). Then $|| \pi_0 - \pi || = 1 - (1/d!)$. We also know that $|| \pi_n - \pi || \rightarrow 0$ as $n \rightarrow \infty$ from the Basic Limit Theorem. It is natural to assume that the distance from stationarity decreases to 0 in a smooth manner; however, it actually experiences what we call the “threshold phenomenon.” An abrupt change happens in a relatively small neighborhood of the value $n = d \log d$. That is, for large $d$ the graph of $|| \pi_n - \pi ||$ versus $n$ looks like the following picture.

The larger the value of the deck size $d$, the sharper (relative to $d\log d$) the drop is near $n = d \log d$.

2.8.3 A random time to exact stationarity

Let’s give a name to each card in the deck (i.e., say the 2 of hearts is card 1, the 3 of hearts is card 2, etc.). Suppose we start with the deck in pristine order (card 1 on top, then card 2, etc.). Though $\pi_n$ will never become exactly random, it is possible to find a random time $T$ at which the deck becomes exactly uniformly distributed, that is, $X_T \sim \text{Unif}(S_{52})$.

Here is an example of such a random time. Suppose that “card i” always refers to the same card (like, say, card 52, the ace of spades), whereas “top card,” “card in position 2,” etc. are just about cards at the time of consideration. Also note that we may describe a sequence of shuffles simply by a sequence of iid random vacriables $U_1, U_2, ...$ uniformly distributed on $\{1, 2, ..., 52 \}$: just say that the $i$-th shuffle moves the top card to position $U_i$. Define the following random times:

$$\begin{align*} T_1 &= \inf \{n : U_n = 52 \} = \text{ 1st time a top card goes below card 52 } \\ T_2 &= \inf \{n > T_1 : U_n \geq 51 \} = \text{ 2nd time a top card goes below card 52 } \\ T_3 &= \inf \{n > T_2 : U_n \geq 50 \} = \text{ 3rd time a top card goes below card 52 } \\ & \vdots \\ T_{51} &= \inf \{n > T_{50} : U_n \geq 2 \} = \text{ 51st time a top card goes card below 52 } \end{align*}$$

and

$$T = T_{52} = T_{51} + 1.$$

It is not hard to see that $T$ has the desired property and that $X_T$ is uniformly distributed. To understand this, start with $T_1$. At time $T_1$, we know that some card is below card 52; we don’t know which card, but that will not matter. After time $T_1$ we continue to shuffle until $T_2$, at which time another card goes below card 52. At time $T_2$, there are 2 cards below card 52. Again, we do not know which cards they are, but conditional on which 2 cards are below card 52, each of the two possible orderings of those 2 cards is equally likely. Similarly, we continue to shuffle until time $T_3$, at which time there are some 3 cards below card 52, and, whatever those 3 cards are, each of their (3!) possible relative positions in the deck is equally likely. And so on. At time $T_{51}$, card 52 has risen all the way up to become the top card, and the other 51 cards are below card 52 (now we do know which cards they are), and those 51 cards are in random positions (i.e. uniform over 51! possibilities). Now all we have to do is shuffle one more time to get card 52 in random position, so that at time $T = T_{52} = T_{51} + 1$, the whole deck is random.

Let us find $ET$. By the definitions above, $T_1 \sim \text{Geom} (1/52), (T_2 - T_1) \sim \text{Geom} (2/52), ..., (T_{51} - T_{50}) \sim \text{Geom}(51/52), (T_{52} - T_{51}) \sim \text{Geom}(52/52).$ So

$$ET = E(T_1) + E(T_2 - T_1) + ... + E(T_{52} - T_{51}) \approx 52 \log 52.$$

Analogously, if the deck had $d$ cards rather than 52, we would have obtained $ET \sim d\log d$ (for large $d$), where $T$ is now a random time at which the whole deck of $d$ cards becomes uniformly distributed on $S_d$.

2.8.4 Strong Stationary Times

As we have observed, the random variable $T$ that we just constructed has the property that $X_T \sim \pi$. $T$ also has two other important properites. First, $X_T$ is independent of $T$. Second, $T$ is a stopping time, that is, for each $n$, one can determine whether or not $T=n$ just by looking at the values of $X_0, ..., X_n$. In particular, to determine whether or not $T = n$ it is not necessary to know any future values $X_{n+1}, X_{n+2}, ...$.

What’s so good about strong stationary times?

This tells us that strong stationary times satisfy the same inequality derived for coupling times.

To see proof of threshold phenomenon in shuffling, refer to book.

3 – MRFs and HMMs

This section looks at aspects of Markov random fields (MRF’s), hidden Markov models (HMM’s), and their applications.

3.1 MRFs on Graphs and HMMs

A stochastic process is a collection of random variables $\{ X_t : t \in T\}$ indexed by some subset $T$ of the real line $\R$. The elements of $T$ are often interpreted as times, in which case $X_t$ represents the state at time $t$ of the random process under consideration. The term random field refers to a generalization of the notion of a stochastic process: a random field $\{ X_s : s \in G\}$ is still a collection of random variables, but now the index set $G$ need not be a subset of $\R$. For example, $G$ could be a subset of the plane $\R^2$. In this section, we’ll consider $G$ as the set of nodes of a graph (the set being at most countable). Important aspects of the dependence among the random variables will be determined by the edges of the graph through a generalization of the Markov property.

More compact notation: for a subset of nodes $A \subset G$, let $x_A$ be the vector $(x_s : s \in A).$ We will also write $p(x_t | x_{N(t)})$ for $\P \{X_t = x_t | X_s = x_s \text { for } s \in N(t)\}$. HMM’s are Markov random fields in which some of the random variables are observable and others are not. We adopt $X$ for hidden random variables and $Y$ for observed random variables.

3.2 Bayesian Framework

What do we get out of these models & how can we use them? One approach is Bayesian: HMM’s fit nicely in the Bayesian framework. $X$ is the object of interest; it is unknown. For example, in modeling a noisy image, $X$ could be the true image. We consider the unknown $X$ to be random, and we assume it has a certain prior distribution. This distribution, our probabilistic model for $X$, is assumed to be a Markov random field. We also postulate a certain probabilistic model for $Y$ conditional on $X$. This conditional distribution of $Y$ given $X$ reflects our ideas about the noise of blurring or whatever transforms the hidden true image $X$ into the image $Y$ that we observe.

Given our assumed prior distribution of $X$ and condiitonal distribution of $(Y|X)$, Bayes’ formula gives the posterior distribution of $(X|Y)$. Thus, given an observed value $Y=y$, in principle we get a posterior distribution $P \{ X = \cdot | Y = y \}$ over all possible true images, so that (again, in principle) we could make a variety of reasonable choices of our estimator of $X$. For example, we could choose the $x$ that maximizes $P \{ X = x | Y=y\}$. This is called MAP estimation, where MAP stands for “maximum a posteriori”.

3.3 Hammersley - Clifford Theorem

How do we specify a Markov random field? Compared to the case of Markov chains, we might want to specify in terms of a conditional distribution. The following example suggests why this approach goes wrong.

EXAMPLE: Suppose we are designing a Markov random field for images on the 3x3 lattice:

For each pixel, let us specify the conditional distribution of its color given the color of its neighbors. Suppose there are two colors, 0 and 1. But it is possible to specify conditional distributions for each pixel that lead don’t work, i.e., there might be no joint distribution having the given conditional distributions.

In general, we can’t expect to specify a full set of conditional distributions as above. Fortunately, the Hammersley-Clifford Theorem says that a random field’s having the Markov property is equivalent to its having a Gibbs distribution, which is a friendly sort of distribution. Thus, instead of worrying baout specifying our MRF’s in terms of consistent conditional distributions, we can just consider Gibbs distributions, which are simple to write down and work with.

Some definitions needed to state HC:

By combining functions $V_C$ for sets $C$ that are subsets of the same clique, we see that we can further reduce the product in the definiton of Gibbs distribution to

$$p(x) = \prod_{C \text{ a clique}} V_C(x).$$

EXAMPLE: A Markov chain $X_0, ..., X_n$ has joint distribution of the form $p(x_0, x_1, ..., x_n) = \pi_0 (x_0) P_1 (x_0, x_1) P_2 (x_1, x_2) ... P_n (x_{n-1}, x_n)$.

By defining $V_{\{0,1\}} (x_0, x_1) = \pi_0 (x_0) P_1 (x_0, x_1)$ and $V_{\{k-1, k\}} (x_{k-1}, x_k) = P_k (x_{k-1}, x_k)$ for $k>0$, we see that this product is a Gibbs distribution on the graph

$$(x_1) -- (x_1) -- (x_2) -- ... -- (x_n)$$