Appendix B — Conditional expectations and martingales

In this appendix, we provide an introduction to conditional expectation, various notions of convergence of random variables, and martingales.

B.1 Conditional expectation

We first handle the case of a discrete r.v.

Definition B.1.

The conditional probability mass function of a r.v. \(Y\) given \(X=x\) is \(p_{Y\mid X}(y\mid x)=\prob{Y=y\mid X=x}\). Given \(\{X=x\}\), the distribution of \(Y\) has a probability mass function \(p_{Y\mid X}(y\mid x)\) and the expected value of this distribution, denoted as \(\E\left[Y\mid X=x \right]\), is given by

\[ \E\left[Y\mid X=x \right] = \sum_y y p_{Y\mid X}(y\mid x). \]

We shall use the notation \(\E\left[Y\mid X \right]\) to denote the conditional expectation of \(Y\) given \(X\).

Next, we extend the notion of conditional expectation to a continuous r.v.

Definition B.2.

Suppose \(X,Y\) are continuous r.v.s with joint density \(f\). Then, the conditional probability density function, denoted by \(f_{Y\mid X}(y\mid x)\), is defined as follows:

\[ f_{Y\mid X}(y\mid x) = \frac{f(x,y)}{f_X(x)}, \textrm{ for } x \textrm{ s.t. } f_X(x)>0. \]

In the above, \(f_X\) denotes the marginal density of \(X\).

The conditional expectation of \(Y\) given \(\{X=x\}\), denoted as \(\E\left[Y\mid X=x \right]\), is given by

\[ \E\left[Y\mid X=x \right] = \int_{-\infty}^{\infty} y f_{Y\mid X}(y\mid x)dy. \]

As before, \(\E\left[Y\mid X \right]\) denotes the conditional expectation of \(Y\) given \(X\).

In the above definitions, we have followed a simpler definition that covers discrete and continuous r.v.s, along the lines of (Grimmett and Stirzaker 2020). A more general definition of the conditional expectation of \(Y\) given a sigma field \(\F\), denoted by \(\E\left[\left.Y\right|\F\right]\), is any random variable \(Z\) that is \(\F\)-measurable and satisfies

\[ \E\left[Y\mathbb{I}_A\right]=\E\left[Z\mathbb{I}_A\right], \forall A \in \F, \]

where \(\mathbb{I}_A\) is the indicator function that takes value \(1\) on the set \(A\) and \(0\) otherwise.

Such a \(Z\) is unique almost surely, and this definition is more general in the sense that it does not rely on the existence of a conditional distribution, see (Durrett 2019) for a detailed exposition. In the rest of this appendix, if not explicitly mentioned, equality between random variables should be interpreted in the almost sure sense.

We list some useful properties of conditional expectation.

Proposition B.1.

The conditional expectation \(\E \left[Y\mid X\right]\) satisfies the following properties:

  1. \(\E\left[ \E\left[Y\mid X \right]\right] = \E Y\).

  2. \(\E\left[ \E\left[Y\mid X \right] g(X)\right] = \E\left[ Y g(X)\right]\) for any \(g\) such that both expectations exist.

  3. \(\E\left[ aY + bZ\mid X \right] = a\E \left[Y\mid X\right] + b\E \left[Z\mid X\right]\).

  4. \(\E \left[Y\mid X\right] = \E Y\) if \(X\) and \(Y\) are independent.

  5. \(\E \left[Y g(X)\mid X\right] = g(X)\E \left[Y\mid X\right]\) for \(g\) such that the expectations exist.

  6. \(\E\left[ \E\left[Y\mid X,Z \right]\mid X\right] = \E\left[ \E\left[Y\mid X \right]\mid X,Z\right] = \E\left[Y\mid X\right]\).

B.2 Notions of convergence of random variables

Definition B.3 (Almost sure or with probability 1 convergence).

Let \(X_m,m\geq 0\) and \(X\) be random variables defined on a common probability space \((\Omega,\mathcal{F},P)\). Then, \(X_m \rightarrow X\) almost surely or \(X_m \rightarrow X\) with probability 1 as \(m \rightarrow \infty\) if \(\prob{\left.w \right| \lim_{m\to\infty} X_m(w) = X(w)} = 1\).

A well-known example of almost sure convergence is the strong law of large numbers, which states that the sample mean converges almost surely to the true mean, under a bounded moment assumption.

Definition B.4 (Convergence in probability).

Let \(X_m,m\geq 0\) and \(X\) be random variables defined on a common probability space \((\Omega,\mathcal{F},P)\). Then, \(X_m {\overset{p}{\longrightarrow}} X\) if \(\lim_{m\rightarrow\infty}\prob{w \vert X_m(w) - X(w)\vert > \epsilon} = 0\) \(\forall\) \(\epsilon>0\), where \(\prob{w \vert X_m(w) - X(w)\vert > \epsilon}\) is usually written as \(\prob{\vert X_m - X\vert> \epsilon}\).

The weak law of large numbers is an example of convergence in probability for the sample mean of i.i.d. r.v.s.

Definition B.5 (\(L^2\) or mean-squared convergence).

