Martingales and Random Walks

Week 2

Lecture Notes

Measurability

(continuing from last time)

A stochastic process is a collection of random variables indexed by time. If you start out at time 0 and each time you pick heads you go one step, it’s now a walk. You have no idea where you’re going to be in the future, but you know the general distribution and have an idea of where you’re likely to do.

We also have a filtration which is a collection of $𝜎$-algebras indexed by time. If we have enough information in the filtration to know what set your outcome is in, you get an adapted stochastic process. Mathematically, these variables are considered $\mathrm{ℱ︀}$-measurable by the filtration $\mathrm{ℱ︀}$.

Independence

Two $𝜎$-algebras are independent if for every element $𝐴$ and $𝐵$ in both $𝜎$-algebras:

$\mathbb{P}(𝐴\cap 𝐵)=\mathbb{P}(𝐴)\times \mathbb{P}(𝐵)$

This is a strong mathematical result, but it is not useful because most useful $𝜎$-algebras are infinite.

BUt if you can show that the joint cdf is the same as the products of the marginal cdfs (WILL COVER LATER) it will do the same thing.

We can say that two random variables are independent if the $𝜎$-algebras generated by them are

One useful way to do this is by determining that if one variable is measurable by a $𝜎$-algebra that is independent of a $𝜎$-algebra generated by another variable, they are independent.

Variance

Variance $𝕍(𝑋)$ is defined by:

$𝑉𝑎𝑟(𝑋)=𝕍(𝑋)=𝔼[(𝑋-𝔼[𝑋]{)}^2]=𝔼[{𝑋}^2]-(𝔼[𝑋]{)}^2$

This variable is necessarily nonnegative, although it may be infinite. If your variance is negative, it is for sure wrong. The standard deviation of $𝑋$ is the square root of the variance.

The reason that it’s squared is that it’s always positive, which means that movements above the mean matter as much as movements below the mean. The reason it’s squared and not absolute value is that if you have tiny differences from the mean, and you square them, they disappear, while bigger ones get bigger. It minimizes tiny differences and maximizes larger ones. This is why it’s called the measurement of central tendency, because it measures how clustered values are around the mean.

Covariance

We have a sample space and we take variables. You measure how much variables fluctuate with each other with respect to the inputs from the sample space.

$\text{Cov}(𝑋,𝑌)=𝔼\left\{(𝑋-𝔼[𝑋])(𝑌-𝔼[𝑌])\right\}$

$={\sum }_{𝜔\in \mathrm{\Omega }}(𝑋(𝜔)-𝔼[𝑋])(𝑌(𝜔)-𝔼[𝑌])\mathbb{P}(𝜔)$

You’re going through every entry and seeing how much $𝑋$ differs from its mean and $𝑌$ differs from its mean, weighting them with their probability measure. It’s how they are different from each other in the same scenario.

We can say that two variables are uncorrelated if their covariance is 0. Independent variables are uncorrelated, but uncorrelated variables may not be independent. The value of covariance doesn’t tell you how correlated variables are, only the correlation coefficient does:

$𝜌(𝑋,𝑌)=\frac{\text{Cov}(𝑋,𝑌)}{\sqrt{𝕍(𝑋)𝕍(𝑌)}}$

If this value is 0, then they are uncorrelated. This coefficient is always $[-1,1]$. −1 means perfectly inverse, and 1 means perfectly direct. This only has to do with direction, not necessarily magnitude.

Let’s consider a probability space. $\mathrm{𝒢︀}$ is a sub-$𝜎$-algebra of $\mathrm{ℱ︀}$, and $𝑋$ random variable. The conditional expectation of $𝑋$ given $\mathrm{𝒢︀}$ is a random variable that is measurable i.e. $𝔼[𝑋|\mathrm{𝒢︀}]$ is $\mathrm{𝒢︀}$-measurable and partial averaging

If i limited myself just to a set $𝐴$ and I averaged $𝑋$ over $𝐴$, I should get the same result as if I took the average of $𝑋$. Underneath this subset, if I average over the $𝑋$ terms.

Conditional expectations are random variables.

Technically, the condition in a conditional expectation is a $𝜎$-algebra.

Important theorems:

