Martingales

Conditional Expectation

Suppose $f(x,y)=\mathbb{P}\{X=x,Y=y\}$, $f_X(x)={\sum }_y^{}f(x,y)$, and ${\sum }_x^{}f(x,y)$
We define $E(Y\mid X)(x)=\frac{{\sum }_y^{}yf(x,y)}{f_X(x)}$

If $X_1,\dots ,X_n,Y$ have a joint probability density function $f$, and $g(x_1,\dots ,x_n)={\sum }_y^{}f(x_1,\dots ,x_n,y)$
$E(Y\mid X_1,\dots ,X_n)(x_1,\dots ,x_n)=\frac{{\sum }_y^{}yf(x_1,\dots ,x_n,y)}{g(x_1,\dots ,x_n)}$

We can easily define continuous analogues,
$f_X(x)={\int }_{-\infty }^{\infty }f(x,y)dy$, $f_Y(y)={\int }_{-\infty }^{\infty }f(x,y)dx$
$E(Y\mid X)(x)=\frac{{\int }_{-\infty }^{\infty }yf(x,y)dy}{f_X(x)}$
And $E(Y\mid X_1,\dots ,X_n)(x_1,\dots ,x_n)=\frac{{\int }_{-\infty }^{\infty }yf(x_1,\dots ,x_n,y)dy}{f_{X_1,\dots ,X_n}(x_1,\dots ,x_n)}$

$E(Y\mid X_1,\dots ,X_n)$ is characterized by two properties,

1. $E(Y\mid X_1,\dots ,X_n)$ depends only on the values of $X_1,\dots ,X_n$ (we can write it as $\varphi (X_1,\dots ,X_n)$ for some $\varphi$). We call $E(Y\mid X_1,\dots ,X_n)$ measurable with respect to $X_1,\dots ,X_n$.
2. Suppose $A$ is an event that depends on $X_1,\dots ,X_n$ and $I_A$ is the indicator function of $A$. $\mathbb{E}(Y{I}_A)=\mathbb{E}[E(Y\mid X_1,\dots ,X_n)I_A]$.

Measure theoretic treatments of probabilities define conditional expectation as the unique random variable satisfying these two properties

As shorthand, we write $E(Y\mid F_n)$, where $F_n$ denotes the information contained in $X_1,\dots ,X_n$

This gives us $\mathbb{E}[E(Y\mid F_n)]=\mathbb{E}(Y)$
And $E(a{Y}_1+b{Y}_2\mid F_n)=aE(Y_1\mid F_n)+bE(Y_2\mid F_n)$

If $Y$ is a function of $F_n$ then $E(Y\mid F_n)=Y$

For any $Y$, if $m<n$, then $E(E(Y\mid F_n)\mid F_m)=E(Y\mid F_m)$

If $Y$ is independent of $F_n$, $E(Y\mid F_n)=\mathbb{E}(Y)$

If $Y$ is any random variable and $Z$ is a random variable that is measurable with $F_n$, then $E(YZ\mid F_n)=ZE(Y\mid F_n)$

Example:
Suppose $X_1,X_2,\dots$ are i.i.d. with $\mu$ and let $S_n=X_1+\cdots +X_n$
Let $F_n$ denote the information in $X_1,\dots ,X_n$ and suppose $m<n$

$E(S_n\mid F_m)=E(X_1+\cdots +X_m\mid F_m)+E(X_{m+1}+\cdots +X_n\mid F_m)$
$E(X_1+\cdots +X_m\mid F_m)=S_m$
$E(X_{m+1}+\cdots +X_n\mid F_m)=\mathbb{E}(X_{m+1}+\cdots +X_n)=(n-m)\mu$
So $E(S_n\mid F_m)=S_m+(n-m)\mu$

Example:
Assume the same as above, but $\mu =0⟹\text{Var}(X_i)=\mathbb{E}(X_i^2)={\sigma }^2$
$E(S_n^2\mid F_m)=E([S_m+(S_n-S_m){]}^2\mid F_m)$
$=E(S_m^2\mid F_m)+2E(S_m(S_n-S_m)\mid F_m)+E((S_n-S_m{)}^2\mid F_m)$

