2 General Markov Chains (September 10, 1999)

2.7 New chains from old

Consider a chain (Xt)(X_{t}) on state-space II, and fix A⊆IA\subseteq I. There are many different constructions of new chains whose state space is (exactly or roughly) just AA, and it’s important not to confuse them. Three elementary constructions are described here. Anticipating the definition of reversible from Chapter 3, it is easy to check that if the original chain is reversible then each new chain is reversible.

2.7.1 The chain watched only on AA

This is the chain (Yn)(Y_{n}) defined by

S0=TA=min⁡{t≥0:Xt∈A}S_{0}=T_{A}=\min\{t\geq 0:X_{t}\in A\}
Sn=min⁡{t>Sn-1:Xt∈A}S_{n}=\min\{t>S_{n-1}:X_{t}\in A\}
Yn=XSn.Y_{n}=X_{S_{n}}.

The chain (Yn)(Y_{n}) has state space AA and transition matrix

P¯A(i,j)=Pi(XTA=j),i,j∈A.\bar{P}_{A}(i,j)=P_{i}(X_{T_{A}}=j),\ i,j\in A.

From the ergodic theorem (Theorem 2.1) it is clear that the stationary distribution πA\pi_{A} of (Yt)(Y_{t}) is just π\pi conditioned on AA, that is

πA⁢(i)=πi/π⁢(A),  i∈A.\pi_{A}(i)=\pi_{i}/\pi(A),\ i\in A. (2.27)

2.7.2 The chain restricted to AA

This is the chain with state space AA and transition matrix P^A\hat{P}_{A} defined by

P^A⁢(i,j)\displaystyle\hat{P}_{A}(i,j) =\displaystyle= P⁢(i,j),  i,j∈A,i≠j\displaystyle P(i,j),\ i,j\in A,i\neq j
P^A⁢(i,i)\displaystyle\hat{P}_{A}(i,i) =\displaystyle= 1-∑j∈A,j≠iP⁢(i,j),  i∈A.\displaystyle 1-\sum_{j\in A,j\neq i}P(i,j),\ i\in A.

In general there is little connection between this chain and the original chain (Xt)(X_{t}), and in general it is not true that the stationary distribution is given by (2.27). However, when the original chain is reversible, it is easy to check that the restricted chain does have the stationary distribution (2.27).

2.7.3 The collapsed chain

This chain has state space I*=A∪{a}I^{*}=A\cup\{a\} where aa is a new state. We interpret the new chain as “the original chain with states AcA^{c} collapsed to a single state aa”. Warning. In later applications we switch the roles of AA and AcA^{c}, i.e. we collapse AA to a single state aa and use the collapsed chain on states I*=Ac∪{a}I^{*}=A^{c}\cup\{a\}. The collapsed chain has transition matrix

pi⁢j*\displaystyle p^{*}_{ij} =\displaystyle= pi⁢j,  i,j∈A\displaystyle p_{ij},\ i,j\in A
pi⁢a*\displaystyle p^{*}_{ia} =\displaystyle= ∑k∈Acpi⁢k,  i∈A\displaystyle\sum_{k\in A^{c}}p_{ik},\ i\in A
pa⁢i*\displaystyle p^{*}_{ai} =\displaystyle= 1π⁢(Ac)⁢∑k∈Acπk⁢pk⁢i,  i∈A\displaystyle\frac{1}{\pi(A^{c})}\sum_{k\in A^{c}}\pi_{k}p_{ki},\ i\in A
pa⁢a*\displaystyle p^{*}_{aa} =\displaystyle= 1π⁢(Ac)⁢∑k∈Ac∑l∈Acπk⁢pk⁢l.\displaystyle\frac{1}{\pi(A^{c})}\sum_{k\in A^{c}}\sum_{l\in A^{c}}\pi_{k}p_{% kl}.

The collapsed chain has stationary distribution π*\pi^{*} given by

πi*=πi,i∈A; πa*=π⁢(Ac).\pi^{*}_{i}=\pi_{i},i\in A;\ \ \pi^{*}_{a}=\pi(A^{c}).

Obviously the 𝐏{\bf P}-chain started at ii and run until TAcT_{A^{c}} is the same as the 𝐏*{\bf P}^{*}-chain started at ii and run until TaT_{a}. This leads to the general collapsing principle

To prove a result which involves the behavior of the chain only up to time TAcT_{A^{c}}, we may assume Ac{A^{c}} is a singleton.

For we may apply the singleton result to the 𝐏*{\bf P}^{*}-chain run until time TaT_{a}, and the same result will hold for the 𝐏{\bf P}-chain run until time TAcT_{A^{c}}.

It is important to realize that typically (even for reversible chains) all three constructions give different processes. Loosely, the chain restricted to AA “rebounds off the boundary of AcA^{c} where the boundary is hit”, the collapsed chain “exits AcA^{c} at a random place independent of the hitting place”, and the chain watched only on AA “rebounds at a random place dependent on the hitting place”.

Bibliography