Stochastic Processes and Financial Mathematics
(part one)

7.5 Exercises on Chapter 7

On the martingale transform

• 7.1 Let $S_n=\sum _{i=1}^n{X}_i$ be the symmetric random walk, from Section 7.4. In each of the following cases, establish the given formula for $(C\circ S{)}_n$.

  • (a) If $C_n=0$, show that $(C\circ S{)}_n=0$.

  • (b) If $C_n=1$, show that $(C\circ S{)}_n=S_n$.

  • (c) If $C_n=S_n$, show that $(C\circ S{)}_n=\frac{S_n^2}{2}-\frac{n}{2}$

• 7.2 Let $M_n$ be a stochastic process. Let $\alpha ,\beta \in \mathbb{R}$ and let $C_n$ and $D_n$ be adapted stochastic processes. Let $X_n=\alpha C_n+\beta D_n$. Show that

  $$(X\circ M{)}_n=\alpha (C\circ M{)}_n+\beta (D\circ M{)}_n$$

  for all $n$.

On long-term behaviour of stochastic processes

• 7.3 Let $(X_n)$ be a sequence of independent random variables, with distribution

  $$\mathbb{P}[X_n=1]=\mathbb{P}[X_n=-1]=\frac{1}{2n^2}$$

  and $\mathbb{P}[X_n=0]=1-\frac{1}{n^2}$. Define

  $$S_n=\sum _{i=1}^n{X}_i$$

  where we take $S_0=0$.

  • (a) Show that $S_n$ is a martingale, and deduce that there exists a real-valued random variable $S_{\mathrm{\infty }}$ such that $S_n\stackrel{a.s.}{\to }{S}_{\mathrm{\infty }}$ as $n\to \mathrm{\infty }$.

  • (b) Show that, almost surely, there exists some $N\in \mathbb{N}$ such that $X_n=0$ for all $n\ge N$.

• 7.4 Write simulations of the symmetric & asymmetric random walks (in a language of your choice). Add functionality to draw the random walk as a graph, with time on the horizontal axis and the value of the walk on the vertical axis.

  Look at several samples from your simulations, with e.g. $1000$ steps of time, and check that they support the claims made in Section 7.4, about the long-term behaviour of random walks.

  Modify your simulation to simulate the random walks in Exercise 7.3 and Question 2 of Assignment 3. Check that your graphs support the result that, in both cases, $S_n\stackrel{a.s.}{\to }{S}_{\mathrm{\infty }}$. From your graphs, do you notice a difference in behaviour between these two cases?

• 7.5 Let $M_n=S_n-L_n$ be the martingale defined in exercise 4.5. Show that $(M_n)$ is not uniformly bounded in $L^1$.

• 7.6 Recall the Galton-Watson process $(Z_n)$ from Section 7.4, and recall that it is parametrized by its offspring distribution $G$.

  • (a) Give an example of an offspring distribution $G$ for which $\mathbb{P}[Z_n\text{ dies out}]=1$.

  • (b) Give an example of an offspring distribution $G$ for which $\mathbb{P}[Z_n\text{ dies out}]=0$.

• 7.7 Consider the following modification of the Pólya urn process. At time $n=0$, the urn contains one red ball and one black ball. Then, at each time $n=1,2,\dots$, we draw a ball from the urn. We place this ball back into the urn, and add one ball of the opposite colour to the urn; so if we drew a red ball, we would add a black ball, and vice versa.

  Therefore, at time $n$ (which means: after the $n^{th}$ draw is complete) the urn contains $n+2$ balls. Let $B_n$ denote the number of red balls in the urn at time $n$, and let $M_n=\frac{B_n}{n+2}$ denote the fraction of red balls in the urn at time $n$.

  • (a) Calculate $\mathbb{E}[M_{n+1}|{\mathcal{F}}_n]$ and hence show that $M_n$ is not a martingale, with respect to the filtration ${\mathcal{F}}_n=\sigma (B_1,\dots ,B_n)$.

  • (b) Write a simulation of the urn (in a language of your choice) and use your simulation to make a conjecture about the value of the almost sure limit of $M_n$ as $n\to \mathrm{\infty }$. Does this limit depend on the initial state of the urn?

