Block Markov Chains on Trees

Markov random fields (MRFs) on lattice have become standard tools in several branches of science and technology including computer science, machine learning, graphical models, statistical physics. Namely, MRFs are known to provide pertinent models for interacting particles systems in statistical mechanics.
We notice that MRFs were introduced by Dobrushin in [?] for the multi-dimensional integer lattice, and developed then on trees [?], [?], [?]. QMFs consist multi-dimensional extensions of Markov chains [?] but with a deeper Markovian structure. In, fact even in the one dimensional case MRFs were shown to be distinct from MCs [?].

MRFs play a crucial role in many areas such as computer science, image recognition, graphical models, psychology and in an increasing number of biological and neurological models. The reader is referred to [?], [?], [?] and the references cited therein for further applications.
In the present paper we introduce the notion of block Markov chains indexed by the vertex-set of a rooted tree $T=(V,E)$. The definition of this notion is quite natural. Since in the one-dimensional case $V=\mathbf{N}_{0}$ with distinguished vertex (root) $"o=0"$, a Markov chain $(Z_{n})_{n\in\mathbf{N}}$ with (finite) state space $\Xi$ is defined through the well known Markov property

$$\mathbf{P}[Z_{n+1}=\xi_{n+1}\,\mid\,Z_{n}=\xi_{n},\cdots,Z_{0}=\xi_{0}]=\mathbf{P}[Z_{n+1}=\xi_{n+1}\,\mid\,Z_{n}=\xi_{n}].$$

The above property can be reformulated by means of the joined probability measure $\mu$ on $\Xi^{V}$ of the process $(Z_{u})_{u\in V}$ as follows

$$\mu[\xi(.)\,\,\hbox{on}\,\,S(x)\,\mid\,\xi(.)\,\,\hbox{on}\,\,V\setminus T^{{}^{\prime}}(x))]=\mu[\xi(.)\,\,\hbox{on}\,\,S_{(}x)\,\mid\,\,\xi(x)]$$

(1.1)

where $S(x)=\{x+1\}$ is the set of successors of the site $x\in V$ and $T^{\prime}(x)=\{x+1,x+2,\cdots\}$ it the set of successive descendants of the vertex $x$ w.r.t. the considered root $o$. We emphasize a suitable natural generalization of the sets $S(x)$ and $T(x)$ for general trees. Roughly speaking, a BMC is a probability measure on $\Omega:=\Xi^{V}$ satisfying the Markov property (1.1) for a fixed root.
The main purpose of this paper is to clarify the structure of BMCs in connection with MCs and MRFs. Mainly, we show that a probability measure which is BMC for every root $o\in V$ is a MC in the sense of [?]. The correlation functions of BMCs are different from those of MCs and MRFs. Consequently, their Markov structure are also different. Namely, it turns out that some conditional independence conditions are necessary on a MC on the considered tree to be BMC.
On the other hand we show that in the one-dimensional case, the notions of MCs and QMCs coincide. This coincidence Makes BMCs strictly a sub-class of MRFs in the one dimensional case. However, we emphasize that a slight modification of the one-dimensional lattice leads to a counter-examples that confirms the huge difference between MCs and BMCs over multi-dimensional trees.
We notice that the natural hierarchical structure of rooted trees, due to the absence of loops, plays a crucial role in the mere definition of BMCs. Therefore, the results are no longer available on general graphs. We forecast that BMCs will play a crucial role in connection with Gibbs measures on trees and their associated phenomena of phase transitions (see [?], [?] and [?]). Namely, phenomena of phase transitions were associated with interesting p-adic models such as the Potts model and the Ising–Vannimenus model [?], [?]. In fact, a work under preparation is dedicated to the clarification of a bridge between BMCs and some p-adic models.
In [?], [?] we clarified the structure of quantum Markov states on a quasi-local algebra $\mathcal{A}$ trees in terms of classical Markovian measure and Gibbs measures on the spectrum of a maximal abelian subalgebra. We stress that this classical Markovian measure is indeed a BMC. This will makes a new bridge between classical and quantum Markov fields.
Let us mention the outlines of the paper. Section 2. is devoted to some notions and notions on rooted trees. In section 3., we recall the basic definition of MC and MRF on graphs. Section 4. is devoted to definition of BMCs as far as its correlation functions. Section 5. is dedicated to results related to the connection of BMCs with MCs and MRFs on trees. In section 6. we deal with the one-dimensional case for which the vertex set is the classical 1D integer lattice $\mathbf{Z}$ occupied with its natural tree structure. In section 7. we develop a counter-example for a BMC which is not a MC.

