1.1 Motivation and definition

1.4 Examples

Example Suppose X_i are IID random variables with \mu=E[X_i] and let S_n= X_1 + \cdots + X_n. If we take m < n then we have \begin{aligned} E[S_n|\mathcal{F}_m] & = E[ X_1+ \cdots + X_m|\mathcal{F}_m ] + E[ X_{m+1}+ \cdots + X_n|\mathcal{F}_m ] \\ & = X_1+ \cdots + X_m + E[ X_{m+1}+ \cdots + X_n] = S_m + (n-m)\mu \end{aligned} since X_1 + \cdots + X_m is \mathcal{F}_m measurable and X_{m+1} + \cdots + X_n is independent of X_1, X_2, \cdots, X_m (see Theorem 1.2, properties 2 and 3.)

Example Let S_n as in the previous example and assume that \mu=0 and let \sigma^2=V(X_i) be the variance. If we take m < n we find, using properties 2. 3. and 5. of Theorem 1.2. \begin{aligned} E[S_n^2|\mathcal{F}_m] & = E[ (S_m + (S_n-S_m))^2|\mathcal{F}_m ] \\ &= E[ S_m^2 |\mathcal{F}_m ] +2 E[ (S_n-S_m) S_m | \mathcal{F}_m ] + E[(S_n-S_m)^2|\mathcal{F}_m ] \\ & = S_m^2 + 2 S_m E[ (S_n-S_m)| \mathcal{F}_m ] + E[(S_n-S_m)^2] \\ & + S_m^2 +2 S_m E[ S_n-S_m] + E[(S_n-S_m)^2] \\ & = S_m^2 + V(S_n-S_m) =S_m^2 +(n-m)\sigma^2 \end{aligned}

2.3 Polya Urn

Consider an urn with balls of two colors, say red and green. Assume that initially there is one ball of each color in the urn. At each time step, a ball is chosen at random from the urn. If a red ball is chosen, it is returned and in addition another red ball is added to the urn. Similarly, if a green ball si chosen, is is returned together with another green ball.

Let X_n denote the number of red balls in the urn after n draws. Then X_0=1 and X_n a (time-inhomogeneous) Markov chain with transitions P(X_{n+1}=k+1| X_n=k) = \frac{k}{n+2} \quad \quad P(X_{n+1}=k| X_n=k) = \frac{n+2 -k}{n+2} We now define M_n= \frac{X_n}{n+2} \quad \text{ fraction of red balls after $n$ draws} Then M_n is a martingale since E[X_{n+1}|X_n=k]= (k+1)\frac{k}{n+2} + k \frac{n+2 -k}{n+2} = \frac{k}{n+2} + k \implies E[X_{n+1}|X_n] = X_n + \frac{X_n}{n+2}. Since this is a Markov chain,
E[M_{n+1}|\mathcal{F}_n]=E[M_{n+1}|X_n]= E\left[\frac{X_{n+1}}{n+3}|X_n\right]= \frac{1}{n+3}\left(X_n + \frac{X_n}{n+2}\right) =\frac{X_n}{n+2}=M_n

2.4 Martingale and Markov chains

There is a natural connection between Markov chain and martingale. We explain this in the context of Markov chains but this is just an example. Consider a function f:S \to \mathbb{R} and let us derive an equation for E[f(X_t)]. Using Kolmogorov equation we have \frac{d}{dt}E[f(X_t)] = \frac{d}{dt} \sum_{i} f(i) p_t(i) = \sum_{i} f(i) (p_t A)(i) = \sum_{i} f(i) \sum_{j} p_t(j) A(j,i) = \sum_{j} \sum_{i} A(j,i) f(i) p_t(j) and thus \frac{d}{dt}E[f(X_t)] = E[ g(X_t)] \quad \text{ where } g = Af Integrating the previous equation we find E[f(X_t)] - E[f(X_0)] = \int_0^t E[ Af(X_s)] ds