$E(S_m^2\mid F_m)=S_m^2$
$E((S_n-S_m{)}^2\mid F_m)=\mathbb{E}((S_n-S_m{)}^2)=\text{Var}(S_n-S_m)=(n-m){\sigma }^2$
$E(S_m(S_n-S_m)\mid F_m)=S_{m}E(S_n-S_m\mid F_m)=S_m\mathbb{E}(S_n-S_m)=0$

Altogether, $E(S_n^2\mid F_m)=S_m^2+(n-m){\sigma }^2$

Example:
Consider the first example where $X_i$ is Bernoulli and $i\le m$

$E(X_i\mid S_n)=\frac{S_n}{n}$
$E(S_m\mid S_n)=E(X_1\mid S_n)+\cdots +E(X_m\mid S_n)=\frac{m}{n}{S}_n$

Consider $E(Y\mid X_{\alpha },\alpha \in \mathcal{A})$ where $X_{\alpha },\alpha \in \mathcal{A}$ is an infinite collection of random variables
Let $F$ denote the information in $\{X_{\alpha }\}$
$Z$ is $F$-measurable if knowledge of $\{X_{\alpha }\}$ determines $Z$, i.e. $Z=\varphi (X_{{\alpha }_1},\dots ,X_{{\alpha }_n})$ for some $\varphi$ and some finite subcollection, or if $Z$ is a limit of such random variables

As an example, say $Y,X_1,X_2,\dots$ are independent random variables and $X_1,X_2,\dots$ are i.i.d. with the standard normal distribution, while $Y$ is unknown, define $Z_j=X_j+Y$, and let $F_n$ denote the information in $Z_1,\dots ,Z_n$

One cannot determine $Y$ given any finite set $F_n$, however $Y$ is $F_{\infty }$ measurable since $Y={\lim }_{n\to \infty }\frac{Z_1+\dots Z_n}{n}$

An event $A$ is $F$-measurable if $I_A$ is an $F$-measurable random variable
$E(Y\mid F)$ is defined as the unique $F$-measurable random variable $Z$ such that $\mathbb{E}(Y{I}_A)=\mathbb{E}(Z{I}_A)$ for all $F$-measurable events A

I.e. $\mathbb{E}(Y{I}_A)=\mathbb{E}(E(Y\mid F)I_A)$

Martingales

A martingale is a model of a fair game

We let $\{F_n\}$ denote an increasing collection of information, a collection of random variables ${\mathcal{A}}_n$ such that ${\mathcal{A}}_m\subset {\mathcal{A}}_n$ if $m<n$, meaning we don’t lose information

The increasing sequence of $F_n$ is known as a filtration

A sequence of random variables $M_0,M_1,M_2,\dots$ with $\mathbb{E}(|M_i|)<\infty$ is a martingale with respect to $\{F_n\}$ if

1. Each $M_n$ is measurable with respect to $F_n$ and
2. $E(M_n\mid F_m)=M_m$ for all $m<n$

The second condition is equivalent to $E(M_n-M_m\mid F_m)=0$ and can be proven by showing $E(M_{n+1}\mid F_n)=M_n$

Example:
$M_n=S_n-n\mu$ is a martingale with respect to $F_n$
$E(M_{n+1}\mid F_n)=E(S_{n+1}-(n+1)\mu \mid F_n)=E(S_{n+1}\mid F_n)-(n+1)\mu =(S_n+\mu )-(n+1)\mu =M_n$

Example:
Suppose $\mathbb{P}\{X_i=1\}=\mathbb{P}\{X_i=-1\}=\frac{1}{2}$

Say we double our bet every instance and stop when we win and let $W_n$ denote the winnings or losses up through $n$ flips of the coin,
$\mathbb{P}\{W_{n+1}=1\mid W_n=1\}=1$