Let \(X_m,m\geq 0\) and \(X\) be random variables defined on a common probability space \((\Omega,\mathcal{F},P)\). Then \(X_m {\overset{L^2}{\longrightarrow}} X\) if \(\E[\vert X_m(w) - X(w)\vert]^2 \rightarrow 0\) as \(m\rightarrow\infty\), where \(\E[\vert X_m(w) - X(w)\vert]^2\) is the mean squared error.

Definition B.6 (Convergence in distribution).

Let \(X_m,m\geq 0\) and \(X\) be random variables (not necessarily defined on a common probability space). We say that \(X_m {\overset{d}{\longrightarrow}} X\) if \(F_{X_m}(x)\longrightarrow F_X(x)\) at all points of continuity of \(F_X\). Here \(F_Y(\cdot)\) denotes the cumulative distribution function (CDF) of the random variable \(Y\).

The reader is referred to (Borkar 1995; Billingsley 2013) for equivalent definitions of convergence in distribution.

It can be shown that

  1. Almost sure convergence \(\implies\) convergence in probability \(\implies\) convergence in distribution.

  2. Mean-squared convergence \(\implies\) convergence in probability \(\implies\) convergence in distribution.

For counterexamples that show that the converses of the above implications do not hold, the reader is referred to (Billingsley 2017).

In this book, we provide almost sure convergence guarantees for the well-known gradient-based zeroth-order optimization algorithms.

B.3 Martingales

A filtration \(\F_n\) is an increasing sequence of sigma fields. A sequence of random variables \(Y_n\) is said to be adapted to \(\F_n\) if \(Y_n\) is \(\F_n\)-measurable, for all \(n\).

A martingale is a stochastic process that is defined below.

Definition B.7.

A sequence \(\{Y_n, n \ge 1\}\) is a martingale with respect to the sequence \(\{X_n, n \ge 1\}\) if, for all \(n \ge 1\),

  • \(\E [ |Y_n| ] < \infty\);

  • \(Y_n\) is adapted to \(\F_n=\sigma(X_1,\ldots,X_n)\); and

  • \(\E[Y_{n+1}|X_1,\ldots,X_n] = Y_n\).

In particular, if \(\E[Y_{n+1}|X_1,\ldots,X_n] = 0\), then \(\{Y_n, n\ge 1\}\) is a martingale difference sequence.

The sequence \(\{X_n\}\) can be the same as the \(\{Y_n\}\) sequence for the conditions listed above to be valid.

Notice that

\[ \begin{align*} \E[\left.Y_{n+2}\right|Y_1,Y_2,\ldots,Y_n] &= \E[\left.\E[\left.Y_{n+2}\right|Y_1,Y_2,\ldots,Y_{n+1}]\right|Y_1,Y_2,\ldots,Y_n] \\ &= \E[\left.Y_{n+1}\right|Y_1,Y_2,\ldots,Y_n] = Y_n. \end{align*} \]

Extending the argument, we have \(\E[Y_{n+m}|Y_1,Y_2,\ldots,Y_n]= Y_n\), for any \(m>0\).

A few examples of martingales are given below.

Example B.1.

Let \(\{X_i\}\) be a sequence of random variables satisfying \(\E[\left.X_{i+1}\right|X_1,X_2,\ldots,X_i] = 0\), \(\forall i\). Define \(S_n=\sum_{i=1}^n X_i\). Then,

\[ \begin{align*} &\E[\left.S_{n+1}\right|S_1,S_2,\ldots,S_n] \\ &= \E[\left.X_{n+1}\right|S_1,S_2,\ldots,S_n] + \E[\left.S_{n}\right|S_1,S_2,\ldots,S_n] \\ & =\E[\left.X_{n+1}\right|X_1,X_2,\ldots,X_n] + S_n = S_n. \end{align*} \]

Thus, \(\{S_n\}\) is a martingale sequence.

Example B.2.

Let \(\{X_i\}\) be a sequence of i.i.d. random variables with mean one. Let \(S_n=\prod_{i=1}^n X_i\). Then, \(\{S_n\}\) is a martingale since

\[ \E[\left.S_{n+1}\right|S_1,S_2,\ldots,S_n] = \E[\left.X_{n+1} S_n\right|S_1,S_2,\ldots,S_n]= \E[X_{n+1}] S_n= S_n. \]

Definition B.8.

Let \(\F_n\) be a filtration. A sequence \(\{Y_n\}\) is a martingale w.r.t. the filtration \(\F_n\) if, for all \(n \ge 1\),

  1. \(\E[|Y_n|] < \infty\);

  2. \(Y_n\) is adapted to \(\F_n\); and

  3. \(\E[Y_{n+1} | \mathcal{F}_n] = Y_n\).

If the equality in the last condition above is replaced by a \(\le\) (resp. \(\ge\)), then the resulting sequence is a super (resp. sub) martingale.