1. Linearity of conditional expectations: $𝔼[{𝑐}_1𝑋+{𝑐}_2𝑌|\mathrm{𝒢︀}]={𝑐}_1𝔼[𝑋|\mathrm{𝒢︀}]+{𝑐}_2𝔼[𝑌|\mathrm{𝒢︀}]$ Let’s consider a situation where $𝑋$ can take one of two values and $𝑌$ can take one of two values, both dependent on $𝑎,𝑏,𝑐,𝑑$. If $𝑌=3$, $𝜔\in \left\{𝑎,𝑐\right\}$, then $𝔼[𝑋|𝑌=3]={\sum }_{𝜔\in \mathrm{\Omega }}𝑋(𝜔)\mathbb{P}(𝜔|𝑌=3)$ and this is the same as ${\sum }_{𝜔\in \mathrm{\Omega }}𝑋(𝜔)\frac{\mathbb{P}(𝜔\cap \left\{𝑎,𝑐\right\})}{\mathbb{P}(\left\{𝑎,𝑐\right\})}$ from Bayes theorem Knowing that Y=3, that means ${\sum }_{𝜔\in \left\{𝑎,𝑐\right\}}𝑋(𝜔)\frac{\mathbb{P}(𝜔)}{2/3}$ $=\frac{3}{2}(𝑋(𝑎)\mathbb{P}(𝑎)+𝑋(𝑐)\mathbb{P}(𝑐))$
2. We can take something that is known outside of an expectation. $𝔼[𝑋𝑌|\mathrm{𝒢︀}]=𝑋𝔼[𝑌|\mathrm{𝒢︀}]$
3. Iterated conditioning. If $\mathrm{\mathscr{H}︀}\subset \mathrm{𝒢︀}$, (think of this as information), then we know less information in $\mathrm{\mathscr{H}︀}$ than in $\mathrm{𝒢︀}$. If I create a new random variable around $𝑋$ when you condition it just on this less information set, you get: $𝔼[𝔼[𝑋|\mathrm{𝒢︀}]|\mathrm{\mathscr{H}︀}]=𝔼[𝑋|\mathrm{\mathscr{H}︀}]$ We use iterated conditioning to complicate a process before simplifying it.
4. Independence: If $𝑋$ is independent of $\mathrm{𝒢︀}$, having the condition doesn’t do anything.
5. Conditional Jensen’s Inequality - not important

Martingale Processes

Consider an adapted stochastic process $𝑀(𝑡)$, for $0\le 𝑡\le 𝑇$ where $𝑇$ is a fixed positive number. The process needs to be such that if I know all the information up to time $𝑠$, my best estimate for where it will be in the future, it will be the same as it is now. On average, I expect it to stay the same. Even though it probably won’t, I expect it to. If you expect it to grow, it’s a submartingale, and if you expect it to shrink, it’s a supermartingale.

Markov

If you have a stochastic process where for every non-negative function $𝑓$ on the number line, there is another $𝑔$ where you can describe the expectation for a future $𝑓(𝑋(𝑡))$ given the information in time $𝑠$ with $𝑔(𝑋(𝑠))$. How much information do we need to calculate the value of this process? We would love to have a stock process that is Markov. This aligns with the idea that all past information is encoded in the current price, so we only need the current price and some function on that to determine a future price.

Random Walks

We can define the outcomes of the tosses of a coin where heads is 1, and tails is −1. The process of flipping a coin and calculating the sum of the values is the symmetric random walk $𝑀$. These increments are independent from each other, whether symmetric or asymmetric. Knowing that there were a bunch of heads in the past doesn’t give you any information about future flips. Our increment is defined by:

${𝑀}_{{𝑘}_{𝑖+1}}-{𝑀}_{{𝑘}_{𝑖}}={\sum }_{𝑗={𝑘}_{𝑖}+1}^{{𝑘}_{𝑖+1}}{𝑋}_{𝑗}$

This starts at plus 1 because… wasn’t listening 😓

If we want to calculate the expected value of this, we can use the linearity of expectation to bring the expectation into the random variable: ${\sum }_{𝑖={𝑘}_{𝑖}+1}^{{𝑘}_{𝑖+1}}𝔼[{𝑋}_{𝑖}]$

By adding these together, we can see that the expectation of the random variable is 0.

Is variance a linear operator? If it is, then $\text{Var}(𝛼𝑋+𝛽𝑌)=𝛼\text{Var}(𝑋)+𝛽\text{Var}(𝑌)$

Using our definition of variance, this is the same as

$𝔼[(𝛼𝑋+𝛽𝑌{)}^2]-𝔼[𝛼𝑋+𝛽𝑌{]}^2$

$={𝛼}^2𝔼[{𝑋}^2]+2𝛼𝛽𝔼[𝑋𝑌]+{𝛽}^2𝔼[{𝑌}^2]-{𝛼}^2𝔼[𝑋{]}^2-2𝛼𝛽𝔼[𝑋]𝔼[𝑌]-{𝛽}^2𝔼[𝑌{]}^2$

and this ends up equalling, once you cancel everything out