There is a martingale hidden in this equation. Indeed consider the random variables Y_t = f(X_t) - f(X_0) - \int_0^t Af(X_s) \, ds Our previous calculation shows that E[Y_t]=0, moreover by the Markov property we have E[Y_{t+s} -Y_t | \mathcal{F}_t ] = E[ f(X_{t+s}) - f(X_t) - \int_t^{t+s} Af(X_u) du | X_t ] =0

3.1 Stopping times

A stopping time T with respect to a sequence of random variables X_0, X_1, \cdots should be such that the random time at which you decide to stop depends only on the information you have accumulated so far. If you decide to stop at time n then it should depend only on X_0, \cdots, X_n and you are not allowed to peek into the future.

Example: T=k is a stopping time.

Example: The hitting time T_A =\inf\{j, X_j \in A \}, for some set A, is a stopping time.

Example: If T and S are stopiing time then \min\{S,T\} is also a stopping time. In particular T_n = \min\{T,n\} is a bounded stopping time since T_n \le n and we have T_0 \le T_1 \le \cdots \le T_n \le T.

3.2 The optional sampling theorem (version 1)

The optional sampling theorem says, roughly speaking, that “you cannot beat a fair game” which means that if M_n is a martingale and T is a stopping time then E[M_T]=E[M_0]. This is not true in general as we have seen when considering the martingale betting system where 1=E[M_T]\not= E[M_0]=0. We start with the following result

3.3 The optional sampling theorem (version 2)

To prove a more general version let us assume that P(T < \infty)=1. Then T_n=\min\{T,n\} converges to T and we can write M_{T} = M_{T_n} 1_{\{T\le n\}} + M_{T} 1_{\{T > n\}} = M_{T_n} + M_{T} 1_{\{T >n \}} - M_n 1_{\{T >n \}}

Since T_n is bounded by the optional sampling theorem we have E[M_{T_n}]=M_0. But we need then to control the remaining two terms.

If we assume that M_T is integrable, E[|M_T|]< \infty, the assumption P(T < \infty)=1 means that 1_{\{T>n\}} converges to 0 and thus by the dominated convergence theorem we have \lim_{n \to \infty} E[M_{T} 1_{\{T >n \}}]=0.

The third term is more troublesome. Indeed for the martingale betting systems, if T > n it means we lost n bets in a row which happens with a probability of \frac{1}{2^n} for a total loss of -1 -2 - \cdots - 2^{n-1}=-(2^n-1). Therefore E[M_n 1_{\{T> n\}}] = \frac{1}{2^n}(1-2^n) \to -1 \text{ as } n \to \infty It does not converge to 0 but to 1 in accordance with the result E[M_T]=1.

These considerations leads to the following

3.4 Applications of the optional sampling theorem.

Example: Gambler’s ruin probability. Define S_0=a and S_n = a+ X_1 + \cdots + X_n where X_i arre IID fair bets P(X_i=-1)=P(X_i=1)=\frac{1}{2}.
Then S_n is a martingale and consider the stopping time T = \min \{n :S_n =0 \text{ or } s_n=N \} which describe the time at which a gambler starting with a fortune a either go bankrupt or reach a fortune of N. Note that if T>n then S_n \le N and thus E[|S_n| 1_{\{T> n\}}] \le N P(T >n) \to 0 as n \to \infty. E[S_T] = E[S_0]=a. But we get then a= E[S_T]= N P(S_T=N) \quad \implies P(S_T=N)= \frac{a}{N} This gives another (computation free) derivation of the gambler’s ruin formula! The case p\not= \frac{1}{2} can also be treated using a (different) martingale and will be considered in the homework.

3.5 The Voter Model

We can use martingale like for the gambler’s ruin to analyze much more complicated models. The voter model is a simple opinion dynamics model. Here are the ingredients.