If the first $n$ flips have turned up tails, $W_n=-(2^n-1)$
$\mathbb{P}\{W_{n+1}=1\mid W_n=-(2^n-1)\}=\frac{1}{2}$
$\mathbb{P}\{W_{n+1}=-(2^{n+1}-1)\mid W_n=-(2^n-1)\}=\frac{1}{2}$

We can verify $E(W_{n+1}\mid F_n)=W_n$, so $W_n$ is a martingale with respect to $F_n$

We can generalize this, such that we make a bet $B_n$ on the $n$th flip, measurable on $F_{n-1}$ and $W_n={\sum }_{j=1}^n{B}_j{X}_j$

We can let $B_n$ be negative, corresponding to betting the coin will come up tails

$E(W_{n+1}\mid F_n)=E\left({\sum }_{j=1}^{n+1}{B}_j{X}_j\mid F_n\right)=E\left({\sum }_{j=1}^n{B}_j{X}_j\mid F_n\right)+E(B_{n+1}{X}_{n+1}\mid F_n)$
$=W_n+B_{n+1}\mathbb{E}(X_{n+1})=W_n$

So the general form is also a Martingale

Example:
Consider an urn with a red ball and a green ball. Every time one draws a ball, it is returned along with another of the same color. Let $X_n$ denote the number of red balls in the urn after $n$ draws

This is a Markov chain,
$\mathbb{P}\{X_{n+1}=k+1\mid X_n=k\}=\frac{k}{n+2}$
$\mathbb{P}\{X_{n+1}=k\mid X_n=k\}=\frac{n+2-k}{n+2}$

$M_n=\frac{X_n}{n+2}$ is a martingale

$E(X_{n+1}\mid X_n)=X_n+\frac{X_n}{n+2}$
Since this is a Markov chain, all relevant information in $F_n$ is contained in $X_n$,
$E(M_{n+1}\mid F_n)=E((n+3{)}^{-1}{X}_{n+1}\mid X_n)$
$=\frac{1}{n+3}\left[X_n+\frac{X_n}{n+2}\right]=\frac{X_n}{n+2}$
$=M_n$

$M_n$ is called a submartingale if $E(M_n\mid F_m)\ge M_m$ and a supermartingale if $E(M_n\mid F_m)\le M_m$

Example:
Let $X_n$ be a finite Markov chain, with $v(x)=E(f(X_T)\mid X_0=x)$ where $T$ is the optimal stopping rule

$M_n=v(X_n)$ is a supermartingale with respect to $X_0,X_1,\dots$

Optional Sampling Theorem

The optional sampling theorem states that you cannot beat a fair game, however it’s a bit subtle

We say $T$ is a stopping time with respect to $\{F_n\}$ is for each $n$, $\{T=n\}$ is measurable with respect to $F_n$

Under certain conditions, $\mathbb{E}(M_T)=\mathbb{E}(M_0)$

Suppose $M_0,M_1,\dots$ is a martingale with respect to $\{F_n\}$ and suppose $T\le K$ is a stopping time which is bounded, then $E(M_T\mid F_0)=M_0$

$M_T={\sum }_{j=0}^K{M}_{j}I\{T=j\}$
$E(M_T\mid F_{K-1})=E(M_{K}I\{T=K\}\mid F_{K-1})+{\sum }_{j=0}^{K-1}E(M_{j}I\{T=j\}\mid F_{K-1})$
$E(M_{j}I\{T=j\}\mid F_{K-1})=M_{j}I\{T=j\}$
$E(M_{K}I\{T=K\}\mid F_{K-1})=E(M_{K}I\{T>K-1\}\mid F_{K-1})$
$=I\{T>K-1\}E(M_K\mid F_{K-1})$
$=I\{T>K-1\}{M}_{K-1}$

Putting it together, we get $E(M_T\mid F_{K-1})=I\{T>K-1\}{M}_{K-1}+{\sum }_{j=0}^{K-1}{M}_{j}I\{T=j\}$
$=I\{T>K-2\}{M}_{K-1}+{\sum }_{j=0}^{K-2}{M}_{j}I\{T=j\}$

