• The function E[Y|X=x] defines a function of the random variable X which we define to be E[Y|X]. For example if we roll two independent dice and X is value of the first roll and Y the sum of the two rolls
  then we have f(x,y) = \frac{1}{36}\,, \quad x=1,2,\cdots, 6 \quad y= x+1, \cdots, x+6. and this
  E[Y|X=x] = x + \frac{7}{2} so that E[Y|X]=X + \frac{7}{2}.

• In a similar way we can define E[Y|X_1,\cdots, X_n] for discrete RV with joint pdf p(x_1, \cdots, x_n, y).

Example: continuous RV: In a similar way, if Y,X_1, \cdots X_n are continuous RV with a joint pdf f(x_1, \cdots, x_n,y) with marginal f(x_1, \cdots,x_n)=\int f(x_1, \cdots, x_n,y) dy then the function y \mapsto \frac{f(x_1, \cdots, x_n,y)}{f(x_1, \cdots,x_n)} defines a probability density function provided (x_1, \cdots,x_n) is such that f(x_1, \cdots,x_n)\not=0. Then the expectation E[Y|X_1=x_1 \cdots X_n=x_n] = \int y \frac{f(x_1, \cdots, x_n,y)}{f(x_1, \cdots,x_n)} \, dy defines a function of (x_1, \cdots,x_n). We leave this function undefined whenever f(x_1, \cdots,x_n)=0 (or set it to 0 if you prefer).

Any function of h(x_1,\cdots,x_n) can be used to define a RV h(X_1, \cdots,X_n). Note that, as a RV, this
does not depend on how the function is defined when f(x_1, \cdots,x_n)=0 since such x have probability 0.

We call the corresponding random variable E[Y|X_1,\cdots, X_n] and call it the conditional expectation of Y given X_1,\cdots, X_n.

Example If X_i are Bernoulli RV and m <n let us compute E[S_m|S_n]. Note first that P(X_1=1| S_n=k) =\frac{p {n-1 \choose k-1} p^{k-1}(1-p)^{n-k}}{{n\choose k}p^k (1-p)^{n-k}} = \frac{k}{n} \implies E[X_1|S_n] = \frac{S_n}{n} and thus E[S_m|S_n] = \frac{m}{n} S_n \,.

Example One of the prototype of a martingale is given by sum of IID random variables. Let S_0=0\,, \quad S_n=X_1 + \cdots X_n As we have seen before, if m< n,
E[S_n|\mathcal{F}_m]= S_m +(n-m)\mu This implies that M_n= S_n-n\mu is a martingale.

Example Suppose Y is a random variable with E[|Y|]< \infty. Then we can build a martingale with respect to \mathcal{F}_n by setting M_n = E[Y|\mathcal{F_n}] Indeed we have, for m \le n E[M_n|\mathcal{F_m}] = E[E[Y|\mathcal{F_n}]\mathcal{F_m}]= E[Y|\mathcal{F}_m]=M_m In that case we say that the martingale is closed by the random variable Y and we can think of M_n as succesively “better” approximation of Y as we incorporate more and more information.

Clearly W_n is \mathcal{F}_n measurable and E[|W_n|]< \infty. Moreover we have \begin{aligned} E[W_{n+1}|\mathcal{F}_n]& = E[B_{n+1} X_n| \mathcal{F}_{n}] + E[W_n| \mathcal{F}_{n}] = B_{n+1} E[X_n| \mathcal{F}_{n}] + W_n = W_n \end{aligned} where we have used that B_{n+1} is \mathcal{F}_m measurable and E[X_n]=0.

The martingale property implies that E[W_n] is constant: we have E[W_n] = E[ E[W_n|\mathcal{F}_{n-1}]] =E[W_{n-1}] which means that your expected winning in fair game is zero.