• A graph G=(V,E) is given. At each vertex of the graph is an agent who can be either in state 0 or in state 1. We view this as two different possible opinions for the agent. We describe the state of the system by a vector {\bf \sigma} = \left( \sigma(v)\right)_{v \in V} \quad \text{ with } \sigma(v) \in \{0,1\} and the state space is S=\{0,1\}^{|V|}.

• We think of G as a weighted directed graph. To every directed edge we associate a weight function c(v,w)>0 and define c(v)= \sum_{w} c(v,w). We do not need assume that c(v, w)= c(w,v). But we assume that the graph is connected: there is path along directed edges between any pair of two vertices. To this weight we can associate transition probabilities p(v,w)=\frac{c(v,w)}{c(v)}
  Let Y_n be the Markov chain on the state state space V with transtion probaility p_{vw}. It is irreducible and has a stationary distribution \pi(v). If c(v,w)=c(w,v) then the Markov chain Y_n is irreducible and we know that the stationary distribution is \pi(v) = \frac{c(v)}{c_G} where c_G =\sum_{v} c(v). In general \pi might be difficult to compute explicitly.

3.6 Exercises

4.1 The convergence theorem

The martingale convergence theorem asserts that, under quite general circumstances, a martingale M_n converges to a limiting random variabel M_\infty.

4.2 Uniform integrability

• From the convergence theorem we have M_n \to M_\infty almost surely. In general it does not imply that \lim_{n}E[M_n]=E[M_\infty] without further assumption on M_n. For example, for the martingale betting system we have E[M_n]=0 for all n. However if we stop betting at time T (first win) then our gain after that stay at 1 and thus we have \lim_n {W_n} = 1 almsot surely so M_\infty=1 and clearly E[M_n] does not converge to E[M_\infty]!

• In order to obtain convergence we need a stronger condition on M_n than our assumption \sup_{n}E[|M_n|] \le C <\infty. The proper mathemtical asuumption is that the sequence M_n should be uniformly integrable (see Math 605 for more details). The sequence \{X_n\} is uniformaly integrable if \sup_{n} E[|X_n|1_{|X_n|\ge R}] \to 0 \text{ as } R \to \infty This means that the tail behavior of X_n is controlled uniformly. We have the following

For example if \sup_{n}E[||X_n^2] \le c < \infty then the \{X_n\} are uniformly integrable. The argument is the same as the one used after Theorem 3.2

4.3 Random Harmonic series

Random harmonic series It is well-known that the harmonic series 1 + \frac{1}{2} + \frac{1}{3} + \cdots diverges while the alternating harmonic series 1 - \frac12 + \frac13 - \cdots converges.

What does happen if we chose the sign in the series randomly? Let X_i be IID random variables with P(X_i=-1)=P(X_i=1)=\frac{1}{2}. Let M_0=0 and for n > 0 define M_n = \sum_{j=1}^n \frac{1}{j}X_j\,. Since M_n is a sum of independent random variable with mean 0, it is a martingale and we have E[M_n]=0 for all n.

By the martingale convergence theorem we have M_n \to M_\infty converges almost surely. Therefore the random harmonic series \sum_{j=1}^\infty \frac{1}{j}X_j converges almost surely.

Note that by independence E[M_n^2] = \sum_{j=1}^n \frac{1}{j^2} < \infty and thus M_n is uniformly integrable and E[\sum_{j=1}^\infty \frac{1}{j}X_j]=0.

4.4 Branching process

Suppose X_n is a branching process with offspring distribution given by a random variable Z with mean \mu=E[Z].

First we prove that M_n= \mu^{-n} X_n is a martingale. We have, using the Markov property, that E[X_{n+1}|\mathcal{F}_n]= E[X_{n+1}|X_n] and E[X_{n+1}|X_n=k] = E[Z^{(n)}_1 +\cdots + Z^{(n)}_k] = \mu k and thus E[X_{n+1}|X_n]=\mu X_n. This proves that \mu^{-n} X_n is a Martingale.

