# Why are these two definitions of Markov property equivalent?

## Question

Suppose that $$S$$ is a finite or a countable subset of $$\mathbb R$$ and $$(\xi_n)_{n\in\mathbb N}$$ is an $$S$$-valued sequence of random variables. Then are these two definitions of Markov property equivalent?
1. For all $$n\in\mathbb N$$ and all $$s\in S$$, $$P(\xi_{n+1}=s|\xi_0,\ldots,\xi_n)=P(\xi_{n+1}=s|\xi_n)$$.
2. For all $$n\in\mathbb N$$ and for all $$s_0,\ldots,s_{n+1}\in S$$, $$P(\xi_{n+1}=s_{n+1}|\xi_0=s_0,\ldots,\xi_n=s_n)=P(\xi_{n+1}=s_{n+1}|\xi_n=s_n)$$.

Here, $$P(A|\xi_0,\ldots,\xi_n):=P(A|\sigma(\xi_0,\ldots,\xi_n))=E(1_A|\sigma(\xi_0,\ldots,\xi_n))$$ for all $$A$$ in the given $$\sigma$$-algebra of the probability space and all random variables $$\xi_0,\ldots,\xi_n$$.

## How did I come to the question

I'm reading Brzezniak, & Zastawniak. "Basic Stochastic Processes." In the book it defines Markov chain as follows(Note that (5.10) is same as 1 in my question):

Definition Suppose that $$S$$ is a finite or a countable set. Suppose also that a probability space $$(\Omega,\mathcal F,P)$$ is given. An $$S$$-values sequence of random variables $$\xi_n$$, $$n\in\mathbb N$$, is called an $$S$$-valued Markov chain or a Markov chain on $$S$$ if for all $$n\in\mathbb N$$ and all $$s\in S$$ $$P(\xi_{n+1}=s|\xi_0,\ldots,\xi_n)=P(\xi_{n+1}=s|\xi_n).\tag{5.10}$$ Here $$P(\xi_{n+1}=s|\xi_n)$$ is the conditional probability of the event $$\{\xi_{n+1}=s\}$$ with respect to random variable $$\xi_n$$, or equivalently, with respect to the $$\sigma$$-field $$\sigma(\xi_n)$$ generated by $$\xi_n$$. Similarly, $$P(\xi_{n+1}=s|\xi_0,\ldots,\xi_n)$$ is the conditional probability of $$\{\xi_{n+1}=s\}$$ with respect to the $$\sigma$$-field $$\sigma(\xi_0,\ldots,\xi_n)$$ generated by the random variables $$\xi_0,\ldots,\xi_n$$.
Property (5.10) will usually be referred to as the Markov property of the Markov chain $$\xi_n$$, $$n\in\mathbb N$$. The set $$S$$ is called the state space and the elements of $$S$$ are called states.

But in the proof of the proposition that follows, it says:

...
A similar line of reasoning shows that $$\xi_n$$ is indeed a Markov chain. For this we need to verify that for any $$n\in\mathbb N$$ and any $$s_0,s_1,\ldots,s_{n+1}\in S$$ $$P(\xi_{n+1}=s_{n+1}|\xi_0=s_0,\ldots,\xi_n=s_n)=P(\xi_{n+1}=s_{n+1}|\xi_n=s_n).$$ ...

It's asserting that 2 in my question implies 1. It gives no proof for that. I'm pretty sure that 1 also implies 2 because if you see the 'definition' in this link: https://en.wikipedia.org/wiki/Markov_property
there is a formulation which is the same as 2.

## My attempt

