What ISN’T a Markov Process?

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:

1. Drawing another red counter,
2. Drawing the blue counter, or
3. 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