But this is not the end of the story. In a betting strategy you will do a sequence of bet and decide of a good moment when you actually stop betting. Consider for example the following well known strategy (often called the martingale strategy): double your bet until you win. If you win the first game you stop and take you gain of W_1=1. If you lose the first game you bet 2 on the second game. If you win the second game you winning is W_2=-1+2 =1 and then stop. If you lose the first two games you know bet 4 on the third game abnd if you win the third game you winning is W_3=-1-2+4=1, and so on… We have then the transition probabilities P(W_{n+1}=1|W_n=1)=1 and P(W_{n+1}=1|W_n=-(2^n-1))=\frac{1}{2} P(W_{n+1}=-(2^{n+1}-1)|W_n=-(2^n-1))=\frac{1}{2} and this is a martingale. It is true that E[W_n]=0 but however when you stop, which happens at a random time T, you always win $1! The time T at which you first win occurs has here a geometric distribution. We will consider stopping time in the next section.

\begin{aligned} E[M_{T}|\mathcal{F}_{K-1}] & = E[ M_K 1_{\{T> K-1\}} | \mathcal{F}_{K-1}] + \sum_{j=0}^{K-1} E[ M_j 1_{\{T=j\}}|\mathcal{F}_{K-1}] \\ & = 1_{\{T> K-1\}} E[ M_K | \mathcal{F}_{K-1}] + \sum_{j=0}^{K-1} M_j 1_{\{T=j\}} = 1_{\{T> K-1\}} M_{K-1} + \sum_{j=0}^{K-1} M_j 1_{\{T=j\}} \\ & = 1_{\{T> K-2\}} M_{K-1} + \sum_{j=0}^{K-2} M_j 1_{\{T=j\}} \end{aligned} where we used that M_j 1_{\{T=j\}} is \mathcal{F}_{K-1} measurable if j\le k-1.

Using this we find \begin{aligned} E[M_{T}|\mathcal{F}_{K-2}]&=E[ E[M_{T}|\mathcal{F}_{K-1}]|\mathcal{F}_{K-2}]\\ & = E[ 1_{\{T> K-2\}} M_{K-1}|\mathcal{F}_{K-2}]+ \sum_{j=0}^{K-2} E[M_j 1_{\{T=j\}}|\mathcal{F}_{K-2}] \\ &= 1_{\{T> K-3\}} M_{K-2} + \sum_{j=0}^{K-3} M_j 1_{\{T=j\}} \end{aligned} and thus, inductively, E[M_T|\mathcal{F}_0]= M_0 \quad \blacksquare

Remark If the sequence M_n is uniformly bounded, i.e. |M_n| \le C then the optional sampling theorem holds since
E[ |M_n| 1_{\{T>n\}}] \le C P(T >n).

Remark Another condition which gurantees the optional sampling theorem is if \sup_{n}E[M_n^2] < \infty. Indeed if this holds given \epsilon>0 we have \begin{aligned} E[|M_n| 1_{T>n}] & = E[|M_n| 1_{|M_n| > C/\epsilon} 1_{T>n}] + E[|M_n| 1_{|M_n| \le C/\epsilon} 1_{T>n}] \\ & \le \frac{\epsilon}{C} E[|M_n|^2 1_{\{T>n\}} ] + \frac{C}{\epsilon}P(T >n) \le \epsilon + \frac{C}{\epsilon}P(T >n) \end{aligned} Taking n \to \infty shows that \lim_{n} E[|M_n| 1_{\{T>n\}}] \le \epsilon.

Example: Gambler’s ruin playing time. Suppose S_n is like in the previous example. Then M_n=S_n^2 -n is also martingale since E[S_{n+1}^2- {n+1} | \mathcal{F_n}]= E[S_n^2 + 2X_{n+1}S_n + X_{n+1}^2- {n+1} | \mathcal{F_n}] = S_n^2 + 1 - (n+1) = S_n^2 -n To apply the optional sampling theorem we note that P(T>n) \le C \rho^n since T is a hiting time for a finite state Markov chain.
Therefore we have E[|S_n| 1_{\{T> n\}}] \le (N^2 + n^2) C \rho^n \to 0 and we can apply the optional sampling theorem and E[M_T] =E[M_0]=a^2 But, using the previous example we find
a^2= E[M_T] = E[S_T^2] - E[T] = N^2 P(S_T=N) - E[T] = aN - E[T] and thus E[T]= a(N-a) which gives the expected length of play.