Recall that [?] a tree is a connected graph with no cycles, i.e. a connected graph which becomes disconnected when each one of its edges is removed.
Let be given an infinite tree $T=(V,E)$. First, we fix any vertex $o=x_{0}\in V$ as a ”root”. Recall that two vertices $x$ and $y$ are said to be nearest neighborsand we denote $x\sim y$ if they are joined through an edge (i.e. $<x,y>\in E$). A list of the vertices $x\sim x_{1}\sim\dots\sim x_{d-1}\sim y$ is called a path from the site $x$ to the site $y$. The distance $d(x,y)$ on the tree is the length of the shortest path from $x$ to $y$.
For $x\in V$, its direct successors (children) is defined by

$$S^{o}(x):=\left\{y\in V\,\,:\,\,x\sim y\,\,\hbox{and}\,\,d(y,o)>d(x,o)\right\}$$

(2.2)

and its $k^{th}$ successors w.r.t. the root $o$ is defined by induction as follows

$$S_{1}^{o}(x):=S^{o}(x);$$

$$S^{o}_{k+1}(x)=S^{o}(S^{o}_{k}(x)),\,\,\forall k\geq 1.$$

The ”future” w.r.t. the vertex $x$ is defined by:

$$S^{o}_{[m,n]}(x)=\bigcup_{k=m}^{n}S^{o}_{k}(x);\quad T_{o}(x)=\bigcup_{k\geq 1}S^{o}_{k}(x);\quad T_{o}^{{}^{\prime}}(x)=T(x)\setminus\{x\}.$$

(2.3)

Note that in the homogeneous case, for which $|S_{o}(x)|=k$ is constant, the graph $T$ is the semi-infinite Cayley tree $\Gamma^{k}_{+}$ of order $k$. Namely, for $k=1$, the graph is reduced to the one-dimensional integer lattice $\mathbf{Z}$.
Consider the map $r$ from $V$ into itself characterized by

$$r(o)=o,$$

$$r(y)=x\quad\hbox{if}\quad y\in S^{o}(x)$$

Let $x\in V$. If $n=d(x,o)$ then

$$o=r^{n}(x)=x_{0}\sim r^{n-1}(x)\sim\cdots\sim r(x)\sim r^{0}(x)=x$$

(2.4)

is the minimal edge-path joining the root $o$ to the vertex $x$, where $r^{k}=\underbrace{r\circ\cdots\circ r}_{k\,\,times}$.
The set

$$R^{o}(x):=\{r(x),r^{2}(x),\cdots,r^{n}(x)=o\}$$

(2.5)

represents the ”past” of the vertex $x$ for the root $o$
The set of nearest-neighbors vertices of $x$ is given as follows:

$$N_{x}=\{y\in V\,\,:\,\,x\sim y\}$$

(2.6)

It is clear that $N_{x}=\{r(x)\}\cup S^{o}(x)$.

In the sequel, the tree $T$ is assumed to be locally finite, i.e. $|N_{x}|<\infty$ for each $x\in V$, in this case the integer $d_{x}:=|N_{x}|$ is called degree of $x$.
The tree can be regarded as growing (upward) away from its fixed root $o$. Each vertex $x\in V$ then has branches leading to its ”children”, which are represented here by $Sô(x)$ and $T^{{}^{\prime}}_{o}(x)$. With the possibility of leaves, that is, vertices $x$ without children i.e. $S(x)=\mathchoice{\mbox{\normalsize\rm\O}}{\mbox{\normalsize\rm\O}}{\mbox{\rm\O}}{\mbox{\rm\O}}$.

Let $\Xi=\{1,\cdots,q\}$. By a stochastic process we mean a family of random variables $(Z_{u})_{u\in V}$ defined on a probability space $(\Omega,\mathcal{F},\mathbf{P})$ and valued in a finite set $\Xi:=\{1,2,\cdots,q\}$. The process $(Z_{u})_{u\in V}$ is defined through its joined probability measure $\mu$ on the Borel space $(\Xi^{V},\mathcal{B})$ where $\mathcal{B}_{V}$ is the cylindrical $\sigma$-algebra, which is generated by the cylinder sets of the following form

$$C(a_{x},\;x\in\Lambda)=\left\{\xi\in\Xi^{V}\,\,:\,\,\xi(x)=a_{x},\,\,\forall x\in\Lambda\right\}$$