If \mu\le 1 we have proved that the probability of extinction is 1 and thus X_n=0 for all n sufficiently large and thus M_n converges to 0 almost surely.

If \mu>1 and then M_n=X_n/\mu^n. By the Martingale convergence theorem we have M_n \to M_\infty. We show that M_\infty is a non-trivial random variable by showing that E[M_\infty]=\lim_n E[M_n]=1 (if we start with single individual).

To do this we need to show uniform integrability. Suppose \sigma^2=V(Z). We have the formula E[(M_{n+1}-M_n)^2|\mathcal{F}_{n}] = E[ M_{n+1}^2|\mathcal{F}_n] -2 E[ M_{n+1} M_n |\mathcal{F}_n] + E[M_n^2|\mathcal{F}_n] = E[ M_{n+1}^2|\mathcal{F}_n] - M_n^2 and so E[ M_{n+1}^2|\mathcal{F}_n] =M_n^2 + E[(M_{n+1}-M_n)^2|\mathcal{F}_{n}] To compute the second term note that E[(M_{n+1}-M_n)^2|\mathcal{F}_{n}]=E[ (\mu^{-(n+1)}X_{n+1}- \mu^{-n} X_n)^2|\mathcal{F}_{n}]= \mu^{-2(n+1)}E[ (X_{n+1}-\mu X_n)^2|\mathcal{F}_{n} ] Now E[ (X_{n+1}-\mu X_n)^2|X_n=k] = E[ ( Z^{(n)}_1 +\cdots + Z^{(n)}_k -\mu k)^2 ]= k \sigma^2 and so E[ (X_{n+1}-\mu X_n)^2|X_n]= X_n \sigma^2.

Combining all this gives (using again that E[\mu^{-n}X_n]=E[M_n]=1) E[M_{n+1}^2] = E[M_n^2] + \mu^{-2(n+1)}\sigma^2 E[X_n] = E[M_n^2] + \frac{\sigma^2}{\mu^{n+2}} Using that E[M_0^2]=1 we find E[M_1]=1+ \frac{\sigma^2}{\mu^2} and by induction E[M_n^2] = 1 + \sigma^2 \sum_{k=2}^{n+1} \frac{1}{\mu^k} This proves that \sup_{n}E[|M_n|^2] < \infty and thus M_n is uniformly integrable.

Thus M_\infty is non-trivial.

4.5 Estimating the mean in Bayesian statistics

Estimation problem Suppose X_1, X_2, \cdots are IID random variables whose mean E[X_i]=\theta^* is unknown. In a Bayesian spirit we equip \theta with a probability distribution (called the prior distribution) and called this random variable \Theta.

Example: The simplest model is when X_i are Bernoulli random variables with a unknown probability of success \theta. A natural prior distribution for \Theta is the uniform distribution on [0,1]. In this case we would have the joint distribution f(x_1, \cdots, x_n ,\theta) = f(x_1, \cdots, X_n |\theta)f(\theta)= {n \choose k} \theta^{x_1+\cdots+ x_n} (1-\theta)^{n-x_1+\cdots+ x_n}

There is a natural martingale associated, namely M_0 = E[\Theta], \quad \quad M_n =E[\Theta|X_1, \cdots, X_n] This means that M_0 is the expectation of \theta under the prior distribution f(\theta) and M_n is the expectation of \theta inder the posterior distribution f(\theta|x_1, \cdots, x_n).

By the martigale convergence theorem (under suitable assumptions on \theta to assure uniform integrability of M_n, for example if \Theta is bounded) we have \lim_{n \to \infty} M_n = M_\infty where M_\infty is a random variable which depends on the infnite sequence X_1, X_2, \cdots.

Since for m> n we have M_n = E[M_m|X_1, \cdots, X_n] taking m \to \infty shows that M_n=E[M_\infty|X_1, \cdots, X_n]. Since \theta is the mean, by the LLN, for fixed \theta we have \theta= \lim_{n\to \infty} \frac{X_1 + \cdots + X_n}{n} and thus \theta is a function of X_1, X_2, \cdots. This shows that M_\infty=\theta and thus \lim_{n \to \infty} E[\Theta|X_1, \cdots, X_n] = \theta