I really don't see a way to start.
For 1 $$\to$$ 2, I put $$\zeta_0=P(\xi_{n+1}=s_{n+1}|\xi_0,\ldots,\xi_n)$$, $$\zeta_1=P(\xi_{n+1}=s_{n+1}|\xi_n)$$. I aslo put $$A=\{\xi_{0}=s_0\}\cap\cdots\cap\{\xi_n=s_n\}$$, $$B=\{\xi_n=s_n\}$$. I found that $$\int_A\zeta_0dP=\int_A\zeta_1dP=P(\xi_0=s_0,\ldots,\xi_{n+1}=s_{n+1})$$ and $$\int_B\zeta_0dP=\int_B\zeta_1dP=P(\xi_n=s_n,\xi_{n+1}=s_{n+1})$$. But I don't know how to continue or if this even helps.

• What is your definition of the conditional probability of an event with respect to a random variable? – saz Oct 20 '18 at 12:20
• @saz Let $(\Omega,\mathcal F,P)$ be the given probability space. Let $\mathcal G$ be a $\sigma$-algebra such that $\mathcal G\subseteq\mathcal F$ and let $A\in\mathcal F$. $P(A|\mathcal G)$ means $E(1_A|\mathcal G)$. Also, for random variables $\xi_0,\ldots,\xi_n$, $P(A|\xi_0,\ldots,\xi_n)$ means $P(A|\sigma(\xi_0,\ldots,\xi_n))$. I'll put this in the question. – zxcv Oct 20 '18 at 12:34

No, the way you stated the definitions they are not equivalent. The reasons is that there might be null sets which cause problems. For instance if $$\xi_n = \sum_{j=1}^n X_j$$ is a simple random walk, then $$(\xi_n)_{n \in \mathbb{N}}$$ satisfies the first definition but not the second one; just note that $$\mathbb{P}(\xi_2 = 2 \mid \xi_0 = 5, \xi_1 = 1) = 0 \neq \mathbb{P}(\xi_2 = 2 \mid \xi_1=1)>0.$$

It is, however, possible to show the following statement:

Theorem Let $$S$$ be a countable set and $$(\xi_n)_{n \in \mathbb{N}}$$ a sequence of $$S$$-valued random variables. Then the following statements are equivalent:

1. $$\mathbb{P}(\xi_{n+1} = s \mid \xi_0,\ldots,\xi_n) = \mathbb{P}(\xi_{n+1}= s \mid \xi_n)$$ for all $$n \in \mathbb{N}$$ and $$s \in S$$,
2. If $$n \in \mathbb{N}$$ and $$s_0,\ldots,s_n \in S$$ are such that $$\mathbb{P}(\xi_0=s_0,\ldots,\xi_n=s_n)>0$$ then $$\mathbb{P}(\xi_{n+1} = s \mid \xi_0 = s_0,\ldots,\xi_n = s_n) = \mathbb{P}(\xi_{n+1} = s \mid \xi_n = s_n) \quad \text{for all s \in S.}$$

For the proof we will use the following auxiliary statement:

Lemma Let $$U$$ be a countable set and $$Y$$ an $$U$$-valued random variable. Then $$\mathbb{P}(1_A \mid Y) = g(Y) \quad \text{a.s.} \tag{1}$$for $$g(y) := \mathbb{P}(A \mid Y=y) ´, \qquad y \in U. \tag{2}$$

In $$(2)$$, $$\mathbb{P}(A \mid Y=y)$$ denotes the classical conditional probability, i.e. $$\mathbb{P}(A \mid Y=y) = \begin{cases} \frac{\mathbb{P}(A \cap \{Y=y\})}{\mathbb{P}(Y=y)}, & \mathbb{P}(Y=y)>0, \\ 0, & \text{otherwise} \end{cases}.$$

Proof of the lemma: The random variable $$g(Y)$$ is clearly $$\sigma(Y)$$-measurable, to prove $$(1)$$ it therefore remains to show that $$\int_F 1_A \, d\mathbb{P} = \int_F g(Y) \, d\mathbb{P} \tag{3}$$ for all $$F \in \sigma(Y)$$. Since the $$\sigma$$-algebra $$\sigma(Y)$$ is generated by sets of the form $$\{Y=u\}$$, $$u \in U$$, it suffices to check $$(3)$$ for $$F=\{Y=u\}$$ with $$u \in U$$ fixed. We consider two cases separately:

