1
00:00:00,000 --> 00:00:04,038
Hi, in this set of lecture we're going to
talk about Markov Models. Now Markov

2
00:00:04,038 --> 00:00:09,010
Models are really simple, they consist of
just two parts. The first thing is there's

3
00:00:09,010 --> 00:00:13,077
a set of states, so those are states that
a person's psyche could be in. They could

4
00:00:13,077 --> 00:00:18,050
be the state of a particular government or
an economy. And then there's going to be

5
00:00:18,050 --> 00:00:22,082
transition probabilities and the
transition probabilities are going to tell

6
00:00:22,082 --> 00:00:26,094
us the probability of moving from one
state to another. So remember all the

7
00:00:26,094 --> 00:00:30,088
stuff we learned about probabilities. How
they sum to one, and that sort of thing.

8
00:00:30,088 --> 00:00:34,087
All those rules are gonna apply here. But
the probabilities are gonna tell us how

9
00:00:34,087 --> 00:00:38,086
likely it is to move from, say, one state
to another. Let me give a couple examples.

10
00:00:38,086 --> 00:00:42,060
So first, let's suppose we have some
students. And those students could be in

11
00:00:42,060 --> 00:00:46,015
either one of two states. They could be
alert, or they could be bored. Now,

12
00:00:46,015 --> 00:00:50,014
there's gonna be some probability, P, that
they move from alert to bored. And maybe

13
00:00:50,014 --> 00:00:53,093
some probability Q that they move from
bored to alert. And over time, students

14
00:00:53,093 --> 00:00:57,082
are gonna be moving back and forth from
the alert state to the bored state. And

15
00:00:57,082 --> 00:01:01,084
the Markov process will give us A
framework with which to understand how

16
00:01:01,084 --> 00:01:06,002
those dynamics take place. Now, alert and bored students 
don't seem maybe that important. So let's do

17
00:01:06,002 --> 00:01:10,007
something more relevant. Let's talk about
countries being free or not free. So

18
00:01:10,007 --> 00:01:14,038
those are the two states. A country can be
free. A country can be not free. Now what

19
00:01:14,038 --> 00:01:18,063
we can do is, we can [inaudible] data [inaudible]
what's the probability that a state moves

20
00:01:18,063 --> 00:01:22,068
from free to not free, and what's the
probability that a state moves from not

21
00:01:22,068 --> 00:01:26,025
free to free? That'll also be, a
Markov process. So if we look at

22
00:01:26,025 --> 00:01:30,056
historically the number of free states and
not free states and then create a

23
00:01:30,056 --> 00:01:35,008
third category called "partly free", which is
the red line, we can see that there's these

24
00:01:35,008 --> 00:01:39,032
different trends, right? The free
states seem to be increasing. The not-free

25
00:01:39,032 --> 00:01:43,083
tend to be decreasing. What we can do is,
we can use Markov process to figure out,

26
00:01:43,083 --> 00:01:48,040
where is this process going to end up. Is
this going to end up with all free states?

27
00:01:48,040 --> 00:01:52,080
Or are we going to end up with maybe some
moderate number of free states in the

28
00:01:52,080 --> 00:01:57,026
process still churning? That's where the
model's going to help us. Now remember we

29
00:01:57,026 --> 00:02:01,066
talked about the different sorts of things
that processes can do? They can go to

30
00:02:01,066 --> 00:02:05,078
equilibria, they can be cycles, they can
be completely random, or they can be

31
00:02:05,078 --> 00:02:10,018
complex. What we're going to find, is that
as long as just a few assumptions hold,

32
00:02:10,018 --> 00:02:13,091
that Markov processes are
gonna be here: they're gonna go to

33
00:02:13,091 --> 00:02:17,068
equilibrium. And so there's a theorem
called the Markov convergence theorem.

34
00:02:17,068 --> 00:02:21,045
This Markov convergence theorem tells
us: as long as a couple really mild

35
00:02:21,045 --> 00:02:25,002
assumptions hold, namely that we have, like a
finite number of states, and those

36
00:02:25,002 --> 00:02:28,084
probabilities stay fixed. And then
one other thing, you can get from any

37
00:02:28,084 --> 00:02:32,086
position, any state, to any other state.
Then what we'll get, is the system goes to

38
00:02:32,086 --> 00:02:36,084
an equilibrium. So this is a really powerful
thing and has all sorts of implications

39
00:02:36,084 --> 00:02:41,007
that we're gonna flesh out as we look 
more deeply into the model. Now to do this, to

40
00:02:41,007 --> 00:02:45,060
understand Markov processes, we're going
to have to introduce a little bit more notation,

41
00:02:45,060 --> 00:02:49,096
another technique, another tool from the
study of models. And these are called

42
00:02:49,096 --> 00:02:54,038
matrices. So matrices are really just like
a little grid, make it two by two, or

43
00:02:54,038 --> 00:02:58,079
three by three. Where you put numbers in
here, like point four, point five, point

44
00:02:58,079 --> 00:03:02,099
six, point five. And those will be the
transition probabilities. So what we're

45
00:03:02,099 --> 00:03:07,007
gonna learn how to do, is we're going to
learn how to multiply by matrices in order

46
00:03:07,007 --> 00:03:11,020
to understand these Markov processes, and
in particular to understand how the Markov

47
00:03:11,020 --> 00:03:15,008
convergence theorem works. We'll use
these matrices to explain why these

48
00:03:15,008 --> 00:03:19,001
systems go to equilibria. Now the reason
we do Markov processes is twofold. One is,

49
00:03:19,001 --> 00:03:23,003
they're really sort of a useful
way to think about how the world works and

50
00:03:23,003 --> 00:03:27,000
we get this really powerful result, the
Markov convergence theorem that says these

51
00:03:27,000 --> 00:03:30,082
systems are going to go to these, this,
these equilibria. Any Markov process goes

52
00:03:30,082 --> 00:03:34,064
to an equilibrium. Second reason we're
going to do them, is what we talked about

53
00:03:34,064 --> 00:03:38,040
in the previous lecture, it's this idea of
exaptation. That the Markov model's

54
00:03:38,040 --> 00:03:42,015
incredibly fertile. Once we have the
Markov idea in our head, once we

55
00:03:42,015 --> 00:03:46,042
understand what a Markov process is, we
can apply it in a whole bunch of different

56
00:03:46,042 --> 00:03:51,000
settings. In fact one of my colleagues, we
give him almost anything, he'll say "that's

57
00:03:51,000 --> 00:03:55,032
a Markov process". And there's a sense in
which a lot of things are Markov processes,

58
00:03:55,032 --> 00:03:59,048
and it's often really, really useful to
think of things in the context of Markov

59
00:03:59,048 --> 00:04:03,054
processes. It's also true, once you have
this idea of transition probabilities and

60
00:04:03,054 --> 00:04:07,065
matrices we see can use those in a lot of
settings as well. Okay, so let's get

61
00:04:07,065 --> 00:04:12,017
started. I'm going to start out just by a
very, very simple Markov process, then

62
00:04:12,017 --> 00:04:16,087
what we're going to do is we're gonna look
at a slightly more complicated one and

63
00:04:16,087 --> 00:04:21,027
then see how the Markov convergence
theorem works. Once we've got all that in

64
00:04:21,027 --> 00:04:25,068
play, then we'll go back and talk about
exaptation, where we can apply other

65
00:04:25,068 --> 00:04:26,089
settings. Okay, thanks.