>> In this module we're going to introduce Martingales. Martingales play a very important role in finance. They won't play a hugely important role in this course, but they will crop up now and again and it's worthwhile understanding what they are and seeing one or two examples of Martingales. We're going to have the following definition of a Martingale, a random process, Xn is a martingale, with respect to the information filtration Fn and probability distribution P, if these two conditions are satisfied. The first condition is just a technical integrability condition which states that the expected value of the absolute value of Xn must be finite for all n. The really important condition, is condition two here, which states that the expected value of Xn plus m, given Fn, is equal to Xn for all nm greater than or equal to 0. A quick comment on what I mean by information filtration. So the information filtration, Fn, is just a complicated way of recognizing the information we have at time n. So Fn will denote all of the information in our model that we know at time n. So usually, you will actually, it'd be the case that Fn is equal to the information given to you by X1 up to Xn. So basically, it's just recognizing that at time n, we've already seen the values X1 up to Xn. Returning to condition two here, we see that what this is really saying, is that the expected value of X, at any time in the future, is equal to its current value today. And so, Martingales have often been used to, to model what are called fair games, they've got a rich history in gambling, for example. Because this condition here, models the idea of a fair game, so your future pay-off, or your expected future pay-off, is equal to your current wealth today, Xm. We define a sub martingale, by replacing condition two with a greater than or equal to sign, And we define a super martingale by replacing condition two with a less than or equal to sign. A martingale then is both a sub martingale and a super martingale. Here's our first example of a martingale. We can construct one from a random walk. Let Sn be equal to the sum of the Xi's from i equals 1 to N, where the Xi's are IID with mean mu, then we can set Mn equal to Sn minus n times mu, and in that case, Mn is a martingale. We can see this because of the following, the expected value of Mn plus n, conditional time n information, is equal to, what we have over here on the right-hand side. So recall, Mn plus n will be equal to Sn plus m, minus n, plus m times mu. So this here is Sn, and here's our m plus m times is mu. Well were taking this expectation conditional on time n information, so in that case, what we can do is, we can take out the first nxi's, because they're known to us as a time end, so we can take them outside the expectation. And what we're left is the expectation of time n, of the sum of the xi's from i equals n plus 1 up to n plus m. Well, the xi's are IID, so knowing the value of the first nxi's tells us nothing about these. We also know that they've got mean mu, so therefore the expected value of this sum here, is equal to m times mu. We also have the n plus m mu over here. Now when we simplify all of this, this m-mu will cancel with this m-mu, we're left with the sum of the xi's and i equals 1 minus n times mu, and of course, we see that this is equal to Mn. So in fact, we have shown that the expected value of m, subscript m plus n, conditional on time n information is equal to Mn, and so it's a Martingale. In this example, we're going to consider what we will call a Martingale betting strategy. Let x1 x2 and so on be IID random variables, where xi can take on two possible values, it can take on 1 or minus 1, in each case it takes on that value with probability 1/2. So you can imagine xi representing the result of a coin-flipping game, you win $1 if coin comes up heads, and you lose $1 if coin comes up tails, that assumes that you bet, $1 on the game. What we're going to do now is to consider a doubling strategy, where we keep doubling the bet until we eventually win, once we win, we stop and our initial bet is $1. So the first thing to note, is that the size of the bet on the nth play is 2 to the n minus 1, and that's because of the following, so on the first play, we bet $1 which is equal to 2 to the 0. On the second play we bet $2, because we're doubling our bet, and this is equal to 2 to the power of 1. On the third play of the game we would double our bet again, so we would bet 4, and that's equal to 2 squared, and so on. So we can see that every time you played the game, we've doubled our bet and so the play, the size of the bet on the nth play is 2 to the n minus 1. That of course assumes we're still playing at time n, because we will only be playing at time n if we haven't yet won the game up until this point. Let Wn denote the total winnings after m coin tosses, And assume we start off with W0 equals 0. What we're going to show, then, is that Wn is a Martingale. To see this, first note that Wn can only take on two possible values, it can only take on the value 1, or it will take on the value minus 2 to the n plus 1, and that is true for all n. Why is this the case? Well, consider the following two situations. The first situation is as follows, suppose we win for the first time on the nth bet. Well in that case, Wn is equal to minus this sum here. Where does this sum come from? Well, we've lost $1 on the first bet, $2 on the second bet, and so on, up to 2 to the n minus $2, on the n minus first bet. Then on the nth bet we win and we win 2 to the power of n minus 1. Remember 2 to the power of n minus 1 is the size of the bet on the nth game, so therefor these are our winnings at time n, if we win for the first time on the nth bet. If you actually compute this sum, just using the, the formula for summing a geometric series, remember it's a to the 1 minus r to the power of n, all over 1 minus r, that's the general formula. In this case, this translates to 1 times 1 minus 2 to the power of n minus 1 divided by 1 minus 2, and that is equal to 2 to the power of n minus 1 minus 1, which is what we have here. So W n, if we win for the first time on the nth bet, is equal to minus 2 to the n minus 1 minus 1, plus 2 to the n minus 1, this term cancels with this term and we're left With 1. Thereafter of course, we're always left with 1 because we stop playing the game as soon as we win. So the other situation that can arise, is that we have not yet won after n bets, in that case, the winnings, Wn is equal to minus 1 plus 2 and so on up to 2 to the n minus 1. It's 2 to the n minus 1 because we also lost the nth bet, so in fact this is a minus, this becomes a minus down here, and we get this quantity here, we sum it up and we get a sum of minus 2 to the n plus 1. So therefore these are the two possible values of Wn, 1 and minus 2 to the power of n plus 1. To show Wn as a martingale, we only need to show the following, that the expected value of Wn plus 1, given Wn, is equal to Wn. And this follows by an iterated expectations argument. And the reason is as follows, suppose we want to calculate the expected value of Wn plus 2 given Wn. Well in that case, we can write this as the following, the expected value of the expected value of Wn plus 2, given Wn plus 1, all given Wn. Now this term inside here, is equal to Wn plus 1 by this result here. So by star, with n equals m plus 1, so by evaluating star but not taking n equals m plus 1 we get that this inner expectation here equals Wn plus 1. So therefore, this is equal to the expected value of Wn plus 1, given wn and of course, this is equal to Wn again by star. So in fact, for any value of little n, we can show that this result holds, just using this iterated expectations argument we did here. So all we need to do to show that Wn is martingale, is to establish star, and that's what we'll do now. There are two cases to consider. The first case is where Wn equals 1. Recall, we have shown that Wn can only take on two values, the first value is 1. So if Wn equals 1, then actually we stop playing the game, because it means we've already won at some point, we've stopped playing the game and therefore, Wn is always equal to 1 in every period after we have first won. So in this case, the probability that Wn plus 1 equals 1, given Wn equals 1, is indeed equal to 1. Which means, the expected value of Wn plus 1, given Wn equals 1 well it must be equal to 1 because that's the only value it can take. It takes on this value 1 with probability 1, so the, this expected value equals 1, which is equal to Wn. The other situation that can occur, is that Wn equals minus 2 to the power of n plus 1. If that's the case, then we will bet 2 to the power of n, on the n plus first toss. So in that case, Wn plus 1 will be either 1, if we win the n plus first toss, or it will be minus 2 to the power of n plus 1 plus 1, and this follows from our arguments on the previous slides. Wn plus 1 will take on this value with probability a half and it'll take on this value with probability half, and that follows because it's a fair coin, we win with probability a half and we lose with probability half. So therefore, we have these two expressions here, from which it immediately follows that the expected value of Wn plus 1, given Wn equals minus 2 to the power of n plus 1, it is equal to 1, with prob-, with probability a half and is equal to minus 2 to the n plus 1, plus 1 of probability a half. If we sum these two together, we get minus 2 to the n plus 1, and that of course is equal to Wn. So in both possible cases, case 1 and case 2, we have shown that the expected value of Wn plus 1, given Wn, is equal to Wn. And so we have shown that Wn is a Matingale. Now let me mention this example is quite complicated, but it was worthwhile introducing because it is easy to generalize this example to the case where you allow random bets on each play of the game, as long as those bets only depend on what you've seen up to that point, you will actually still get a Martingale. For a final example, we look at something called Polya's Urn, we won't go through all the details, in fact, you can complete the details yourself. Considering urn, which contains red balls and green balls, so we've got some urns like this, there are red balls in there and there are green balls inside this urn. And at each time step a ball is chosen randomly from the urn, if the ball is red, then it's returned to the urn with an additional red ball. If the ball is green, then it is returned to the urn with an additional green ball. So what we're going to do is we're going to see that there are n plus 2 balls in the urn, at time n. And this follows, because we begin with two balls, and after every play of the game we add an additional ball, either an additional red ball, or an additional green ball. So we have n plus 2 balls in the urn, after time n. Let Xn denote the number of red balls in the urn after n draws. Then, if Xn is equal to k, Xn plus 1 can only take on two possible values, it will take on the value k plus 1, or the value k. It will take on the value k plus 1, if the ball withdraw on the nth plus 1 play is a red ball and that will occur with probability k over n plus 2, k because there are k balls-, k red balls in the urn and n plus 2 because n plus 2 is the total number of balls in the urn. Likewise Xn plus 1 would be equal to k given Xn equals k, if we draw a green ball, because if we draw a green ball we will not be adding an additional red ball. So Xn plus 1 equals k, given Xn equals k that occurs with probability n plus 2 minus k divided by n plus 2. And now, what we claim and what you can easily check, is that Mn, which is equal to Xn divided by n plus 2, is a Martingale.