(3.7)

where $\Lambda\subset V$ finite and $(a_{x})_{x\in\Lambda}\in\Xi^{|\Lambda|}$. For the sake of shortness we denote $\Omega$ instead of $\Omega_{V}$ and $\mathcal{B}$ instead of $\mathcal{B}_{V}$. For $\Lambda\subset V$, we denote $\Omega_{\Lambda}=\Xi^{\Lambda}$. Recall that

$$\mu\left[\xi(.)\,\,\hbox{on}\,\,\Lambda\right]=\mathbf{P}\left[\bigcap_{u\in\Lambda}(Z_{u}=\xi(u))\right]$$

(3.8)

where $\xi\in\Omega_{\Lambda}$.
The conditional probability is defined as follows

$$\mu\left[\xi(.)\,\,\hbox{on}\,\,\Lambda\,\,\mid\,\,\xi(.)\,\,\hbox{on}\,\,\Lambda^{{}^{\prime}}\right]=\frac{\mu\left[\xi(.)\,\,\hbox{on}\,\,\Lambda\cup\Lambda^{{}^{\prime}}\right]}{\mu\left[\xi(.)\,\,\hbox{on}\,\,\Lambda^{{}^{\prime}}\right]}$$

(3.9)

where $\Lambda,\Lambda^{{}^{\prime}}\subseteq V$ and $\xi\in\Xi^{V}$ such that

$$\mu\left[\xi(.)\,\,\hbox{on}\,\,\Lambda^{{}^{\prime}}\right]>0.$$

Denoting

$$\mathcal{F}_{u}:=\sigma(Z_{u})\,\,;\,\,\mathcal{F}_{\Lambda}=\sigma\left(Z_{u}\,\,;\,\,u\in\Lambda\right)$$

(3.10)

the $\sigma$-algebra generated by $Z_{u}$ and $(Z_{v},\,v\in\Lambda),$ respectively.

The conditional probabilities (3.11) are assumed to be invariant under graph isomorphism.

In what follows, a root $o$ for the tree $T=(V,E)$ is fixed. For each $n\in\mathbf{N}$, we denote $\Lambda_{n}:=S_{n}^{o}(o)$ the set of vertices whose distance to the root $o$ equals $n$. Let $\Lambda_{n]}=S_{[0,n]}^{o}(o)=\bigcup_{k=0}^{n}\Lambda_{k}$. For the sake of shortness, when confusion seems impossible we will use the notations $S(x),\,T(x),T^{{}^{\prime}}$ and $r(x)$ instead of $S_{o}(x),\,T_{o}(x),T_{o}^{{}^{\prime}}(x)$ and $r_{o}(x)$, respectively.

Let us set a random enumeration for elements of $\Lambda_{n}$ as follows

$\displaystyle{\Lambda_{n}}:=\left(x^{(1)}_{\Lambda_{n}},x^{(2)}_{\Lambda_{n}},\cdots,x^{(|\Lambda_{n}|)}_{\Lambda_{n}}\right)$

where $|\Lambda_{n}|$ denotes the cardinality of $\Lambda_{n}$.

In [?] a triplet of $\sigma$-algebras $(\mathcal{F}_{1},\,\mathcal{F}_{2},\,\mathcal{F}_{3})$ such that

$$\mathbf{P}(A\,\mid\,\mathcal{F}_{1}\vee\mathcal{F}_{2})=\mathbf{P}(A\,\mid\,\mathcal{F}_{2}),\quad\forall A\in\mathcal{F}_{3}$$

(4.14)

was referred as Markov triple. In these notations (4.13) means that $(\mathcal{F}_{S(x)},\,\mathcal{F}_{V\setminus T(x)},\,\mathcal{F}_{x})$ is a Markov triple.

The following elementary formula for conditional probabilities will be used frequently in the sequel.

$$\mathbf{P}(A\cap B\mid C)=\mathbf{P}(A\mid B\cap C)\mathbf{P}(B\mid C).$$

(4.15)

Let $\mu$ is an $o$-BMC. According to (4.15), we have

	$\displaystyle\mu[\xi(.)\,\hbox{on}\,\Lambda_{n]}]$	$\displaystyle=$	$\displaystyle\mu[\xi(.)\,\hbox{on}\,\Lambda_{n}\,\mid\,\xi(.)\,\hbox{on}\,\Lambda_{n-1]}]\times\mu[\xi(.)\,\hbox{on}\,\Lambda_{n-1]}]$
		$\displaystyle=$	$\displaystyle\mu[\xi(.)\,\hbox{on}\,\Lambda_{0}]\prod_{k=0}^{n-1}\mu[\xi(.)\,\hbox{on}\,\Lambda_{k+1}\,\mid\,\xi(.)\,\hbox{on}\,\Lambda_{k]}].$