In our simple example we can compute the posterior distribution by Bayes rule (after dusting up our knowledge of the Beta random variables) f(\theta|x_1,\cdots, x_n ) = \frac{{n \choose k} \theta^{x_1+\cdots+ x_n} (1-\theta)^{n-x_1+\cdots+ x_n}}{\int_0^1 {n \choose k} \theta^{x_1+\cdots+ x_n} (1-\theta)^{n-x_1+\cdots+ x_n} d\theta} = \frac{(n+1)!}{k! (n-k)!} \theta^{x_1+\cdots+ x_n} (1-\theta)^{n- x_1+\cdots+ x_n} which a beta random variable with parameter \alpha=k+1 and \beta=n+1-k. The mean of beta random variables with parameters \alpha and \beta is \frac{\alpha}{\alpha + \beta} E[\Theta| X_1, \cdots, X_n] = \frac{1+ X_1+ \cdots + X_n}{n+2}

This is related to the Polya’s urn. To see this let us compute P(X_1+ \cdots + X_{n+1}=k+1|X_1+ \cdots+ X_n=k) under that model. By conditioning we find \begin{aligned} & P(X_1+ \cdots + X_{n+1}=k+1|X_1+ \cdots+ X_n=k) \\ &= \int_0^1 P( X_{n+1}=1|\Theta=\theta) f(\theta|X_1+\cdots X_n=k) d\theta = E[\theta|X_1+\cdots X_n=k]=\frac{k+1}{n+1} \end{aligned}

4.6 Polya’s urn again

Let us consider the general Polya’s urn starting with r red balls and g green balls. At each time a ball is drawn at random, replaced in the urn together with c extra balls of the same color.

We let X_n to be the number of green balls at time n and M_n=\frac{X_n}{r+g+nc} to be fraction of green balls at time n. We P(X_{n+1}=j+c|X_n=j) = \frac{j}{r+g+nc} \quad \quad P(X_{n+1}=j|X_n=j)=\frac{r+g+nc-j}{r+g+nc} Thus \begin{aligned} E[M_{n+1}|X_n=j]&= \frac{j+c}{r+g+(n+1)c}\frac{j}{r+g+nc} + \frac{j}{r+g+(n+1)c} \frac{r+g+nc-j}{r+g+nc} \\ & = \frac{j(r+g +(n+1)c)}{(r+g+(n+1)c)(r+g+n+c)} = \frac{j}{r+g+n+c} \end{aligned}

This implies that M_{n+1} is a martingale and by the martingale convergence theorem we have M_n \to M_\infty. Let us compute the distribution of M_\infty. To do this imagine that in n draws the first m ones are green and the last l=n-m are red. This event has probability \frac{g}{g+r}\frac{g+c}{g+r+ c}\cdots \frac{g+ (m-1)c}{g+r +(m-1)c} \frac{r}{g+r+mc}\cdots \frac{r+ (n-m-1)c}{g+r +(n-1)c} Observe that drawing m green balls and l=n-m red balls in n draws in any order has exactly the same probability: the deonminator remains the same but the terms in the numerator are permuted.

This is all we need. As a warm up let us consider the special case r=g=c=1 we have P(X_n= m+1) = {n \choose m} \frac{m!(n-m)!}{(n+1)!} = \frac{1}{n+1} \quad m=0,1,2,\cdots, n This shows M_n converges to the uniform distribution on [0,1]. P(X_n= m+2) = {n \choose m} \frac{m!(n-m)!}{(n+1)!} = \frac{1}{n+1} \quad m=0,1,2,\cdots, n