Definition B.7 is retrieved by choosing \(\mathcal{F}_n\) to be \(\sigma(X_0,X_1,\ldots,X_n)\), which is the smallest \(\sigma\)-field with respect to which \(X_1,\ldots,X_n\) are measurable. If \(Y\) is a martingale with respect to \(\mathcal{F}\), then it is also a martingale with respect to \(\mathcal{G}\) where \(\mathcal{G}_n = \sigma(Y_1,\ldots,Y_n)\). This is because \(\mathcal{G}_n\) is the smallest sigma algebra w.r.t which \(Y_n\) is measurable for every \(n\), and thus, \(\mathcal{G}_n\subset \mathcal{F}_n\), \(\forall n\). Hence,

\[ E[Y_{n+1}|\mathcal{G}_n] = E[E[Y_{n+1}|\mathcal{F}_n]|\mathcal {G}_n] = E[Y_n|\mathcal{G}_n]=Y_n \mbox{ a.s.} \]

Example B.3.

Let \(\{X_i\}\) be i.i.d. and let \(S_n=\sum_{i=1}^n X_i\). Then,

  1. \(\{S_n\}\) is a submartingale if \(\E[X_i] \geq 0\); and

  2. \(\{S_n\}\) is a supermartingale if \(\E[X_i] \leq 0\).

Example B.4.

Let \(\{Z_n\}\) be a martingale sequence, and \(S_n = Z_n - Z_{n-1}\). Then,

\[ \begin{align*} \E[S_n|S_1,\ldots,S_{n-1}] &= \E[Z_n|S_1,\ldots,S_{n-1}] - \E[Z_{n-1}|S_1,\ldots,S_{n-1}] \\ & = Z_{n-1} - Z_{n-1} = 0. \end{align*} \]

Further, \(\E[|S_n|] \le \E[|Z_n|] + \E[|Z_{n-1}|] < \infty\). Thus, the sequence \(\{S_n\}\) is a martingale difference.

B.3.1 Applications

Mean Estimation

Consider a r.v. \(Y\) with mean \(\mu\) and variance \(\sigma ^2\). Suppose we are given i.i.d samples \(Y_1, Y_2 \ldots Y_n\) from the distribution of \(Y\). Let \(x_n\) denote the sample mean, i.e.,

\[ x_n = \frac{1}{n} \sum_{k = 1}^n Y_k. \]

We have

\[ \begin{align*} x_{n+1} &= \frac{1}{n+1}\sum_{k = 1}^{n+1}Y_{k+1} = \frac{n}{n+1} \left( \frac{1}{n}\sum_{k = 1}^n Y_k \right) + \frac{1}{n+1}Y_{n+1}. \end{align*} \]

Hence, sample mean can be iteratively computed as follows:

\[ \begin{align*} x_{n+1} &= x_n + \frac{1}{n+1}(Y_{n+1} - x_n) \end{align*} \]

Instead of \(\frac{1}{n+1}\), one can employ a more general step-size \(\alpha_n\) satisfying standard stochastic approximation conditions, to arrive at the following update rule:

\[ x_{n+1} = x_n + \alpha_n(Y_{n+1} - x_n). \tag{B.1} \]

Rewriting the equation above, we obtain

\[ \begin{align*} x_{n+1} &= x_n + \alpha_n(Y_{n+1} - x_n) \tag{B.2} \\ &= x_n + \alpha_n[(\mu -x_n) + (Y_{n+1} - \mu)] \tag{B.3} \\ &= x_n + \alpha_n[(\mu - x_n) + w_{n+1}], \tag{B.4} \end{align*} \]

where \(w_{n+1} = Y_{n+1} - \mu\) is the noise term. Notice that

\[ \begin{align*} \E[w_{n+1}|x_1,\ldots x_n] &= \E[w_{n+1}|Y_1,\ldots Y_n] \\ &= \E[Y_{n+1}|Y_1,\ldots Y_n] - \mu \\ &= \E [Y_{n+1}] - \mu=0. \end{align*} \]

Hence, \(\{w_n\}\) is a martingale difference sequence.

Urn model

Suppose we have an empty urn to which we randomly add a red or a blue ball (one at a time) iteratively. Let us define

\[ Y_{n+1} = \begin{cases} 1, &\text{if } (n+1)\text{th ball is red}\\ 0, & \text{otherwise} \end{cases} \]

\(S_n = \sum_{k = 1}^n Y_k\) denotes the total number of red balls. Then \(x_n = \frac{S_n}{n}\) denotes the fraction of red balls. We have

\[ \begin{align*} x_{n+1} &= \frac{1}{n+1} \sum_{k=1}^{n+1} Y_k \\ &= (1-\frac{1}{n+1})x_n + \frac{1}{n+1} Y_{n+1} \\ &= x_n + \alpha_n (Y_{n+1} - x_n), \end{align*} \]

where \(\alpha_n=\frac{1}{n+1}\), \(n\geq 0\). Suppose the conditional probability that the next ball added at iterate \((n+1)\) is red, given the past, depends only on \(x_n\), i.e.,

\[ \prob { Y_{n+1} = 1| x_1 \ldots x_n} = p(x_n). \]

Then,

\[ \begin{align*} x_{n+1} &= x_n +\alpha_n(p(x_n) - x_n) + w_{n+1}, \end{align*} \]

where \(w_{n+1} = Y_{n+1} - p(x_n)\). Notice that

