6
$\begingroup$

I feel like I'm being very dense/employing some sort of circular reasoning, but I'm having trouble understanding the Markov Property. According to Durrett (ISBN-10:1461436141), $X_n$ is a Markov chain with transition matrix $p(i,j)$ if for any $j, i, i_{n-1}, \ldots, i_0$: $$P(X_{n+1}=j \mid X_n=i, X_{n-1}=i_{n-1}, \ldots, X_0=i_0)=p(i,j)$$

It seems to me that this property can never be satisfied. For example, suppose the transition matrix:

\begin{array}{c|ccc} & a & b & c \\ \hline a & 0 & 1 & 0 \\ b & 0.5 & 0 & 0.5 \\ c & 0 & 1 & 0 \end{array}

which is graphically represented as:

markov_chain

$P(X_3=c \vert X_2=b, X_1=b)=0 \neq p(b,c)=0.5$. I can similarly do this to any chain and have every probability be equal to $0$. Is this because I'm conditioning on an event with 0 probability? Or is it because I should be saying $$\sum_{x \in \{a,b,c\}} P(X_3=c \mid X_2=b, X_1=x)=0.5=p(b,c)$$

Or am I just thinking about it completely wrong?

$\endgroup$
5
  • 1
    $\begingroup$ Your beef is with elementary conditioning, not the Markov property. How do you define P(A|B) when P(B)=0? In your question, you seem to assume that, then, P(A|B)=0, why? $\endgroup$
    – Did
    Commented Mar 1, 2015 at 18:19
  • $\begingroup$ ah yes, that seems to be the flaw...I realized that I was dividing by zero, but assigned $P(X_3=c \vert X_2=b, X_1=b)$ a value of 0. Thanks! $\endgroup$
    – lycus
    Commented Mar 1, 2015 at 18:21
  • $\begingroup$ @lycus Yes, impossible conditions can't be thought of that way - conditions just change the $\mathbb{P}$ measure rather than really the event it's considering $\endgroup$ Commented Mar 2, 2015 at 0:42
  • $\begingroup$ I answered your question. In short, to let the Markov property work the sample path ${X_3 =c, X_2=b, X_1=b}$ should be undefined. If you define this sample path, the property doesn't hold as you pointed out. If you have any questions, just ask. $\endgroup$
    – Pedro
    Commented Mar 5, 2015 at 3:52
  • 1
    $\begingroup$ In the book "Markov chains and mixing times" by Levin, Peres & Wilmer, they explicitly mention in their definition of the Markov property that the event encoding the previous states of your chain must have positive measure. $\endgroup$
    – sourisse
    Commented Mar 5, 2015 at 4:24

1 Answer 1

2
$\begingroup$

This is a very good question and it should deserve a lot more upvotes.

To answer your question I need to go a little bit probability theory theoretical. The invalid combinations you give are not members of the sample space $\Omega$. So you cannot condition on them, since they are not a member of our set of possible outcomes (also called sample paths). Why are they not a member of the set of possible outcomes? Since we just chose them not to be valid outcomes to let our markov property work. If you chose them to be a member of the sample space, then the Markov property doesn't work as you pointed out nicely.

So we just define our Markov property on a sample space $\Omega$ which does not include invalid outcomes. Something that is not a subset of the sample space is something you can't condition on. Remember, conditioning is taking subsets.

How does our desired sample space look like? Well, all valid sequences of a certain length of random variables $X_n$ are members of the sample space for that length $n$. (We need to define a sample space for each sequence length of random variables, so we have a lot of sample spaces in fact and we just use the sample space of the correct length when asking probabilities in that sample space with our probability measure). And for each of these sample spaces, we can find ask the probability of something in our sample space with our probability measure P. We can ask for instance in the sample space of sequences of length 3 the measure of $P(X_3 = c | X_2 =b, X_1 = a)$.

So we need define a sample spaces for every sequence length we want to find probability measures of. And every time this sample space contains all possible combinations of paths up to that length.

You could say that the probability of $P(X_3 = c|X_2 = b,X_1 = x)$ is undefined in the sample space of length 3 for which the markov property holds.

$\endgroup$
9
  • $\begingroup$ To restrict Omega to sequences of positive probability (that you call "valid" sequences) leads to awfully complicated sample spaces and is never the choice made. Rather, one goes for the simplest possible sample space (typically, $S^\mathbb N$ with $S$ the state space) and one plays with the probability measure on it. "We need to define a sample space for each sequence length of random variables, so we have a lot of sample spaces in fact and we just use the sample space of the correct length..." Actually, the opposite holds. $\endgroup$
    – Did
    Commented Mar 7, 2015 at 11:43
  • $\begingroup$ Product spaces are generally acknowledged to be easier to visualize than convoluted parts of product ones, hence it seems that visualization considerations point to the theoretically correct option, not the one you present. More annoyingly, you present the peculiar approach developed in your post as the canonical one and this is just not the case. $\endgroup$
    – Did
    Commented Mar 8, 2015 at 10:23
  • $\begingroup$ ((Funny: The detailed comment by the OP that my last comment addresses, disappeared while I was typing mine. Curious minds may try to guess the content of the missing comment from mine.)) $\endgroup$
    – Did
    Commented Mar 8, 2015 at 10:24
  • $\begingroup$ I think it is better that you answer the question then. Maybe you know more about the subject than me, I tried to bring over what I know as clear as possible. Could be you know more than me, but really: no offense. Maybe I can learn from you too then. $\endgroup$
    – Pedro
    Commented Mar 8, 2015 at 10:28
  • $\begingroup$ Since the OP accepted your answer, I see little point to do that. But I am curious: where did you pick the "one specific (non product) sample space for each sequence length" idea from? $\endgroup$
    – Did
    Commented Mar 8, 2015 at 10:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .