The strong Markov property

The subject is the strong Markov property of a Markov chain.

The strong Markov property#

Let $(X_n)_{n \ge 0}$ be a Markov chain on the probability space $(\Omega, \mathcal{F}, \mathbb{P})$ with set of states $I$ and transition matrix ${(p_{ij})_{i, j \in I}.}$ For every $n$ in ${\mathbb{N} = \{0, 1, 2, \dots\}}$ denote by $\mathcal{F}_n$ the smallest sub-$\sigma$-algebra of $\mathcal{F}$ containing the events

$$\{ X_n = i_n, \dots, X_0 = i_0 \}, \qquad i_n, \dots, i_0 \in I.$$

The $\sigma$-algebra $\mathcal{F}_n$ is made of the events for which one can say whether they occurred or not after observing the random variables ${X_0, \dots, X_n.}$ Roughly speaking, $\mathcal{F}_n$ represents the history of the Markov chain up to time ${n.}$

Definition 6.1 (Natural filtration). The family $(\mathcal{F}_n)_{n \ge 0}$ of sub-$\sigma$-algebras of $\mathcal{F}$ is called the natural filtration of the Markov chain ${(X_n)_{n \ge 0}.}$

Definition 6.2 (Stopping time). A random variable ${T \colon \Omega \to \mathbb{N} \cup \{+\infty\}}$ is a stopping time, with respect to the filtration ${(\mathcal{F}_n)_{n \ge 0},}$ if the event $\{T \le n\}$ belongs to the $\sigma$-algebra $\mathcal{F}_n$ for all ${n \ge 0.}$

In the sense of Definition 6.2, for every state $j$ the time $T_j$ of the first entrance in ${j,}$

$$T_j = \inf\{ n \ge 1 : X_n = j \} \qquad (\text{with } \inf \emptyset := +\infty),$$

is a stopping time with respect to the natural filtration $(\mathcal{F}_n)_{n \ge 0}$ because, for all ${n \ge 1,}$

$$\begin{aligned} \{T_j \le 0\} &= \emptyset, \\ \{T_j \le n\} &= \bigcup_{\nu=1}^{n} \{X_\nu = j\}. \end{aligned}$$

In a similar way, for every state $j$ the time $U_j$ of the first exit from ${j,}$ defined for every ${\omega \in \Omega}$ by

$$U_j(\omega) = \begin{cases} \min\{ n \ge 1 : X_n(\omega) \neq j \} & \text{if } X_n(\omega) \neq j \text{ for some } n \ge 1, \\ +\infty & \text{otherwise,} \end{cases}$$

is a stopping time with respect to the natural filtration $(\mathcal{F}_n)_{n \ge 0}$ because, for all ${n \ge 1,}$ we have

$$\begin{aligned} \{U_j \le 0\} &= \emptyset, \\ \{U_j \le n\} &= \bigcup_{\nu=1}^{n} \{X_\nu \neq j\}. \end{aligned}$$

The first exit from a state#

The distribution of the random variable $U_j$ can be found explicitly, and it gives an insight into the behaviour of a Markov chain.

Theorem 6.3. If ${0 < p_{jj} < 1,}$ then under $\mathbb{P}_j$ the random variable $U_j$ has geometric distribution with parameter ${1 - p_{jj}.}$ The random variable $X_{U_j}$ defined by

$$X_{U_j}(\omega) = \sum_{n \ge 1} X_n(\omega) \mathbf{1}_{\{U_j = n\}}(\omega)$$

if ${U_j(\omega) < +\infty,}$ and in an arbitrary way on the set $\{U_j = +\infty\}$ (which has probability 0), satisfies, for all ${k \neq j,}$

$$\mathbb{P}_j\{ X_{U_j} = k \} = \frac{p_{jk}}{1 - p_{jj}}.$$

Proof (complete). The distribution of $U_j$ is found by noting that

$$\mathbb{P}_j\{ U_j > n \} = \mathbb{P}_j\{ X_n = j, \dots, X_1 = j \} = (p_{jj})^n$$

for all ${n \ge 1,}$ so that