\[ \begin{align*} \E(w_{n+1}| x_1, \ldots x_n) &= \E(Y_{n+1}-p(x_n)|x_1,\ldots x_n) \\ &= \prob{Y_{n+1}=1|x_1, \ldots x_n} - p(x_n) \\ &= p(x_n) - p(x_n)= 0. \end{align*} \]

Therefore, \(\{w_{n}\}\) is a martingale difference sequence.

In the next section, we state and prove the well-known maximal inequality for martingales. This inequality will be used subsequently in the proof of the martingale convergence theorem. The latter claim helps in establishing asymptotic convergence of stochastic approximation algorithms with noise factors that are martingale differences.

B.3.2 Maximal inequality

We state and prove the Doob-Kolmogorov Inequality below.

Theorem B.1.

If \(\{S_n\}\) is a martingale with respect to \(\{X_n\}\) then

\[ \P\left(\max_{1\le i\le n} |S_i| \ge \epsilon\right) \le \frac{1}{\epsilon^2}\E[S_n^2] \textrm{ for any } \epsilon > 0. \]

Proof.

For the given \(\epsilon>0\), we define a partition of \(\Omega\) as follows:

\[ A_k \cup \left(\bigcup^k_{i=1}B_i\right) = \Omega, \]

where \(A_0 = \Omega, A_k = \{|S_i| < \epsilon, \forall i \le k\}\), and \(B_k = A_{k-1} \cap \{|S_k|\ge\epsilon\}\). Here \(B_k\) denotes the even when \(|S_i| \ge \epsilon\) for the first time with \(i=k\).

The sets \(B_1,\ldots,B_k, A_k\) form a partition of \(\Omega\), which implies

\[ \E[S_n^2] = \sum^n_{i=1}\E[S_n^2 I_{B_i}] + \E[S_n^2 I_{A_n}] \ge \sum_{i=1}^n\E[S_n^2 I_{B_i}]. \]

Notice that

\[ \begin{align*} \E[S_n^2 I_{B_i}] &= \E[(S_n-S_i+S_i)^2 I_{B_i}] \\ &= \underbrace{\E[(S_n-S_i)^2 I_{B_i}]}_{(I)} + \underbrace{2\E[(S_n-S_i)S_i I_{B_i}] }_{(II)}+ \underbrace{\E[S_i^2 I_{B_i}]}_{(III)}. \end{align*} \]

Note that \((I) \ge 0\) and \((III) \ge \epsilon^2P(B_i)\), because \(|S_i| \ge \epsilon\) if \(B_i\) occurs. To deal with term \((II)\), note that

\[ \begin{align*} \E[(S_n-S_i)S_i I_{B_i}] &= \E\left[S_i I_{B_i}\E[(S_n-S_i)|X_1,\ldots,X_i]\right] \\ &= 0, \end{align*} \]

since \(B_i\) concerns \(X_1,\ldots,X_i\) only, the inequality presented above becomes

\[ \E[S^2_n] \ge \sum^n_{i=1}\epsilon^2 \\ P(B_i) = \epsilon^2\prob{\max_{1\le i\le n} |S_i| \ge \epsilon}. \]

\(\square\)

B.3.3 Martingale convergence theorem

Theorem B.2.

Suppose \(\{S_{n}\}\) is a martingale sequence satisfying \(\mathbb{E}[S_{n}^2] < M < \infty\) for some \(M\) and \(\forall \; n\). Then, there exists a r.v. \(S\) such that

  1. \(S_{n} \xrightarrow{a.s} S\) as \(n \rightarrow \infty\);

  2. \(S_{n} \xrightarrow{L^{2}} S\) as \(n \rightarrow \infty\) (mean-squared sense).

Proof.

We begin with the proof of the first claim, i.e., almost sure convergence. Notice that \(S_{m}\) and \(S_{m+n}-S_{m}\) are uncorrelated \(\forall m,n \geq 1\) since \(\E[S_{m}(S_{m+n}-S_{m})]=0\). Further,

\[ \begin{align*} \E[S_{m+n}^{2}] &= \E[S_{m}^{2}]+\E[(S_{m+n}-S_{m})^2] \geq \E[S_{m}^{2}]. \end{align*} \]

Thus, \(\{\E[S_{n}^{2}]\}\) is a non-decreasing sequence that is bounded above (by assumption). Choose \(M\) such that \(\E[S_{n}^{2}] \uparrow M\) as \(n \rightarrow \infty\). Now, it is enough to show that \(\{S_{n}(\omega)\}_{n=1}\) is Cauchy convergent as it would imply almost sure convergence.
Let \(C=\{\omega \; | \; S_{n}(\omega) \textrm{ is Cauchy convergent}\}\), i.e.,

\[ C =\{\omega \; | \; \forall \epsilon >0, \exists m \textrm{ such that } |S_{m+i}(\omega)-S_{m+j}(\omega)| < \epsilon \; \forall \; i,j \geq 1\}. \]

If \(|S_{m+i}-S_{m}| < \epsilon\) and \(|S_{m+j}-S_{m}| < \epsilon\) then \(|S_{m+i}-S_{m+j}|< 2\epsilon\) by triangle inequality. So,