For $k=1,\cdots,n-1$, the same reason as above implies that

$$\mu[\xi(.)\,\hbox{on}\,\Lambda_{k+1}\,\mid\,\xi(.)\,\hbox{on}\,\Lambda_{k]}]=\prod_{j=1}^{|\Lambda_{k}|}\mu\bigl{[}\xi(.)\,\hbox{on}\,S(x_{\Lambda_{k}}^{(j)})\,\mid\,\xi(.)\,\hbox{on}\,\Lambda_{n-1]}\cup\bigcup_{i=j+1}^{|\Lambda_{k}|}S(x_{\Lambda_{k}}^{(i)})\bigr{]}.$$

Since $x_{\Lambda_{k}}^{(i)}\in\Lambda_{n-1]}\cup\bigcup_{i=j+1}^{|\Lambda_{k}|}S(x_{\Lambda_{k}}^{(i)})\subset V\setminus T^{{}^{\prime}}(x_{\Lambda_{k}}^{(i)})$ then the block Markov property (4.13) leads to

$$\mu\bigl{[}\xi(.)\,\hbox{on}\,S(x_{\Lambda_{k}}^{(j)})\,\mid\,\xi(.)\,\hbox{on}\,\Lambda_{n-1]}\cup\bigcup_{i=j+1}^{|\Lambda_{k}|}S(x_{\Lambda_{k}}^{(i)})\bigr{]}=\mu\bigl{[}\xi(.)\,\hbox{on}\,S(x_{\Lambda_{k}}^{(j)})\,\mid\,\xi(x_{\Lambda_{k}}^{(j)})\bigr{]}.$$

Therefore

$$\mu[\xi(.)\,\hbox{on}\,\Lambda_{n]}]=\mu[\xi(o)]\prod_{k=0}^{n-1}\prod_{x\in\Lambda_{k}}\mu\bigl{[}\xi(.)\,\hbox{on}\,S(x)\,\mid\,\xi(x)\bigr{]}.$$

(4.16)

The following theorem extends the local Markov property (4.13) to a global one, which concerns the conditional independence of the $\sigma$-algebras $\mathcal{F}_{T(x)}$ and $\mathcal{F}_{V\setminus T^{{}^{\prime}}(x)}$ given $\mathcal{F}_{x}$.

Proof. If $T^{{}^{\prime}}(x)=\mathchoice{\mbox{\normalsize\rm\O}}{\mbox{\normalsize\rm\O}}{\mbox{\rm\O}}{\mbox{\rm\O}}$ then (4.17) holds true.
We will proceed by induction on $S_{\left[1,n\right]}(x):=\bigcup_{k=1}^{n}S_{k}(x)$. One has

$$\mu\left[\xi(.)\,\,\hbox{on}\,\,S_{\left[1,n+1\right]}(x)\,\,\big{|}\,\,\xi(.)\,\,\hbox{on}\,\,V\setminus T^{{}^{\prime}}(x)\right]$$

$$=\mu\left[\xi(.)\,\,\hbox{on}\,\,S_{n+1}(x)\,\,\big{|}\,\,\xi(.)\,\,\hbox{on}\,\,S_{\left[1,n\right]}(x)\cup V\setminus T^{{}^{\prime}}(x)\right]$$

$$\times\mu\left[\xi(.)\,\,\hbox{on}\,\,S_{\left[1,n\right]}(x)\,\,\big{|}\,\,\xi(.)\,\,\hbox{on}\,\,V\setminus T^{{}^{\prime}}(x)\right].$$

Denoting $S_{n}(x)=\{x_{1}^{(n)},\cdots,x^{(n)}_{|S_{n}(x)|}\}$, one has

$$\mu\left[\xi(.)\,\,\hbox{on}\,\,S_{n+1}(x)\,\,\big{|}\,\,\xi(.)\,\,\hbox{on}\,\,S_{\left[1,n\right]}(x)\cup V\setminus T^{{}^{\prime}}(x)\right]$$