$={𝛼}^2\text{Var}(𝑋)+2𝛼𝛽\text{Cov}(𝑋,𝑌)+{𝛽}^2\text{Var}(𝑌)$

Clearly, this is not a linear operator. Only in the scenario where the variables are independent and their coefficient is 1, i.e. they are independent and identically distributed (iid), do they act as if they are linear.

When we look at the random walk $𝑀$, we can see that each increment of the random walk is independent, and the coefficient is 1. So in this case, the summation of the variances happens to equal the variance of the summations.

What about $𝔼[{𝑋}_{𝑗}^2]$? Because the negative outcome is squared, it becomes 1, which means that the variance is 1, so that the summation of variances is $𝑙-𝑘$. If you have a walk that lasts 5 steps or 500 steps, the expectation is the same, but the variance goes from 5 to 500.

We can prove this symmetric random walk is a Martingale.

We need to prove for $𝑘<𝑙$ that

$𝔼[𝑀(𝑙)|\mathrm{ℱ︀}(𝑘)]=𝑀(𝑘)$

If we add a zero, nothing should happen, right?

$=𝔼[𝑀(𝑙)-𝑀(𝑘)+𝑀(𝑘)|\mathrm{ℱ︀}(𝑘)]$

Now we can use the linearity of expectations to take out the $𝑀(𝑘)$

$𝔼[𝑀(𝑙)-𝑀(𝑘)|\mathrm{ℱ︀}(𝑘)]+𝔼[𝑀(𝑘)|\mathrm{ℱ︀}(𝑘)]$

for the purposes of this, $\mathrm{ℱ︀}(𝑘)$ is the information we would know at time $𝑘$, and $𝑀(𝑘)$ is definitely known with respect to that information. We also know that the difference between $𝑀$ is the increment, and that the increment is independent of information, so we can ignore it:

$𝔼[𝑀(𝑙)-𝑀(𝑘)]+𝑀(𝑘)$

We already know that the expectation of the increment is 0, so

$𝑀(𝑘)=𝑀(𝑘)$

First Order Variation

This is the total change of the process. The first order variation in a function is the change in the y-axis. We’ll consider $\mathrm{\Pi }$ as the partition of the process, going from $\left\{{𝑡}_0,{𝑡}_1,\dots ,{𝑡}_{𝑛}\right\}$, where this is a sequence of ordered values that ends at $𝑡$. Let’s get an operator called the norm which gives you the length of the biggest piece of the partition: $||\mathrm{\Pi }||$

We want a brute force way to calculate this first order variation for any function. We’ll cut up our function into a bunch of different pieces, and then look at the value of the function at every point (the “realizations” of this process). You can get all the changes in y at the different values and add them all up. In order to get the true value, we would add more and more points, maybe an infinite number of points. We need to take the limit as the norm of the partition approaches 0. The mechanical way to do this is to take the norm and cut it in half at every step:

$𝐹{𝑉}_{𝑇}(𝑓)={lim}_{||\mathrm{\Pi }\left|\right|\to 0}{\sum }_{𝑗=0}^{𝑛-1}|𝑓({𝑡}_{𝑗+1})-𝑓({𝑡}_{𝑗})|$

For a continuous and differentiable function, we can use the mean value theorem which means that for every increment, there exists a number which exists within that increment where the derivative of that point is equal to the slope between the beginning and end of the increment. In this case, we can use this fact to simplify this to get the Riemann integral.

Quadratic Variation

$[𝑓,𝑓](𝑇)={lim}_{||\mathrm{\Pi }\left|\right|\to 0}{\sum }_{𝑗=0}^{𝑛-1}(𝑓({𝑡}_{𝑗+1})-𝑓({𝑡}_{𝑗}){)}^2$

Does not have a nice real world analogy. It is that same change squared. This is uninteresting outside of stochastic calculus because the quadratic variation for a continuous, differentiable function is always 0.

We can create a handy inequality here. We can take out the norm like this and say

${lim}_{||\mathrm{\Pi }\left|\right|\to 0}\left|\right|\mathrm{\Pi }\left|\right|{\sum }_{𝑗=0}^{𝑛-1}({𝑓}^{\prime }({𝑡}_{𝑗}^{\ast }){)}^2({𝑡}_{𝑗+1}-{𝑡}_{𝑗})$

is greater than or equal to the same but with the difference squared, because the norm is the largest piece.

And because this is a continuously shrinking limit that’s being added together, we can say that this is an integral of a derivative. But we also know that because the term of the norm is here, that goes to 0, which means that the entire thing is 0. And because that is greater than or equal to the quadratic variation formula, that must also always be zero (because it has to be positive).

