1.1 Martingale sequences: examples and further patterns

Examples and further patterns

A4-1 sums of independent random variables

Suppose Y _N is an independent, integrable sequence. Set ${\displaystyle X_n=\sum _{k=0}^n{Y}_k\forall n\ge 0}$ .

If $E\left[Y_n\right](\ge )0\forall n\ge 1$ , then X _N is a (S)MG.

A4-2 products of nonnegative random variables

Suppose $Y_{\mathbf{N}}\sim Z_{\mathbf{N}},Y_n\ge 0\mathrm{a}.\mathrm{s}.\forall n$ . Consider ${\displaystyle X_{\mathbf{N}}:X_n=c\prod _{k=0}^n{Y}_k,c>0}$ .

If $E\left[Y_{n+1}\right|W_n](\ge )1\mathrm{a}.\mathrm{s}.\forall n$ , then $(X_{\mathbf{N}},Z_{\mathbf{N}})$ is a (S)MG

$X_n\sim W_n$ and $X_{n+1}=Y_{n+1}{X}_n$ . Hence, $E\left[X_{n+1}\right|W_n]=X_{n}E\left[Z_{n+1}\right|W_n](\ge )X_n\mathrm{a}.\mathrm{s}.\forall n$

A4-3 discrete random walk

Consider $Y_0=0$ and $\{Y_n:1\le n\}$ iid. Set ${\displaystyle X_n=\sum _{k=0}^n{Y}_k\forall n\ge 0}$ . Suppose $P(Y_n=k)=p_k$ . Let

Now ${\displaystyle g_Y\left(1\right)=1,g_Y^{\text{'}}\left(1\right)=E\left[Y_n\right],g_Y^{\text{'}\text{'}}\left(s\right)=\sum _{k}k(k-1)p_k{s}^{k-2}>0\text{for}s>0}$ . Hence, $g_Y\left(s\right)=1$ has at most two roots, one of which is $s=1$ .

1. $s=1$ is a minimum point iff $E\left[Y_n\right]=0$ , in which case X _N is a MG (see A4-1 )
2. If $g_Y\left(r\right)=1$ for $0<r<1$ , then $E\left[r^{Y_n}\right]=1\forall n\ge 1$ . Let ${\displaystyle Z_0=1,Z_n=r^{X_n}=\prod _{k=1}^n{r}^{Y_k}}$ . By A4-2, Z _N is a MG

For the MG case in Theorem IXA3-6 , the Y _n are centered at conditional expectation; that is

$E\left[Y_{n+1}\right|W_n]=0\mathrm{a}.\mathrm{s}.$ The following is an extension of that pattern.

A4-4 more general sums

Consider integrable $Y_{\mathbf{N}}\sim Z_{\mathbf{N}}$ and bounded $H_{\mathbf{N}}\sim Z_{\mathbf{N}}$ . Let $W_n=$ a constant for $n<0$ and $H_n=1$ for $n<0$ . Set

Then $(X_{\mathbf{N}},Z_{\mathbf{N}})$ is a MG.

$X_n\sim W_n;\forall n\ge 0$ and $E\left[X_{n+1}\right|W_n]=X_n+H_{n}E\{Y_{n+1}-E\left[Y_{n+1}\right|W_n]|W_n\}=X_n+0\mathrm{a}.\mathrm{s}.$

IXA4-2

A4-5 sums of products

Suppose Y _N is absolutely fair relative to Z _N , with $E\left[\right|Y_n{|}^k]<\infty \forall n$ , fixed $k>0$ . For $n\ge k$ , set

Then $(X_{{\mathbf{N}}_k},Z_{{\mathbf{N}}_k}){\mathbf{N}}_k=\{k,k+1,k+2,\cdots \}$ is a MG,

$X_{n+1}=X_n+K_{n+1}$ , where

We consider, next, some relationships with homogeneous Markov sequences .

Suppose $(X_{\mathbf{N}},Z_{\mathbf{N}})$ is a homogeneous Markov sequence with finite state space $E=\{1,2,\cdots ,M\}$ and transition matrix $P=\left[p\right(i,j\left)\right]$ . A function f on E is represented by a column matrix $f={[f\left(1\right),f\left(2\right),\cdots ,f\left(M\right)]}^T$ . Then $f\left(X_n\right)$ has value $f\left(k\right)$ when $X_n=k$ . $Pf$ is an $m\times 1$ column matrix and $Pf\left(j\right)$ is the j th element of that matrix. Consider $E\left[f\left(X_{n+1}\right)\right|W_n]=E\left[f\left(X_{n+1}\right)\right|X_n]\mathrm{a}.\mathrm{s}.$ . Now

A nonnegative function f on E is called (super)harmonic for P iff $Pf(\le )f$ .

A4-6 positive supermartingales and superharmonic functions.

Suppose $(X_{\mathbf{N}},Z_{\mathbf{N}})$ is a homogeneous Markov sequence with finite state space $E=\{1,2,\cdots ,M\}$ and transition matrix $P=\left[p\right(i,j\left)\right]$ . For nonnegative f on E , let $Y_n=f\left(X_n\right)\forall n\in \mathbf{N}$ . Then $(Y_{\mathbf{N}},Z_{\mathbf{N}})$ is a positive (super)martingale P(SR)MG iff f is (super)harmonic for P .

As noted above $E\left[f\left(X_{n+1}\right)\right|W_n]=Pf\left(X_n\right)$ .

1. If f is (super)harmonic $Pf\left(X_n\right)(\le )f\left(X_n\right)=Y_n$ , so that
   $$E\left[Y_{n+1}\right|W_n](\le )Y_n\mathrm{a}.\mathrm{s}.$$
2. If $(Y_{\mathbf{N}},Z_{\mathbf{N}})$ is a P(SR)MG, then
   $$Y_n=f\left(X_n\right)(\ge )E\left[f\left(X_{n+1}\right)\right|W_n]=Pf\left(X_n\right)\mathrm{a}.\mathrm{s}.,\text{so}\text{that}f\text{is}\text{(super)harmonic}$$

IX A4-3

An eigenfunction f and associated eigenvalue λ for P satisfy $Pf=\lambda f$ (i.e., $(\lambda I-P)f=0$ ). In most cases, $\left|\lambda \right|<1$ . For real λ , $0<\lambda <1$ , the eigenfunctions are superharmonic functions. We may use the construction of Theorem IXA3-12 to obtain the associated MG.

A4-7 martingales induced by eigenfunctions for homogeneous markov sequences

Let $(Y_{\mathbf{N}},Z_{\mathbf{N}})$ be a homogenous Markov sequence, and f be an eigenfunction with eigenvalue λ . Put $X_n={\lambda }^{-n}f\left(Y_n\right)$ . Then, by Theorem IAXA3-12 , $(X_{\mathbf{N}},Z_{\mathbf{N}})$ is a MG.

A4-8 a dynamic programming example.

We consider a horizon of N stages and a finite state space $\mathbf{E}=\{1,2,\cdots ,M\}$ .

• Observe the system at prescribed instants
• Take action on the basis of previous states and actions.