$$=\prod_{i=1}^{|S_{n}(x)|}\mu\left[\xi(.)\,\,\hbox{on}\,\,S(x_{i}^{(n)})\,\,\big{|}\,\,\xi(.)\,\,\hbox{on}\,\,(\bigcup_{k=i+1}^{n}S(x_{k}^{(n)}))\cup S_{\left[1,n\right]}(x)\cup V\setminus T^{{}^{\prime}}(x)\right].$$

From (4.13), one gets

$$\mu\left[\xi(.)\,\,\hbox{on}\,\,S(x_{i}^{(n)})\,\,\big{|}\,\,\xi(.)\,\,\hbox{on}\,\,(\bigcup_{k=i+1}^{n}S(x_{k}^{(n)}))\cup S_{\left[1,n\right]}(x)\cup V\setminus T^{{}^{\prime}}(x)\right]$$

$$=\mu\left[\xi(.)\,\,\hbox{on}\,\,S(x_{i}^{(n)})\,\,\big{|}\,\,\xi(x_{i}^{(n)})\right].$$

Thus

$$\mu\left[\xi(.)\,\,\hbox{on}\,\,S_{n+1}(x)\,\,\big{|}\,\,\xi(.)\,\,\hbox{on}\,\,S_{\left[1,n\right]}(x)\cup V\setminus T^{{}^{\prime}}(x)\right]$$

$$=\prod_{i=1}^{|S^{(n)}(x)|}\mu\left[\xi(.)\,\,\hbox{on}\,\,S(x_{i}^{(n)})\,\,\big{|}\,\,\xi(x_{i}^{(n)})\right].$$

Using the same argument as above , we obtain

$$\mu\left[\xi(.)\,\,\hbox{on}\,\,S_{n+1}(x)\,\,\big{|}\,\,\xi(.)\,\,\hbox{on}\,\,S_{\left[1,n\right]}(x)\right]$$

(4.18)

$$=\prod_{i=1}^{|S_{n}(x)|}\mu\left[\xi(.)\,\,\hbox{on}\,\,S(x_{i}^{(n)})\,\,\big{|}\,\,\xi(x_{i}^{(n)})\right].$$

On the other hand, the induction’s hypthesis leads to

$$\mu\left[\xi(.)\,\,\hbox{on}\,\,S_{[1,n]}(x)\,\,\big{|}\,\,\xi(.)\,\,\hbox{on}\,\,V\setminus T^{{}^{\prime}}(x)\right]=\mu\left[\xi(.)\,\,\hbox{on}\,\,S_{[1,n]}(x)\,\,\big{|}\,\,\xi(x)\right].$$

Therefore

$$\mu\left[\xi(.)\,\,\hbox{on}\,\,S_{[1,n+1]}(x)\,\,\big{|}\,\,\xi(.)\,\,\hbox{on}\,\,V\setminus T^{{}^{\prime}}(x)\right]$$

$$=\mu\left[\xi(.)\,\,\hbox{on}\,\,S_{n+1}(x)\,\,\big{|}\,\,\xi(.)\,\,\hbox{on}\,\,S_{\left[1,n\right]}(x)\right]\times\mu\left[\xi(.)\,\,\hbox{on}\,\,S_{[1,n]}(x)\,\,\big{|}\,\,\xi(x)\right]$$

$$=\mu\left[\xi(.)\,\,\hbox{on}\,\,S_{[1,n+1]}(x)\,\,\big{|}\,\,\xi(x)\right].$$

Finally, one finds

			$\displaystyle\mu\left[\xi(.)\,\,\hbox{on}\,\,T^{{}^{\prime}}(x)\,\,\big{|}\,\,\xi(.)\,\,\hbox{on}\,\,V\setminus T^{{}^{\prime}}(x)\right]$
		$\displaystyle=$	$\displaystyle\lim_{n\to[1,\infty)}\mu\left[\xi(.)\,\,\hbox{on}\,\,S_{[1,n+1]}(x)\,\,\big{|}\,\,\xi(.)\,\,\hbox{on}\,\,V\setminus T^{{}^{\prime}}(x)\right];$
		$\displaystyle=$	$\displaystyle\lim_{n\to[1,\infty)}\mu\left[\xi(.)\,\,\hbox{on}\,\,S_{[1,n+1]}(x)\,\,\big{|}\,\,\xi(x)\right];$
		$\displaystyle=$	$\displaystyle\mu\left[\xi(.)\,\,\hbox{on}\,\,T^{{}^{\prime}}(x)\,\,\big{|}\,\,\xi(x)\right].$

Proof. From Theorem 1, for each $\xi^{\prime}\in\Omega_{T^{{}^{\prime}}(x)\setminus\Lambda}$