We will deal with some situations where the first order variation will be infinite, and quadratic variation will give us a more interesting result.

The random walk evolves in a discontinuous, non-differentiable way. It also is random, so there are multiple different versions of the same function. Subdividing this function with first order variation gives you that the expectation is 0 most of the time. We can consider it as

$𝐹{𝑉}_4(𝑀)={\sum }_{𝑗=1}^4|{𝑋}_{𝑗}|$

so you get the total change as being 4. Open question: explain this step more clearly.

For quadratic order variation, this is

$[𝑀,𝑀](4)={\sum }_{𝑗=1}^4({𝑋}_{𝑗}{)}^2=4$

This does not necessarily occur! If the step size changed to 2 and −1, this is no longer true. The quadratic order variation is only the same as first order variation when the random walk is symmetric.

Scaled Symmetric Random Walk

Brownian motion is an approximation for a process that constantly fluctuates. Our random walk jumps up and down simplistically. We need to start taking steps a lot more often, but the problem with that is it would significantly magnify our variation without changing much. We also need to decrease step size. We create more and more steps by subdividing the x-axis, and make them smaller. This gives us our scaled symmetric random walk. We will take $𝑛$ times as many steps, but the step size is decreased by $\sqrt{𝑛}$:

${𝑊}^{(𝑛)}(𝑡)=\frac{1}{\sqrt{𝑛}}{\sum }_{𝑗=1}^{𝑛𝑡}{𝑋}_{𝑗}$

We still have independence of increments in this walk. The expected value of a walk is still 0. We can use the same arguments to determine that this is a martingale. But if we look at the variance of the increments in the scaled symmetric random walk, it is now

$\text{Var}\left({\sum }_{𝑗=𝑛𝑠+1}^{𝑛𝑡}\frac{1}{\sqrt{𝑛}}{𝑋}_{𝑗}\right)$

This presents a problem for our attempt to convert between summation of variances because there is now a coefficient. But because $𝛼=𝛽$ in this case, Open question: explain this conversion more clearly.

$={\sum }_{𝑗=𝑛𝑠+1}^{𝑛𝑡}\frac{1}{𝑛}\text{Var}({𝑋}_{𝑗})$

$=\frac{1}{𝑛}(𝑛𝑡-𝑛𝑠)=𝑡-𝑠$

The reason it has to be $\sqrt{𝑛}$ and not $𝑛$ is because in this formula, the variance would be going to 0 as $𝑛$ goes to $\infty$.

The quadratic variation becomes $𝑡$, but the first order variation goes to $\infty$.

Normal Distribution

We will prove that the scaled symmetric walk approaches the normal distribution. Any normal variable is defined by $𝜇$ and ${𝜎}^2$. It also has a

${𝜑}_{{𝑊}^{(𝑛)}(𝑡)}(𝑠)=𝔼[{𝑒}^{𝑠{𝑊}^{(𝑛)}(𝑡)}]$

$=𝔼[{𝑒}^{{\sum }_{𝑗=1}^{𝑛𝑡}\frac{𝑠}{\sqrt{𝑛}}{𝑋}_{𝑗}}]$

$=𝔼\left[{\prod }_{𝑗=1}^{𝑛𝑡}{𝑒}^{\frac{𝑠}{\sqrt{𝑛}}{𝑋}_{𝑗}}\right]$

This is the expected value of the product as a whole bunch of independent variables, which means that it’s the same as the product of the expectations:

$={\prod }_{𝑗=1}^{𝑛𝑡}𝔼\left[{𝑒}^{\frac{𝑠}{\sqrt{𝑛}}{𝑋}_{𝑗}}\right]$

Important: understand what’s random and what’s not. ${𝑋}_{𝑗}$ only is random. Given the expectation of ${𝑋}_{𝑗}$ being known:

$={\prod }_{𝑗=1}^{𝑛𝑡}\left(\frac{1}{2}{𝑒}^{\frac{𝑠}{\sqrt{𝑛}}}+\frac{1}{2}{𝑒}^{-\frac{𝑠}{\sqrt{𝑛}}}\right)$

this is the same as

$={\left(\frac{1}{2}{𝑒}^{𝑠/\sqrt{𝑛}}+\frac{1}{2}{𝑒}^{-𝑠/\sqrt{𝑛}}\right)}^{𝑛𝑡}$

This is the moment generating function

We are trying to prove that

${lim}_{𝑛\to \infty }{𝜑}_{{𝑊}^{(𝑛)}(𝑡)}(𝑠)={𝑒}^{\frac{1}{2}{𝑠}^2𝑡}$

because this means that the walk is normally distributed. We can take the natural log of both sides