Example: 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? To see this let X_i be IID random variables with P(X_i=-1)=P(X_i=1)=\frac{1}{2}. Let M_0=o and for n \ge 0 define M_n = \sum_{j=1}^n \frac{1}{j}X_j is a martingale with E[M_n]=0 and E[M_n^2] = \sum_{j=1}^n \frac{1}{j^2} < \infty.

• In the voter model, at each unit time you pick a voter, say voter at vertex v. The voter picks one of his neighbor w with probability p_{vw} and his neighbor at W has a different opinion than his opinion the voter at v adopts the opinion of w. This is admittedly a pretty simplisitic model but let us anlayze it nonetheless. Let denote by X_n the corresponding Markov chain on S. The transition probabilities are given by \begin{aligned} P( {\bf \sigma}, {\bf \sigma} + {\bf e}_v ) &= \frac{1}{|V|} 1_{\{\sigma(v)=0\}} \sum_{w : \sigma(w)=1} p(v,w) \\ P( {\bf \sigma}, {\bf \sigma} - {\bf e}_v ) & = \frac{1}{|V|} 1_{\{\sigma(v)=1\}} \sum_{w : \sigma(w)=0} p(v,w) \end{aligned} where {\bf e}_v is the state with {\bf e}_v(v)=1 and {\bf e}_v(w)=0 if w\not= v.

• The key insight is the following

Using the fact that \pi is the stationary distribution we have the balance equation \sum_{v} \pi(v) p(v,w) = \sum_{v} \pi(w) p(w,v) Using this and then exchanging the indices v and w we find
\sum_{w:\sigma(w)=0} \sum_{v} \pi(v)p(v,w) = \sum_{w:\sigma(w)=0} \sum_{v} \pi(w)p(w,v) = \sum_{v:\sigma(v)=0} \sum_{w} \pi(v)p(v,w) which implies that E[M_{n+1}-M_{n}| X_n =\sigma] =0 and therefore M_n is a martingale. \quad \blacksquare