\[ \begin{align*} C &= \{ \omega| \forall \textrm{ (rational) } \epsilon > 0, \exists \; m \text{ s.t. } |S_{m+i}(\omega)-S_{m}(\omega)| < \epsilon, \; \forall \; i \geq 1 \} \\ &= \underset{\epsilon>0}{\bigcap} \; \underset{m \geq 1}{\bigcup} \{ |S_{m+i}-S_{m}| < \epsilon, \forall i \geq 1 \} \\ C^{\mathsf{c}} &=\underset{\epsilon>0}{\bigcup} \; \underset{m \geq 1}{\bigcap} \{ |S_{m+i}-S_{m}| \geq \epsilon, \text{ for some } i \geq 1 \}. \end{align*} \]

Let \(A_{m}(\epsilon) = \{ |S_{m+i}-S_{m}| \geq \epsilon\) \(i \geq 1 \}\) then, \(C^{c} = \underset{\epsilon>0}{\bigcup} \; \underset{m \geq 1}{\bigcap} A_{m}(\epsilon)\). If \(\epsilon \geq \epsilon'\), \(A_{m}(\epsilon) \subseteq A_{m}(\epsilon')\).

We want \(\P(C^{c})=0\). Notice that

\[ 0 \leq \lim_{\epsilon \downarrow 0} \P\left(\underset{m}{\bigcap} \; A_{m}(\epsilon) \right) \leq \lim_{\epsilon \downarrow 0} \lim_{m \rightarrow \infty} \P(A_{m}(\epsilon)). \]

If \(\lim_{m \rightarrow \infty} \P(A_{m}(\epsilon))=0\) for any \(\epsilon >0\), then \(\P(C^{c})=0\).
Let \(Y_{n}=S_{m+n}-S_{m}\), for a fixed \(m\). Then, \(\{Y_{n}\}\) is a martingale since \(\E[Y_{n+1}|Y_{1},\dots,Y_{n}]=Y_{n}\).
Applying the Doob-Kolmogorov inequality for \(Y_{i}\), we obtain

\[ \begin{align*} & \P(|Y_{i}| \geq \epsilon \text{ for some } 1 \leq i \leq n) \leq \frac{1}{\epsilon^{2}} \EE{Y_{n}^{2}}, \\ & \P(|S_{m+i}-S_{m}| \geq \epsilon, \text{ for some } 1 \leq i \leq n) \leq \frac{\EE{\left(S_{m+n}-S_{m}\right)^{2}}}{\epsilon^{2}}, \\ &0 \leq \P(A_{m}(\epsilon)) \leq \frac{\E(S_{m+n}-S_{m})^{2}}{\epsilon^{2}} = \frac{\E[S_{m+n}^{2}]+\E[S_{m}^{2}]-2\E[S_{m+n}S_{m}]}{\epsilon^{2}}. \end{align*} \]

Notice that

\[ \begin{align*} \E[S_{m+n}S_{m}] &= \E[\E[S_{m+n}S_{m}|S_{1}, \dots, S_{m}]] \\ &=\E[S_{m}E[S_{m+n}|S_{1},\dots,S_{m}]]= E[S_{m}^{2}]. \end{align*} \]

Thus,

\[ \begin{align*} 0 \leq \prob{A_{m}(\epsilon)} &\leq \frac{\E[S_{m+n}^{2}]-E[S_{m}^{2}]}{\epsilon^{2}} \\ & \leq \lim_{n \rightarrow \infty} \frac{\E[S_{m+n}^{2}]-E[S_{m}^{2}]}{\epsilon^{2}} = \frac{M-\E[S_{m}^{2}]}{\epsilon^{2}} \\ \P[A_{m}(\epsilon)] & \leq \frac{M-\E[S_{m}^{2}]}{\epsilon^{2}}. \end{align*} \]

As \(m \rightarrow \infty\), \(\E[S_{m}^{2}] \uparrow M\). Hence, \(\lim_{m \rightarrow \infty}\P[A_{m}(\epsilon)] =0\), implying \(\P(C^{\mathsf{c}})=0\) (or) \(\P(C)=1\), i.e., the sequence \(\{S_{n}\}\) is Cauchy convergent. Thus, \(\exists \; S\) such that \(S_{n} \overset{a.s}{\rightarrow} S\) as \(n \rightarrow \infty\).

We now turn to proving convergence in mean-squared sense. For this claim, we need Fatou’s Lemma, which is stated as follows:
If \(\{X_{n}\}\) is such that \(X_{n} \geq 0, \forall n\), then

\[ \E[\liminf_{n \rightarrow \infty} X_{n}] \leq \liminf_{n \rightarrow \infty} \E[X_{n}] \]

Notice that