${lim}_{𝑛\to \infty }log\left({𝜑}_{{𝑊}^{(𝑛)}(𝑡)}(𝑠)\right)=\frac{1}{2}{𝑠}^2𝑡$

Let’s make a convenience variable $𝑥$

$𝑥=\frac{1}{\sqrt{𝑛}}$

We are satisfied that the limit of $𝑛$ going to $\infty$ is the same as $𝑥$ going to 0.

${lim}_{𝑥\to 0^{+}}(\frac{𝑡}{{𝑥}^2}log(\frac{1}{2}{𝑒}^{𝑠𝑥}+\frac{1}{2}{𝑒}^{-𝑠𝑥}))$

this results in a 0/0, which is undesirable. In order to get rid of this situation, we will apply L’Hopital’s rule.

$\stackrel{𝐿}{=}\frac{𝑠𝑡}{2}{lim}_{𝑥\to 0^{+}}(\frac{\frac{1}{2}{𝑒}^{𝑠𝑥}-\frac{1}{2}{𝑒}^{-𝑠𝑥}}{𝑥})$

which is still indeterminate, so we will apply it once again, which will give us the normal distribution

Open question: copy the limiting argument from the video.

Brownian Motion

Suppose there is a continuous function $𝑊(𝑡)$ which starts at $𝑊(0)=0$ and depends on $𝜔$. We have increments that are independent and each of the increments are normally distributed. The expectation is 0, and the variation is ${𝑡}_{𝑖+1}-{𝑡}_{𝑖}$. The quadratic variation of Brownian motion is known to be $𝑡$. Because this is a continuous, non-differentiable variable, its first order variation goes to infinity.

Let’s talk about mean squared convergence. We can define a random process that will converge to our quadratic variation, and if its square does as well, and the mean of that square converges as well, the expectation must as well.

We have a sample quadratic variation for a random partition

${𝑄}_{\mathrm{\Pi }}={\sum }_{𝑗=0}^{𝑛-1}(𝑤({𝑡}_{𝑗+1})-𝑊({𝑡}_{𝑗}){)}^2$

We will make more intricate partitions as we go on so that the limit approaches 0.

I want to show that

${lim}_{||\mathrm{\Pi }\left|\right|\to 0}𝔼[{𝑄}_{\mathrm{\Pi }}]=𝔼[𝑇]$

where $𝑇$ is a constant. Because $𝑇$ is a constant, expectation is itself and variance is 0. We can then show that we want ${𝑄}_{\mathrm{\Pi }}$ to approach both the variance and the value of $𝑇$.

$𝔼[{𝑄}_{\mathrm{\Pi }}]=𝔼[{\sum }_{𝑗=0}^{𝑛-1}(𝑊({𝑡}_{𝑗+1})-𝑊({𝑡}_{𝑗}){)}^2]$

We can use the linearity of expectation to get

$={\sum }_{𝑗=0}^{𝑛-1}𝔼[(𝑊({𝑡}_{𝑗+1})-𝑊({𝑡}_{𝑗}){)}^2]$

Using our previous definition of variance as

$𝔼[{𝑋}^2]=\text{Var}(𝑋)+𝔼[𝑋{]}^2$

We know that the mean of the increment of Brownian motion is 0 and its variation is time $𝑡$.

So this becomes

${\sum }_{𝑗=0}^{𝑛+1}({𝑡}_{𝑗+1}-{𝑡}_{𝑗})=𝑡$

therefore,

${lim}_{||\mathrm{\Pi }\left|\right|\to 0}𝔼[{𝑄}_{\mathrm{\Pi }}]=𝑡$

because the limit of a constant is the same as the constant.

$\text{Var}((𝑊({𝑡}_{𝑗+1})-𝑊({𝑡}_{𝑗}){)}^2)=𝔼[(𝑊({𝑡}_{𝑗+1})-𝑊({𝑡}_{𝑗}){)}^4]$

Without standardization, the fourth moment is $3{𝜎}^4$

The variance of an increment is the duration of time.

${lim}_{\parallel \mathrm{\Pi }\parallel \to 0}\text{Var}({𝑄}_{\mathrm{\Pi }})=2{lim}_{\parallel \mathrm{\Pi }\parallel \to 0}{\sum }_{𝑗}({𝑡}_{𝑗+1}-{𝑡}_{𝑗}{)}^2=0$

We have derived the quadratic variation of time. 🤯

Time is a continuous, differentiable function, so it’s 0.

Overall: we have determined that the quadratic variation of Brownian motion is equal to the time almost surely, since any individual continuous differentiable function formed by Brownian motion has probability 0 of occurring.