We can now apply Theorem 3.2 where we take the stopping time to be the consensus time at which everyone is agreement. T= \inf\{ n, X_n(v)=0 \text{ for all } v \text{ or } X_n(v)=1 \text{ for all } v Since the Markov chain has finite state space P(T < \infty)=1 and M_n is bounded (in fact 0 \le M_n\le 1). We have like for the gambler’s ruin P(X_T =(1,\cdots, 1))=E[M_T]= E[M_0]= \pi X(0)

Example If the underlying model is a random walk on the graph c(v,w)=c(w,v)=1 then \pi(v) = \frac{\deg(v)}{2|E|} and we can easily compute
\pi X_0. For example if we consider the complete graph on N vertices or any regular graph such that all vertices have the same degree then P(X_T =(1,\cdots, 1)) is simply equal to the proportion of vertices with opinion 1.

Example: Suppose S_n = X_1 + \cdots + X_n is a sum of IID random variables such that E[X_i]=\mu and a \le X_i \le b. Then the function h(x_1, \cdots, x_n) satisfies the bounded difference property with c_k=(b-a) and we obtain the classical Hoeffding’s theorem for bounded random variables \begin{aligned} P \left( \frac{X_1 + \cdots + X_n}{n} - \mu \ge \varepsilon \right) &\le e^{- \frac{2 n \varepsilon^2}{(b-a)^2}}\ \end{aligned}

Example: Suppose we are interested in estimating the variance. Then using the unbiased variance estimator V_N(X_1, \cdots, X_N)=\frac{1}{N-1} \sum_{k=1}^N\left(X_i - \frac{S_N}{N}\right)^2 = \frac{1}{N-1}\sum_{i=1}^N X_i^2 - \frac{S_N^2}{(N-1)N} If we change X_1 into \widehat{X}_1 then S_N(X_1, \cdots, X_N ) - S_N(\widehat{X}_1, \cdots, X_N ) = X_1 - \widehat{X}_1 and so V_N(X_1, \cdots, X_N)- V_N(\widehat{X}_1, \cdots, X_N) = \frac{X_1^2 - \widehat{X}_1^2}{N-1} - \frac{X_1 - \widehat{X}_1}{N-1} \left(\frac{S_N(X_1, \cdots, X_N )}{N} + \frac{S_N(\widehat{X}_1, \cdots, X_N )}{N} \right)

Let us assume a \le X_i \le b, since we can replace X_i by X_i -(a+b/2) without changing V_N we can instead assume that -\frac{(b-a)}{2} \le X_i \le \frac{(b-a)}{2} and then find the bounded difference bound |V_N(X_1, \cdots, X_N)- V_N(\widehat{X}_1, \cdots, X_N)| \le \frac{\frac{5}{4}(b-a)^2}{N-1} = c_k and thus by McDiarmid we get P( V_N - \sigma^2 \ge \varepsilon ) \le e^{- \frac{\varepsilon^2}{2 \sum_{k=1}^N c_k^2}} \le e^{ - \frac{(N-1)^2}{N} \frac{4 \varepsilon^2}{50 c^4}} \,\le\, e^{ -(N-2)\frac{4\varepsilon^2}{50c^4}} and this decay exponentially in N again and can be used for a confidence interval for the variance which is very similar to the one for the mean.

Empirical processe satisfy the bounded difference property: indeed if we set g(x_1, \cdots, x_n) = \left| \frac{1}{n}\sum_{k=1}^n f(x_i) - E[f(X)] \right| Then g(x_1, \cdots, \tilde{x}_k, \cdots, x_n) = \left| \frac{1}{n}\sum_{k=1}^n f(x_i) - E[f(X)] + \frac{1}{n} (f(\tilde{x}_k) - f(x_k)) \right| \le g(x_1, \cdots, \tilde{x}_k, \cdots, x_n) + \frac{2B}{n} from which we conclude that Z(x_1, \cdots, \tilde{x}_k, \cdots, x_n) \le Z(x_1, \cdots, {x}_k, \cdots, x_n) +\frac{2B}{n}. Interchanging x_k and {\tilde x}_k proves the bounded difference property with c_k=\frac{2B}{n}. Then Theorem 4.3 show that, for every \epsilon>0. P(|Z - E[Z]|> \epsilon) \le 2 e^{-\frac{n \epsilon^2}{2 B^2}} This tells us that the behavior of Z is control by its mean E[Z]. For example if we set \delta=e^{-\frac{n \epsilon^2}{2 B^2}} we have |Z-E[Z]| \le B \sqrt{\frac{2}{n}\log \frac{1}{\delta}} \quad \text{ with probability at least } 1- 2 \delta for any \delta >0.

To go further we need to control the mean E[Z] and to do this we need two results.

Note that if Y_i satisfies the condition of the theorem so does -Y_i and thus we also have E[ \max_{i} |Z_i| ] = E[ \max_{i} \max\{ Z_i, -Z_i\} ] \le \sigma \sqrt{ 2 \log{2 N}} \le 2 \sigma \sqrt{ \log{N}}

This is a very useful since have gotten rid of E[f(X_i)] which maybe unknown and we have now a quantity which depnds only on the data X_1, \cdots, X_n. How useful this can be is deonstrated next in the context of Glivenko-Catelli Theorem.

We obtain therefore the martingale \begin{aligned} M_n = \sum_{j=1}^n f(X_j) -Pf(X_{j-1}) & = f(X_n) -f(X_0) + \sum_{j=0}^{n-1} (f(X_j)- Pf(X_j)) \\ & = f(X_n) -f(X_0) - \sum_{j=0}^{n-1} Af(X_j) \end{aligned} \tag{5.1} for f bounded and where we used the notation A=P - I. This martingale is called the Dynkin’s martingale.

If we want to apply martingale theory to analyze the sum \sum_{j=1}^n g(X_j) then we would like to use the martingale Equation 5.1. To do this we must a find a function f such that Af = (P -I)f = - g Then we would have a martingale M_n = f(X_n) - f(X_0) + \sum_{j=0}^{n-1} g(X_j) \quad \quad \text{ with } Af = -g which, up to the correction term f(X_n) - f(X_0) is equal to \sum_{j=1}^n g(X_j).

We claim that E\left[ \frac{e^{i \theta M_n}}{\prod_{j=1}^n E[ e^{i \theta} D_j |\mathcal{F}_{j-1}] } \right] =1 \tag{5.2} Indeed, using the properties of conditional expectations we have \begin{aligned} & E\left[ \frac{e^{i \theta M_n}}{\prod_{j=1}^n E[ e^{i \theta} D_j |\mathcal{F}_{j-1}] } \right] = E \left[ E\left[ \frac{e^{i \theta M_n}}{\prod_{j=1}^n E[ e^{i \theta} D_j |\mathcal{F}_{j-1}] } | \mathcal{F}_{n-1} \right]\right] = E \left[ \frac{E[e^{i \theta M_n}|\mathcal{F}_{n-1}]}{\prod_{j=1}^n E[ e^{i \theta} D_j |\mathcal{F}_{j-1}] } \right] \\ & = E \left[ \frac{E[e^{i \theta M_{n-1}+D_n}|\mathcal{F}_{n-1}]}{\prod_{j=1}^n E[ e^{i \theta} D_j |\mathcal{F}_{j-1}] } \right] = E \left[ \frac{ e^{i \theta M_{n-1}} E[e^{i \theta D_{n}}|\mathcal{F}_{n-1}]}{\prod_{j=1}^n E[ e^{i \theta} D_j |\mathcal{F}_{j-1}] } \right] = E\left[ \frac{e^{i \theta M_{n-1}}}{\prod_{j=1}^{n-1} E[ e^{i \theta} D_j |\mathcal{F}_{j-1}] } \right] \\ \end{aligned} Iterating proves the statement. We now use a Taylor expansion to find \log E[e^{i\frac{\theta}{\sqrt{n}}D_j}|\mathcal{F}_{j-1}] = - \frac{\theta^2}{2n}E[D_j^2|\mathcal{F}_{n-1}] + \frac{1}{\sqrt{n}} R_n where R_n is a bounded random variable. Note that E[D_j^2|\mathcal{F}_{n-1}] = E[(f(X_j) - Pf(X_{j-1}))^2 | X_{j-1} ] = Pf^2(X_{j-1}) - (Pf(X_{j-1}))^2

Using the the strong law of large numbers for Markov chain,
\lim_{n \to \infty }\sum_{j=1}^\infty \log E[e^{i\frac{\theta}{\sqrt{n}}D_j}|\mathcal{F}_{j-1}] = - \frac{\theta^2}{2} \pi (Pf^2 - (Pf)^2) \quad \text{ almost surely} Therefore, from Equation 5.2, we find that \lim_{n \to \infty} E\left[ e^{i \theta M_n} \right] = e^{-\frac{\theta^2 \sigma^2}{2}} where \sigma^2 = \pi (f^2 - (Pf)^2) .
Since \frac{1}{\sqrt{n}}M_n and \frac{1}{\sqrt{n}}\sum_{j=0}^{n-1} {\overline h}{X_j} only differ by \frac{1}{\sqrt{n}}(f(X_n)-f(X_0)) we obtain the central limit theorem. \quad \blacksquare.