\[ \begin{align*} \E[(S_{n}-S)^{2}] & = \E[\lim \inf_{m \rightarrow \infty} (S_{n}-S_{m})^{2}] \tag{B.5} \\ & \leq \lim \inf_{m \rightarrow \infty} \E[(S_{n}-S_{m})^{2}] \tag{Fatou's Lemma} \\ & = M - \E[S_{n}^{2}] \overset{n \rightarrow \infty}{\longrightarrow} 0. \tag{B.6} \end{align*} \]

\(\implies \E[(S_{n}-S)^{2}] \overset{n \rightarrow \infty}{\longrightarrow} 0 \text{ or } S_{n} \overset{L^{2}}{\rightarrow} S\).

To arrive at the equality in (B.5), we used the following fact for a fixed \(n\):

\[ \begin{align*} \E\left[\lim_{m \rightarrow \infty}(S_{n}^{2}+S_{m}^{2}-2 S_{m} S_{n})\right] =& \E[{S_{n}}^{2}+S^{2}-2S_{n}S] \\ =& \E[({S_{n}}-S)^{2}]. \end{align*} \]

Further, (B.6) is justified as follows:

\[ \begin{align*} \lim_{m \rightarrow \infty} \E[(S_{n}-S_{m})^{2}] &= \lim_{m \rightarrow \infty}(\E[S_{n}^{2}]+\E[S_{m}^{2}]-2\E[S_{n}S_{m}]) \\ &= \lim_{m \rightarrow \infty} (\E[S_{m}^{2}]-\E[S_{n}^{2}]) \\ &=M-\E[S_{n}^{2}]. \end{align*} \]

Hence proved.

\(\square\)

B.3.4 More general martingale convergence results

We state here a few general martingale convergence theorems that are popular in the literature, see for instance, (Borkar 1995, chap. 3). As before, for a random variable \(X\), let \(X^+ \stackrel{\triangle}{=} \max (X,0)\).

Theorem B.3.

Let \((S_n,\mathcal{F}_n)\), \(n\geq 0\), be a submartingale satisfying \(\sup_n E[S_n^+] <\infty\). Then \(S_n \rightarrow S\) a.s.

Theorem B.4.

Let \((S_n,\mathcal{F}_n),n\geq 0\), be a martingale or a non-negative submartingale satisfying \(\sup_n E[|S_n|^p] <\infty\), for some \(p\in (1,\infty)\). Then there exists a random variable \(S\) such that

  • \(S_n\rightarrow S\) a.s.,

  • \(S_n\stackrel{L^p}{\rightarrow} S\).

Definition B.9.

  1. A sequence of random variables \(\{S_n\}\) is said to be uniformly integrable (U.I.) if it is integrable and

    \[ \lim_{a\rightarrow\infty} \sup_n E[|S_n| I\{|S_n|\geq a\}]=0. \]

  2. A martingale \((S_n,\mathcal{F}_n),n\geq 0\), is said to be regular if there exists a random variable \(Y\) with \(E[|Y]<\infty\), such that \(S_n = E[Y|\mathcal{F}_n]\), \(\forall n\).

Lemma B.5.

\(\{S_n\}\) is U.I. if and only if \(\sup_n E[|S_n|]<\infty\) and

\[ \lim_{P(A)\rightarrow 0} \sup_n \int_A |S_n| dP =0. \]

Theorem B.6.

Let \((S_n,\mathcal{F}_n)\), \(n\geq 0\) be a martingale. Then the following are equivalent:

  • \((S_n,\mathcal{F}_n)\), \(n\geq 0\), is regular.

  • \(\{S_n\}\) is U.I.

  • There exists a random variable \(S\) with \(E[|S|]<\infty\) and \(S_n \stackrel{L^1}{\rightarrow}S\).

  • \(\sup_n E[|S_n|] <\infty\) and \(S:=\lim_{n\rightarrow\infty} S_n\) satisfies \(S_n=E[S|\mathcal{F}_n]\), \(\forall n\).

Note that the existence of the limiting random variable \(S\) in Theorem B.6(iv) follows from Theorem B.4.

We shall now consider the class of square integrable martingales \((S_n,\mathcal{F}_n),n\geq 0\), i.e., those for which \(E[S_n^2]<\infty\), \(\forall n\). Note that if \((S_n,\mathcal{F}_n),n\geq 0\), is a martingale, then

\[ E[S_{n+1}^2|\mathcal{F}_n] \geq (E[S_{n+1}|\mathcal{F}_n])^2 \]

\[ = S_n^2 \mbox{ a.s.} \]

The inequality above follows from the conditional Jensen’s inequality, while the equality results from the martingale property. Thus, \((S_n^2,\mathcal{F}_n)\), \(n\geq 0\), is a submartingale and by the Doob decomposition theorem,

\[ S_n^2 = X_n + Z_n, \mbox{ }n\geq 0, \]

where \((X_n,\mathcal{F}_n)\), \(n\geq 0\), is a zero-mean martingale and \(\{Z_n\}\) is the quadratic variation process where \(Z_n\) is obtained as

\[ Z_n = \sum_{m=1}^{n} (E[S_m^2|\mathcal{F}_{m-1}] - S_{m-1}^2) + E[S_0^2], \]

and is seen to be measurable w.r.t. \(\mathcal{F}_{n-1}\), \(\forall n\geq 0\), where \(\mathcal{F}_{-1}=\{\Omega,\phi\}\). Note also that because \((S_n^2,\mathcal{F}_n)\), \(n\geq 0\), is a submartingale, \(Z_{n+1}\geq Z_n\) a.s., \(\forall n\).

Theorem B.7.

Let \((S_n, \mathcal{F}_n),n\geq 0\), be a square integrable martingale and let \(\{Z_n\}\) be its associated quadratic variation process such that each \(Z_n\) is measurable w.r.t. \({\mathcal{F}_{n-1}}\). Let \(Z_\infty= \lim_{n\rightarrow\infty} Z_n\) a.s. Then \(\{S_n\}\) converges almost surely on the set \(\{Z_\infty<\infty\}\). Also, \(S_n=o(f(Z_n))\) on \(\{Z_\infty=\infty\}\) for every increasing \(f:\mathbb{R}^+\cup \{0\} \rightarrow \mathbb{R}^+\cup \{0\}\) satisfying

\[ \int_{0}^{\infty} (1+f(t))^{-2}dt <\infty. \]

Remark B.1.

Even though the above theorems are given for scalar valued martingales, they continue to hold even with vector-valued martingales. In most of the asymptotic convergence analyses that we cover for our algorithms, Theorem B.7 is seen to be useful. Consider, for instance, the following stochastic approximation algorithm as in (2.1):

\[ x_{n+1} = x_n + a(n)(h(x_n)+M_{n+1}), \]

under the assumptions (A1)-(A4) of (Borkar 2022, chap. 2). We list these below for ease of reference.

  • The function \(h:\mathbb{R}^d\rightarrow\mathbb{R}^d\) is Lipschitz continuous.

  • The step-size sequence \(\{a(n)\}\) is a sequence of positive real numbers satisfying

    \[ \sum_n a(n)=\infty, \mbox{ } \sum_n a(n)^2 <\infty. \]

  • The sequence \(\{M_{n}\}\) forms a martingale difference sequence w.r.t. the filtration \(\mathcal{F}_n \equiv \sigma(x_m, M_m, m\leq n)\), \(n\geq 0\). In addition,

    \[ E[\|M_{n+1}\|^2|\mathcal{F}_n] \leq \check{U}(1+ \|x_n\|^2). \]

  • \(\sup_n \|x(n)\| <\infty\) a.s.

Define now

\[ S_n \stackrel{\triangle}{=} \sum_{m=0}^{n-1} a(m)M_{m+1}, \mbox{ } n\geq 1. \]

Then \((S_n,\mathcal{F}_n)\), \(n\geq 1\) forms a martingale sequence. Using the Euclidean norm, we obtain

\[ E[\|S_n\|^2] = E[S_n^T S_n] = \sum_{m=0}^{n-1} a(m)^2 \|M_{m+1}\|^2] <\infty, \]

as the cross terms of the form \(a(i)a(j) E[M_{i+1}^TM_{j+1}]=0\), for all \(i\not=j\). Further, the quadratic variation process \(\{Z_n\}\) associated with \((S_n,\mathcal{F}_n), n\geq 1\) is the following:

\[ Z_n = \sum_{m=1}^{n} (E[\|S_m\|^2|\mathcal{F}_{m-1}] - \|S_{m-1}\|^2) + E[\|S_0\|^2] \]

\[ = \sum_{m=1}^n E[\|(S_m-S_{m-1})\|^2|\mathcal{F}_{m-1}] + E[\|S_0\|^2] \]

\[ = \sum_{m=1}^{n} a(m-1)^2 E[\|M_{m}\|^2|\mathcal{F}_{m-1}] + E[\|S_0\|^2] \]

\[ \leq \check{U} \sum_{m=1}^{n} a(m-1)^2 (1+ \|x_{m-1}\|^2) + E[\|S_0\|^2], \]

from (A3). Thus,

\[ Z_n \leq \check{U} \sum_{m=1}^{n} a(m-1)^2(1+\sup_m\|x_{m-1}\|^2) + E[\|S_0\|^2]. \]

It now follows from (A2) (the square summability of step-size condition) and (A4) (stability of the iterates) that

\[ Z_n \rightarrow Z_\infty \leq \check{U} \sum_{m=1}^{\infty} a(m-1)^2(1+\sup_m\|x_{m-1}\|^2) + E[\|S_0\|^2] <\infty \mbox{ a.s.,} \]

from (A2) and (A4). From Theorem B.7, it will then follow that the martingale sequence \(\{S_m\}\) converges almost surely.

B.4 Bibliographic remarks

The background material presented in this appendix is based on (Grimmett and Stirzaker 2020; Borkar 1995; Billingsley 2017).

B.5 Exercises

Exercise 1.

Suppose \(X_n \inD X\) and \(Y_n \inP c\) for some constant \(c\). Show that \(X_n Y_n \inD c X\).

Exercise 2.

Suppose \(X_n \inP X\) and \(Y_n \inP Y\). Show that \(X_n Y_n \inP XY\).

Exercise 3.

Suppose \(X_n \inLone X\) and \(Y_n \inLone Y\). Disprove the following claim: \(X_n Y_n \inLone XY\).

Exercise 4.

Suppose \(X_n \inLp{2} X\) as \(n \to \infty\). Show that

\[ \var(X_n) \to \var(X) \textrm{ as }n \to \infty. \]

Exercise 5.

Answer the following questions to understand the relation between convergence in probability and in distribution.

  1. Prove that convergence in probability implies convergence in distribution, and give a counterexample to show that the converse need not hold.

  2. Show that convergence in distribution to a constant random variable implies convergence in probability to that constant.

Exercise 6.

Let \(\{X_n\}\) and \(\{Y_n\}\) be martingale sequences on a common probability space, i.e., for all \(n\),

\[ \begin{align*} &\E\left[|X_n| + |Y_n|\right]<\infty, \E\left[X_{n+1} \mid Z_1,\ldots, Z_n\right]=X_n, \textrm{ and } \\ &\E\left[Y_{n+1} \mid Z_1,\ldots, Z_n\right]=Y_n. \end{align*} \]

Show that, for \(m\le n\),

\[ \E\left[X_{n} Y_m \mid Z_1,\ldots, Z_m\right]=X_m Y_m. \]

Exercise 7.

Let \(\{X_n\}\) be a martingale sequence.

Consider the following two statements:
I: For all \(n\ge 1\), \(\E[X_n] = E[X_1]\).
II: For all \(n\ge 1\), \(\var(X_n) = \var(X_1)\).
III: For all \(n\ge 1\), \(\var(X_n) \ge \var(X_1)\).
IV: For all \(n\ge 1\), \(\var(X_n) \le \var(X_1)\).

Which of the statements above are true?

Exercise 8.

Let \(\{X_i\}\) be a i.i.d. sequence of random variables with mean zero and variance \(\sigma^2\). Define \(S_n=X_1+\ldots+X_n\), and \(Y_n= S_n^2 - n \sigma^2\). Show that \(\{Y_n\}\) is a martingale sequence.

Exercise 9.

Let \(X_i, i=1,2,\ldots\) be a sequence of independent random variable with common mean \(\mu\) and variance \(\E\left[( X_i-\mu)^2\right] \le k^{3/2}\). Let \(\overline X_n = \frac{1}{n}\sum_{i=1}^n X_i\) be the sample mean. Does \(\overline X_n\) converge in the mean-squared sense to \(\mu\)?

Exercise 10.

Let \(\{X_i\}\) be a i.i.d. sequence of positive random variables with mean one. Define \(Y_n=\prod_{i=1}^n X_i\).

Consider the following two statements:
I: \(\{Y_n\}\) is a martingale sequence.
II: \(\{\sqrt{Y_n}\}\) is a supermartingale sequence.
II: \(\{\sqrt{Y_n}\}\) is a submartingale sequence.

Which of the statements above are true?

Exercise 11.

Let \(\{X_n\}\) be a martingale sequence, with \(X_n \in [0,1], \ \forall n\). Does \(X_n\) converges almost surely?

Exercise 12.

Let \(\{X_n\}_{n\ge 1}\) be a sequence of independent random variables (r.v.s). Let \(f:\R\rightarrow\R\) be a function such that \(\E[|f(X_n)|] < \infty\), \(\forall n\). Let \(a_n = \E(f(X_n))] \ne 0\), \(\forall n\). Define

