In this last video,

we illustrate how to use the techniques

we have recently learned in order to

answer some questions about the following

classical problem– consider a gambler

putting a bet of $1 in a game that has a pay off

of one dollar if she wins. We assume that this

is a fair game, so the probability of winning

$1 on each play of the game is one-half. And so the probability of

losing the bet is also one-half. Suppose that she

starts with i dollars and continues to play

the game until either she reaches a goal of n dollars, or

she has no money left, whatever comes first. Let us consider a

first question, which is the following– what is the

probability that she ends up with having her

goal of n dollars? Now, how to go about

solving this problem? Can we think of a Markov

chain representation for this problem? But in that case, what

would be good choices for the definition

of the states? Let us think. At any point in time, the

only relevant information is the amount of money

the gambler has available. How she got to that amount

in the past is irrelevant. And if this amount is

neither zero nor n, then she will play again. And the next state

will be a number which will be increased

or decreased by one unit, depending on winning

or losing the next bet. So we can represent the

possible evolution of this game with the following

probability transition graph. So we have n plus 1 states. This is the state where

she loses all her money. This is the state where

she has i amount of money before the next betting. And here, this is the state

n where she reaches her goal and she can leave. In terms of the

transition probability, assuming that you are at a

given time in that state, that means that you have

i money in your pocket, and you play the next bet. With a probability one-half,

you will gain or win. And so your amount

of money is i plus 1. Or you lose and your

money is i minus 1. And you keep repeating until

you reach either n or zero. And then you stop. So this is a Markov chain, and

that state 0 and that state n are absorbing states. Once you reach them,

you stay there forever. So what this question is

asking is the probability a of i of– starting from i, what

is the probability that you will end up in that

absorbing state? And we have done this

calculation previously. So let us repeat the

technique very briefly. Clearly here, if you

start with 0 dollars, you will never reach that. So it’s going to be 0. On the other hand, if you

start with your desired goal, you don’t play anymore. So your probability is 1. Now of course,

what is of interest is if i is strictly

between 0 and n. And now the question is how

to calculate that probability. And we have seen

that the way to do that is to look

at the situation, and say let’s assume that

you are in that state i. And what happens next? Well with a probability 0.5,

you will move to that state. And now you are in that level

with i plus 1 amount of money. And what is the probability

that, given that you’re here, you’re going to end up in n? It’s going to be a i plus one. So it’s a i plus one. Plus the other

alternative is that you are going to lose money

and end up in that state. And there, the remaining

probability to reach the time n is a i minus 1. So you have this

kind of equation. This is valid for all

i between 0 and n. And this is a system of

equations that you can solve. It’s not very

difficult to solve. Actually, you can

look in the textbook. There will be some

trick to do that. There are many, many

ways to do that. We’re not going to spend

our time going into details, but essentially if

you solve that system, you will see that the

answer will be that a of i is i over n. So if you start with

i amount of money, the probability that you’re

going to reach your goal here is i over n. So here clearly, if

you’re extremely greedy, and you have a very,

very, very high goal, that means n is

very, very large– so large that compared

to your initial amount i, n can be considered

to be infinity. Then the probability that you’re

going to reach your high goal will go to 0, where

n goes to infinity. So again, if you are

extremely greedy, no matter how much your fixed

amount of initial money is, the probability that you

will stop the game reaching your goal is going to

be increasingly small. And since the other state

is 1 minus this one, the priority that you’re

going to get ruined is going to be closer to 1. All right, so we have

that answer here. What about the next question? Next question is

the following– what would be the expected

wealth at the end? Again, this is a

Markov chain where there are two absorbing states. All the others are transient. You’re guaranteed

with probability 1 that you will reach

either 0 or n. So it’s a valid question to

know once you reach either 0 or n, what is the expected

wealth at the end? Well, if you arrive

here, it’s going to be 0. And if you arrive here,

it’s going to be n. So the expected

value of that wealth will be 0 times the probability

of ending in that, plus n times the probability

of getting there. So it’s going to be that

expression– 0 times 1 minus a of i,

plus n times a of i. And here what we then get is

n times i over n, which is i. Which is quite interesting. This is exactly how you started. So in some sense, in expectation

there is no free lunch here. The next question is–

how long does the gambler expect to stay in the game? We know that eventually,

he will either reach 0 or n with probability 1. The question is– how

long is it going to take? Again, we have seen

in a previous video that this is essentially

calculating the expectation to absorption. And we know how to do that. So let’s recap what we had said. If you define mu of i to be

the expected number of plays starting from i,

what do you have? Well, for i equal

to 0 or i equals n, either way– if you

start from here, or you start from here–

the expected number of plays is 0, right? Because you’re done. And otherwise, you use the same

kind of derivation that we had. If you start at i

between 1 and n, then you will see that mu of i,

after one transition, plus 1, you will either be in state

i plus 1– in that case, this expectation will

be mu i plus 1 — or you will be in

state i minus 1. In that case, the

expectation is mu i minus 1. So this is an equation

that you have, which is almost the

same as this one, except that you

have a plus 1 in it. And as we had discussed

before, in general this is the kind of

formula that you have. Now you can solve the system. I will let you do that. There are many ways to do this. But the solution that

you’re going to have is that mu i will be equals

to i times n minus i. This is the result. Finally what would

be the case if you didn’t have a fair game– for

example, unfair to the gambler or unfair to the casino? What we mean here is

that the probability p is different from 0.5. So here, instead of 0.5,

you have p everywhere. And here, of course,

you have 1 minus p everywhere on this side. So you have a

probability p of winning, and probability 1 minus

p of losing each bet. So you might ask the

same question– well, for the probability a of

i, you still have 0 here. You still have 1 here. The formula that you

would write here, instead of writing

it this way, it would be– you start from

here with a probability p. You end up here. And with a probability of 1

minus p, you end up there. And the expression that

you get for a of i– if you define r to be 1

minus p over p– you will see that a of i is going to be

1 minus r to the power of i over 1 minus r to the power n. And what would be the expected

amount of time she will play? Instead of that equation,

if you solve it, you would have mu of i

equals r plus 1 divided by r minus 1 times i minus

n times 1 minus r to the i divided by 1 minus

r to the power n. Because you would have here

again p, and 1 minus p here. And you can see that when p is

strictly less than one-half– in other words, it’s even

worse for this gambler– then a of i– which is

the probability of getting to this favorable

state– will also go to 0 when n goes to infinity. And in the case where p is

strictly greater than 0.5– that means that she has some

favored odd on her favor– then in that case, this number r

to the power n will go to zero. And 1 minus r of i will

represent the probability that she would become

infinitely rich. In other words, being very

greedy and n going to infinity. This will go to 0 and 1

minus r to the power of i is the probability that she

would get infinitely rich.

finally

only if the background were dark by default. my eyes are dying

Thank you for the whole serious!

This really helped thanks, if I could, I would give you some

Mon-né💰