% Plain-TeX version of "Markov processes on trees and their local times" % \magnification=\magstep1 \parskip=\medskipamount \def\blob{$\bullet$} \def\disc{$\circ$} \def\leq{\leqslant} \def\geq{\geqslant} \def\l{\lambda} \def\tbE{\tilde{\Bbb E}} \def\G{{\cal G}} \def\dG{\partial G} \def\half{\raise1pt\hbox{$\scriptstyle{1 \over 2}\displaystyle$}} \def\quarter{\raise1pt\hbox{$\scriptstyle{1 \over 4}\displaystyle$}} \def\frac#1{{\textstyle{1\over #1}\displaystyle}} \def\brak#1#2{\langle#1,#2\rangle} \def\endbox{\hfill$\square$\par} \def\Pr{\mathop{\rm Pr}\nolimits} \font\bigx=cmbx10 scaled \magstep2 \input mssymb % \leftline{\bigx Markov processes on trees and their local times} \bigskip \leftline{{\bf Martin W Baxter}\footnote{$^{1,}$}% {Email: m.w.baxter@statslab.cam.ac.uk}% \footnote{*}{\sl This research was conducted whilst the author was visiting the Department of Mathematics, University of British Columbia, Vancouver.}} \medskip \leftline{\rm Statistical Laboratory, University of Cambridge, 16 Mill Lane Cambridge CB2 1SB} \bigskip\bigskip \noindent {\bf Abstract.} This paper derives necessary and sufficient conditions for a Markov chain on a tree to visit any one of its uncountable number of leaves enough for it to build up a local time there. Additionally, when all local times exist, conditions are found for them to be jointly continuous in both time and space using existing results for symmetric Markov processes. \bigskip \leftline{{\it Mathematics Classification (1991)}\/: 60J27, 60J55, 05C05} \bigskip\bigskip \leftline{\bf 1. Introduction} We consider some (fixed) tree with a countable number of branches and nodes but, typically, an uncountable number of leaves. In particular, we will study the behaviour of a continuous time Markov chains taking a random walk around the tree. The cases of our especial interest are those in which the process passes through an infinite number of states in a finite time to reach the `boundary' of the tree and reflect back off it. The substantive question we answer is whether the process has a local time, and if so whether it has a version which is jointly continuous in time and space. Our program will be to calculate expressions for the first and second moments of some hitting times and use them to derive a necessary and sufficient condition for a boundary point of the tree to be regular. Necessary and sufficient conditions are also achieved for the local times to be jointly continuous in time and space with respect to the appropriate topology on the tree and its boundary. Formally the conditions that we shall insist on for the tree are: \item{\blob}there are a countable number of nodes, \item{\blob}each node has a finite number of (positive length) edges connecting it to other nodes, \item{\blob}there are no loops (circuits), \item{\blob}the tree is connected, and \item{\blob}there is a distinguished point of the tree called the root or 0. Thus every pair of nodes has a unique shortest path (least number of edges) between them. We shall use the following notations: \item{\disc}we shall call the set of the nodes of the tree $I$; \item{\disc}for any two points $i$, $j$ in $I$, we denote the path between them as $[i,j]$; \item{\disc}for any three points $i$, $j$ and $k$ in $I$, we let $i\cdot j\cdot k$ be the unique point $l$ such that the paths $[i,l]$, $[j,l]$ and $[k,l]$ have no common edges. In other words, $l$ is the furthest point in common of any two of $[i,j]$, $[i,k]$ and $[j,k]$; \item{\disc}for any two points $i$ and $j$ in $I$, we use $i*j$ as an abbreviation for $0\cdot i\cdot j$, the point at which the paths $[0,i]$ and $[0,j]$ diverge; \item{\disc}for any point $i$ in $I$, we set $i_0$ to be the point next to $i$ on the path $[i,0]$, taking, for completeness, $0_0=0$; \item{\disc}for any two adjacent points $i$ and $j$, we define $A_{ij}$ to be the set of points of $I$ which are closer to $i$ than to $j$, that is $$ A_{ij}:=\{k\in I:j\notin[i,k]\,\}=I\backslash A_{ji}, $$ and we shall often use the notation $A_i^0$ for $A_{ii_0}$, the set of all points for which $i$ stands between them and the root; \item{\disc}by a {\it boundary point} of $I$ we will mean any infinite path from 0, and we write $\dG$ for the set of all boundary points and $G$ for the union of $I$ and $\dG$; and \item{\disc}it is useful to be able to consider the topology on $G$ generated by the basis of open sets comprising the individual points of $I$ and all the sets $A_i^0$. We shall call this topology $\G$ and note that $(G,\G)$ is compact and metrisable. We will discover that the key to understanding the behaviour of the process is to view the tree as a topological space, with some appropriate topology. One of the topologies we shall discover to be important is a metric topology induced by the Q-matrix of the Markov chain. We say that a random walk on the tree with Q-matrix $Q$ and invariant distribution $\pi$ is symmetrisable (or reversible) if $\pi_i q_{ij}=\pi_j q_{ji}$ for all $i$ and $j$ in $I$. We can then define $d$ to be the metric on $I$ such that $d(i,j)=(\pi_i q_{ij})^{-1}$, for $i$ and $j$ adjacent points of $I$. Extending $d$ to $G$, allowing it to take infinite values if necessary, we say that $d$ is {\it Lipschitz continuous} at $x$ in $\dG$, the boundary of $G$, if there exists a constant $K$ such that $d(x,y)\leq Kd(x,x*y)$ for all $y$ in $\dG$ (and hence for all $y$ in $G$). We state now a summary of the major results of the paper. \noindent{\bf Theorem A.} {\sl Given a symmetric Markov random walk on the graph $I$ with metric $d$, then the process has a local time at a boundary point $x$ if and only if $d(0,x)$ is finite. Further, if all boundary points have a local time and $d(0,\cdot)$ is a continuous function on $G$, then the joint local time $L=\{L(t,x):t\in\Bbb R^+,\ x\in G\}$ is continuous almost surely if and only if there exists a probability measure $m$ on $(G,d)$ such that $$ \lim_{\delta\downarrow0}\sup_{x\in G}\int_0^\delta \left({1\over\epsilon} \log{1\over m(B_d(x,\epsilon))}\right)^{1/2}\,d\epsilon = 0, $$ where $B_d(x,\epsilon):=\{y\in G:d(x,y)\leq\epsilon\}$.} \noindent{\bf Theorem B.} {\sl Given a symmetric Markov random walk on the graph $I$ with metric $d$, such that $d$ is finite and uniformly Lipschitz continuous on $G$ and that the number of edges a node may have is bounded, then the joint local time $L=\{L(t,x):t\in\Bbb R^+,\ x\in G\}$ is continuous almost surely if $$ \lim_{m\rightarrow\infty}\sup_{x\in\dG} \sum_{n=m}^\infty\sqrt{{1\over n}d(x_n,x)}=0, $$ where $x_n$ is the $n$th point on the path from 0 to $x$.} We can note that Theorems A and B generalise theorem~1 of Baxter~[2], where the tree was symmetric and there was no dependence on the choice of boundary point. \bigskip\bigbreak\leftline{\bf 2. Construction}\nobreak Given such a tree, we can define a Markov chain on it in one of two ways. We may either have an existing Q-matrix, or we have a metric on the tree itself. Formally we can express the equivalence with a result \noindent{\bf Proposition 1.} {\sl Let $\cal D$ be the set of metrics on $I$ which are path-additive, that is if the path from $i$ to $j$ is $i=i_1,i_2,\ldots,i_n=j$ then $d\in{\cal D}$ means that $d(i,j)=\sum_{r=1}^{n-1}d(i_r,i_{r+1})$. Let $\cal Q$ be the set of all Q-matrices on $I$ which are reversible with respect to an invariant distribution $\pi$, that is that $$ \pi_i q_{ij} = \pi_j q_{ji}, \qquad\hbox{\rm for all $i$, $j$ in $I$,} $$ and $\pi\in\Pr(I):=\{\pi:\sum\pi_i=1\}$ and $q_{ij}>0$ if and only if $i$ and $j$ are adjacent points. Then there is a correspondence between ${\cal D}\times\Pr(I)$ and $\cal Q$.} \noindent {\it Proof of Proposition 1.} We can map the pair $(d,\pi)$ of ${\cal D}\times\Pr(I)$ into $\cal Q$ by defining $$ \eqalign{q_{ij}&:={1\over\pi_i d(i,j)},\qquad\hbox{\rm if $i$ and $j$ are adjacent,}\cr q_{ij}&:=0,\qquad\hbox{\rm if $i\neq j$ otherwise,}\cr \hbox{\rm and}\qquad -q_{ii}=q_i&:=\sum_{j\neq i}q_{ij}<\infty.\cr} $$ Then $\pi_i q_{ij}=\pi_j q_{ji}$, and so $Q=(q_{ij})\in{\cal Q}$. Conversely, given $Q$ in $\cal Q$, we can take its invariant distribution $\pi$ and define a metric $d$ on adjacent points $i$ and $j$ by $d(i,j):=(\pi_i q_{ij})^{-1}=d(j,i)$. Then extend $d$ to all of $I\times I$ by path-additivity.\endbox We shall call such a set-up $(Q,\pi,d)$. We can extend $d$ to all the points of $G$, allowing it to take infinite values where necessary. Given such a set-up, we would now like to construct a process which has $Q$ as its Q-matrix. \noindent {\bf Theorem 2.} {\sl Given $I$ and a $(Q,\pi,d)$ as in Propostion~1, there exists a Markov process $X_t$ whose standard transition matrix function $P_t$ satisfies $P'(0)=Q$ and $\pi_i p_{ij}(t)=\pi_j p_{ji}(t)$, and its resolvent $R(\l):=\int_0^\infty e^{-\l t}P_t\,dt$, seen as a map from $L^2(\pi)$ into ${\cal D}^Q$ satisfies $$ {\cal E}^Q(f,R(\l)g)+\l\brak{f}{R(\l)g}=\brak{f}{g}, $$ where $$ \eqalign{{\cal E}^Q(f,g)&:={\textstyle{1\over2}\displaystyle} \sum_{i\neq j}\pi_i q_{ij}(f_j-f_i)(g_j-g_i),\cr {\cal D}^Q&:=\{f\in L^2(\pi):{\cal E}^Q(f,f)<\infty\,\},\cr \hbox{\rm and}\qquad \brak{f}{g}&:=\sum_{i\in I}\pi_i f_i g_i,\qquad \hbox{\rm for $f$, $g$ in $L^2(\pi)$.}\cr} $$ Further the process $X$ is honest and reflects off the boundary of the tree if it explodes (passes through infinitely many states by a finite time).} \noindent{\it Proof of Theorem 2.} As each $q_i$ is finite, because of the finite ramification condition, the result is an immediate application of theorem 9.13 of Rogers and Williams~[5]. The functions $j\mapsto\delta_{ij}$ are in ${\cal D}^Q$, so ${\cal D}^Q$ is dense in $L^2(\pi)$.\endbox Now we have the process constructed, we begin to follow as closely as possible the scheme of previous calculations with the binary tree. Happily our increased generality will lead to simplification of some of the manipulations required. We begin with a reminder of results about the first moment of hitting times. \noindent{\bf Theorem 3.} {\sl If $i$ and $j$ are adjacent points of $I$, and $T_j$ is the first hitting time of $j$, $T_j:=\inf\{t\geq0:X_t=j\}$, then $$ \Bbb E_i T_j = d(i,j)\pi(A_{ij}), $$ from which it follows that $\Bbb E_i(T_j)+\Bbb E_j(T_i)=d(i,j)$.} \noindent{\it Proof of Theorem 3.} Note firstly that the process starting at $i$ stays in $A_{ij}$ until time $T_j$. For any $k$ in $A_{ij}$, the chance of hitting $k$ before $j$ is simply the ratio $d(i,j)/d(k,j)$. (To see this just look at the chain on the path $[k,j]$ starting at $i$, and solve some linear equations.) If we get to $k$ before $T_j$, then the number of excursions from $k$ back to itself before $T_j$ will be geometrically distributed, with the probability of not returning being $$ \Bbb P_k(T_j<\hbox{\rm first return time})={q_{kk'}\over q_k} \Bbb P_{k'}(T_j < T_k) = (\pi_k q_k d(k,j) )^{-1}, $$ where $k'$ is the point next to $k$ in the path $[k,j]$. Hence the expected number of visits to $k$ before $T_j$, starting from $k$, is $\pi_k q_k d(j,k)$, and the expected time spent in $k$ up to $T_j$, starting from $i$, must be $\pi_k d(i,j)$. By summing over all $k$ in $A_{ij}$ we achieve the stated result.\endbox It is not much less painless to obtain an expression for the second moment of such a hitting time. This will be essential for showing that sufficient conditions are in fact necessary by giving lower bounds for various quantities. \noindent{\bf Theorem 4.} {\sl If $i$ and $j$ are adjacent points of $I$, then} $$ {\Bbb E_i(T^2_j)\over \Bbb E_i(T_j)}= 2\sum_{k,l\in A_{ij}}\pi_k \pi_l d(i\cdot k\cdot l,j)/\pi(A_{ij}). $$ \noindent{\it Proof of Theorem 4.} We will let $T_j(i)$ be a random variable with the distribution of $T_j$ under $\Bbb P_i$. We can expand $T_j(i)$ by conditioning on the first jump, and use the strong Markov property to write that $$ T_j(i) = E_i + X, \quad\hbox{\rm where}\quad X:=\cases{0&with probability $q_{ij}/q_i$,\cr T_i(k)+\tilde T_j(i)&with probability $q_{ik}/q_i$, $k\neq j$,\cr} $$ and where $E_i$ is distributed as the holding time of the process in state $i$, that is exponentially with rate $q_i$, and $\tilde T_j(i)$ is distributed as $T_j(i)$ independently of $E_i$ and the other $T_i(k)$. By taking the expectation of this decompostion and equating with Theorem 3, we see that $\Bbb E(X)=\pi(A_{ij})/(\pi_i q_{ij})-1/q_i$. Now $$ \Bbb E(X^2)=\sum_{k\neq j}{q_{ik}\over q_i}\Bbb E_k(T^2_i) +2\sum_{k\neq j}{q_{ik}\over q_i}(\Bbb E_k T_i)(\Bbb E_i T_j) +(1-q_{ij}/q_i)\Bbb E_i(T^2_j), $$ and $$ \Bbb E_i(T_j^2)=\Bbb E(E_i^2)+2(\Bbb E E_i)(\Bbb E X)+\Bbb E(X^2). $$ Using Theorem 3 and simplifying, we deduce that $$ q_{ij}\Bbb E_i(T^2_j) = \sum_{k\neq j}q_{ik}\Bbb E_k(T_i^2)+ 2{\pi(A_{ij})^2\over\pi_i^2 q_{ij}}. $$ Multiplying both sides by $\pi_i$, we see that $$ {\Bbb E_i(T_j^2)\over d(i,j)}=\sum_{k\neq j}{\Bbb E_k(T_i^2)\over d(i,k)} +2d(i,j)\pi(A_{ij})^2, $$ where the sum is taken over points $k$ adjacent to $i$. In other words, if we let $h_k:=\Bbb E_k(T_{k'}^2)/d(k,k')$ where $k'$ is the point next to $k$ on the path $[k,j]$, then $h$ is the (minimal non-negative) solution to $$ h_i = 2d(i,i')\pi(A_{ii'})^2+\sum_{k\neq j}h_k. $$ Hence we see that $$ h_i=2\sum_{k\in A_{ij}}d(k,k')\pi(A_{kk'})^2, $$ or after a change of summation variables, $$ h_i = 2 \sum_{k,l\in A_{ij}}\pi_k \pi_l d(i\cdot k\cdot l,j), $$ which when divided by $\pi(A_{ij})$ produces the desired formula.\endbox \bigskip \leftline{\bf 3. Exploring the boundary} Before trying to decide which boundary points may or may not be regular, we should really pause to consider which of them can possibly be hit to begin with. One object we might look at is the Ray-Knight compactification of $(Q,\pi,d)$ chain, but this can be rather involved (and certainly can be larger than the points of $G$). However, as in \S81 of Williams~[6], it is enough to look at the set of points of the boundary which can actually be visited. In his language, we define a map $\phi$ from $I$ to $l^1(I)$ by taking $\phi(i)$ to be the function sending $j$ to $r_1(i,j)$ where $r_1(i,j)$ is the appropriate entry of the resolvent matrix $R(1)$, that is that $r_1(i,j)=\int_0^\infty e^{-t}p_{ij}(t)\,dt$. Then $X$ can only visit points of the set $E$, identified as the closure of $\phi(I)$ in $l^1(I)$ (which need not be compact). We can characterise $E$ in the following way. (Note we can extend $r_1$ to $G\times I$ by taking monotone limits along paths to boundary points of $G$.) \noindent{\bf Theorem 5.} {\sl The set $E$ contains only points of $G$, and a point $x$ in $G$ is also in $E$ if and only if $r_1(x,0)>0$. The topology on $E$ is such that the sequence $(x_n)$ converges to $x$ in $E$ if and only if the sequence converges in $\G$ and $r_1(x_n,0)$ converges to $r_1(x,0)>0$. Further \item{\blob}$E$ is compact $\iff$ $E$ is closed in $G$ and $r_1(\cdot,0)$ is $\G$-continuous, and \item{\blob}$E$ is locally compact $\iff$ $r_1(\cdot,0)$ is $\G$-continuous. \noindent In addition,} $$ \eqalign{ \sum_{i\in[0,x]}\pi[i,x]d(i_0,i)&<\infty\qquad\hbox{\sl is necessary for $x$ to be in $E$,}\cr \hbox{\sl and}\quad\sum_{i\in[0,x]}\pi(A_i^0)d(i_0,i)&<\infty\qquad \hbox{\sl is sufficient for $x$ to be in $E$.}\cr} $$ \noindent{\it Proof of Theorem 5.} Firstly, suppose $(i_n)$ is a sequence in $I$ such that $\phi(i_n)$ converges to a point $x$ in $l^1(I)$. Then as $(G,\G)$ is a compact metrisable space, and thus sequentially compact, there exists a subsequence $(i_{n_j})$ which converges to some point $\xi$ in $G$. The subsequence is eventually contained in any neighbourhood $A_y^0$ of $\xi$, and $r_1(i,k)\leq r_1(y,k)$ for all points $i$ in that neighbourhood and all points $k$ outside it. Hence $x_k\leq r_1(y,k)$. But as $y$ moves along the path $[0,\xi]$, $r_1(y,k)$ tends monotonically to the limit we call $r_1(\xi,k)$, which is bounded below by $x_k$. But as $\sum x_k=1$ and $\sum r_1(\xi,k)\leq 1$, we must have equality everywhere and $x_k=r_1(\xi,k)$ for all points $k$ of $I$. Thus $r_1(\xi,k)$ will be positive for some (and hence all) $k$. Now choose a function $f_y$ on $I$ to be (for $y$ on the path $[0,\xi]$) $$ f_y(i):={r_i(i,y)\over r_1(y,y)}-{r_1(i,y_0)\over r_1(y_0,y_0)}= \Bbb E_i(e^{-T_y})-\Bbb E_i(e^{-T_{y_0}}), $$ which is non-negative on the set $A_y^0$ and non-positive on the set $A_{y_0y}$. By the convergence of $(i_n)$ in $E$, $f_y(i_n)$ tends to a limit. But along the subsequence $f_y$ tends to a strictly positive limit, due to $r_1(\xi,y)$ being positive, so that we deduce that eventually the sequence $f_y(i_n)$ is positive, and hence that $(i_n)$ is eventually in $A_y^0$. In other words, the sequence $(i_n)$ converges to $\xi$ in $G$. Conversely, if $\xi$ is in $G$ and $r_1(\xi,0)$ is positive, we shall show that $\xi$ is a point of $E$. For each $y$ in the path $[0,\xi]$, $$ r_1(\xi,k)\geq \Bbb E_{\xi}e^{-T_y}r_1(y,k)={r_1(\xi,0)\over r_1(y,0)} r_1(y,k), $$ and hence $\sum_k r_1(\xi,k)\geq r_1(\xi,0)/r_1(y,0)$, the right-hand side of which tends upwards to 1 as $y$ tends to $\xi$ along the path. By Fatou's lemma, the left-hand side is also bounded above by 1, so equality must hold, which is sufficient for $\xi$ to be in $E$ (81.2 of Williams~[6]). Proving the topology the other way, we take $(x_n)$ to be a sequence in $E$ which converges to $x$ in the $\G$-topology with $r_1(x_n,0)\rightarrow r_1(x,0)>0$. Then setting $y_n:=x*x_n$, so that $y_n$ lies on the path $[0,x]$ and $x_n$ is in the neighbourhood $A_{y_n}^0$ of $x$, and $y_n$ tends to $x$ in $\G$ as $n$ tends to infinity. We have that $$ r_1(x_n,k) = r_1(x,k) {r_1(x_n,0)\over r_1(x,0)}\qquad\hbox{\rm for all $k\notin A_{y_n}^0$.} $$ Note that $r_1(x,A_{y_n}^0)$ goes to $0$ as $n$ gets large, as does $r_1(x_n,A_{y_n}^0)$ because $$ r_1(x_n,A_{y_n}^0)=1-\bigl(1-r_1(x,A_{y_n})\bigr){r_1(x_n,0)\over r_1(x,0)}. $$ Hence $$ \sum_{k\in I}|r_1(x_n,k)-r_1(x,k)|\leq r_1(x_n,A_{y_n}^0) + r_1(x,A_{y_n}^0) + \left|1-{r_1(x_n,0)\over r_1(x,0)}\right|, $$ which shows that indeed $(x_n)$ converges to $x$ in $E$. For the conditions for the compactness of $E$, note that the function $r_1(\cdot,0)$ is automatically $\G$-continuous at points of $G$ which are not in $E$ and takes the value zero there. Suppose $E$ is compact. We wish to show that $r_1(\cdot,0)$ is continuous at any point $\xi$ of $E$. Suppose we have a sequence $(\xi_n)$ of points of $G$ converging to $\xi$ in the $\G$-topology, but such that $r_1(\xi_n,0)$ does not converge to $r_1(\xi,0)$. By taking a subsequence, if necessary, we can assume that $r_1(\xi_n,0)$ actually tends to some other limit. But as $E$ is a compact metric space, the sequence must have an $E$-convergent subsequence. This gives a contradiction, showing that $r_1$ is in fact continuous on $G\times\{0\}$. Conversely, suppose $E$ is $\G$-closed and $r_1(\cdot,0)$ is $\G$-continuous. If $(x_n)$ is any sequence in $E$, it is enough to show that it has an $E$-convergent subsequence, so that $E$ must be sequentially compact and hence compact. As $(G,\G)$ is compact, there exists a $\G$-convergent subsequence tending to some point $\xi$ in $G$. As $E$ is $\G$-closed, the point $\xi$ is also in $E$. And the continuity of $r_1$, gives that the subsequence is also $E$-convergent. The proofs for local compactness have a similar flavour. Finally, for the necessity condition, we define $W_j:=\Bbb E_j e^{-T_0}$. Then by conditioning on the first jump and re-arranging, we have that $$ \eqalign{ (1+q_i)W_i &= \sum_{j\neq i}q_{ij}W_j\qquad i\neq0,\cr W_0 &= 1.\cr} $$ Re-arranging again, and setting $U_i:=\pi_i q_{ii_0}(W_{i_0}-W_i)\geq0$, we derive the equations $U_i=\pi_i W_i + \sum_j U_j$, where the sum is taken over all points adjacent to $i$ except for $i_0$. From which we can deduce that $U_i\geq\sum_{j\in A_i^0}\pi_j W_j$ and thus that $$ 1-W_i\geq \sum_{k\in[0',i]}d(k_0,k)\sum_{j\in A_k^0}\pi_j W_j \geq \sum_{k\in[0',i]}d(k_0,k)\pi[k,\xi] W_{\xi}, $$ where $i$ is a point on the path $[0,\xi]$ and $0'$ is the point next to 0 on that path. If $\xi$ is in $E$ then $W_{\xi}$ is positive, so the sum in question must be finite. For sufficiency, things are simpler. From Theorem 3, we can write that $$ \Bbb E_i(1-e^{-T_{i_0}})\leq \Bbb E_i(T_{i_0})=\pi(A_i^0)d(i_0,i). $$ Using the result that for $(x_n)$ in $(0,1)$, $\sum(1-x_n)<\infty$ if and only if $\prod x_n>0$, we get $$ \prod_{i\in[0,\xi]}\Bbb E_i(e^{-T_{i_0}})=\Bbb E_{\xi}e^{-T_0} ={r_1(\xi,0)\over r_1(0,0)}>0, $$ and so $r_1(\xi,0)$ is positive and $\xi$ is in $E$.\endbox \bigskip\bigbreak\leftline{\bf 4. Local times} We can now return to the actual process $X$ on the tree. Recall that a point $x$ is regular if $\Bbb P_x(H_x=0)=1$, where $H_x=\inf\{t>0:X_t=x\}$. Given that the chain is recurrent, this is equivalent to the condition that $\Bbb P_i(T_x<\infty)=1$ for any and all $i$ in $I$. The regularity of a point also characterises whether the process has a local time there (almost surely). It will be useful to recall the Lower Bound lemma of Baxter~[2], which translates control of second moments into an appropriate lower bound. \noindent{\bf Lower Bound lemma.} {\sl If $X:\Omega\rightarrow[0,\infty]$ is a random variable such that $\Bbb E(X^2)\leq K\Bbb E(X)<\infty$ for some $K$, then} $$ \eqalign{{\Bbb E}\left(1-e^{-X}\right)&\geq\alpha\Bbb E(X)\cr \hbox{\sl where}\quad \alpha=\alpha(K)&={1-e^{-4K}\over 8K}.\cr} $$ The following theorem provides a very natural characterisation of regularity. \noindent {\bf Theorem 6.} {\sl The point $\xi$ in $E$ is regular for the chain if and only if $d(0,\xi)$ is finite.} \noindent {\it Proof of Theorem 6.} Sufficiency is straightforward, using Theorem 3. $$ \Bbb E_0(T_{\xi})=\sum_{i\in[0',\xi]}d(i_0,i)\pi(A_{i_0i})\leq \sum_{i\in[0',\xi]}d(i_0,i)=d(0,\xi), $$ where $0'$ is the point next to $0$ on the path to $\xi$. If the distance is finite, then $\Bbb P_0(T_{\xi}<\infty)=1$ and $\xi$ is regular. Necessity is more involved. To digress initially, if $\tilde I$ is any connected subtree of $I$, then we can have a reduced chain on $\tilde I$ with Q-matrix $\tilde Q$ given by $$ \eqalign{\tilde q_{ij} &:= q_{ij}\qquad i,j\in \tilde I,\ i\neq j,\cr \tilde q_i &:= \sum_{j\in\tilde I}q_{ij}\qquad i\in\tilde I,\cr} $$ and setting $\tilde\pi_i:=\pi_i/\pi(\tilde I)$ for $i\in\tilde I$ to be a symmetrising distribution for $\tilde Q$. Then Theorems 3 and 4 become, for $i$ and $j$ adjacent points of $\tilde I$: $$ \eqalign{\tbE_i(T_j)&=\tilde d(i,j)\tilde\pi(\tilde A_{ij})= d(i,j)\pi(\tilde A_{ij}),\cr \hbox{\rm and}\qquad {\tbE_i(T_j^2)\over\tbE_i(T_j)}&= 2\sum_{k,l\in\tilde A_{ij}}\pi_k \pi_l d(i\cdot k\cdot l,j) /\pi(\tilde A_{ij}),\cr} $$ Note that as there are fewer ways to get lost, $\tbE_i(e^{-\l T_j})\geq \Bbb E_i(e^{-\l T_j})$ for $i$ and $j$ in $\tilde I$. Let us choose $\tilde I$ to be the points of the path $[0,\xi]$. Then for $i$ in $\tilde I$, $$ {\tbE_{i_0}(T_i^2)\over\tbE_{i_0}(T_i)}= 2\sum_{k,l\in [0,i_0]}\pi_k \pi_l d(i_0\cdot k\cdot l,i)/\pi[0,i_0] \leq 2(1+d(0,i)), $$ Then by the Lower Bound lemma, $$ \tbE_{i_0}(1-e^{-T_i})\geq{1-e^{-4}\over 16}\pi[0,i_0] {d(i_0,i)\over 1+d(0,i)}\geq \alpha{d(i_0,i)\over 1+d(0,i)}, $$ for some positive constant $\alpha$. If $d(0,\xi)$ is infinite, then by Kronecker's lemma, we have that $$ \sum_{i\in[0,\xi]}\tbE_{i_0}(1-e^{-T_i})=\infty\qquad\Rightarrow \qquad\tbE_0 e^{-T_{\xi}}=0. $$ By the domination mentioned above, things are no better in the original chain, so that $\Bbb E_0 e^{-T_{\xi}}=0$ and $\xi$ is not regular.\endbox We will later be interested to know whether or not the space $(G,d)$ is compact (or locally compact). This theorem gives a useful exact characterization. \noindent{\bf Theorem 7.} {\sl The metric space $(G,d)$ is compact if and only if $d(0,\cdot)$ is finite everywhere and $\G$-continuous. Similarly $(G,d)$ is locally compact if and only if $d(0,\cdot)$ is $\G$-continuous into the space $[0,\infty]$.} \noindent{\it Proof of Theorem 7.} Suppose that the space is compact. Then each $d(0,x)$ must be finite for each $x$. Also if $x_n$ converges in the $\G$-topology to $x$ without $d(0,x_n)$ converging to $d(0,x)$, then by replacing $(x_n)$ with a subsequence if necessary we may assume that in fact $d(0,x_n)$ converges to some limit $l$ not equal to $d(0,x)$ (though the limit may be infinite). But as $(G,d)$ is a compact metric space, it is sequentially compact and the sequence will have a genuine subsequence which is $d$-convergent to $x$. But if $d(x_{n_j},x)$ goes to zero, then that implies that $d(0,x_{n_j})$ converges to $d(0,x)$ which is a contradiction. Hence $d$ is $\G$-continuous. Conversely, if $d$ is finite and $\G$-continuous, and $(x_n)$ is a sequence of points of $G$, it is enough to show that $(x_n)$ has a $d$-convergent subsequence. Take a $\G$-convergent subsequence $(x_{n_j})$ converging to $x$, so $d(0,x_{n_j})$ converges to $d(0,x)$, as $d$ is $\G$-continuous. Now $$ d(x_{n_j},x)=\bigl(d(0,x_{n_j})-d(0,x)\bigr)+ 2\bigl(d(0,x)-d(0,x*x_{n_j})\bigr), $$ the former term of which goes to zero by the above, and the latter term similarly because the sequence $(x*x_{n_j})$ is also $\G$-convergent to $x$. The local compactness equivalence is similar.\endbox As an immediate corollary we see that $(G,d)$ is compact if and only if the $\G$ and $d$ topologies are equivalent, which is the case that we are now interested in. We can now consider the important question of when, given that a local time exists, it is jointly continuous in both its time and space variables. To start with, we need to define a new metric $\rho$ to enable us to take advantage of existing results. The next theorem provides a vital equivalence of $\rho$ and $\sqrt{d}$, by means of upper and lower bounds coupled with the variance control of Theorem~4. \noindent {\bf Theorem 8.} {\sl If $(G,d)$ is compact, and we define $$ \eqalign{ \rho^2(x,y)&:={r_1(x,x)-r_1(y,x)\over\pi(x)}+{r_1(y,y)-r_1(x,y)\over\pi(y)}\cr &=\Bbb E_y(1-e^{-T_x}){r_1(x,x)\over\pi(x)} +\Bbb E_x(1-e^{-T_y}){r_1(y,y)\over\pi(y)},\cr} $$ on $I\times I$, then we can continuously extend $\rho$ to $G\times G$. Further the metric $\rho$ is equivalent to $\sqrt{d}$, and there exist finite positive constants $c$ and $C$ such that} $$ c\,d(x,y)\leq\rho^2(x,y)\leq Cd(x,y),\qquad\hbox{\sl for all $x,y$ in $G$.} $$ \noindent{\it Proof of Theorem 8.} Firstly to extend $\rho$ to the boundary of $I$, we remember that $r_1$ is $\pi$-symmetric so that $$ {r_1(x,x)\over\pi(x)}={r_1(x,0)\over\pi(0)\Bbb E_0 e^{-T_x}} $$ If we can show that $r_1(x,0)$ and $\Bbb E_0 e^{-T_x}$ are both uniformly $d$-continuous in $x$, then $r_1(x,x)/\pi(x)$ will extend continuously to the boundary of $(G,d)$. We achieve this by noting that $$ |r_1(x,0)-r_1(y,0)|\leq r_1(x*y,0)d(x,y)\leq d(x,y), $$ and $$ |\Bbb E_0(e^{-T_x})-\Bbb E_0(e^{-T_y})|\leq\Bbb E_0(e^{-T_{x*y}}) d(x,y)\leq d(x,y). $$ Hence as $r_1(x,x)/\pi(x)$ is a continuous positive function on a compact space, it must have a minimum positive value $m$, and a maximum finite value $M$. In particular, we can achieve the upper bound as $$ \rho^2(x,y)\leq M\left(\Bbb E_x(1-e^{-T_y})+\Bbb E_y(1-e^{-T_x})\right) \leq Md(x,y), $$ so that the constant $C$ can take the value $M$. Now Theorem 4 produces the bound $$ {\Bbb E_i(T_j^2)\over\Bbb E_i(T_j)}=2\sum_{k,l\in A_{ij}}\pi_k \pi_l d(i\cdot k\cdot l,j)/\pi(A_{ij})\leq 4D, $$ where $D$ is the maximum distance of points of $G$ from 0, and $i$ and $j$ are adjacent. Letting $\alpha$ be the constant $(1-e^{-16D})/32D$, then the Lower Bound lemma of Baxter~[2], says that $$ \Bbb E_i(1-e^{-T_j})\geq\alpha\Bbb E_i(T_j). $$ Now if the path between $x$ and $y$ is given by $x=i_0,i_1,\ldots,i_n=y$, then $$ \Bbb E_x(1-e^{-T_y})=1-\prod_{r=0}^{n-1}\left(1-\Bbb E_{i_r} (1-e^{-T(i_{r+1})})\right). $$ Now, as $1-x\leq e^{-x}$, we can obtain the lower bound $$ \Bbb E_x(1-e^{-T_y}) % \geq 1-\prod_{r=0}^{n-1}\exp\left(-\Bbb E_{i_r}(1-e^{-T(i_{r+1})})\right) \geq 1-\prod_{r=0}^{n-1}\exp\left(-\alpha \Bbb E_{i_r}(T_{i_{r+1}})\right)=1-\exp(-\alpha\Bbb E_xT_y). $$ Finally, as $1-e^{-x}\geq x/2$ for $x$ in $[0,1]$, we have that $\Bbb E_x(1-e^{-T_y})\geq(\alpha/2)\Bbb E_xT_y$ for $d(x,y)$ less than $1/\alpha$. Thus $\rho^2(x,y)\geq c(\Bbb E_xT_y+\Bbb E_yT_x)=c\,d(x,y)$, where $c$ is a constant less than or equal to both $m\alpha/2$ and $m(1-e^{-\half})/2D$ (to mop up those $(x,y)$ for which $d(x,y)\geq1/\alpha$).\endbox We are now in a position to apply everything we have done in conjunction with the results of Marcus and Rosen~[4] on the local times of symmetric processes. They posit a symmetric 1-potential density $u_1(x,y)$, in our language $r_1(x,y)/\pi(y)$, which the proof of Theorem~8 told us has a continuous extension to $G\times G$. Their metric $(u_1(x,x)+u_1(y,y)-2u_1(x,y))^{1/2}$ is our metric $\rho$ of Theorem~8, which we found was equivalent to $\sqrt{d}$. Hence we can reformulate their theorems 1 and 8.1 to meet our context. \noindent{\bf Theorem 9.(Marcus and Rosen)} {\sl Suppose that $(G,d)$ is compact. Let $L=\{L(t,x):t\in\Bbb R^+,\ x\in G\}$ be the local time of $X$ on $G$. Then $L$ is continuous almost surely if and only if there exists a probability measure $m$ on $(G,d)$ such that $$ \lim_{\delta\downarrow0}\sup_{x\in G}\int_0^\delta \left({1\over\epsilon} \log{1\over m(B_d(x,\epsilon))}\right)^{1/2}\,d\epsilon = 0, $$ where $B_d(x,\epsilon):=\{y\in G:d(x,y)\leq\epsilon\}$.} \noindent{\it Proof of Theorem 9.} $X$ is a strongly symmetric standard Markov process with a continuous 1-potential density, so satisfies the Marcus and Rosen conditions. It only remains to replace $\rho$ with $\sqrt{d}$ in their equation (8.3) and change variables.\endbox If a local time does not exist everywhere, we can still make a statement: \noindent{\bf Theorem 10. (Marcus and Rosen)} {\sl Suppose that $(G,d)$ is locally compact and $N$ is a compact neighbourhood on which $d$ is finite. Let $L=\{L(t,x):t\in\Bbb R^+,\ x\in N\}$ be the local time of $X$ on $N$. Then $L$ is continuous almost surely if and only if there exists a probability measure $m$ on $(N,d)$ such that} $$ \lim_{\delta\downarrow0}\sup_{x\in N}\int_0^\delta \left({1\over\epsilon} \log{1\over m(B_d(x,\epsilon))}\right)^{1/2}\,d\epsilon = 0. $$ {\it Proof of Theorem 10.} We can merely consider the restriction of $X$ to $N$ and proceed as before, and note that $B_d(x,\epsilon)\subset N$ for all $x$ in $N$ for $\epsilon$ small enough. \endbox Although we cannot improve on the necessary and sufficient conditions of Theorems 9 and 10, in some particular situations we can derive sufficient conditions that are more easily verifiable. Let $e(j)$ denote the number of points adjacent to $j$ in $I$ which are further from 0 than $j$. In other words, $e(0)$ is the number of edges attached to node 0, and $e(j)$ is one fewer than the number of edges attached to node $j$ for all other $j$ in $I$. Then \noindent{\bf Theorem 11.} {\sl If (G,d) is compact, $d$ is uniformly Lipschitz continuous, and $e(j)$ is bounded above by some $E$, then the local time $L=\{L(t,x):t\in\Bbb R^+,\ x\in G\}$ is continuous almost surely if $$ \lim_{m\rightarrow\infty}\sup_{x\in\dG} \sum_{n=m}^\infty\sqrt{{1\over n}d(x_n,x)}=0, $$ where $x_n$ is the $n$th point on the path from 0 to $x$.} \noindent{\it Proof of Theorem 11.} We first need to define a measure $m$ on $G$, which we will express as a combination of a measure on $I$ and another on $\dG$. Calling these $m_1$ and $m_2$ respectively, we define $$ \eqalign{ m_1(x_n)&:= 2^{-n} |\{i\in I:\hbox{\rm $i$ is $n$ edges away from 0}\}|^{-1},\cr \hbox{\rm and}\qquad m_2(A_{x_n}^0\cap\dG)&:= \left(\prod_{r=0}^{n-1}e(x_r)\right)^{-1}.\cr} $$ Which is to say that $m_1$ distributes $2^{-n}$ of mass uniformly on the points of level $n$, and $m_2$ is the distribution on the boundary obtained by uniformly choosing from each of the $e(j)$ possible choices at node $j$. For convenience we have taken $m_1$ such that its total mass is two, though this makes no difference to anything. As the $e(j)$ are bounded, we can represent bounds for $m_1$ and $m_2$ as $$ \eqalign{ \log{1\over m_1(x_n)}&\leq n\log(2E),\cr \hbox{\rm and}\qquad \log{1\over m_2(A_{x_n}^0)}&\leq n\log(E),\cr} $$ which are useful linear bounds that we shall need later. We can set $m$ to be any appropriate combination of $m_1$ and $m_2$, such as $(\quarter m_1+\half m_2)$. The key inequality that we need is that for $x$ in $\dG$, $y$ in $A_{x_r}^0$, and $s\geq r$, then $$ d(x_s,y)\leq d(x_s,x*y)+d(y,x*y)\leq (K+1)d(x_r,x), $$ where $K$ is the uniform Lipschitz co-efficient. Replacing $(K+1)$ with $K$ we have that $$ A_{x_r}^0\subset B_d(x_s,\epsilon)\qquad\hbox{\rm for $\epsilon\geq Kd(x_r,x)$, $s\geq r$.} $$ Let us define $f$ to be the integrand of Marcus and Rosen, $$ f(x,\epsilon):= \left({1\over\epsilon}\log{1\over m(B_d(x,\epsilon))}\right)^{1/2}. $$ So we can get an upper bound for the integral of Theorem 9, by using our lower bound for $B_d(x_s,\epsilon)$ on the intervals $[Kd(x_r,x),Kd(x_{r-1},x)]$. Thus for $s\geq M+1$, $$ \eqalign{ \int_0^{Kd(x_M,x)}f(x_s,\epsilon)\,d\epsilon &\leq\sum_{r=M+1}^s \left(\log{2\over m_2(A_{x_r}^0)}\right)^{1/2} {\sqrt{K}\over2}\bigl(\sqrt{d(x_{r-1},x)}-\sqrt{d(x_r,x)}\bigr)\cr &\quad + \left(\log{4\over m_1(x_s)}\right)^{1/2}{\sqrt{K}\over2} \sqrt{d(x_s,x)}\cr &\leq c\left(\sum_{r=M+1}^s \sqrt{r}\bigl(\sqrt{d(x_{r-1},x)}- \sqrt{d(x_r,x)}\bigr)+\sqrt{sd(x_s,s)}\right)\cr &= c\left(\sqrt{(M+1)d(x_M,x)}+\sum_{r=M+1}^{s-1}(\sqrt{r-1}-\sqrt{r}) \sqrt{d(x_r,x)}\right)\cr &\leq c\left(2\sqrt{Md(x_M,x)}+\sum_{r=M+1}^{s-1}\sqrt{\frac{r} d(x_r,x)}\right).\cr} $$ Where $c$ is some constant. The case $s\leq M$ is simpler as $$ \eqalign{ \int_0^{Kd(x_M,x)}f(x_s,\epsilon)\,d\epsilon & \leq \left(\log{4\over m_1(x_s))}\right)^{1/2}{\sqrt{K}\over2} \sqrt{d(x_M,x)}\cr & \leq c\sqrt{sd(x_M,x)}\cr & \leq c\sqrt{Md(x_M,x)}.\cr} $$ In other words, combining both cases we have that (for some new constant $c$) $$ \sup_{y\in[0,x]}\int_0^{Kd(x_M,x)}f(y,\epsilon)\,d\epsilon \leq c\left(\sqrt{Md(x_M,x)}+\sum_{r=M+1}^\infty \sqrt{\frac{r} d(x_r,x)}\right). $$ We must digress now, to get a bound for the first term on the right-hand side above. \noindent{\bf Lemma 12.} {\sl Let $a_n(x)$ be a non-negative real sequence which is decreasing in $n$ for each $x$ in some index set $X$.} $$ \hbox{\sl If}\quad \lim_{m\rightarrow\infty}\sup_{x\in X}\sum_{n=m}^\infty a_n(x)=0, \quad\hbox{\sl then}\quad \lim_{n\rightarrow\infty}\sup_{x\in X}na_n(x)=0. $$ {\it Proof of Lemma 12.} Fix $\epsilon$ positive, and $m$ an integer. For each $x$ in $X$, let the set $\{n\geq m: na_n(x)\geq\epsilon\}$ be denoted as the increasing sequence $(n^x_i)_{i=1}^{i_x}$, where $i_x$ may be infinite. It will be convenient to define $n^x_0$ to be $m$. As the sequence $a_n(x)$ is decreasing in $n$, we know that $$ a_n(x)\geq a_{n^x_i}(x) \geq {\epsilon\over n^x_i},\qquad \hbox{\rm for $n^x_{i-1}\leq n < n^x_i$.} $$ Thus $$ \sum_{n=m}^\infty a_n(x)\geq \epsilon\sum_{i=1}^{i_x} \left(1-{n^x_{i-1}\over n^x_i}\right). $$ Setting $r_i(x)$ to be the ratio $n^x_{i-1}/n^x_i$, there are then three possible cases: \item{(i)}if $i_x=0$, then the bound is zero. \item{(ii)}if $r_i(x)$ is less than $\half$ for any $i$, then a lower bound for the line above is $\half\epsilon$. \item{(iii)}if $r_i(x)$ is at least $\half$ for all $i$, then using the inequality that $1-y\geq-\half\log y$ for $\half\leq y\leq 1$, we may deduce that the lower bound is at least $\half\epsilon\log(i_x/m)$. As $m$ gets larger, eventually case (ii) becomes impossible. Then, it is also impossible for $\sup_x i_x$ to be infinite, by case (iii). So, once $m$ is larger than $\sup_x i_x$, case (i) applies for every $x$, or in other words, $\sup_x ma_m(x)\leq\epsilon$. In fact, what we have actually proved is that $$ \sup\{n:a_n(x)\geq \epsilon/n\}\leq e\min\bigl\{n:\sum_{r=n}^\infty a_r(x)\leq\half\epsilon\bigr\}, $$ which provides the necessary uniformity.\endbox Returning to the proof of Theorem 11, we can use Lemma 12, choosing the decreasing sequences $a_n(x)$ to be $\sqrt{{1\over n}d(x_n,x)}$. Taking the supremum of our previous upper bound, we get $$ \sup_{y\in[0,x]}\int_0^{Kd(x_M,x)}f(y,\epsilon)\,d\epsilon\leq c(S_1(M)+ S_2(M)), $$ where $$ \eqalign{S_1(m)&:=\sup_{x\in\dG}\sum_{n=m}^\infty\sqrt{\frac{n}d(x_n,x)},\cr \hbox{\rm and}\quad S_2(m)&:=\sup_{x\in\dG}md(x_m,x).\cr} $$ As $\dG$ is compact, $\delta_M:=\inf\{Kd(x_M,x):x\in\dG\}$ is positive for each $M$, but also tends to zero as $M$ goes to infinity. Replacing the limit of integration with $\delta_M$ and taking the supremum over all points $x$, we finally achieve $$ \sup_{x\in\dG}\int_0^{\delta_M}f(x,\epsilon)\,d\epsilon\leq c(S_1(M)+ S_2(M)), $$ which gives the desired result.\endbox \bigskip\bigbreak\leftline{\bf 5. Conclusions} We have achieved a set of necessary and sufficient conditions for a point of the boundary to be reachable at all and another set characterising the regularity of such boundary points. The key object used was the $d$-metric on the tree which not only determined regularity but when all points are regular, it indicates exactly whether the local time can be chosen to be continuous. This has all been shown in the framework of a general `discrete' tree, but some obvious generalisations seem likely. In particular, to the continuum trees of Aldous~[1] and Krebs~[3]. These have nodes arbitrarily close together and are suited to a Brownian motion approach, rather than the chains used here. In our language, Krebs~[3] has shown that it is possible to run a Brownian motion on a continuum tree $(G,d)$ (assuming that $\dG$ is a dense subset, and that each node has no more than three edges) which is compact and has finite box-counting dimension, and that the process will have a local time which is jointly continuous. This is `consistent' with our Theorems 7 and 9, in which compactness gives the existence of local times and the `dimension' condition of Marcus and Rosen gives their continuity. It remains to determine rigorous necessary conditions for diffusions on classical and such continuum trees. One programme of attack on this problem would be to prove the continuous space analogues of the discrete results presented here. A start will be made in this direction in a subsequent paper. \bigskip\bigbreak\centerline{\bf References} {\frenchspacing\parindent=0pt\parskip=\medskipamount \everypar={\hangindent=12pt\hangafter=1\relax} 1. Aldous, D.J.: The Continuum Random Tree III. {\rm Ann. Probab.} {\bf 21}, 248--289 (1993) 2. Baxter, M.W.: Markov processes on the boundary of the binary tree. In: Az\'ema J. et al.:{\rm S\'eminaire de Probabilit\'es XXVI} (Lect. Notes Math., vol. 1526, pp. 210--224) Berlin Heidelberg New York: Springer 1993 3. Krebs, W.B.: Brownian motion on the Continuum Tree. (preprint) 4. Marcus, M.B., Rosen, J.: Sample Path Properties of the Local Times of Strongly Symmetric Markov Processes via Gaussian Processes. {\rm Ann. Probab.} {\bf 20}, 1603--1684 (1992) 5. Rogers, L.C.G., Williams, D.: Construction and Approximation of Transition Matrix Functions. {\rm Analytic and Geometric Stochastics}, suppl. to {\rm Adv. Appl. Probab.} {\bf 18}, 133--160 (1986) 6. Williams, D.: {\rm Diffusions, Markov Processes and Martingales, Vol.1: Foundations}. Chichester New York: Wiley 1979 } \end