$$\mu\left[\xi(.)\,\,\hbox{on}\,\,\Lambda,\,\,\xi^{{}^{\prime}}(.)\,\,\hbox{on}\,\,T^{{}^{\prime}}(x)\setminus\Lambda\,\,\big{|}\,\,\xi(.)\,\hbox{on}\,\,V\setminus T^{{}^{\prime}}(x)\right]$$

$$=\mu\left[\xi(.)\,\,\hbox{on}\,\,\Lambda,\,\,\xi^{{}^{\prime}}(.)\,\,\hbox{on}\,\,T^{{}^{\prime}}(x)\setminus\Lambda\,\,\big{|}\,\,\xi(x)\right].$$

Summing up on ${\xi^{\prime}\in\Omega_{T^{{}^{\prime}}(x)\setminus\Lambda}}$, one finds (4.19).
The following result proposes a multi-dimensional analogue of the Chapmann-Kolmogorov equation.

Proof. For each $\xi^{{}^{\prime}}\in\Omega_{S_{n}(x)}$, using the same reason as in (4.18), we get

$$\mu\left[\xi(.)\,\,\hbox{on}\,\,S_{n+m}(x)\,\,\big{|}\xi^{{}^{\prime}}(.)\,\,\hbox{on}\,\,S_{n}(x)\,\,\right]$$

$$=\mu\left[\xi(.)\,\,\hbox{on}\,\,S_{n+m}(x)\,\,\big{|}\xi^{{}^{\prime}}(.)\,\,\hbox{on}\,\,S_{n}(x)\,,\,\xi(x)\,\right].$$

Then

$$\mu\left[\xi(.)\,\,\hbox{on}\,\,S_{n+m}(x)\,\,\big{|}\xi^{{}^{\prime}}(.)\,\,\hbox{on}\,\,S_{n}(x)\,\,\right]\times\mu\left[\xi^{{}^{\prime}}(.)\,\,\hbox{on}\,\,S_{n}(x)\,\,\big{|}\,\,\xi(x)\,\,\right]$$

$$=\left[\xi(.)\,\,\hbox{on}\,\,S_{n+m}(x)\,,\,\xi^{{}^{\prime}}(.)\,\,\hbox{on}\,\,S_{n}(x)\,\,\big{|}\,\,\xi(x)\,\,\right].$$

Summing up, one gets (4.20).

Proof. First, we see that if $y\in T^{{}^{\prime}}(x)$ then $T^{{}^{\prime}}(y)\subseteq T^{{}^{\prime}}(x)$. This implies that for each $y\in V\setminus T^{{}^{\prime}}(x)$ is connected, the set of its roots $\{r^{k}(y),\,k=0,\cdots\}$ ( defined in (2.4)) is disjoint of the set $T^{{}^{\prime}}(x)$. Then the path $y\sim r(y)\sim\cdots\sim o$ is in $V\setminus T^{{}^{\prime}}(x)$. Therefore, the subgraph whose vertex set $V\setminus T^{{}^{\prime}}(x)$ is connected. Since every element of $S(x)$ is joined to $x$, we conclude that the subgraph $(\Lambda\cup(V\setminus T^{{}^{\prime}}(x)),\sim)$ is connected. Taking into account that the fact that every connected subgraph of a tree is a subtree, the proof is complete.

Proof. First let us write $S(x):=\{y_{1},y_{2},\cdots,y_{|S(x)|}\}$. According to (4.15), we have

$$\mu\left[\xi(.)\,\,\hbox{on}\;S(x)\,\,\big{|}\,\,\xi(.)\,\,\hbox{on}\;V\setminus T^{{}^{\prime}}(x)\right]$$

$$=\prod_{k=1}^{|S(x)|}\mu\left[\xi(y_{k})\,\,\mid\,\,\xi(.)\,\,\hbox{on}\;(V\setminus T^{{}^{\prime}}(x))\cup\{y_{k+1},\cdots,y_{n}\}\right].$$

