Telescoping Markov chain

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In probability theory, a telescoping Markov chain (TMC) is a vector-valued stochastic process that satisfies a Markov property and admits a hierarchical format through a network of transition matrices with cascading dependence.

For any N> 1 consider the set of spaces \{\mathcal S^\ell\}_{\ell=1}^N. The hierarchical process \theta_k defined in the product-space

\theta_k = (\theta_k^1,.....,\theta_k^N)\in\mathcal S^1\times......\times\mathcal S^N

is said to be a TMC if there is a set of transition probability kernels \{\Lambda^n\}_{n=1}^N such that

(1) \theta_k^1 is a Markov chain with transition probability matrix \Lambda^1

\mathbb P(\theta_k^1=s|\theta_{k-1}^1=r)=\Lambda^1(s|r)

(2) there is a cascading dependence in every level of the hierarchy,

\mathbb P(\theta_k^n=s|\theta_{k-1}^n=r,\theta_k^{n-1}=t)=\Lambda^n(s|r,t)     for all n\geq 2.

(3) \theta_k satisfies a Markov property with a transition kernel that can be written in terms of the \Lambda's,

\mathbb P(\theta_{k+1}=\vec s|\theta_k=\vec r)=\Lambda^1(s_1|r_1)\prod_{\ell=2}^N\Lambda^\ell(s_\ell|r_\ell,s_{\ell-1})

where \vec s = (s_1,\ldots,s_N)\in\mathcal S^1\times\cdots\times\mathcal S^N and \vec r = (r_1,\ldots,r_N)\in\mathcal S^1\times\cdots\times\mathcal S^N.