$$\mathbb{P}_j\{ U_j = n \} = \mathbb{P}_j\{ U_j > n - 1 \} - \mathbb{P}_j\{ U_j > n \} = (1 - p_{jj}) (p_{jj})^{n-1}.$$

The distribution of $X_{U_j}$ is found in a similar way, computing, for ${k \neq j,}$

$$\begin{aligned} \mathbb{P}_j\{ X_{U_j} = k \} &= \sum_{n=1}^{\infty} \mathbb{P}_j\{ X_n = k, X_{n-1} = j, \dots, X_1 = j \} \\ &= \sum_{n=1}^{\infty} p_{jk} (p_{jj})^{n-1} = \frac{p_{jk}}{1 - p_{jj}}. \end{aligned} \tag*{$\blacksquare$}$$

The Markov property implies that the distribution of $U_j$ is memoryless, and so it must be a geometric distribution.

The chain restarted at a stopping time#

Roughly speaking, the strong Markov property is the Markov property when one considers past, present and future with respect to a stopping time, not a constant time as in the usual Markov property. As a first step we prove Theorem 6.4.

Theorem 6.4. Let $(X_n)_{n \ge 0}$ be a Markov chain on a probability space $(\Omega, \mathcal{F}, \mathbb{P})$ with transition matrix $(p_{ij})_{i, j \in I}$ and let $T$ be a stopping time with respect to its natural filtration such that ${\mathbb{P}\{T < \infty\} = 1.}$ For all ${\omega \in \Omega}$ and ${n \ge 0}$ denote

$$Y_n(\omega) = \begin{cases} X_{T(\omega)+n}(\omega) & \text{if } T(\omega) < +\infty, \\ i_\infty & \text{if } T(\omega) = +\infty, \end{cases}$$

where $i_\infty$ is an arbitrary state. The collection of random variables $(Y_n)_{n \ge 0}$ is a Markov chain with the same transition matrix ${(p_{ij})_{i, j \in I}.}$

Proof (complete). First note that $Y_n$ is a random variable because, for all ${n \ge 0}$ and ${j \in I,}$ the set $\{Y_n = j\}$ is an event, that is, it belongs to ${\mathcal{F},}$ as it can be written in the form

$$\{X_{T+n} = j\} = \bigcup_{0 \le \nu < \infty} \big( \{T = \nu\} \cap \{X_{\nu+n} = j\} \big)$$

if ${j \neq i_\infty}$ and

$$\{T = +\infty\} \cup \bigg( \bigcup_{0 \le \nu < \infty} \big( \{T = \nu\} \cap \{X_{\nu+n} = i_\infty\} \big) \bigg)$$

if ${j = i_\infty.}$ Here and below, an event written with $X_T, X_{T+1}, \dots$ is contained in ${\{T < +\infty\}{:}}$ for instance, $\{X_T = i\}$ stands for ${\{T < +\infty, X_T = i\}.}$

To prove the theorem it suffices to check that, for all ${n \ge 0}$ and all finite families $(i_k)_{0 \le k \le n}$ of states such that the event ${\{Y_n = i_n, \dots, Y_0 = i_0\}}$ has strictly positive probability, and for all states ${j,}$ we have

$$\mathbb{P}\Big( \{Y_{n+1} = j\} \;\Big|\; \bigcap_{0 \le k \le n} \{Y_k = i_k\} \Big) = \mathbb{P}\{Y_{n+1} = j \mid Y_n = i_n\} = p_{i_n j}.$$

As a first step we show that

$$\mathbb{P}\{X_{T+n+1} = j, X_{T+n} = i_n, \dots, X_T = i_0\} = p_{i_n j} \, \mathbb{P}\{X_{T+n} = i_n, \dots, X_T = i_0\}.$$

To this end note that