We can do this argument again conditioning on $F_{K-2}$ to get $E(M_T\mid F_{K-2})=E(E(M_T\mid F_{K-1})\mid F_{K-2})$
$=I\{T>K-3\}{M}_{K-2}+{\sum }_{j=0}^{K-3}{M}_{j}I\{T=j\}$

This can be iterated until we arrive at $E(M_T\mid F_0)=M_0$

However, $T$ is not always bounded, such as in the betting game we first introduced. So when is the optional sampling theorem valid?

Consider $T_n=\min \{T,n\}$
$M_T=M_{T_n}+M_{T}I\{T>n\}-M_{n}I\{T>n\}$

$\mathbb{E}(M_{T_n})=\mathbb{E}(M_0)$ since $T_n$ is bounded, but what about the other terms? The first one approaches 0 essentially because $I\{T>n\}$ approaches 0 as $n\to \infty$.

So the problematic term for our nice result is $\mathbb{E}(M_{n}I\{T>n\})$, which does not necessarily approach 0. In our doubling betting example, $I\{T>n\}=2^{-n}$ and $M_n=1-2^n$, so we get $2^{-n}(1-2^n)$, which does not approach 0.

Optional Sampling Theorem: Suppose $M_0,M_1,\dots$ is a martingale with respect to $\{F_n\}$ and $T$ is a stopping time satisfying $P\{T<\infty \}=1$, $\mathbb{E}(|M_T|)<\infty$, and ${\lim }_{n\to \infty }\mathbb{E}(|M_n|I\{T>n\})=0$, then $\mathbb{E}(M_T)=\mathbb{E}(M_0)$.

Example:
Let $X_n$ be a simple random walk on $\{0,\dots ,N\}$ with absorbing boundaries, let $X_0=a$, and let $T=\min \{j:X_j=0\text{ or }N\}$

Since $X_n$ is bounded, we know immediately $\mathbb{E}(M_T)=\mathbb{E}(M_0)=a$ and $E(M_T)=N\mathbb{P}\{X_T=N\}$

Therefore, $\mathbb{P}\{X_T=N\}=\frac{a}{N}$

Now let $M_n=X_n^2-n$
$E(M_{n+1}\mid F_n)=E(X_{n+1}^2-(n+1)\mid F_n)=X_n^2+1-(n+1)=M_n$ (using this), so this is a Martingale

Using the same $T$ as before, $M_n$ is no longer bounded, however we can show there exists $C<\infty$ and $\rho <1$ such that $\mathbb{P}\{T>n\}\le C{\rho }^n$

Since $|M_n|\le N^2+n$, we can show $\mathbb{E}(|M_T|)<\infty$ and $\mathbb{E}(|M_n|I\{T>n\})\le C{\rho }^n(N^2+n)\to 0$

Hence, $\mathbb{E}(M_T)=\mathbb{E}(M_0)=a^2$

Since $\mathbb{E}(M_T)=\mathbb{E}(X_T^2)-\mathbb{E}(T)=N^2\mathbb{P}\{X_T=N\}-\mathbb{E}(T)=aN-\mathbb{E}(T)$, we see $\mathbb{E}(T)=a(N-a)$

Uniform Integrability

${\lim }_{n\to \infty }\mathbb{E}(|M_T|I\{T>n\})=0$ is hard to verify, so we’d like to find some easier conditions

Suppose we have $X$ with $\mathbb{E}(|X|)<\infty$,
${\lim }_{K\to \infty }\mathbb{E}(|X|I\{|X|>K\})={\lim }_{K\to \infty }{\int }_K^{\infty }|x|dF(x)=0$

We say $X_1,X_2,\dots$ is uniformly integrable if for every $ϵ>0$ there is some $K$ with $\mathbb{E}[|X_n|I\{|X_n|>K\}]<ϵ$ for each $n$, where $K$ depends on $ϵ$ (not $n$)

