Not a Markov Process |
Here is the classic example of a non-Markov process:
You have two red counters and one blue counter in a bag. The
sequence of states
S = {s0, s1, …, sN}
Where
sn
= the counter taken out of the bag at time n
...is NOT a Markov process.
Why not?
Because if all you know is the current state, you don’t have
enough information to give the probabilities of transitioning to each next
state.
For example, what are the transition probabilities when you have just
removed a red counter?
Well, the possibilities for the next state are:
- Drawing another red counter,
- Drawing the blue counter, or
- The bag is empty.
But the probability of drawing the other red counter depends
on whether this is the second time we have drawn one, i.e. whether the other
red counter is still in the bag. If this is the first red counter we’ve drawn,
the transition probability to drawing another red counter will be greater than
zero. If this is the second red counter we’ve drawn, the transition
probability to drawing another red counter will be zero. Same for the blue
counter or the bag being empty. How could we know whether these are possible
states to transition to just from knowing that our current state is a red
counter? There isn’t enough information, so this isn’t a Markov process.
GENIUS QUESTION
“But”, you ask, “Couldn’t we define the set of states
differently in a way that does have the Markov property? Would that make this a
Markov process?” That is an excellent question, you total genius.
Hey, I found this picture of you! |
Coincidentally,
I had the same question, which I asked in this Stack Exchange Mathematics post and will now summarize!
Why can’t we redefine the state space for the
counters-in-a-bag problem to be:
sn
= the counters remaining in the bag
Surely counters-in-a-bag would then be a Markov process,
since we would know the probability of transition to each state if we know
the current state?
The first place this thinking is wrong is in trying to
define whether ‘taking counters out of a bag’ is a Markov process. A Markov
process isn’t ever an activity – it’s a set of states that can be transitioned
through. For any randomized activity, you could define several different state
sequences to represent it, each of which may or may not be a Markov process.
For example:
sn
= the counter taken out of the bag at time n
e.g.
{RED, BLUE, RED}
sn
= the counters remaining in the bag at time
e.g.
{RED+BLUE, RED, EMPTY}
sn
= the list of all previously drawn counters
e.g.
{RED, RED+BLUE, RED+BLUE+RED}
sn
= the amount of fun and excitement you experience when drawing a counter
e.g.
{MEDIUM, NOT VERY MUCH, WOULD RATHER BE LISTENING TO GANGNAM STYLE}
No reason you can’t draw coins from a bag WHILE listening to Gangnam Style! |
So while actually getting counters and taking them out of a bag may be a raging Saturday night in the math department, it is neither a
Markov process nor a non-Markov process. This is why redefining the state space
to make 'sn' the number of counters in the bag isn’t a solution; it’s just a
different problem.
Great. Then, is the first state space we described a Markov
process? Clearly no.
What about the second one, with the state describing all
remaining counters? Technically it is, since you can give each transition
probability at each state. However, creating states that artificially include
information about previous states counts as actually including those states,
so it is definitely not a first-order Markov model, which is really the useful
one.
Processes where your states have to have a large order lose most of the
benefits of a Markov model (its simplicity). So, people assume that Markov
models should be first order, otherwise you should be representing your system
differently. The counters-in-a-bag problem can’t be represented with an order
small enough to exclude any previous states, so it’s not suited to
representation by a Markov process.
GET IT RIGHT |
No comments:
Post a Comment