$$\begin{aligned} &\mathbb{P}\{X_{T+n+1} = j, X_{T+n} = i_n, \dots, X_T = i_0\} \\ &\quad = \sum_{l=0}^{\infty} \mathbb{P}\{X_{T+n+1} = j, X_{T+n} = i_n, \dots, X_T = i_0, T = l\} \\ &\quad = \sum_{l=0}^{\infty} \mathbb{P}\big( \{X_{l+n+1} = j\} \mid \{X_{l+n} = i_n, X_{l+n-1} = i_{n-1}, \dots, X_l = i_0, T = l\} \big) \\ &\qquad \cdot \mathbb{P}\{X_{l+n} = i_n, X_{l+n-1} = i_{n-1}, \dots, X_l = i_0, T = l\}. \end{aligned}$$

Here a term whose conditioning event has probability 0 is read as 0. Now, if ${n \ge 1,}$ the event ${\{X_{l+n-1} = i_{n-1}, \dots, X_l = i_0, T = l\}}$ belongs to the $\sigma$-algebra ${\mathcal{F}_{l+n-1},}$ and, by the usual Markov property, we find

$$\begin{aligned} &\mathbb{P}\{X_{T+n+1} = j, X_{T+n} = i_n, \dots, X_T = i_0\} \\ &\quad = \sum_{l=0}^{\infty} \mathbb{P}\big( \{X_{l+n+1} = j\} \mid \{X_{l+n} = i_n\} \big) \\ &\qquad \cdot \mathbb{P}\{X_{l+n} = i_n, X_{l+n-1} = i_{n-1}, \dots, X_l = i_0, T = l\} \\ &\quad = p_{i_n j} \sum_{l=0}^{\infty} \mathbb{P}\{X_{l+n} = i_n, X_{l+n-1} = i_{n-1}, \dots, X_l = i_0, T = l\} \\ &\quad = p_{i_n j} \, \mathbb{P}\{X_{T+n} = i_n, X_{T+n-1} = i_{n-1}, \dots, X_T = i_0\}. \end{aligned}$$

Indeed, each event of $\mathcal{F}_{l+n-1}$ is a countable union of disjoint events ${\{X_{l+n-1} = k_{l+n-1}, \dots, X_0 = k_0\},}$ and condition (ii) of Definition 1.2 of the first post applies to each of them intersected with ${\{X_{l+n} = i_n\}.}$ The equality also holds for ${n = 0.}$ The identity ${\mathbb{P}\{Y_{n+1} = j \mid Y_n = i_n\} = p_{i_n j}}$ can be checked in the same way. $\blacksquare$

The stopped chain#

We now prove that the Markov chain ${Y = (Y_m)_{m \ge 0}}$ is also independent of its past up to a stopping time $T$ with respect to the conditional probabilities ${\mathbb{P}\{\cdot \mid X_T = i, T < +\infty\}.}$

Definition 6.5 (Stopped Markov chain). Let $(X_n)_{n \ge 0}$ be a Markov chain and $T$ a stopping time of its natural filtration. The Markov chain stopped at time $T$ is the family $X^{|T}$ of random variables $(X^{|T}_n)_{n \ge 0}$ defined by ${X^{|T}_n = X_{T \wedge n},}$ where ${T \wedge n = \min\{T, n\}.}$

Lemma 6.6. Let $(X_n)_{n \ge 0}$ be a Markov chain. For every stopping time ${T,}$ all ${m, k \ge 0,}$ all ${i, j_1, \dots, j_m \in I}$ and every event $B$ belonging to the $\sigma$-algebra $\mathcal{F}_k$ with ${\mathbb{P}(\{X_k = i\} \cap \{T = k\} \cap B) > 0,}$ we have

$$\begin{aligned} &\mathbb{P}\big( \{X_{k+m} = j_m, \dots, X_{k+1} = j_1\} \mid \{X_k = i\} \cap \{T = k\} \cap B \big) \\ &\quad = \mathbb{P}\{X_{k+m} = j_m, \dots, X_{k+1} = j_1 \mid X_k = i\}. \end{aligned}$$

Proof (complete). The finite measures $\mathbb{Q}_1$ and $\mathbb{Q}_2$ on the $\sigma$-algebra ${\mathcal{F}_k,}$ defined for every ${B \in \mathcal{F}_k}$ by