If $X_n$ is uniformly integrable then for every $ϵ>0$ there is some $\delta >0$ where $\mathbb{P}(A)<\delta ⟹\mathbb{E}(|X_n|I_A)<ϵ$ for each $n$

To show this, let $\delta =ϵ/(2K)$, so if $\mathbb{P}(A)<\delta$ then
$\mathbb{E}(|X_n|I_A)\le \mathbb{E}(|X_n|I_A;|X_n|\le K)+\mathbb{E}(|X_n|I_A;|X_n|>K)<K\mathbb{P}(A)+(ϵ/2)<ϵ$

Example:
Consider our martingale betting strategy, with random variables $W_0,W_1,W_2,\dots$, and $A_n$ the event $\{X_1=X_2=\cdots =X_n=-1\}$

$\mathbb{P}(A_n)=2^{-n}$
$\mathbb{E}(|W_n|I_{A_n})=(2^n-1)\cdot 2^{-n}\to 1$
This cannot satisfy the conditions for uniform integrability for any $ϵ<1$

Now suppose $M_0,M_1,\dots$ is a uniformly integrable martingale (with respect to $X_0,X_1,\dots$) and $T$ is a stopping time with $\mathbb{P}\{T<\infty \}=1$

We have ${\lim }_{n\to \infty }\mathbb{P}\{T>n\}=0$
So we therefore have ${\lim }_{n\to \infty }\mathbb{E}(|M_n|I\{T>n\})=0$

Optional Sampling Theorem (again): Suppose $M_0,M_1,\dots$ is a uniformly integrable martingale with respect to $\{F_n\}$ and $T$ is a stopping time with $\mathbb{P}\{T<\infty \}=1$ and $\mathbb{E}(|M_T|)<\infty$, then $\mathbb{E}(M_T)=\mathbb{E}(M_0)$

If $X_1,X_2,\dots$ is a sequence of random variable and there is $C<\infty$ such that $\mathbb{E}(X_n^2)<C$ for each $n$, then the sequence is uniformly integrable

To show this with our previous definition, let $\delta ={ϵ}^2/4C$ and suppose $\mathbb{P}(A)<\delta$
$\mathbb{E}(|X_n|I_A)=\mathbb{E}[|X_n|I(A\cap \{|X_n|\ge 2C/ϵ\})]+\mathbb{E}[|X_n|I(A\cap \{|X_n|<2C/ϵ\})]$
$\le (ϵ/2C)\mathbb{E}[|X_n{|}^{2}I(A\cap \{|X_n|\ge 2C/ϵ\})]+(2C/ϵ)\mathbb{P}(A)$
$\le (ϵ/2C)\mathbb{E}(|X_n{|}^2)+(2C/ϵ)\mathbb{P}(A)<ϵ$

Example:
What if we set the the signs of the harmonic series randomly?
$\mathbb{P}\{X_i=1\}=\mathbb{P}\{X_i=-1\}=1/2$
$M_n={\sum }_{j=1}^n\frac{1}{j}{X}_j$

This is a martingale, since each $X_n$ has mean 0

$\mathbb{E}(M_n^2)=\text{Var}(M_n^2)={\sum }_{j=1}^n\text{Var}\left(\frac{1}{j}{X}_j\right)={\sum }_{j=1}^n\frac{1}{j^2}<\infty$
So this is uniformly integrable

Martingale Convergence Theorem

This theorem states when a martingale converges to a limiting random variable $M_{\infty }$. Let’s use Polya’s urn as an example

Let $0<a<b<\infty$, suppose that $M_n<a$, let $T=\min \{j:j\ge n\text{ and }{M}_j\ge b\}$, and $T_m=\min \{T,m\}$
For $m>n$, the optional sampling theorem says $\mathbb{E}(M_{T_m})=M_n<a$
But $\mathbb{E}(M_{T_m})\ge \mathbb{E}(M_{T_m}I\{T\le m\})=\mathbb{E}(M_{T}I\{T\le m\})\ge b\mathbb{P}\{T\le m\}$
So $\mathbb{P}\{T\le m\}<a/b$