• 7.8 Consider an urn that, at time $n=0$, contains $K\ge 1$ balls, each of which is either black or red. At each time $n=1,2,\dots$, we do the following, in order:

  • 1. Draw a ball $X_1$ from the urn, and record its colour. Place $X_1$ back into the urn.

  • 2. Draw a ball $X_2$ from the urn, and discard it.

  • 3. Place a new ball, with the same colour as $X_1$, into the urn.

  Thus, for all time, the urn contains exactly $K$ balls. We write $M_n$ for the fraction of red balls in the urn, after the $n^{th}$ iteration of the above steps is complete.

  • (a) Show that $M_n$ is a martingale.

  • (b) Show that there exists a random variable $M_{\mathrm{\infty }}$ such that $M_n\stackrel{a.s.}{\to }{M}_{\mathrm{\infty }}$ as $n\to \mathrm{\infty }$, and deduce that $\mathbb{P}[M_{\mathrm{\infty }}=0\text{ or }{M}_{\mathrm{\infty }}=1]=1$.

  This process is known as the discrete time ‘Moran model’, and is a model for the evolution of a population that contains a fixed number $K$ of individual organisms – represented as $K$ balls. At each time $n$, an individual $X_2$ (is chosen and) dies and an individual $X_1$ (is chosen and) reproduces.

  Although this model is a highly simplified version of reality, with careful enough application it turns out to be very useful. For example, it is the basis for current methods of reconstructing genealogical trees from data obtained by genome sequencing.

• 7.9 Consider the Pólya urn process from Section 7.4. Suppose that we begin our urn, at time $n=0$, with two red balls and one black ball. Let $M_n$ denote the resulting fraction of red balls in the urn at time $n$.

  • (a) Show that $M_n$ does not converge almost surely to $0$.

  • (b) Write a simulation of the Pólya urn process (in a language of your choice) and compare the effect of different initial conditions on $M_{\mathrm{\infty }}$.

• 7.10 Let $(S_n)$ denote the simple asymmetric random walk, with $q>p$. In Exercise 4.2 we showed that

  $$M_n=(q/p{)}^{S_n}$$

  is a martingale.

  • (a) Show that there exists a real valued random variable $M_{\mathrm{\infty }}$ such that $M_n\stackrel{a.s.}{\to }{M}_{\mathrm{\infty }}$.

  • (b) Deduce that $\mathbb{P}[M_{\mathrm{\infty }}=0]=1$ and that $(M_n)$ is not uniformly bounded in $L^2$.

  • (c) Use (a) and (b) to show that $S_n\stackrel{a.s.}{\to }-\mathrm{\infty }$. Explain briefly why this means that $S_n\stackrel{a.s.}{\to }\mathrm{\infty }$ for asymmetric random walks with $p>q$.

• 7.11 Let $S_n$ denote the symmetric random walk, from Section 7.4. Recall that $S_0=0$.

  • (a) Show that $S_n$ is even when $n$ is even, and odd when $n$ is odd.

  • (b) Define $p_n=\mathbb{P}[S_n=0]$. Show that $p_{2n}=(\genfrac{}{}{0ex}{}{2n}{n})2^{-2n}$ and $p_{2n+1}=0$.

    (Hint: Count the number of ways to return to zero after precisely $2n$ steps.)

  • (c) Show that $p_{2(n+1)}=(1-\frac{1}{2(n+1)})p_{2n}$ for all $n$, and hence show that $p_{2n}\to 0$ as $n\to \mathrm{\infty }$.

    (Hint: Use the inequality $1-x\le e^{-x}$, which holds for all $x\ge 0$.)

• 7.12 Let $S_n$ denote the symmetric random walk, from Section 7.4. Let $f:\mathbb{N}\to \mathbb{N}$ be a deterministic function.

  • (a) Show that if $\frac{S_n}{f(n)}$ is a martingale (for $n\ge 1$), then $f$ is constant.

  • (b) Show that if $\frac{S_n}{f(n)}$ is a supermartingale (for $n\ge 1$), then $f$ is constant.