\[ S_n =\dfrac{\prod_{m=1}^{n} f(X_m)}{\prod_{m=1}^{n} a_m}, \forall n\ge 1. \]

Answer the following:

  1. Is \(\E[|S_n|] < \infty,\ \forall n\)?

  2. Is \(\{S_n\}\) a martingale sequence?

Exercise 13.

Suppose \(X_n\), \(n\geq 0\) is a sequence of real-valued random variables adapted to a filtration \(\{{\cal F}_n\}\). Let \(h:{\cal R}\rightarrow {\cal R}\) be a given function. Define a sequence \(\{R(n)\}\) of random variables according to

\[ R(n) = \sum_{m=1}^{n} \gamma(m) (h(X_m) - E[h(X_m)\mid {\cal F}_{m-1}]), \]

\(n\geq 1\), where \(\gamma(n)\), \(n\geq 1\) are some positive scalars. Give suitable conditions on \(\gamma (n)\), \(n\geq 1\) and \(h(\cdot)\) under which \((R(n),{\cal F}_n)\), \(n\geq 1\) is (i) a martingale, (ii) a square integrable martingale, and (iii) an almost surely convergent martingale sequence?

Exercise 14.

Let \((X_n, {\cal F}_n)\), \(n\geq 0\) be a supermartingale, and define

\[ \begin{align*} Y_0 &= X_0, \\ Y_n &= Y_{n-1} + (X_n - E[X_n \mid {\cal F}_{n-1}]), \mbox{ }n\geq 1. \end{align*} \]

Also define

\[ \begin{align*} A_0 &= 0, \\ A_n &= A_{n-1} + (X_{n-1} - E[X_n \mid {\cal F}_{n-1}]), \mbox{ }n\geq 1. \end{align*} \]

  • Express \(X_n\) in terms of \(Y_n\) and \(A_n\) for general \(n\geq 0\).

  • What kind of a process is \((Y_n, {\cal F}_n)\), \(n\geq 0\)?

  • Is \(\{A_n\}\) an increasing or a decreasing sequence? Prove your claim.