This is true for all $m$, so $\mathbb{P}\{T<\infty \}\le \frac{a}{b}$
In other words, with probability $1-(a/b)$ the proportion of red balls never gets as high as $b$
If it does go up to $b$ (with probability $a/b$), the inverse of this argument says it’ll drop back down to $a$ with probability $\frac{1-b}{1-a}$

The probability this continues happening is ${\lim }_{n\to \infty }{\left(\frac{a}{b}\right)}^n{\left(\frac{1-b}{1-a}\right)}^n=0$
This tells us the proportion cannot fluctuate infinitely between any two numbers, i.e. $M_{\infty }$ exists
It happens to be we can also prove that this setup results in a uniform distribution directly

Martingale Convergence Theorem: Suppose $M_0,M_1,\dots$ is a martingale with respect to $\{F_n\}$ such that there exists $C<\infty$ with $\mathbb{E}(|M_n|)<C$ for all $n$. There there exists a random variable $M_{\infty }$ such that ${\lim }_{n\to \infty }{M}_n=M_{\infty }$.

Fix $a<b$ and think of $M_n$ as representing the cumulative results of a fair game
Whenever $M_n<a$, keep betting 1 until $M_n>b$, then stop until $M_n<a$ again

Our winnings are then $W_n={\sum }_{j=1}^n{B}_j(M_j-M_{j-1})$, where $B_j$ is 0 or 1 and $M_j-M_{j-1}$ is $\pm 1$

Note that $W_n$ is a martingale and $W_n\ge (b-a)U_n-|M_n-a|$ where $U_n$ denotes the number of “upcrossings” (passes between $a$ and $b$)

$\mathbb{E}(W_0)=\mathbb{E}(W_n)\ge (b-a)\mathbb{E}(U_n)-\mathbb{E}(|M_n-a|)$
$\mathbb{E}(|M_n-a|)\le \mathbb{E}(|M_n|)+a\le C+a$
$\mathbb{E}(U_n)\le \frac{\mathbb{E}(W_0)+C+a}{b-a}$

This holds for all $n$, so the expected number of upcrossings is bounded, meaning the number of upcrossings is always finite

Note that the martingale property $\mathbb{E}(M_n)=\mathbb{E}(M_0)$ does not imply that $\mathbb{E}(M_{\infty })=\mathbb{E}(M_0)$, such as in the martingale betting strategy $W_{\infty }={\lim }_{n\to \infty }{W}_n=1\ne \mathbb{E}(W_0)$

If $M_n$ is a uniformly integrable martingale then $M_{\infty }={\lim }_{n\to \infty }{M}_n$ exists and $\mathbb{E}(M_{\infty })=\mathbb{E}(M_0)$

Example:
Let $M_n$ be the proportion of red balls in Polya’s urn and suppose that at time $n=0$ there are $k$ red balls and $m$ green balls. Since $M_n$ is bounded, it is uniformly integrable, and $M_n$ approaches $M_{\infty }$ with $\mathbb{E}(M_{\infty })=\mathbb{E}(M_0)=k/(k+m)$

Example:
Let $X_1,X_2,\dots$ be independent random variables with $\mathbb{P}\{X_i=3/2\}=\mathbb{P}\{X_i=1/2\}=\frac{1}{2}$

Let $M_0=1$ and for $n>0$, let $M_n=X_1\dots X_n$
Note that $\mathbb{E}(M_n)=\mathbb{E}(X_1)\dots \mathbb{E}(X_n)=1$
$E(M_{n+1}\mid F_n)=E(X_1\dots X_{n+1}\mid F_n)=X_1\dots X_{n}E(X_{n+1}\mid F_n)=M_n$
Therefore, $M_n$ is a martingale with respect to $X_1,X_2,\dots$
Since $\mathbb{E}(|M_n|)=1$, the conditions of the martingale convergence theorem hold and $M_n\to M_{\infty }$ for some $M_{\infty }$