Next let us consider c=1 and g, r arbitrary \begin{aligned} P(X_n= m+g+r) & = {n \choose m} \frac{r(r+1)\cdots (r+m-1) g (g+1) \cdots (g+n-m-1)} {(g+r)(g+r+1) \cdots (g+r+(n-1))} \\ &= \frac{(g+r-1)!}{(r-1)!(g-1)!} \frac{n!}{m!(n-m)!} \frac{(r+m-1)! (g+n-m-1)!} {(g+r+(n-1))!} \\ &= \frac{(g+r-1)!}{(r-1)!(g-1)!} \frac{m^{r-1} (n-m)^{g-1} }{n^{r+g-1}} \frac{\frac{(r+m-1)!}{m!m^{r-1}} \frac{(g+n-m-1)!}{(n-m)!(n-m)^{g-1}}}{\frac{(g+r+(n-1))!}{n!n^{r+g-1} }} \end{aligned}

We now take the limit n \to \infty and m \to \infty such that \frac{m}{n}\to x and \frac{n-m}{n} \to 1-x Note that \frac{a + (n-1)!}{n! n^{r+g-1} } = \frac{(n +1)}{n} \frac{n+2}{n} \frac{n+a-1}{n} \to 1 \quad \text{ as } n \to \infty Therefore as n \to infty P(M_n= \frac{m+g+r}{r+g+n} \to \frac{(g+r-1)!}{(r-1)!(g-1)!} \left( \frac{m}{n}\right)^{r-1} \left(\frac{n-m}{n}\right)^{g-1} \frac{1}{n} By a Riemann sum argument this shows that the distribution of M_n converges to beta random variable with parameters g and r.

A similar argument shows that if c>1 then M_n converges to beta random variable with parameters g/c and r/c.

5.1 Conditional Jensen inequality

If \phi: \mathbb{R} \to \mathbb{R} is a convex function then the graph of \phi lies above any tangent line to the graph and so for any point x_0 we can find a number a such that \phi(x) \ge \phi(x_0)+ a (x-x_0) If \phi is differentiable at x_0 then a=\phi'(x_0) while in general we have more than one choice for a. This simple geometric observation lies behind Jensen inequality, a simple, yet so important inequality.

5.2 Hoeffding’s bound

Recall that if X is a normal random variable then its moment generating function is given by E[e^{tX}]= e^{\mu t + \frac{\sigma^2 t^2}{2}} which implies, by Chernov bound the concentration bound P( X - E[X] \ge \epsilon) \le \inf_{t \ge 0} \frac{E\left[e^{t(X- E[X])}\right]}{e^{t\epsilon}} = e^{- \sup_{t \ge 0} \left\{ t\epsilon - \frac{\sigma^2 t^2}{2} \right\} } = e^{-\frac{\epsilon^2}{2\sigma^2}} Note that we also have a similar bound for the left tail, P(X-E[X]\le - \epsilon) \le e^{-\frac{\epsilon^2}{2\sigma^2}} prove in the same way.

It turns out that bounded random variables also satisfies such Gaussian concentration bound. To do this we need the following fact which expresses the fact that among all random variable supported on the interval [-A,B] with mean 0 the one which is most spread out is a random variable concentrated on the endpoints -A and B.

5.3 Azuma-Hoeffdings concentration inequality

The next theorem provides concentration inequality for martingales with bounded increments.

5.4 McDiarmid Theorem

McDiarmid theorem is an application of Azuma-Hoeffdings theorem and provides concentration bounds for (nonlinear) function of independent random variables X_1, \cdots, X_n, under certain conditions.

5.5 Balls and Bins

Another classical example in probability is the so-called “Balls and Bins problem”: suppose we have m balls that are thrown in n bins, the location of each ball is chosen at random independently of the other balls. It turns out this problem occur in manay algorithmic optmization problems. We can ask many questions realated to this problem. For example what is the probability that one bin has more than two balls in it (this is a version of the famous birthday problem!), or we can ask what is the maximal number of balls in a bin or the number of empty bins, and so on…

Let us compute first the expected number of empty bins. We write N=X_1 + \cdots X_n where X_i=1 is the i^{th} bin is empty and 0 otherwise. For the first urn to be empty, it must be missed by all balls and this occur with probbaility \left(1-\frac{1}{n}\right)^m and thus E[N]= n\left(1-\frac{1}{n}\right)^m We prove a concentration bound around the mean using a martingale argument. We consider the sequence of random variable Y_i to be the bin in which the i^{th} ball falls and write N=N(Y_1, \cdots, Y_m). To apply Theorem 5.4 we check the bounded difference equality. Consider how N changes when we change the location of the i^{th} ball. If the i^{th} balls lands in a bin of its own then changing Y_i may increase N by 1 or left it unchanged. If it lands in a bin with other balls, then changing Y_i may decrease N by 1. Then, by Theorem 5.3 we have P(|N - E[N]|\ge \epsilon)\le 2 e^{-\frac{2\epsilon^2}{m}}

5.6 Empirical processes

As another application of Azuma-Hoeffding’s theorem we consider empirical processe which are given by Z(X_1, \cdots, X_n)=\sup_{f \in \mathcal{F}} \left| \frac{1}{n}\sum_{k=1}^n f(X_i) - E[f(X_i)] \right| where X_i are IID random variables and f belongs to a class of function \mathcal{F}. We assume here that \sup_{x}|f(x)| \le B \text{ for all } f \in \mathcal{F} i.e. the functions f are uniformly bounded. One of the simplest example of empirical process to consider the function f_t(x)=1_{x \le t}. By the LLN we have \frac{1}{n}\sum_{k=1}^n 1_{\{X_i\le t\}} \to P(X \le t)=F_X(t) \quad \text{ almost surely} where F_X is the distribution of the RVs X_i. By Glivenko–Cantelli Theorem we have \sup_{t \in \mathbb{R} }| \frac{1}{n}\sum_{k=1}^n 1_{\{X_i\le t\}} - F_X(t)| \to 0 \quad \text{ almost surely} that is we have uniform convergence of the empirical distribution to the true distribution.

6.1 Martingale and Markov chain

Consider a Markov chain X_j with state space S and transition probabilities P and consider a bounded function f: S \to \mathbb{R} .
We want to construct a martingale associated to the sequence of random variables f(X_j), j=0,1,2,\cdots.
If the f(X_j) were independent it would be enough to assume that they have mean 0.
In general we use the following idea. If we have sequence of integrable RV Y_1, Y_2, \cdots then we set D_m= Y_m - E[Y_m|Y_0, \cdots, Y_{m-1}] and we have then E[D_m|Y_0, \cdots, Y_{m-1}]=0. So we can build a martingale by M_n = \sum_{j=1}^n D_j = \sum_{j=1}^n (Y_m - E[Y_m|Y_0, \cdots, Y_{m-1}]) \,.

The same idea works for Markov chain: if f is bounded then, using the Markov property D_m = f(X_m)- E[f(X_m)|Y_0, \cdots, Y_{m-1}] = f(X_m)- E[f(X_m)| Y_{m-1}] = f(X_m) -Pf(X_{m-1}) is a martingale increment with respect to the sequence X_1, X_2, \cdots.

6.2 Poisson equation

What we have uncovered to build a martingale from a Markov chain is an important equation

Note that Poisson equation needs not have a solution for arbitrary g. We investigate this in the context of finite state space Markov chain.

6.3 Central limit theorem

We can now use this to prove a central limit theorem for Markov chain.

6.4 Peskun theorem

In the context of Monte-Carlo methods one can try and use the central limit theorem as way to compare different Monte-Carlo Markov chain methods used to sample the same distribution \pi. Indeed the smaller the variance, the “better” the Monte-Carlo will perform since the fluctuations around the stationary values \pi g will be smaller.

The following theorem is a result in this direction. It shows that the more a Monte-Carlo Markov chain “jumps”, the smaller the asymptotic variance will be.