By Lemma 1 the subgraph of $T$ whose set of vertices is $V^{{}^{\prime}}:=(V\setminus T^{{}^{\prime}}(x))\cup\{y_{k+1},\cdots,y_{n}\}$ is a tree. Then

			$\displaystyle\prod_{k=1}^{|S(x)|}\mu\left[\xi(y_{k})\,\,\mid\,\,\xi(.)\,\,\hbox{on}\;(V\setminus T^{{}^{\prime}}(x))\cup\{y_{k+1},\cdots,y_{n}\}\right]$
		$\displaystyle=$	$\displaystyle\prod_{k=1}^{|S(x)|}\mu\left[\xi(y_{k})\,\,\mid\,\,\xi(.)\,\,\hbox{on}\;(V\setminus\{y_{k}\})\cap V^{{}^{\prime}}\right]$
		$\displaystyle=$	$\displaystyle\prod_{k=1}^{|S(x)|}\mu\left[\xi(y_{k})\,\,\mid\,\,\xi(.)\,\,\hbox{on}\;N_{y_{k}}\cap V^{{}^{\prime}}\right].$

where the last equality derives from the fact that $\mu$ is a Markov chain in the sense of Definition. 2. Since $N_{y_{k}}\cap V^{{}^{\prime}}=\{x\}$, we get (5.21). For the second part of the proof, the conditional independence of $\mathcal{F}_{y}:=\sigma(Z_{y}),y\in S(x)$ leads to

$$\prod_{k=1}^{|S(x)|}\mu\left[\xi(y)\,\,\mid\,\,\xi(x)\right]=\mu\left[\xi(.)\,\,\hbox{on}\;S(x)\,\mid\,\,\xi(x)\right].$$

Hence, (5.21) leads to (4.17). Therefore $\mu$ is a o-block Markov chain, for any root $o\in V$. This achieves the proof.

Proof. Since $x\notin\Lambda$, then according to (4.17) one gets

	$\displaystyle\mu\left[\xi(x)\,\,\big{|}\,\,\xi(.)\,\,\hbox{on}\,\,\Lambda\right]$	$\displaystyle=$	$\displaystyle\frac{\mu\left[\xi(x)\,;\,\,\xi(.)\,\,\hbox{on}\,\,\Lambda\cap T^{{}^{\prime}}(x)\,;\;\xi(.)\,\,\hbox{on}\,\,\Lambda\setminus T^{{}^{\prime}}(x)\right]}{\mu\left[\xi(.)\,\,\hbox{on}\,\,\Lambda\cap T^{{}^{\prime}}(x)\,;\,\,\xi(.)\,\,\hbox{on}\,\,\Lambda\setminus T^{{}^{\prime}}(x)\right]},$
		$\displaystyle=$	$\displaystyle\frac{\mu\left[\xi(.)\,\,\hbox{on}\,\,\Lambda\cap T^{{}^{\prime}}(x)\,\,\big{|}\,\,\xi(x)\right]\mu\left[\xi(x)\,\,\big{|}\,\,\xi(.)\,\,\Lambda\setminus T^{{}^{\prime}}(x)\right]}{\mu\left[\xi(.)\,\,\hbox{on}\,\,\Lambda\cap T^{{}^{\prime}}(x)\,\,\big{|}\,\,\xi(.)\,\,\hbox{on}\,\,\Lambda\setminus T^{{}^{\prime}}(x)\right]}$
		$\displaystyle=$	$\displaystyle\frac{\mu\left[\xi(.)\,\,\hbox{on}\,\,\Lambda\cap T^{{}^{\prime}}(x)\,\,\big{|}\,\,\xi(x)\right]\mu\left[\xi(x)\,\,\big{|}\,\,\xi(r(x))\right]}{\mu\left[\xi(.)\,\,\hbox{on}\,\,\Lambda\cap T^{{}^{\prime}}(x)\,\,\big{|}\,\,\xi(r(x))\right]}.$

Again from (4.17), we have

$$\mu\left[\xi(.)\,\,\hbox{on}\,\,\Lambda\cap T^{{}^{\prime}}(x)\,\,\big{|}\,\,\xi(x)\right]=\mu\left[\xi(.)\,\,\hbox{on}\,\,\Lambda\cap T^{{}^{\prime}}(x)\,\,\big{|}\,\,\xi(x)\,\,;\,\,\xi(r(x))\right].$$

This leads to

	$\displaystyle\mu\left[\xi(x)\,\,\big{|}\,\,\xi(.)\,\,\hbox{on}\,\,\Lambda\right]$	$\displaystyle=$	$\displaystyle\frac{\mu\left[\xi(x)\,\,;\,\,\xi(.)\,\,\hbox{on}\,\,\Lambda\cap T^{{}^{\prime}}(x)\,\,,\,\,\xi(r(x))\right]}{\mu\left[\xi(.)\,\,\hbox{on}\,\,\Lambda\cap T^{{}^{\prime}}(x)\,\,;\,\,\xi(r(x))\right]}$
		$\displaystyle=$	$\displaystyle\mu\left[\xi(x)\,\,\big{|}\,\,\xi(.)\,\,\hbox{on}\,\,\{r(x)\}\cup\Lambda\cap T^{{}^{\prime}}(x)\right].$