Is $M_n$ uniformly integrable?

$\ln M_n={\sum }_{j=1}^n\ln X_j$
$\mathbb{E}(\ln X_i)<0⟹\ln M_n\to -\infty$
Therefore $M_n\to 0$

$\mathbb{E}(M_0)\ne \mathbb{E}(M_{\infty })$, i.e. $M_n$ is not uniformly integrable

Example:
A normal problem in statistics is estimating the mean $\theta$ of a distribution given $Y_1,Y_2,Y_3,\dots$

In Bayesian statistics, the parameter $\theta$ is taken to be a random variable taken from a prior distribution

Under the prior distribution, $\mathbb{E}[\theta ]=\mu$, and let $M_0=\mu$ and $M_n=E[\theta \mid Y_1,\dots ,Y_n]$

$M_n$ is a martingale and the conditional distribution on $M_n$ is called the posterior distribution

We also know ${\lim }_{n\to \infty }{M}_n=M_{\infty }$
The strong law of large numbers says ${\lim }_{n\to \infty }\frac{Y_1+\cdots +Y_n}{n}=\theta$
So ${\lim }_{n\to \infty }E[\theta \mid Y_1,\dots ,Y_n]=\theta$

Assume these samples are from a Bernoulli distribution with $\mathbb{P}\{Y_j=1\}=\theta$
$\mathbb{P}\{Y_1+\cdots +Y_n=k\}=\left(\genfrac{}{}{0ex}{}{n}{k}\right){\theta }^k(1-\theta {)}^{n-k}$
$f_n(\theta \mid k)=\frac{\left(\genfrac{}{}{0ex}{}{n}{k}\right){\theta }^k(1-\theta {)}^{n-k}}{{\int }_0^1\left(\genfrac{}{}{0ex}{}{n}{k}\right){\theta }_1^k(1-{\theta }_1{)}^{n-k}d{\theta }_1}=\frac{(n+1)!}{k!(n-k)!}{\theta }^k(1-\theta {)}^{n-k}$

This is the beta distribution with parameters $k+1$ and $n-k+1$
The mean happens to be $\frac{k+1}{n+2}$

$\mathbb{P}\{Y_{n+1}=k+1\mid Y_1+\cdots +Y_n=k\}={\int }_0^1\mathbb{P}\{Y_{n+1}=1\mid \theta \}{f}_n(\theta \mid k)d\theta$
$={\int }_0^1\theta f_n(\theta \mid k)d\theta =\frac{k+1}{n+2}$

Maximal Inequalities

If $M_i$ is a sequence of random variables, defined the maximum processes as ${\overline{M}}_n=\max \{M_0,\dots ,M_n\}$ and $M_n^{\ast }=\max \{|M_0|,\dots ,|M_n|\}$

Maximal inequalities relate probabilities or expectations for ${\overline{M}}_n,M_n^{\ast }$ to $M_n,|M_n|$ respectively

Reflection Principle: Suppose $X_i$ are independent random variables whose distributions are symmetric about the origin, and let $M_0=0$ and $M_n=X_1+\cdots +X_n$. For every $a>0$, $\mathbb{P}\{{\overline{M}}_n\ge a\}\le 2\mathbb{P}\{M_n\ge a\}$

To prove this, let $T=\min \{j:M_j\ge a\}$
$\mathbb{P}\{{\overline{M}}_n\ge a\}={\sum }_{j=0}^n\mathbb{P}\{T=j\}$
$\mathbb{P}\{M_n\ge a\}={\sum }_{j=0}^n\mathbb{P}\{T=j,M_n\ge a\}={\sum }_{j=0}^n\mathbb{P}\{T=j\}\mathbb{P}\{M_n\ge a\mid T=j\}$
The independence and symmetry of $X_i$ shows that $\mathbb{P}\{M_n\ge a\mid T=j\}\ge \mathbb{P}\{M_n-M_j\ge 0\mid T=j\}=\mathbb{P}\{M_n-M_j\ge 0\}\ge \frac{1}{2}$ (noting that $M_j$ can be greater than $a$ makes this easier to understand)