Challenge questions

• 7.13 In this question we establish the formula (7.10), which we used in the proof of Lemma 7.4.8.

  Let $(Z_n)$ be the Galton-Watson process, with the offspring distribution $G$. Suppose that $\mathbb{E}[G]=\mu$ and $\mathrm{var}(G)={\sigma }^2<\mathrm{\infty }$. Set $M_n=\frac{Z_n}{{\mu }^n}$.

  • (a) Show that

    $$\mathbb{E}[(M_{n+1}-M_n{)}^2|{\mathcal{F}}_n]=\frac{Z_n{\sigma }^2}{{\mu }^{2(n+1)}},$$

  • (b) Deduce from part (a) and exercise 3.6 that $\mathbb{E}[M_{n+1}^2]=\mathbb{E}[M_n^2]+\frac{{\sigma }^2}{{\mu }^{n+2}}.$

• 7.14 In this question we prove the inequality (7.4), which we used in the proof of the martingale convergence theorem.

  Let $M_n$ be a sequence of random variables such that $M_n\stackrel{a.s.}{\to }{M}_{\mathrm{\infty }}$. Define

  $$X_n=\underset{k\ge n}{inf}|M_k|.$$

  • (a) Explain why $(X_n)$ is an increasing sequence and, hence, why there is a random variable $X_{\mathrm{\infty }}$ such that $X_n\stackrel{a.s.}{\to }{X}_{\mathrm{\infty }}$.

  • (b) Show that, for all $ϵ>0$ and all $n\in \mathbb{N}$ there exists some $n^{\prime }\ge n$ such that

    $$|M_{n^{\prime }}|-ϵ\le X_n\le |M_n|.$$

  • (c) Deduce that $X_{\mathrm{\infty }}=|M_{\mathrm{\infty }}|$.

  • (d) Check that the monotone convergence theorem applies to $(X_n)$.

  • (e) Deduce that $\mathbb{E}[|M_{\mathrm{\infty }}|]\le \underset{n\in \mathbb{N}}{sup}\mathbb{E}[|M_n|]$.

• 7.15 In this question we give a rigorous proof of Lemma 7.4.7.

  Let $Z_n$ and $X_i^{n+1}$ be as in (7.9) (i.e. $Z_n$ is a Galton-Watson process) and suppose that $\mathbb{E}[X_i^{n+1}]=\mu <1$.

  Let $\alpha \in [0,1]$. For each $i,n$ we define an independent random variable $C_i^{n+1}$, with the same distribution as $C$ where $\mathbb{P}[C=1]=\alpha$ and $\mathbb{P}[C=0]=1-\alpha$. We define

  $$

  $$\begin{array}{}\text{(7.11)}& {\tilde{X}}_i^{n+1}=\{\begin{array}{ll}0& \text{ if }{X}_i^{n+1}=0\text{ and }{C}_i^{n+1}=0\\ 1& \text{ if }{X}_i^{n+1}=0\text{ and }{C}_i^{n+1}=1\\ X_i^{n+1}& \text{ if }{X}_i^{n+1}\ge 1.\end{array}\end{array}$$

  Define ${\tilde{Z}}_n$ by setting ${\tilde{Z}}_0=1$, and then using (7.9) with ${\tilde{Z}}_n$ in place of $Z_n$ and ${\tilde{X}}_i^{n+1}$ in place of $X_i^{n+1}$. Define $f:[0,1]\to \mathbb{R}$ by $f(\alpha )=\mathbb{E}[X_i^{n+1}]$.

  • (a) Convince yourself that ${\tilde{Z}}_n$ is a Galton-Watson process, with offspring distribution given by (7.11).

  • (b) Explain briefly why $0\le Z_n\le {\tilde{Z}}_n$ for all $n$.

  • (c) Show that $f(0)<1$ and $f(1)\ge 1$. Deduce that there exists a value $\alpha \in [0,1]$ such that $f(\alpha )=1$.

  • (d) Show that $\mathbb{P}[Z_n\text{ dies out}]=1$.