$$\begin{aligned} \mathbb{Q}_1(B) &= \mathbb{P}\big( \{X_{k+m} = j_m, \dots, X_{k+1} = j_1\} \cap \{X_k = i\} \cap \{T = k\} \cap B \big), \\ \mathbb{Q}_2(B) &= \mathbb{P}\{X_{k+m} = j_m, \dots, X_{k+1} = j_1 \mid X_k = i\} \cdot \mathbb{P}\big( \{X_k = i, T = k\} \cap B \big) \end{aligned}$$

coincide, because by the Markov property they coincide on the events of the form ${\{X_k = i_k, \dots, X_0 = i_0\},}$ which generate the $\sigma$-algebra ${\mathcal{F}_k.}$ In detail, as $\{X_k = i\} \cap \{T = k\}$ belongs to ${\mathcal{F}_k,}$ each such event $A$ is contained in it or disjoint from it, and in the first case ${\mathbb{Q}_1(A) = \mathbb{Q}_2(A)}$ is the Markov property, while in the second both vanish. Every event of $\mathcal{F}_k$ is a countable disjoint union of events ${A,}$ so ${\mathbb{Q}_1 = \mathbb{Q}_2,}$ and dividing by ${\mathbb{P}(\{X_k = i\} \cap \{T = k\} \cap B) > 0}$ gives the lemma. $\blacksquare$

Theorem 6.7. Let $T$ and ${Y = (Y_m)_{m \ge 0}}$ be as in Theorem 6.4, and let $i$ be a state with ${\mathbb{P}\{X_T = i, T < +\infty\} > 0.}$ The families of random variables $Y$ and $X^{|T}$ are independent with respect to the probability measure ${\mathbb{P}\{\cdot \mid X_T = i, T < +\infty\}.}$

Proof (complete). Write ${j_0 = i.}$ It suffices to check that, for all ${n, m > 0}$ and all states ${j_1, \dots, j_m, i_0, \dots, i_n,}$ the events ${\{Y_m = j_m, \dots, Y_1 = j_1, Y_0 = j_0\}}$ and ${\{X_{T \wedge n} = i_n, \dots, X_{T \wedge 0} = i_0\}}$ are independent. We begin by computing

$$\begin{aligned} &\mathbb{P}\{Y_m = j_m, \dots, Y_0 = j_0, X_{T \wedge n} = i_n, \dots, X_0 = i_0 \mid X_T = i\} \\ &\quad = \sum_{k \ge 0} \mathbb{P}\{X_{k+m} = j_m, \dots, X_k = i, T = k, X_{k \wedge n} = i_n, \dots, X_0 = i_0\} / \mathbb{P}\{X_T = i\} \\ &\quad = \sum_{k \ge 0} \mathbb{P}\{X_{k+m} = j_m, \dots, X_{k+1} = j_1 \mid X_k = i, T = k, X_{k \wedge n} = i_n, \dots, X_0 = i_0\} \\ &\qquad \cdot \frac{\mathbb{P}\{X_k = i, T = k, X_{k \wedge n} = i_n, \dots, X_0 = i_0\}}{\mathbb{P}\{X_T = i\}}. \end{aligned}$$

By Lemma 6.6, for all ${k \ge 0,}$ we have

$$\begin{aligned} &\mathbb{P}\{X_{k+m} = j_m, \dots, X_{k+1} = j_1 \mid X_k = i, T = k, X_{k \wedge n} = i_n, \dots, X_0 = i_0\} \\ &\quad = \mathbb{P}\{X_{k+m} = j_m, \dots, X_{k+1} = j_1 \mid X_k = i\} \\ &\quad = \mathbb{P}\{Y_m = j_m, \dots, Y_1 = j_1 \mid X_T = i\} \end{aligned}$$

because $(Y_m)_{m \ge 0}$ is a Markov chain with the same transition matrix as $(X_n)_{n \ge 0}$ and ${\{X_T = i\} = \{Y_0 = i\} \cap \{T < +\infty\}.}$ We find then