• If $$u$$ is such that $$\mathbb{P}(Y=u)=0$$, i.e. $$\mathbb{P}(F)=0$$, then clearly both sides of $$(3)$$ equal to $$0$$.
• If $$u$$ is such that $$\mathbb{P}(Y=u)>0$$, then $$\int_F g(Y) \, d\mathbb{P} = \int_{\{Y=u\}} \underbrace{g(Y)}_{g(u)} \, d\mathbb{P} = g(u) \mathbb{P}(Y=u).$$ By the definition of $$g$$, we have $$g(u) = \mathbb{P}(A \mid Y=u) = \mathbb{P}(A \cap \{Y=u\})/\mathbb{P}(Y=u)$$, and so $$\int_F g(Y) \, d\mathbb{P} = \mathbb{P}(A \cap \{Y=u\}) = \int_{\{Y=u\}} 1_A \, d\mathbb{P} = \int_F 1_A \, d\mathbb{P}.$$

Proof of the theorem: Fix $$s \in S$$ and $$n \in \mathbb{N}$$. By the above lemma, we have

$$\mathbb{P}(\xi_{n+1} = s \mid \xi_0,\ldots,\xi_n) = g(\xi_0,\ldots,\xi_n) \quad \text{and} \quad \mathbb{P}(\xi_{n+1} = s \mid \xi_n) = h(\xi_n) \tag{4}$$ where \begin{align*} g(y_0,\ldots,y_n) &:= \mathbb{P}(\xi_{n+1} = s \mid \xi_0=y_0,\ldots,\xi_n=y_n)\\ h(y_n) &:= \mathbb{P}(\xi_{n+1} = s \mid \xi_n = y_n) . \end{align*}

$$1. \implies 2.$$: Let $$s_0,\ldots,s_n$$ be such that $$F:=\{\xi_0=s_0,\ldots,\xi_n = s_n\}$$ satisfies $$\mathbb{P}(F)>0$$. By assumption and $$(4)$$, we have $$g(\xi_1,\ldots,\xi_n) = \mathbb{P}(\xi_{n+1} =s \mid \xi_0,\ldots,\xi_n) = \mathbb{P}(\xi_{n+1} = s \mid \xi_n) = h(\xi_n).$$ In particula, $$1_{\{\xi_0=s_0,\ldots,\xi_n = s_n\}} g(\xi_1,\ldots,\xi_n) = 1_{\{\xi_0=s_0,\ldots,\xi_n = s_n\}} h(\xi_n),$$ i.e. $$1_{\{\xi_0=s_0,\ldots,\xi_n = s_n\}} g(s_0,\ldots,s_n) = 1_{\{\xi_0=s_0,\ldots,\xi_n = s_n\}} h(s_n).$$ Since $$\mathbb{P}(\xi_0=s_0,\ldots,\xi_n=s_n)>0$$, this is equivalent to saying that $$g(s_0,\ldots,s_n) = h(s_n);$$ by the very definition of $$g$$ and $$h$$ this yields $$\mathbb{P}(\xi_{n+1} = s \mid \xi_0=s_0,\ldots,\xi_n=s_n) = \mathbb{P}(\xi_{n+1} = s \mid \xi_n = s_n).$$

$$2. \implies 1.$$: If 2. holds then it follows from the very definition of $$g$$ and $$h$$ that $$g(y_0,\ldots,y_n) = h(y_n)$$ for all $$y_0,\ldots,y_n \in S$$ such that $$\mathbb{P}(\xi_0=y_0,\ldots,\xi_n=y_n)>0$$. Hence, $$g(\xi_0,\ldots,\xi_n) = h(\xi_n) \quad \text{a.s.}$$ which implies by $$(4)$$ that $$\mathbb{P}(\xi_{n+1} = s \mid \xi_0,\ldots,\xi_n) = \mathbb{P}(\xi_{n+1}= s \mid \xi_n) \quad \text{a.s.}$$