In this problem, we are looking at a student whose
performance from day to day sort of oscillates according
to a Markov chain.
In particular, the student can either be in state 1, which is
a state of being up to date, or in state 2, which is a
state of being kind of fallen behind.
Now, the transition probabilities between these
two states are given by the numbers here, which is 0.2
from state 1 to 2, 0.6 from 2 to 1, 0.4 from 2 back to 2,
and 0.8 from 1 back to state 1.
The quantity we're interesting calculating is this notion of
first passage time.
Let me define what that means.
Suppose we are looking at a time horizon of
time 0, 1, 2, 3.
And let's call the state of the Markov chain x of t.
Suppose we start from the chain being in state 2 here.
Now, if we look at a particular sample path, let's
say 2 and 2 again on day 1, and 2 again on day 2, and on
day 3, the student enters state 1.
So in this sample path, we start from time 0 and time 3
is the first time we enter state 1.
And we'll say that the first passage time, namely, the
first time we enter state 1 in this case, is equal to 3.
More formally, we'll define tj as the first pass the time to
state 1 conditional on that we start from state j at time 0.
Now, this quantity, of course, is random.
Depending on the realization, we have different numbers.
And we are interested in calculating the
expected value of t2.
That is, on average, if we start from state 2 here, how
long would it take for us to enter state 1?
Now to calculate this quantity, in the following
recursion will be very important.
The idea is we don't know exactly what t2 is.
But t2 has to satisfy a certain recurrent equation,
namely, t2 must be equal to 1 plus summation j
equal to 1 to 2 P2jtj.
Now let me explain what this equation means.
Let's say we are at state 2.
Well, we don't actually know how long it's going to take
for us to enter state 1.
But we do know after one step, I will be go
into some other state.
Let's call it state j.
And from state j, it's going to take some time to enter
state 1 finally.
So this equation essentially says the time for us to first
enter state 1 from 2 is 1--
which is the next step--
plus the expected time from that point on to enter 1.
So that constitutes our [? recurrent ?]
relationship.
Now, by this definition, we can see that this is simply 1
plus P21 times t1 plus P22 times t2.
Now, the definition of tj says t1 must be 0 because, by
definition, if we start from state 1, we are
already in state 1.
So the time to reach state 1 is simply 0.
So this term disappears.
And we end up with 1 plus P22 t2.
If we plug in a number of P22--
which is 0.4 right here--
we get 1 plus 0.4 t2.
Now we started from t2 and we ended up with another
expression involving numbers and only one
unknown, which is t2.
Combining this together and solving for t2, we get t2
equals 1 divided by 1 minus 0.4, which is 5/3.
And that is the answer for the first part of the problem.
In the second part of the problem, we are asked to do
something similar as before but with a slight twist.
Here, I copied over the definition for tj, which is
the first time to visit state 1 starting from state j at
time t equals 0.
And the little tj is this expectation.
And here we're going to define a similar quantity, which is
t1, let's say, star, defined as the first time to visit
state 1 again.
So that's the recurrence part starting from state 1,
1 at t equals 0.
So this is the recurrence time from state 1
back to state 1 again.
As an example, again, we look at t equals 0, 1, 2, 3, 4.
And here, if we start from state 1 on time 0, we went to
state 2, 2, 1, 1 again.
Now here, again, time 3 will be the first time to visit
state 1 after time 0.
And we don't count the very first 0.
And that will be our t1 star.
So t1 star in this particular case is equal to 3.
OK.
Same as before, we like to calculate the expected time to
revisit state 1.
Define little t1 star expected value of t1 star.
And we'll be using the same recurrence trick through the
following equation.
We say that t1 star is equal to 1 plus j from 1 to 2.
Now, since we started from state 1, this goes from 1 to
state 1j and tj.
Again, the interpretation is we started at state 1 at time
t equals 0, we went to some other state--
we call it j--
and front of state j, it goes around, and after time
expected value tj, we came back to state 1.
Here, and as before, this equation works because we are
working with a Markov chain whereby the time to reach some
other state only depends on the current state.
And that's why we're able to break down the
recursion as follows.
If we write out the recursion, we get 1 plus
P11 t1 plus P12 t2.
As before, t1 now is just the expected first passage time
from state 1.
And by definition, it is 0.
Because if we start from state 1, it's already in state 1 and
takes 0 time to get there.
So again, like before, this term goes out.
And we have 1 plus 0.2 times 5/3.
And this number came from the previous calculation of t2.
And this gives us 4/3.
So this completes the problem.
And just to remind ourselves, the kind of crux of the
problem is this type of recursion which expresses a
certain quantity in the one incremental step followed by
the expected time to reach a certain destination
after that one step.
And we can do so because the dynamics is modeled by a
Markov chain.
And hence, the time to reach a certain destination after this
first step only depends on where you start again, in this
case, state j.