$$\begin{aligned} &\mathbb{P}\{Y_m = j_m, \dots, Y_0 = j_0, X_{T \wedge n} = i_n, \dots, X_0 = i_0 \mid X_T = i\} \\ &\quad = \mathbb{P}\{Y_m = j_m, \dots, Y_1 = j_1 \mid X_T = i\} \\ &\qquad \cdot \sum_{k \ge 0} \frac{\mathbb{P}\{X_T = i, T = k, X_{T \wedge n} = i_n, \dots, X_0 = i_0\}}{\mathbb{P}\{X_T = i\}} \\ &\quad = \mathbb{P}\{Y_m = j_m, \dots, Y_1 = j_1 \mid X_T = i\} \cdot \mathbb{P}\{X_{T \wedge n} = i_n, \dots, X_0 = i_0 \mid X_T = i\}. \end{aligned} \tag*{$\blacksquare$}$$

Visits to a recurrent state#

We can now prove that a Markov chain returns to a recurrent state $i$ infinitely many times.

Theorem 6.8. Let $i$ be a state, and let $N_i$ be the random variable with values in ${\mathbb{N} \cup \{+\infty\}}$

$$N_i = \sum_{1 \le n < \infty} \mathbf{1}_{\{X_n = i\}},$$

the number of visits in the state ${i.}$ The state $i$ is recurrent if and only if ${N_i = +\infty}$ almost surely under ${\mathbb{P}_i.}$

Proof (complete). Consider the sequence $(T_i^{(n)})_{n \ge 1}$ of stopping times inductively defined by

$$\begin{aligned} T_i^{(1)}(\omega) &= \min\{ n \ge 1 : X_n(\omega) = i \}, \\ T_i^{(n+1)}(\omega) &= \min\{ k > T_i^{(n)}(\omega) : X_k(\omega) = i \} \end{aligned}$$

(with ${\min \emptyset := +\infty}$). If $i$ is transient, the conclusion follows from Corollary 3.7, since ${\sum_{n \ge 0} p^{(n)}_{ii} < +\infty}$ for transient states.

If $i$ is recurrent, then, by Definition 3.1, the event $\{T_i^{(1)} < +\infty\}$ is $\mathbb{P}_i$-almost sure. It follows that, for all ${n > 0,}$ we have

$$\mathbb{P}_i\{N_i \ge n\} = \mathbb{P}_i\{T_i^{(n)} < +\infty\} = \mathbb{P}_i\{T_i^{(n)} < +\infty \mid T_i^{(1)} < +\infty\}.$$

Consider now the Markov chain $(Y_n)_{n \ge 0}$ restarted from ${T_i^{(1)}{:}}$

$$Y_n(\omega) = \begin{cases} X_{T_i^{(1)}(\omega)+n}(\omega) & \text{if } T_i^{(1)}(\omega) < +\infty, \\ i_\infty & \text{if } T_i^{(1)}(\omega) = +\infty, \end{cases}$$

where $i_\infty$ is an arbitrary state. Since the stopping time $T_i^{(1)}$ is $\mathbb{P}_i$-almost surely finite and the random variable $Y_0$ is $\mathbb{P}_i$-almost surely equal to ${i,}$ by Theorem 6.4 the sequences of random variables $(X_n)_{n \ge 0}$ and $(Y_n)_{n \ge 0}$ have the same distributions. Moreover, the $n$-th entrance in $i$ of $(X_n)_{n \ge 0}$ coincides with the ${(n - 1)}$-th entrance in $i$ of ${(Y_n)_{n \ge 0}.}$ Therefore we have

$$\mathbb{P}_i\{ T_i^{(n)} < +\infty \mid T_i^{(1)} < +\infty \} = \mathbb{P}_i\{ T_i^{(n-1)} < +\infty \}$$

for ${n \ge 2.}$ Recursively,

$$\mathbb{P}_i\{ N_i \ge n \} = \dots = \mathbb{P}_i\{ T_i^{(1)} < +\infty \} = 1$$

for all ${n,}$ that is, ${\mathbb{P}_i\{N_i = +\infty\} = 1.}$ $\blacksquare$