This completes the proof.

Proof. Consider a subtree $T^{{}^{\prime}}=(V^{{}^{\prime}},E^{{}^{\prime}})$ of $T$. Let $x\in V^{{}^{\prime}}$. If $V^{{}^{\prime}}\cap N_{x}=\mathchoice{\mbox{\normalsize\rm\O}}{\mbox{\normalsize\rm\O}}{\mbox{\rm\O}}{\mbox{\rm\O}}$ then $V^{{}^{\prime}}=\{x\}$ and (3.12) is trivial. Otherwise, let us denote $N_{x}\cap V^{\prime}=\{y_{1},y_{2},\cdots,y_{d}\}$ with $d=|N_{x}\cap V^{{}^{\prime}}|$. Remark that if $o=y\in N_{x}\cap V^{{}^{\prime}}$ then $r_{o}(x)=y$ and $N_{x}\cap V^{{}^{\prime}}\setminus\{y\}\subseteq S(x)\cap V^{{}^{\prime}}\subseteq T^{{}^{\prime}}_{o}(x)\cap V^{{}^{\prime}}$. As $\mu$ is an $y_{1}$-BMC, by Lemma 2 we have

$$\mu[\xi(x)\,\,\mid\,\,\xi(.)\,\hbox{on}\,\,V^{{}^{\prime}}\setminus\{x\}]=\mu[\xi(x)\,\,\mid\,\,\xi(.)\,\hbox{on}\,\,\{y_{1}\}\cup(T_{y_{1}}^{{}^{\prime}}(x)\cap V^{{}^{\prime}})].$$

Since $\mu$ is an $y_{2}$-BMC by Lemma 2 , we have

			$\displaystyle\mu[\xi(x)\,\,\mid\,\,\xi(.)\,\hbox{on}\,\,\{y_{1}\}\cup(T_{y_{1}}^{{}^{\prime}}(x)\cap V^{{}^{\prime}})]$
		$\displaystyle=$	$\displaystyle\mu[\xi(x)\,\,\mid\,\,\xi(.)\,\hbox{on}\,\,\{y_{2}\}\cup\bigl{(}\{y_{1}\}\cup T_{x_{1}}^{{}^{\prime}}(x)\cap T_{y_{2}}^{{}^{\prime}}(x)\cap V^{{}^{\prime}}\bigr{)}]$
		$\displaystyle=$	$\displaystyle\mu[\xi(x)\,\,\mid\,\,\xi(.)\,\hbox{on}\,\,\{y_{1},y_{2}\}\cup\bigl{(}T_{y_{1}}^{{}^{\prime}}(x)\cap T_{y_{2}}^{{}^{\prime}}(x)\cap V^{{}^{\prime}}\bigr{)}].$

Iterating this procedure, we get

	$\displaystyle\mu[\xi(x)\,\,\mid\,\,\xi(.)\,\hbox{on}\,\,V^{{}^{\prime}}\setminus\{x\}]$	$\displaystyle=$	$\displaystyle\mu[\xi(x)\,\,\mid\,\,\xi(.)\,\hbox{on}\,\,\{y_{1},y_{2},\cdots,y_{d}\}\cup\bigl{(}\bigcap_{i=1}^{d}T_{y_{i}}^{{}^{\prime}}(x)\cap V^{{}^{\prime}}\bigr{)}]$
		$\displaystyle=$	$\displaystyle\mu[\xi(x)\,\,\mid\,\,\xi(.)\,\hbox{on}\,\,N_{x}\cap V^{{}^{\prime}}]$

because

$$\bigcap_{i=1}^{d}T_{y_{i}}^{{}^{\prime}}(x)\cap V^{{}^{\prime}}=\bigcap_{y\in N_{x}}T_{y}^{{}^{\prime}}(x)\cap V^{{}^{\prime}}=\mathchoice{\mbox{\normalsize\rm\O}}{\mbox{\normalsize\rm\O}}{\mbox{\rm\O}}{\mbox{\rm\O}}.$$

(5.23)

Therefore, the measure $\mu$ satisfies (3.12). This finishes the proof, the verification of (5.23) being left to the reader.