Doob’s Maximal Inequality: Suppose $M_i$ is a nonnegative submartingale with respect to $F_n$. Then for every $a>0$, $\mathbb{P}\{{\overline{M}}_n\ge a\}\le \frac{\mathbb{E}[M_n]}{a}$

Let $A_j$ denote the $F_j$-measurable event $\{T=j\}$ (same $T$ as before),
$\mathbb{E}[M_n]\ge \mathbb{E}[M_{n}I\{T\le n\}]={\sum }_{j=0}^n\mathbb{E}[M_n{I}_{A_j}]$
$\mathbb{E}[M_n{I}_{A_j}]=\mathbb{E}[E(M_n{I}_{A_j}\mid F_j)]=\mathbb{E}[E(M_n\mid F_j)I_{A_j}]\ge \mathbb{E}[M_j{I}_{A_j}]\ge \mathbb{E}[a{I}_{A_j}]=a\mathbb{P}(A_j)$

So $\mathbb{E}[M_n]\ge {\sum }_{j=0}^{n}a\mathbb{P}(A_{j)}=a\mathbb{P}\{{\overline{M}}_n\ge a\}$

If $M_i$ is not necessarily nonnegative, we cannot immediately use the inequality, but there’s still an extension

If $\mathbb{E}[|M_n{|}^r]<\infty$ then $|M_n{|}^r$ is a submartingale,
$\mathbb{E}[|Y{|}^r\mid F_n]\ge |E[Y\mid F_n]{|}^r$
$\mathbb{E}[|M_{n+1}{|}^r\mid F_n]\ge |E(M_{n+1}\mid F_n){|}^r=|M_n{|}^r$

Likewise, if $\mathbb{E}[e^Y]<\infty$,
$E[e^Y\mid F]\ge e^{E(Y\mid F)}$
$E[e^{b{M}_{n+1}}\mid F_n]\ge e^{E(b{M}_{n+1}\mid F_n)}=e^{b{M}_n}$ for all $b$

Doob’s Maximal Inequality (again): Suppose $M_i$ is a martingale with respect to $F_n$, then for every $a,b>0$ and $r\ge 1$,

• $\mathbb{P}\{|{\overline{M}}_n|\ge a\}\le \frac{\mathbb{E}[|M_n{|}^r]}{a^r}$
• $\mathbb{P}\{{\overline{M}}_n\ge a\}\le \frac{\mathbb{E}[e^{b{M}_n}]}{e^{ba}}$

Example:
Let $S_n=X_1+\cdots +X_n$ denote a simple random walk in $\mathbb{Z}$ and let $b=1/\sqrt{n}$

$S_n$ is a martingale so we have,
$\mathbb{P}\{\max \{S_1,\dots ,S_n\}\ge a\sqrt{n}\}\le e^{-a}\mathbb{E}[e^{S_n/\sqrt{n}}]$
$\mathbb{E}[e^{S_n/\sqrt{n}}]=\mathbb{E}[e^{(X_1+\cdots +X_n)/\sqrt{n}}]=(\mathbb{E}[e^{X_1/\sqrt{n}}]{)}^n={\left(\frac{e^{1/\sqrt{n}}+e^{-1/\sqrt{n}}}{2}\right)}^n$
Taylor series shows that $\frac{e^{1/\sqrt{n}}+e^{-1/\sqrt{n}}}{2}=1+\frac{1}{2n}+O\left(\frac{1}{n^2}\right)$
${\lim }_{n\to \infty }\mathbb{E}[e^{S_n/\sqrt{n}}]={\lim }_{n\to \infty }{\left[1+\frac{1}{2n}+O\left(\frac{1}{n^2}\right)\right]}^n=e^{1/2}$

Hence,
$\mathbb{P}\{\max \{S_1,\dots ,S_n\}\ge a\sqrt{n}\}\le C{e}^{-a}$, i.e. the random walk in $\mathbb{Z}$ is recurrent