%--- A separate LaTex file for figures is attached as last 35 lines of ---- %--- this file. Cut and use it as instructed in the comment line there. -- % 35 pages text + 2 figures. BODY \documentstyle[leqno]{article} % ----------------------------- % macro.tex (v940307) for LaTex % ----------------------------- \catcode`@=11 \@addtoreset{equation}{section} \def\theequation{\thesection.\arabic{equation}} \def\@begintheorem#1#2{\it \trivlist \item[\hskip \labelsep{\bf #1\ #2.\ }]} \def\@opargbegintheorem#1#2#3{\it \trivlist \item[\hskip \labelsep{\bf #1\ #2\ (#3).}]} \newtheorem{prp}{Proposition} \@addtoreset{prp}{section} \def\theprp{\thesection.\arabic{prp}} \catcode`@=12 \def\appendix{\par\setcounter{section}{0}\setcounter{subsection}{0} \def\thesection{\Alph{section}} \vspace{3.5ex plus 1ex minus .2ex}\par\noindent{\Large\bf Appendix} \nopagebreak\vspace{2.0ex plus .2ex}\nopagebreak\\ \nopagebreak} \newtheorem{lem}[prp]{Lemma}\newtheorem{thm}[prp]{Theorem} \newtheorem{cor}[prp]{Corollary} \newenvironment{prf}{\begin{trivlist} \item[{\em Proof.}]}{\ignorespaces \hfill $\Box$ \end{trivlist} \bigskip \par} \newenvironment{rem}{\begin{trivlist} \item[{\em Remark.}]}{\ignorespaces \end{trivlist} \bigskip \par} \def\prpb{\begin{prp}}\def\prpe{\end{prp}} \def\lemb{\begin{lem}}\def\leme{\end{lem}} \def\thmb{\begin{thm}}\def\thme{\end{thm}} \def\corb{\begin{cor}}\def\core{\end{cor}} \def\prfb{\begin{prf}}\def\prfe{\end{prf}} \def\remb{\begin{rem}}\def\reme{\end{rem}} \def\labelenumi{(\arabic{enumi})} \def\itmb{\begin{enumerate}}\def\itme{\end{enumerate}} \def\eqnb{\begin{equation}}\def\eqne{\end{equation}} \def\eqab{\begin{eqnarray}}\def\eqae{\end{eqnarray}} \def\eqsb{\begin{eqnarray*}}\def\eqse{\end{eqnarray*}} \def\arrb#1{\begin{array}{#1}}\def\arre{\end{array}} \def\tabb#1{\par\noindent\begin{tabular}{#1}} \def\tabe{\end{tabular}\par\noindent} \def\eqna#1{\label{e:#1}}\def\eqnu#1{(\ref{e:#1})} \def\prpa#1{\label{p:#1}}\def\prpu#1{Proposition~\ref{p:#1}} \def\prpi#1#2{Proposition~\ref{p:#1}~(\ref{i:#2})} \def\lema#1{\label{l:#1}}\def\lemu#1{Lemma~\ref{l:#1}} \def\thma#1{\label{t:#1}}\def\thmu#1{Theorem~\ref{t:#1}} \def\cora#1{\label{c:#1}}\def\coru#1{Corollary~\ref{c:#1}} \def\seca#1{\label{s:#1}}\def\secu#1{Section~\ref{s:#1}} \def\appu#1{Appendix~\ref{s:#1}} \newcount\cvno\global\cvno=0 \def\cv#1{\expandafter\ifx\csname cvno#1\endcsname\relax \global\advance\cvno by 1 \expandafter\xdef\csname cvno#1\endcsname{\hbox{$C_{\the\cvno}$}}\csname cvno#1\endcsname\else\csname cvno#1\endcsname\fi} % constants: \cv9 \cv0 \def\cvrn{\global\cvno=0} % resets counter \cvno \def\cvrs#1{\expandafter\let\csname cvno#1\endcsname =\relax} % clears \cv#1 %------------------ \def\Rom#1{\uppercase\expandafter{\romannumeral#1}} \def\defd{\stackrel{\rm def}{=}} \def\norm#1{\|#1\|} \def\limf#1{\displaystyle \lim_{#1\to\infty}} \def\mada{\hfill\par\hfil{\Huge NOT YET.}\hfil\par} \def\dsp{\displaystyle} \def\AHFA{\hbox{\vrule height16pt depth10pt width0pt}\displaystyle} %Adjustment of Heights for Fractions in Array %------------ \newcount\fgno\global\fgno=0 \def\fgl#1{\expandafter\ifx\csname fgno#1\endcsname\relax \global\advance\fgno by 1 \expandafter\xdef\csname fgno#1\endcsname{\the\fgno}\else \immediate\write16{Duplicate FGLABEL: #1.}\fi} \def\fgr#1{\expandafter\ifx\csname fgno#1\endcsname\relax \immediate\write16{Undefined FGLABEL: #1.}?\else \csname fgno#1\endcsname\fi} % order \fgl{f1} \fgl{f2}, refer fig.~\fgr{f1} or \figu{f1} \def\figu#1{Figure~\fgr{#1}} %------------ %other macros %------------ \newenvironment{oprf}{\begin{trivlist} \item[{\em Outline of Proof.}]}{ \ignorespaces \hfill $\Box$ \end{trivlist} \bigskip \par} \newenvironment{prfof}[1]{\begin{trivlist} \item[{\em Proof of #1.}]}{ \ignorespaces \hfill $\Box$ \end{trivlist} \bigskip \par} \newenvironment{defi}{\begin{trivlist} \item[{\bf Definition.}] \it }{ \ignorespaces \end{trivlist} \bigskip \par} \def\oprfb{\begin{oprf}}\def\oprfe{\end{oprf}} \def\prfofb{\begin{prfof}}\def\prfofe{\end{prfof}} \def\defb{\begin{defi}}\def\defe{\end{defi}} \def\tblb[#1]{\begin{table}[#1]}\def\tble{\end{table}} \def\tbla#1{\label{tb:#1}}\def\tblu#1{Table~\ref{tb:#1}} \def\integers{{\bf Z}} \def\pintegers{{\bf Z_{+}}} \def\reals{{\bf R}} \def\twreals{{\bf R^2}} \def\sg{Sierpinski gasket} \def\rg{scale-irregular $abb$-gasket}\def\rgs{scale-irregular $abb$-gaskets} \def\rag{scale-irregular $aaa$-gasket}\def\rags{scale-irregular $aaa$-gaskets} \def\Fgasket{H} \def\prb#1{{\rm Prob[\;}#1{\rm \;]}} \def\EE#1{{\rm E[\;}#1{\rm \;]}} \def\VV#1{{\rm V[\;}#1{\rm \;]}} \def\varia#1#2{{\rm V^{#1}[\ }#2\; {\rm ]}} \def\paths{\tilde{\omega}} \def\Paths{\tilde{\Omega}} \def\edges{{\cal E}} \def\duals{{\bf C^{\edges}}} \def\FF{F} \def\tFF{\tilde{F}} \def\vphi{\phi} \def\vF{\FF} \def\gg{g} \def\tPi{\tilde{\Pi}} \def\tA{\tilde{A}} \def\tB{\tilde{B}} \def\vZ{\vec{Z}} \def\WW{\tilde{W}} \def\vPhi{\Phi} \def\xw{\tilde{w}}\def\xa{\tilde{a}}\def\tC{\tilde{C}} \def\Ppt#1#2#3{P^{(#1)}_{#2}{\rm [\;}#3{\rm \;]}} \def\Ept#1#2#3{E^{(#1)}_{#2}{\rm [\;}#3{\rm \;]}} \def\Qpt#1#2#3{Q^{(#1)}_{#2}{\rm [\;}#3{\rm \;]}} \def\Qlmt#1#2{Q_{#1}{\rm [\;}#2{\rm \;]}} \def\tX{\tilde{X}} \def\Triangles#1{{\cal T}_{#1}} %-- end of macros ---------- \title { Asymptotically one-dimensional diffusions on scale-irregular gaskets. } \author { Tetsuya Hattori \\ {\small Faculty of Engineering, Utsunomiya University, } \\ {\small Ishii-cho, Utsunomiya 321, Japan } \\ {\small e-mail: hattori@tansei.cc.u-tokyo.ac.jp } } \begin{document} \maketitle \begin{abstract} A simple class of fractals which lack exact self-similarity is introduced, and the asymptotically one-dimensional diffusion process is constructed. The process moves mostly horizontally for very small scales, while for large scales it diffuses almost isotropically, in the sense of the off-horizontal relative jump rate for the decimated random walks of the process. \par An essential step in the construction of diffusion is to prove the existence of appropriate time-scaling factors. For this purpose, a limit theorem for a discrete-time multi-type supercritical branching processes with singular and irregular (varying) environment, is developed. % \bigskip \par \noindent {\em Mathematics Subject Classification: } 60J60, 60J25, 60J85, 60J15 \end{abstract} \bigskip \par \noindent {\bf Running title: Asymptotically one-dimensional diffusion on scale-irregular gasket} %---------------------------------------------------------------------- \section{Introduction.} \seca{s1} % rnd1 (v940529) \fgl{abb} In this paper we construct asymptotically one-dimensional diffusion processes on the \rgs. We generalize the \sg, a triangle based fractal, to define the \rgs, which we introduce as simple examples of finitely ramified fractals that are scale-irregular, i.e. do not have exact self-similarity. Let $\{ (a_N,b_N),\ N\in\integers \}$ be a sequence of pair of positive integers. Let $\Fgasket'_0$ be the set of vertices and edges of a triangle, considered as a graph. Join $a_0+2b_0\ \Fgasket'_0$s' as in \figu{abb} to form a triangle $\Fgasket'_{-1}$, so that one side of $\Fgasket'_{-1}$ is composed of $a_0+1\ \Fgasket'_0$s' and the other two sides are composed of $b_0+1\ \Fgasket'_0$s'. Repeat this procedure recursively to obtain $\Fgasket'_{-n-1}$ from $a_{-n}+2b_{-n}\ \Fgasket'_{-n}$s', for $n\in\pintegers$. We regard one of the three vertices of $\Fgasket'_{-n}$ to be the origin $O$ and regard $\Fgasket'_{-n} \subset \Fgasket'_{-n-1}$. Let $\Fgasket_0$ be the two copies of the infinite graph (extending infinitely outward) ${\displaystyle \bigcup_{n=0}^{\infty} \Fgasket'_{-n}}$ joined at the origin $O$. Next, define $\Fgasket_1 \supset \Fgasket_0$ by adding a structure (bonds and vertices) similar to the structure of $\Fgasket'_{-1}$ in \figu{abb}, but with $(a_0,b_0)$ replaced by $(a_1,b_1)$, to each of the unit triangle. Repeat this procedure recursively inwards and add substructure of $a_{N+1}+2b_{N+1}$ triangles to each of the smallest triangle in $\Fgasket_N$ to obtain $\Fgasket_{N+1} \supset \Fgasket_N$. We call the graph $\Fgasket_N$ a pre-gasket (of scale $N$). Let $G_N$ denote the set of vertices in $\Fgasket_N$. Each element of $G_N$ (including $O$) has four $N$-neighbor points; by an $N$-neighbor point we mean a vertex in $\Fgasket_N$ joined by an edge of $\Fgasket_N$. If $N>N'$ then $G_N \supset G_{N'}$. Put $\dsp \lambda_n=\prod_{k=1}^{n} \min\{a_k+1,b_k+1\}^{-1}$, $n\in\pintegers$. We introduce metric $d$ such that $d(x,y)=\lambda_n$ if $x$ and $y$ are $n$-neighbor points. See \appu{sa}. $\dsp G=\overline{\bigcup_N G_N}=\overline{\bigcup_N \Fgasket_N}$ is the \rg. The definitions are independent of embedding into Euclidean spaces, but for simplicity, the terminology for subsequent explanations will be as if a \rg\ $G$ is embedded in $\twreals$ such that $x$-axis is contained in $G$ and $G$ is contained in upper half plane (e.g. horizontal means parallel to $x$-axis). If $a_N$ and $b_N$ are independent of $N$, the corresponding fractal has exact self-similarity. The \sg\ is the \rg\ with $a_N=b_N=1,\ N\in\integers$. If $b_N=a_N$, $N\in\integers$, which we call the \rags, there is an obvious local spatial symmetry (isotropy) shared with \sg. \par For a process $X$ taking values in $G$ we define $T_{n,i}(X)\,,\ n\in\integers\,$, (the time that $X$ hits $G_n$ for the $i+1$-th time, counting only once if it hits the same point more than once in a row) by $T_{n,0}(X)= \inf \left\{ t \ge 0 \, |\ X(t) \in G_n \right\}\,$, and \[ T_{n,i+1}(X)= \inf \left\{ t > T_{n,i}(X) \, |\ X(t) \in G_n \setminus \left\{ X(T_{n,i}(X)) \right\} \right\} \,,\ i=0,1,2,\cdots. \] For an integer $n$ and a Markov process $X$ on $G$ or on $G_N$ for some $N\ge n$, we call a simple random walk $X^{(n)}$ on $G_n$ defined by $X^{(n)}(i) = X(T_{n,i}(X))$ the $n$-decimated walk of $X$. By definition, \prpb\prpa{consistency} If $n0$, we define a simple random walk $X_{N,w}$ on $G_N$ as follows. At each integer time, the random walker jumps to one of the four $N$-neighbor points, and the relative rates of the jumps are $1$ (resp. $w$) for a jump in horizontal (resp. $\pm 60^{\circ}$ or $\pm 120^{\circ}$) direction. We prove in this paper the following. \thmb \thma{main} Assume that $\{ (a_N,b_N),\ N\in\integers \}$ is a bounded sequence of pairs of integers satisfying \eqnb \eqna{simple} a_N \ge 2,\ b_N \ge 2,\ b_N<2 a_N,\ \ N\in\integers, \eqne and let $G$ be the \rg\ defined by this sequence. Then there exist a sequence of positive numbers $w_N$, $N\in\integers$ satisfying \eqnb \eqna{a1} \limf{N} w_N = 0 , \eqne and a symmetric Feller process $X$ (a continuous $G$-valued strong Markov process whose transition operators map the space of bounded continuous functions into itself, symmetric with respect to a measure $\mu$ on $G$ defined by $\int f \,d\mu = {\limf{N}} \left(\prod_{k=0}^{N} (a_k+2b_k)^{-1}\right) \sum_{x\in G_N} f(x)$), such that for $N\in\integers$, the $N$-decimated walk of $X$ is equal in law to the random walk $X_{N,w_N}$. \thme The assumptions \eqnu{simple} are to avoid complications. We will prove \thmu{main} for any $w_0$ satisfying \eqnb \eqna{asymp} w_0 \in I \defd (0,\inf_N \{2a_N/b_N\} -1). \eqne From \prpu{consistency} and \thmu{main}, the $(N-1)$-decimated walk of $X_{N,w_N}$ is equal in law to $X_{N-1,w_{N-1}}$, from which it follows that the sequence $\{w_N\}$ satisfies a recursion relation \eqnb \eqna{wrec} w_{N-1}=f_{(a_N,b_N)}(w_N)\,,\ N\in\integers, \eqne where \eqnb \eqna{frec} f_{(a,b)}(w)=\frac{2w\{(1+a)b+(a\,b+a+b)w\}}{b(b+2)+2(b^2+a+b)w+b^2 w^2}\,. \eqne Proof of \eqnu{wrec} is elementary (but lengthy), and is similar to that of \cite[Proposition 1.1]{HHW93}. It is elementary to see that \prpb \prpa{wasymp} If \eqnu{simple} and \eqnu{asymp} are satisfied, there exists one and only one sequence $\{w_N\}$ which satisfies \eqnu{wrec} and which is in the open interval $I$. Moreover, $\{w_N\}$ is strictly decreasing and satisfies \eqnu{a1}. $ \dsp \limf{n} \frac{w_{n+s}}{w_n} \prod_{k=1}^{s} \delta_{n+k} =1$ uniformly in $s\in\pintegers$, where $\dsp \delta_k \defd \frac{2(1+a_k)}{2+b_k} >1$. For \rags\ (i.e. $b_N=a_N$), it also holds that $I=(0,1)$ and $\dsp \lim_{N\to -\infty} w_N=1$. \prpe The ratio of the rate for a off-horizontal to horizontal jump of $X_{N,w_N}$ is $w_N$, hence \eqnu{a1} means that on small scales the process favors horizontal moves, while $w_N>0$ means that the process span the whole fractal space and is not confined in a line. For spatially symmetric \rags, $\lim_{N\to -\infty} w_N=1$, which implies that isotropy is asymptotically restored. Not much studies has been done on this diffusion. The asymptotically one-dimensional diffusion is first constructed on the \sg\ \cite{HHW93}. \cite{V} gives a characterization of the diffusion on the \sg\ by exit distributions. \par The fractals may be regarded to have ^^ obstacles' or holes in the space, when compared to uniform Euclidean spaces. Intuitively, a random walker that favors horizontal motion performs a one-dimensional random walk between a pair of obstacles, and eventually is forced to move in off-horizontal direction before they could move further horizontally. There are obstacles of various scales (sizes), separated by distances of the same order as their scales, hence globally, the random walker is scattered almost isotropically. This picture may be regarded as a new mechanism of homogenization, unique to fractals. The intuitive picture of isotropy restoration can be made mathematically persuasive through analyses of renormalization groups \cite{HHW93,HHW87}. The intuition implicitly guided the studies in \cite{HHW93}, but in spite of the generality in the intuition, it was not clear how to obtain such diffusions for fractals which lack exact self-similarity. Also the statements for the diffusion in that work were not referring to the properties which explicitly embodied the picture. It is the purpose of this paper to report some positive answers (\thmu{main}) to these points. \medskip\par We construct the diffusion as a weak limit of $X_{N,w_N}([L_N t])$, $N\in\integers$, for a time-scaling constant $L_N$. A key step in the construction is an asymptotic estimate of number of steps of $X_{N,w_N}$, whose expectation value is $L_N$. We apply a limit theorem for discrete-time multi-type supercritical branching processes with singular and irregular environment. We need multi-type branching processes because the horizontal and off-horizontal jumps have different transition probabilities. Branching rates change with the generation $N$ (irregular environment) because the substructure of a triangle in the pre-gasket varies with its scale $N$. Environment varies also because the transition probabilities of the random walk $X_{N,w_N}$ vary with $N$. In particular, birth rates of types corresponding to the numbers of off-horizontal jumps approach $0$ as $N\to\infty$ (singular environment). Compared with existing related results, there are two major complications arising from these requirements; criterion for supercriticality, and scaling factor for total number of descendants. For a construction of spatially symmetric diffusion on an exact self-similar finitely ramified fractal \cite{Kus,BP,L,Kum}, the expectation of off-spring for the associated branching process is a constant matrix independent of generation $N$. For a construction of asymptotically one-dimensional diffusion on an exact self-similar finitely ramified fractal \cite{HHW93,HW}, the off-spring expectation matrix has a limit as $N\to\infty$. In these cases, the largest eigenvalue of the (limit of) off-spring expectation matrix gives the (asymptotic) growth rate of descendant expectations and governs supercriticality. A pioneering work for scale-irregular fractals by Hambly \cite{Ham} deals with spatially symmetric diffusions on fractals called $HSG(\bar{\nu})$ (which have much in common with \rags\ as far as construction of diffusions are concerned). Due to the spatial symmetry, the associated branching process is of one-type, hence the off-spring expectation is one-dimensional, which gives the growth rate. In the present study, off-spring expectation is a multi-dimensional matrix, and neither is constant nor has a limit. Thus a criterion for supercriticality cannot be given in terms of growth rates. Furthermore, the ratios of expectations of the population between different types are unbounded, which obscures at first site, the existence of scaling factor for total descendant numbers. \par Our approach is partly inspired by a study on multi-type branching processes in random environment by Cohn. Much of our proof of \prpu{Cohn} follows the idea in \cite{Cohn}. In that work, a probability measure on environments is considered, and the assumptions on stationarity and ergodicity implicitly assured the last two assumptions in \prpu{Cohn} (including supercriticality) to hold almost surely. This approach is not suitable for our purpose to consider singular environment, where some of the branching rates vanish in the limit. To formulate a sufficient condition of supercriticality in \thmu{limit}, we introduce a recursion relation in \appu{sd} which reflects recursive nature of branching processes. We apply this recursion relation also to prove continuity of limit distribution in \thmu{cont}. The idea of using recursion relation to prove continuity originally appeared in \cite[Lemma 2.7]{HHW93}, which we refine to put it into a framework of branching processes, and generalize to handle irregular environments. It turns out in \prpu{total} that the existence of scaling factor for total descendant follows from a fact that the distribution of normalized population converge to a limit independent of types. Consideration on the branching processes may be interesting in its own respect, so we will discuss this in \secu{s3} independently of other sections. \par To apply the general theory of branching processes to the diffusion, we consider in \secu{s2} estimates for generating functions. The calculations are lengthy, for some of which the author used REDUCE, a computer program for rigorous formula reduction (\prpu{REDUCE}). We use these basic estimates to obtain estimates for number of steps of $X_{N,w_N}$, to which one can apply \cite[Sect. 3]{HHW93}. %---------------------------------------------------------------------- \section{Branching process with singular and irregular environment.} \seca{s3} % rnd3 (v940529) Let $d\ge 2$ be an integer and put $\edges\defd \{1,2,3,\cdots,d\}$. Consider a discrete time $d$-type branching process $\vZ_N = (Z_{N,j}$, $j\in\edges)$, $N\in\pintegers$. Given $n\in\pintegers$ and $i\in\edges$, let \[ \vZ_{n,N,i} \defd ( Z_{n,N,i,j}\,,\ \ j\in\edges),\ \ \ N=n,n+1,\cdots,\] be random vectors which give the distribution of the number of descendant at time $N$ from a single ancestor of type $i$ at time $n$. We have, for $r\in\pintegers$ and $j\in\edges$, \[ Z_{n+r,j}= \sum_{i\in\edges} \sum_{u=1}^{Z_{n,i}} Z_{n,n+r,i,j,u} \,, \] where $(Z_{n,n+r,i,j,u}\,,\ j\in\edges)$, $u\in\pintegers$, are i.i.d.\ copies of $\vZ_{n,n+r,i}$ when conditioned on $Z_{n,i}$. Let $\{e_n\}$ be a non-negative sequence. \prpb \prpa{Cohn} Assume that following three conditions hold for each $i\in\edges$. \itmb \item Uniform estimates for second moments of $\dsp W_{nNij} \defd \frac{Z_{nNij}}{\EE{Z_{nNij}}}$; \[ \arrb{c} \AHFA \dsp v \defd \sup_{n\in\pintegers} \sup_{N\ge n+n_0} e_n\,\EE{W_{nNij}^2} < \infty,\ \ j\in\edges\,, \\ \AHFA \dsp \limf{p} \sup_{N\ge n+n_0} \EE{W_{nNij}^2;\ W_{nNij}>p} =0,\ \ j\in\edges, n\in\pintegers\,, \arre \] for some constant $n_0\in\pintegers$. \item For each $n\in\pintegers$, $\dsp \gamma_{ni} \defd \limf{N} \frac{\EE{Z_{nNij}}}{\EE{Z_{nN1j}}} > 0$ exist, positive and independent of $j\in\edges$. \item $e_N \,Z_{Nj}$ diverges in probability to infinity; $\dsp \lim_{N\to\infty} \prb{e_N \,Z_{Nj} \ge p} = 1$, $j\in\edges$, $p>0$. \itme Then the sequence of normalized random vectors $(Z_{Nj}/\EE{Z_{Nj}},\ j\in\edges)$ converges in $L_2$ as $N\to\infty$ to a random vector $(W,W,\cdots,W)$ with $\EE{W}=1$. \prpe Proofs of the results in this section is postponed to the end of the section. Generalization to include $e_N$ is for our application in \secu{s2}. A simple sufficient condition for the existence of $\gamma_{ni}$ is given in \appu{sc}, in terms of off-spring expectation matrices $A_N$ ($ A_{Nij} = \EE{Z_{N-1,N,i,j}}$). The last assumption states supercriticality. One of our main concern here is a useful condition for the last assumption to hold. \defb A family of sequences of pairs of reals $\{(x_{k,n},y_{k,n})$, $n=0,1,\cdots,k\}$, $k\in\pintegers$, is said to satisfy the assumption R, if there exist sequences of non-negative numbers $\{a_n\}$, $\{w_n\}$, $\{w'_n\}$, $n\in\pintegers$, satisfying $ 2 \le \inf_n a_n$, $\sup_n a_n < \infty$, and $\dsp \max\{w_n,w'_n\} \le \min\{1,\ C_w \delta^{-n}\}$, $n\in\pintegers $, for constants $C_w>0$ and $\delta > 1$, such that \eqsb x_{k,n} &\le& x_{k,n+1}^{a_{n+1}}+w_{n+1} \, \min\{1-x_{k,n+1}^{a_{n+1}}\,,\ y_{k,n+1}\} \,,\ \ \\ y_{k,n} &\le& x_{k,n+1}+ w'_{n+1} \, y_{k,n+1} \,,\ \ \ \ 0\le n\le k\,, \eqse hold for all $k\in\pintegers$. Similarly, $\{(x_{k,n},y_{k,n})$, $n\in\pintegers\}$, $k\in\pintegers$, is said to satisfy the assumption R, if similar relation hold for $n\in\pintegers$ and $k\in\pintegers$. \defe \thmb \thma{limit} Assume that for some $j_0\in\edges$, $Z_{0,j}=1$, $j=j_0$, and $Z_{0,j}=0$, otherwise. Let $p>0$ and $j\in\edges$. Suppose that there exists an integer $n_0$ and a non-empty subset $\edges' \subset \edges$, not equal to $\edges$, such that the family of sequences $\{(x_{k,n},y_{k,n})\}$ defined by \eqsb x_{k,n} &=& \max_{i\in\edges'} \prb{e_{n_0+k} \,Z_{n,n_0+k,i,j}1 \,. \eqne Then \[ \lim_{N\to\infty} \prb{e_{N} \,Z_{N,j} \ge p} = 1 \,. \] \thme The assumption \eqnu{Rxkk} is an ^^ a priori estimate' that $\prb{e_{n_0+k} Z_{k,n_0+k,i,j} p$ then $\dsp \prb{X \le p} \le 1-d+\sqrt{d^2-1}$, where $d=1+2^{-1} \,\VV{X} \, (\EE{X}-p)^{-2}$. \prpe The next statement is on the existence of norming factor for total descendant numbers. \prpb \prpa{total} Assume that the sequence $\dsp (Z_{N,j}/\EE{Z_{N,j}}$, $j\in\edges)$, $N\in\pintegers$, converges in probability as $N\to\infty$ to a random vector $(W,W,\cdots,W)$. Then $\dsp \frac{\sum_{j\in\edges} Z_{N,j}}{\sum_{j\in\edges} \EE{Z_{N,j}}} $ converges in probability as $N\to\infty$ to $W$. \prpe We complete our list of the results with a sufficient condition for the continuity of the limit distribution, stated in terms of the assumption R. Let $W_{n,i}$, $n\in\pintegers$, $i\in\edges$, be real valued random vectors, and let \[ \Phi_{n,i}(t) \defd \EE{\exp \left( \sqrt{-1} \, t \, W_{n,i}\right)}\,, \] denote the characteristic function. We assume an ^^ a priori' estimate of the form \eqnb \eqna{apriori} |\Phi_{n,i}(t)| \le 1 - C_{n} \, t^2 \,,\ \ -t_n < t < t_n\,,\ n\ge n_0\,,\ i\in\edges', \eqne for some non-empty subset $\edges' \subset \edges$ not equal to $\edges$, an integer $n_0$, and positive reals $C_{n}$ and $t_n$. \thmb \thma{cont} Assume that $\{t_k,\ k\in\pintegers\}$ in \eqnu{apriori} diverges to infinity as $k\to\infty$ exponentially fast at most ($\dsp \limsup_{k\to\infty} t_k^{1/k} < \infty$), and satisfies \[ \theta \defd \inf_{k;\;\exists t_j0 \,. \] If for any sequence of reals $\{s_k,\ k\in\pintegers\}$ the family of sequences $\{(\tilde{x}_{k,n},\tilde{y}_{k,n})$, $n\in\pintegers\}$, $k\in\pintegers$, defined by \eqsb \tilde{x}_{k,n} &=& \max_{i\in\edges'} \left| \Phi_{n_0+n,i}(s_k) \right| \\ \tilde{y}_{k,n} &=& \max_{i\in\edges\setminus\edges'} \left| \Phi_{n_0+n,i}(s_k) \right| \,, \ \ \ n\in\pintegers\,,\ k\in\pintegers\,, \eqse satisfies the assumption R, and if \[ \liminf_{k\to\infty} \left( t_k^2 \, C_{k} \, \prod_{\mu=0}^{k-n_0} a_\mu \right)^{1/k} > 1 \,, \] holds with $a_{\mu}$ as in the assumption R, then the distribution of $W_{n,i}$ is continuous for all $n\in\pintegers$ and $i\in\edges$. \thme The intuition for the assumptions is similar to those for \thmu{limit}, with $W_{n,i}$ being a weak limit of $\dsp \frac{\sum_j Z_{nNij}}{\sum_{k,j} \EE{Z_{0Nkj}}}$. \smallskip\par The rest of this section is devoted to the proofs of the stated results. \prfofb{\prpu{Cohn}} Since $W_{nNij} \ge 0$ and $\EE{W_{nNij}}=1$, the family of random variables $\dsp \{W_{nNij}\,,\ N=n,n+1,\cdots\}$ is tight, hence there exists a subsequence of integers $\{k_N\}$ such that $W_{n,k_N,i,j}$ converges weakly as $N\to\infty$ to a random variable $\WW_{nij}$. By assumption $\EE{W_{nNij}^2}$ is uniformly bounded in $N$, which, with the tightness, implies that $\{W_{nNij}\}$ is uniformly integrable. The assumption also implies that $\{W_{nNij}^2\}$ is uniformly integrable. Weak convergence and uniform integrability imply convergence of expectations; \eqnb \eqna{expec} \EE{\WW_{n,i,j}} = \limf{N} \EE{W_{n,k_N,i,j}} =1\,. \eqne \eqnb \eqna{varia} \sup_{n\in\pintegers} e_n\,\EE{\WW_{n,i,j}^2} \le v \,. \eqne Put $\dsp W_{n,N,i,j,u} \defd \frac{Z_{n,N,i,j,u}}{\EE{Z_{n,N,i,j,u}}}$. $(W_{n,N,i,j,u}\,,\ j\in\edges)$, $u\in\pintegers$, are i.i.d.\ copies of $(W_{n,N,i,j}\,,\ j\in\edges)$ when conditioned on $Z_{n,i}$. Hence $(W_{n,k_N,i,j,u}$, $j\in\edges$, $u\in\pintegers)$, conditioned on $Z_{n,i}$, converges weakly as $N\to\infty$ to a random vector $(\WW_{n,i,j,u}$, $j\in\edges$, $u\in\pintegers)$, where $(\WW_{n,i,j,u}\,,\ j\in\edges)$, $u\in\pintegers$, are i.i.d.\ copies of $(\WW_{n,i,j}\,,\ j\in\edges)$ when conditioned on $Z_{n,i}$. Hence \eqnu{expec} and \eqnu{varia} imply, for positive integer $p$, \[\arrb{l} \AHFA \dsp \EE{\left( Z_{ni}^{-1}\,\sum_{u=1}^{Z_{ni}} (\WW_{niju}-1) \right)^2;\ Z_{ni}\ge p} = \sum_{q=p}^{\infty} q^{-1} \EE{(\WW_{nij1}-1)^2\,;\ Z_{ni}=q} \\ \le (v/e_n+1)/p\,. \arre\] This implies, with the assumption on supercriticality and Chebyshev's inequality, that for $\eta>0$ and $\epsilon>0$, there exists $n_0$ such that if $n\ge n_0$ then \[\arrb{l} \AHFA \dsp \prb{\left| Z_{ni}^{-1}\,\sum_{u=1}^{Z_{ni}} (\WW_{niju}-1) \right| \ge \epsilon} \\ \AHFA \dsp \le \prb{\left| Z_{ni}^{-1}\,\sum_{u=1}^{Z_{ni}} (\WW_{niju}-1) \right| \ge \epsilon\,,\ Z_{ni}\ge \frac{2(v+e_n)}{\eta\,\epsilon^2\,e_n}}+\eta/2 \ \le\ \eta \,. \arre\] Convergence in probability follows; \eqnb \eqna{inprob} \limf{n} \prb{\left| Z_{ni}^{-1}\,\sum_{u=1}^{Z_{ni}} \WW_{niju}-1 \right| \ge \epsilon} = 0 \,,\ \ \epsilon>0. \eqne The second assumption in the statement and a property of branching process \eqnb \eqna{brprexpec} \EE{Z_{N,j}}= \sum_{k\in\edges} \EE{Z_{n,k}} \, \EE{Z_{n,N,k,j}} \eqne implies that the limit \[ \beta_{n,i} \defd \limf{N} \frac{\EE{Z_{n,k_N,i,j}}}{\EE{Z_{k_N,j}}} =\frac{\gamma_{n,i}}{\sum_{k} \EE{Z_{n,k}} \, \gamma_{n,k}} \,, \] exists, positive, independent of $j$, and satisfies $\dsp \sum_{i\in\edges} \beta_{ni} \, \EE{Z_{ni}} = 1 $. This, with \eqnu{inprob} and the non-negativity of $Z$ and $\WW$ implies convergence in probability, \eqnb \eqna{bWZ} \limf{n} \prb{ \left| \sum_{i\in\edges} \left(\beta_{ni} \, \sum_{u=1}^{Z_{ni}} \WW_{niju} \right) - \sum_{i\in\edges} \beta_{ni} \, Z_{ni} \right| > \epsilon }=0 \,, \eqne for $\epsilon>0$. Note that in \eqnu{bWZ} everything except possibly $\WW_{niju}$ is independent of the choice of subsequence $\{k_N\}$. Put \[ \xi_n(x) \defd \limf{N} \prb{ Z_{k_N,j}/\EE{Z_{k_N,j}} \le x_j\,,\ j\in\edges \mid \vZ_n} \,. \] $\xi_n(x)$ is a bounded martingale, hence converges as $n\to\infty$ to a random vector $\xi(x)$ a.s. The definitions of $\WW_{niju}$ and $\beta_{ni}$ with \eqnu{brprexpec} imply \[ \xi_n(x) = \prb{ \sum_{i\in\edges} \left(\beta_{ni} \, \sum_{u=1}^{Z_{ni}} \WW_{niju} \right) \le x_j\,,\ j\in\edges \mid \vZ_n} \,, \] on set of continuity points. This with \eqnu{bWZ} implies that $\xi(x)$ is independent of the choice of subsequence $\{k_N\}$. In particular, \[ \EE{\xi(x)}= \limf{N} \prb{Z_{k_N,j}/\EE{Z_{k_N,j}} \le x_j\,,\ j\in\edges } \] is independent of the subsequence, hence $Z_{N,j}/\EE{Z_{N,j}}$ converges weakly to a random vector with distribution function $\EE{\xi(x)}$. Furthermore, \eqnu{bWZ} implies that this random vector has equal components. Convergence in probability, and then in $L_2$, is now proved exactly as in \cite[step 4]{Cohn}. \prfofe \prfofb{\thmu{limit}} By definition $0\le x_{k,n} \le 1$ and $0 \le y_{k,n} \le 1$ for all $n$ and $k$. With the assumption R and \eqnu{Rxkk}, we see that $\{(x_{k,n},y_{k,n})\}$ satisfies all the assumption of \thmu{recineq}. \thmu{recineq} implies $\dsp \lim_{k\to\infty} \max\{x_{k,0},\ y_{k,0}\}=0$, which gives $\dsp \lim_{N\to\infty} \prb{e_N Z_{0Nij} \ge p} = 1$. \prfofe \prfofb{\prpu{Schwarz}} Put $Y=X-\EE{X}$, $v=\VV{X}=\VV{Y}$, $b=\EE{X}-p>0$, and $t=\prb{Y>-b}=\prb{X>p}$. $\dsp 0=\EE{Y} \le \EE{Y;\ Y\le -b} + \EE{Y;\ Y>0} $ implies $\dsp \EE{Y;\ Y>0} \ge b \, (1-t)$. Using Schwarz inequality we have \[t\,v \ge \prb{Y>0}\,\EE{Y^2;\ Y>0} \ge (\EE{Y;\ Y>0})^2 \ge b^2\,(1-t)^2\,.\] The statement follows by solving this algebraic inequality in $t$. \prfofe \prfofb{\prpu{total}} \eqsb \lefteqn{ \limf{N} \EE{\min\{1,\ \left| \frac{\sum_{j\in\edges} Z_{N,j}}{\sum_{j\in\edges} \EE{Z_{N,j}}}-W \right| \}} } \\ &\le& \limf{N} \EE{\sum_{j} \frac{\EE{Z_{N,j}}}{\sum_k \EE{Z_{N,k}}} \min\{1,\ \left| \frac{Z_{N,j}}{\EE{Z_{N,j}}} -W \right| \} } \\ &\le& \sum_{j\in\edges} \limf{N} \EE{\min\{1,\ \left| \frac{Z_{N,j}}{\EE{Z_{N,j}}} -W \right| \} } = 0 \,. \eqse The assumption implies the last equality. Hence the statement follows. \prfofe \prfofb{\thmu{cont}} Note that the definition and assumption on $\theta$ imply $0< \theta < 1/2$. Let $n_1 \ge n_0$, and let $\{s_k,\ k\in\pintegers\}$ be a sequence of reals satisfying \eqnb \eqna{tst} \theta \, t_{n_1+k} \le |s_k| \le t_{n_1+k}\,,\ \ k\in\pintegers\,. \eqne Put \eqsb x_{k,n} &=& \max_{i\in\edges'} \left| \Phi_{n_1+n,i}(s_k) \right| \\ y_{k,n} &=& \max_{i\in\edges\setminus\edges'} \left| \Phi_{n_1+n,i}(s_k) \right| \,, \ \ \ 0\le n \le k,\ k\in\pintegers\,. \eqse The assumption R implies that $\{(x_{k,n},y_{k,n})\}$ satisfies the recursion relation in the assumption of \thmu{recineq}. with $\{w_{n_1+n-n_0}\}$ and $\{a_{n_1+n-n_0}\}$ in place of $\{w_{n}\}$ and $\{a_{n}\}$. Also \eqnu{tst} and the assumptions on a priori estimates imply \[ \liminf_{k\to\infty} \left\{ -\log x_{k,k} \prod_{\mu=0}^{k} a_{n_1+\mu-n_0}\right\}^{\frac{1}{k}} \ge \liminf_{k\to\infty} \left\{ \theta^2 C_k t_k^2 \prod_{\mu=n_1-n_0}^{k-n_0} a_{\mu}\right\}^{\frac{1}{k-n_1}} >1 . \] We see that $\{(x_{k,n},y_{k,n})\}$ satisfies all the assumption of \thmu{recineq}, hence there exist positive constants $C_1$ and $C_2$ (which may depend on $n_1$ but not on $k$) such that \eqnb \eqna{expdecay} \left| \Phi_{n_1,i}(s_k) \right| \le C_1 \, \exp(-C_2 \, k^2)\,, \ \ \ k\in\pintegers\,,\ i\in\edges\,. \eqne Let $t\in\reals$ be a number satisfying $|t|> \min_j \{ t_j \}$, and let $t_k=\min\{t_j \mid t_j>|t|\}$. (The assumption $\limf{k} t_k =\infty$ implies that the minimum exists.) The definition of $\theta$ implies that there exists a $t_j$ satisfying $\dsp t_k > t_j > \theta \, t_k $. The choice of $t_k$ therefore implies that \eqnb \eqna{tk} \theta \, t_k < |t| < t_k \,. \eqne The assumption $\dsp \limsup_{k\to\infty} t_k^{1/k} < \infty$ implies that there exist positive constants $C_3$ and $C_4$ such that $t_k < C_3 \, C_4^k$, $k\in\pintegers$. With \eqnu{tk} we have $k > (\log |t| - \log C_3)/\log C_4$. This and \eqnu{tk}, \eqnu{tst}, and \eqnu{expdecay} imply \eqnb \eqna{expd2} \left| \Phi_{n_1,i}(t) \right| \le C_5 \, \exp(-C_6 \, (\log |t|)^2)\,, \eqne for sufficiently large $|t|$, with positive constants $C_5$ and $C_6$ independent of $t$. Therefore, if $n\ge n_0$, then $\Phi_{n,i}\in L_1(\reals)$ for all $i\in\edges$. By the assumption of recursion relation, it follows inductively that $\Phi_{n,i}\in L_1(\reals)$ for any $n \in \pintegers$, which implies that $W_{n,i}$ is continuous. \prfofe %---------------------------------------------------------------------- \section{Convergence of path measures.} \seca{s2} % rnd2 (v940529) %\\cv1-8 \fgl{type} Consider a pre-gasket $\Fgasket_N$ and its vertices $G_N$. Modulo translation in $\twreals$ and reflection with respect to vertical lines, there are $4$ types of points $A$, $B$, $D$, and $E$ in $G_{N}$ and $8$ types of edges (seen as ordered pair of points) $Ap$, $Ar$, $Bp$, $Bq$, $Br$, $Dq$, $Ep$, and $Er$, in $\Fgasket_{N}$ (\figu{type}). We put \[ \edges \defd \{ Ap,\ Ar,\ Bp,\ Bq,\ Br,\ Dq,\ Ep,\ Er \}\,. \] Note that these definitions can be taken independent of $N$. We will use the same notation without explicitly specifying $N$. \par Let $(a,b)$ be a pair of positive integers, and consider the case that $\Fgasket_N$-substructure of the pre-gasket $\Fgasket_{N-1}$ is parametrized by $(a,b)$: In the notation of \secu{s1}, $(a_N,b_N)=(a,b)$. Let $\Paths(a,b,i)$ be the set of walks on $G_N$ whose starting point $X$ and stopping point form an edge of type $i\in\edges$ in $\Fgasket_{N-1}$, and such that do not pass through points in $G_{N-1} \setminus \{X\}$: \[ \arrb{r} \Paths(a,b,i)=\{ \paths=(\paths(0),\cdots, \paths(L)) \subset G_N \ \mbox{for some $L$} \mid (\paths(0),\paths(L)) \mbox{ is type } i, \\ \paths(k) \not\in G_{N-1} \setminus \{\paths(0)\},\; \overline{\paths(k)\paths(k+1)} \in \Fgasket_N,\ k=0,\cdots,L-1 \}\,. \arre \] There is a natural one to one correspondence of the set $\Paths$ between different $N$s' by a scale transformation; $N$-dependence comes only from the possible differences in the parameters $(a,b)$. Hence we omit $N$ from the notation $\Paths(a,b,i)$. \par For $i \in \edges$ and $\paths \in \Paths(a,b,i)$, let $L_i(\paths)$ be the number of steps in $\paths$ (ordered pairs of the form $(\paths(i),\paths(i+1))$) which are of type $i$. Define \[ \FF_{i}(a,b;u) \defd \sum_{\paths\in\Paths(a,b,i)} \prod_{i\in\edges} {u_{i}}^{L_i(\paths)}\,,\ \ \ u\in \duals\,. \] In view of previous remarks, there is no $N$-dependence in $\FF_{i}$. $\FF_{i}$ is a generating function of number of steps of walks, hence is a rational function of $u$. \par Let $\Pi(w)={}^t(\Pi_{Ap}(w),\cdots,\Pi_{Er}(w))$ be as in \tblu{transition}. % \tblb[hbt] \caption{Transition probabilities} \tbla{transition} \begin{center} \tabb{|c||c|c|c|c|c|c|c|c|} \hline $i$ & $Ap$ & $Ar$ & $Bp$ & $Bq$ & $Br$ & $Dq$ & $Ep$ & $Er$ \\ \hline $\Pi_{i}(w)$ & $\frac{w}{2+2w}$ & $\frac{1}{2+2w}$ & $ \frac{w}{1+3w}$ & $ \frac{w}{1+3w}$ & $ \frac{1}{1+3w}$ & $ \frac{1}{2}$ & $ \frac{w}{1+w}$ & $ \frac{1}{1+w}$ \\ \hline \tabe \end{center} \tble % The random walk $X_{N,w_N}$ on $G_N$ defined in \secu{s1} is specified by a positive number $w_N$, defined in \eqnu{asymp} and \eqnu{wrec}. It is easy to see from \figu{type} that the (one-step) jump probability of $X_{N,w_N}$ for a jump of type $i$ is $\Pi_{i}(w_N)$. The definitions of $\Pi$ and $\FF$ together with \eqnu{wrec} imply \eqnb \eqna{PiF} \Pi(f_{(a,b)}(w)) = \FF(a,b;\Pi(w)) \,. \eqne Define $\sharp\edges$-dimensional matrix $A(a,b,w)$ by \[ A(a,b,w)_{ij} \defd \frac{\partial \FF_{i}}{\partial u_j}(a,b;u=\Pi(w)) \,. \] It turns out that $A(a,b,w)_{Dq,j}$ for $j\ne Ap$, $Ar$, $Dq$ diverge as $w\to 0$. We therefore define $\sharp \edges$-dimensional diagonal matrix $S(w) = \mbox{{\rm diag}}( S_i(w),\ i\in\edges )$ by \eqnb \eqna{S} S_{Dq}(w) = w \,,\ \ \ S_{i}(w) = 1 \,,\ i\ne Dq \,, \eqne and define rational functions $\tFF_{i}(a,b,w;u)$, $i\in\edges$, $u\in \duals$, by \eqnb \eqna{tFF} \tFF_{i}(a,b,w;u) \defd S_{i}(f_{(a,b)}(w)) \, \FF_{i}(a,b;S^{-1}(w) u) \,. \eqne Also we define a vector $\tPi(w)$ and a matrix $\tA(a,b,w)$ by \eqsb \tPi(w) &\defd& S(w) \, \Pi(w)\,, \\ \tA(a,b,w)_{ij} &\defd& \AHFA\dsp \frac{\partial \tFF_{i}}{\partial u_j}(a,b,w;u=\tPi(w)) = S_i(f_{(a,b)}(w)) \, A(a,b,w)_{ij} \, S_j^{-1}(w) \,. \eqse % \prpb \prpa{REDUCE} Let $a$, $a'$, $b$, and $b'$ be integers no less than $2$, and let $I$ be the interval defined in \eqnu{asymp}. Then the elements of matrix $\tA(a,b,w)$ are positive for $w\in I$ and \eqnb \eqna{supA} \sup_{w\in I} \tA(a,b,w)_{ij} < \infty \,,\ \ \ i\in\edges,\ j\in\edges \,, \eqne \eqnb \eqna{infA} \inf_{w,w'\in I} \left( \tA(a',b',w') \tA(a,b,w) \right)_{ij} > 0 \,, \ \ i\in\edges,\ j\in\edges \,, \eqne \eqnb \eqna{A22} \tA(a,b,0)_{Ar,Ar} \ge (a+1)^2 \,. \eqne For each $i\in\edges$ put $\gg_{a,b,i}(w,h) = \tFF_{i}(a,b,w;\tPi(w)+w\, h)$. Then $\gg_{a,b,i}$ is a rational function in $h\in\duals$ and $w$, analytic at $h=0$ for $w\in I$, and for each $j_1,\cdots,j_4 \in\edges$, \[ \sup_{w\in I} \left| \frac{1}{w} \frac{\partial^2 \gg_{a,b,j_1}}{\partial h_{j_2} \partial h_{j_3} }(w,h=0) \right| < \infty\,, \ \ \mbox{and }\ \sup_{w\in I} \left| \frac{1}{w} \frac{\partial^3 \gg_{a,b,j_1}}{\partial h_{j_2} \partial h_{j_3} \partial h_{j_4}}(w,h=0) \right| < \infty\,. \] \prpe \prfb $A(a,b,w)$ has non-negative elements because it is an expectation matrix for number of steps. From graphical considerations we see that every type $j$ of steps appear with positive probability for any $i$, hence they are positive. $\tFF$ is related to the generating function for number of steps of random walks (see also \prpu{branching} below), from which we see that $\gg_{a,b,i}(w,h)$ are rational functions both in $h$ and $w$, and analytic at $h=0$. The parameter $w$ is the relative jump rate of the random walk. Therefore for $w \in I$ there are no singularities. The only possible relevant singularities of $\tFF$ are at $w=0$. The estimates in the statement are proved by explicit calculation of $\tFF$ with aid of computer. We give in \appu{sb} explicit form of $\tA(a,b,w=0)$ obtained as the first derivatives of $\tFF$ using REDUCE. The explicit formula implies \eqnu{supA}, \eqnu{infA}, and \eqnu{A22}. The estimates on higher derivatives of $\tFF$ at $w=0$ is also obtained using REDUCE. See \appu{sb} for more information on computer aided proof of this Proposition. \prfe Note that \eqnu{supA} and \eqnu{infA} imply \eqnb \eqna{sumApos} \inf_{w\in I} \sum_{k\in\edges} \tA(a,b,w)_{kj}>0,\ \ j\in\edges\,. \eqne We go back to the gasket and look into the $N$-dependence. Assume that $\zeta \defd \{ (a_N,b_N),\ N\in\integers \}$ is a bounded sequence of pairs of integers satisfying \eqnu{simple}, which determines the gasket $G$. For $N\in\integers$, let $\vF_N=(\FF_{N,Ap},\cdots,\FF_{N,Er})$ be a $\duals$-valued function in $\sharp \edges \, (=8)$ variables defined by \eqnb \eqna{FN} \FF_{N,i}(u) \defd \FF_{i}(a_N,b_N;u)\,,\ i\in\edges. \eqne Also define a diagonal matrix, $\Pi_{N} \defd \mbox{{\rm diag}}( \Pi(w_N))$. Using $\vF_N$ and $\Pi_N$, we can write the generating functions for the number of steps of $X_{N,w_N}$. Let $i \in \edges$, $j \in \edges$, and $n \le N$. Let $Z_{nNij}$ be the random variable which counts the number of steps of type $j \in \edges$ between the times $T_{n,1}(X_{N,w_N})$ and $T_{n,0}(X_{N,w_N})$, under the condition that $\left(X_{N,w_N}(T_{n,0}(X_{N,w_N})),X_{N,w_N}(T_{n,1}(X_{N,w_N}))\right)$ forms an edge of type $i$ in $\Fgasket_n$. $T_{n,i}$ is a hitting time of $G_n$ defined in \secu{s1}. By strong Markov property of simple random walks, the distribution of $Z_{nNij}$ is independent of the starting point of $X_{N,w_N}$, and the random variables which count the number of steps of type $j \in \edges$ between the times $T_{n,k+1}(X)$ and $T_{n,k}(X)$, $k=0,1,2,\cdots$, are independent and equal in distribution to $Z_{nNij}$, under similar conditions. By definition, $\dsp Z_{nnij}=1\ (j=i),\ \ =0\ (j\ne i)$. % \prpb \prpa{branching} Fix $n\in\integers$ and $i\in\edges$. $(Z_{nNij}\,,\ j\in\edges)$, $N=n,n+1,\cdots$, is a multi-type branching process whose generating functions $\vphi_{nN}=(\phi_{nN,Ap},\cdots,\phi_{nN,Er})$ defined by $\dsp \phi_{nNi}(z) \defd \EE{\prod_{j\in\edges} z_j^{Z_{nNij}}}$, satisfy, for $nn, \eqne holds. The definitions of $\Pi_N$ and $\vF_N$ imply \eqnb \eqna{phiF1} \vphi_{n,n+1}(z) =\Pi_n^{-1} \vF_{n+1} (\Pi_{n+1} z)\,,\ \eqne which, together with \eqnu{phiconvo} implies \eqnu{phiF}. \prfe \prpu{wasymp} implies that some off-spring branching rates vanish as $N\to\infty$, hence we are considering branching process with singular environment. \par For integers $n$ and $N$ satisfying $n\le N$, define $\sharp\edges$-dimensional matrices \[ \tPi_{N} \defd \mbox{{\rm diag}}( \tPi(w_N)),\ \ \tA_{N} \defd \tA(a_N,b_N,w_N),\ \ \tB_{nN} \defd A_{n+1} A_{n+2} \cdots A_{N} \,.\] Then \eqnu{phiF}, \eqnu{PiF}, and \eqnu{wrec} imply \eqnb \eqna{EB} \EE{Z_{nNij}} = \left( \tPi^{-1}_{n} \, \tB_{nN} \, \tPi_{N} \right)_{ij} \,,\ \ i\in\edges,\ j\in\edges,\ N\ge n\,. \eqne Elementwise positivity of $A_N$ and hence of $B_{nN}$ were noted in \prpu{REDUCE}; \eqnb \eqna{ABpositive} \tA_{Nij}>0,\ \tB_{nNij}>0,\ \ i,j\in\edges,\ N>n\,. \eqne % \prpb \prpa{estimB} \itmb \item For each $n_0\in\integers$ there exist positive constants $C_1$ and $C_2$ such that if $n\in\integers$ and $N\in\integers$ satisfy $N-2\ge n \ge n_0$, then \eqsb \tB_{nNij} &\ge& C_1 \prod_{k=n+1}^{N} (a_k+1)^2 \,,\\ \tB_{nNij} \,\frac{w_N^2}{w_n^2} &\ge& C_2 \prod_{k=n+1}^{N} \left( 1+\frac{b_k}{2}\right)^2 \,, \ \ i\in\edges,\ j\in\edges. \eqse \item There exist limits \[ \gamma_{ni} \defd \lim_{N\to\infty} \frac{\tB_{nNij}}{\tB_{nN1j}} \,,\ \ n\in\integers,\ i\in\edges,\ j\in\edges\,, \] independent of $j$, which satisfy, for each $n_0\in\integers$, \[ 0 < \inf_{n\ge n_0,i\in\edges} \gamma_{ni} \le \sup_{n\ge n_0,i\in\edges} \gamma_{ni} < \infty \,. \] \item For each $n_0\in\integers$ there exists a positive constant $C_3$ such that if integers $n$, $m$, and $N$ satisfy $m-1\ge n\ge n_0$ and $N\ge \max\{m,n+2\}$, then \[ \sum_{k\in\edges} \tB_{n,m-1,i,k} \, \sum_{k'\in\edges} \tB_{mNk'j} \le C_3 \, \tB_{nNij}\,, \ \ \ i\in\edges,\ j\in\edges\,. \] \itme \prpe \prfb Since $\vF$ is rational in $w$, $\tA$ is also rational. Therefore \eqnu{A22} implies $\tA_{k22} \ge (a_k+1)^2 + C_4 \, w_k$, $k\in\integers$, where $C_4$ is a positive constant. \prpu{wasymp} implies that $\sum_{k\ge n} w_k < \sum_{k\ge n_0} w_k < \infty$, $n \ge n_0$, hence we obtain the first estimate for $\tB_{nNij}$. \prpu{wasymp} implies that for each $n_0$ there exists a constant $C_5>0$ such that $\dsp \frac{w_N}{w_n} \ge C_5 \, \prod_{k=n+1}^{N} \delta_k^{-1}$, $N\ge n\ge n_0$. With the first estimate, we have the second estimate. The estimates \eqnu{supA} and \eqnu{infA} imply that the elementwise positive matrices $\tA_{N}$, $N\in\integers$, satisfy the assumption of \thmu{Frobenius} in \appu{sc} with $q=2$. \thmu{Frobenius} then implies the second assertion. $\zeta \defd \{ (a_N,b_N),\ N\in\integers \}$ is a bounded sequence, hence contains finite number of distinct pairs; as far as $\zeta$ is concerned, taking supremum or infimum in $N$ is taking maximum or minimum among finite possibilities. Assume $N \ge m+2$. Then \[ \arrb{l} \AHFA \dsp \tB_{nNij} \ge \sum_{k\in\edges} \tB_{n,m-1,i,k} \sum_{k'\in\edges} \tA_{mkk'} \, \min_{k''\in\edges} \tB_{mNk''j} \\ \AHFA \dsp \ge \sum_{k} \tB_{n,m-1,i,k} \sum_{k'} \tB_{mNk'j} \inf_{\ell\in\edges, m' \ge n_0} \sum_{\ell'} \tA_{m' \ell \ell'} \frac{ \dsp \AHFA \inf_{k''} \{\tB_{mNk''j}/\tB_{mN1j}\} }{\dsp \AHFA \sharp \edges \sup_{k''} \{\tB_{mNk''j}/\tB_{mN1j}\} } \,. \arre\] It is now easy to see that the second assertion and \eqnu{sumApos} imply the third assertion. The cases $N =m$ and $N=m+1$ can be proved similarly. \prfe Put $\dsp W_{nNij} \defd \frac{Z_{nNij}}{\EE{Z_{nNij}}}$. % \prpb \prpa{higher} Let $i\in\edges$ and $j\in\edges$. For each $n_0\in\integers$ there exists a positive constant $C$ such that for all $N$ and $n\ge n_0$ satisfying $N\ge n+2$, \[ \EE{W_{nNij}^2} \le C \, \tPi_{ni} \, w_n^{-1} \,.\] Also, for each $n\in\integers$ the third moment is bounded in $N$; $\dsp \sup_{N\ge n} \EE{W_{nNij}^3} < \infty $. \prpe \prfb By taking derivatives of $\vphi_{nN}$ in \prpu{branching} we obtain \eqsb \lefteqn{ \EE{W_{nNij}^2} } \\ &=& \{ \sum_{k_1,k_2,k_3\in\edges} \sum_{m=n+1}^N \left(\tPi_n^{-1} \tB_{n,m-1} \right)_{i,k_1} \, \frac{\partial^2 \tFF_{k_1} }{\partial u_{k_2} \partial u_{k_3} } (a_m,b_m,w_m;\tPi(w_m)) \, \\ &&\times \left(\tB_{m,N} \tPi_N\right)_{k_2,j} \left(\tB_{m,N} \tPi_N\right)_{k_3,j} + \left(\tPi_n^{-1} \, \tB_{n,N} \, \tPi_N\right)_{i,j} \} \, \EE{Z_{nNij}}^{-2} \,. \eqse \prpu{wasymp} implies that for each $n_0$ there exists a constant $C>0$ such that \[ w_N \le C \, w_n\, \prod_{k=n+1}^{N} \delta_k^{-1}\,,\ \ N\ge n\ge n_0\,. \] With \prpu{REDUCE}, \eqnu{EB}, and \prpu{estimB} we have the bound for the second moment. The bound on the third moment is proved in a similar way. \prfe Let $\edges'\subset\edges$ be the set of horizontal edges; \eqnb \eqna{horizontal} \edges' \defd \{ Ar,\ Br,\ Er \}\,. \eqne Note that \tblu{transition} and \eqnu{S} imply that there exist positive constants $C$ and $C'$ such that for $w\in I$ we have \eqnb \eqna{tPi} C \le \tPi_i(w) \le C'\,,\ \ i\in\edges'\,,\ \ \ C\, w \le \tPi_i(w) \le C'\, w\,,\ \ i\in\edges\setminus\edges'\,. \eqne Define, for $N\in\pintegers$, \eqnb\eqna{LN} L_N \defd \sum_{i\in\edges}\sum_{j\in\edges} \EE{Z_{0Nij}}\,. \eqne The next Theorem shows that $L_N$ is the appropriate scaling factor for the random walk $X=X_{N,W_N}$ on $H_N$. Note that $\dsp T_{n,1}(X)-T_{n,0}(X)=\sum_{j\in\edges} Z_{nNij}$, where $i$ is the type of edge formed by the endpoints of $X$ in this time interval. % \thmb \thma{stepconverge} Let $m\in\integers$ and $i\in\edges$. $(W_{mNij}$, $j\in\edges)$, $N=m,m+1,\cdots$, converges in $L_2$ (hence in probability and in law) as $N\to\infty$. The limit is a random vector with equal components $(W_{mi},\cdots,W_{mi})$, satisfying $\EE{W_{mi}}=1$ and $\dsp \sup_{n\ge m} w_n \EE{W_{ni}^2} < \infty$. $\dsp L_N^{-1} \sum_{j\in\edges} Z_{mNij}$ converges in probability as $N\to\infty$ to $\dsp W'_{mi} \defd \frac{\gamma_{mi}\,W_{mi}}{\sum_{j,k} \EE{Z_{0mjk}} \, \gamma_{mk}}\,$, with $\gamma_{mi}$ as in \prpu{estimB}. The distribution of $W'_{mi}$ is continuous. \thme \prfb As noted in \prpu{branching}, $(Z_{mNij}$, $j\in\edges)$, $N=m,m+1,\cdots$, is a branching process. The number of descendant at time $N$ from a single ancestor of type $k$ at time $n$ is equal in distribution to that of $(Z_{nNkj}$, $j\in\edges)$. Fix $j\in\edges$. \prpu{higher} implies, with \eqnu{tPi}, \[ \sup_{n\ge m} \sup_{N\ge n+2} w_n\,\EE{W_{nNij}^2} < \infty \,. \] Furthermore, with $\EE{W_{nNij}}=1$ and the Schwarz inequality, this implies the uniform integrability of $W_{nNij}$; $\dsp \limf{p} \sup_{N\ge n+2} \EE{W_{nNij};\ W_{nNij}>p} =0 $. This with the uniform bound for $\EE{W_{nNij}^3}$ in \prpu{higher} and the Schwarz inequality implies \[ \limf{p} \sup_{N\ge n+2} \EE{W_{nNij}^2;\ W_{nNij}>p} =0 \,,\ \ n\ge m\,. \] \prpu{estimB} with \eqnu{EB} implies that for each $n\ge m$, $\dsp \limf{N} \frac{\EE{Z_{nNij}}}{\EE{Z_{nN1j}}}$ exists, positive and independent of $j\in\edges$. Hence, if we prove that $w_N\,Z_{mNij}$ diverges in probability to infinity, then all the assumptions of \prpu{Cohn} will be satisfied, with $e_N$ replaced by $w_{m+N}$ and $n_0=2$. \prpu{Cohn} then will imply that $(W_{mNij},\ j\in\edges)$ converges in $L_2$ as $N\to\infty$, to a random vector with equal components. \par By definition, $Z_{mmij}=1$ $(j=i)$ and $=0$ $(j\ne i)$. Fix $p>0$ and $j\in\edges$, and define a family of sequences $\{(x_{k,n},y_{k,n})\}$ $0\le n\le k$, $k\in\pintegers$, by \eqsb x_{k,n} &=& \max_{i'\in\edges'} \prb{w_{m+n_0(k)+k}\,Z_{m+n,m+n_0(k)+k,i',j}\le p} \,, \\ y_{k,n} &=& \max_{i'\in\edges\setminus\edges'} \prb{w_{m+n_0(k)+k}\,Z_{m+n,m+n_0(k)+k,i',j}\le p} \,, \eqse where $\edges'$ is defined in \eqnu{horizontal}. $n_0(k)$ is an arbitrary function of $k$ taking non-negative integer values (to be specified later). Define a sequence $\{\xa_n,\ n\in\pintegers\}$ by $\xa_n = a_{m+n}+1$, and $\{\xw_n,\ n\in\pintegers\}$ by \[ \xw_n \defd \max_{i'\in\edges'} \prb{\sum_{k\in\edges\setminus\edges'}Z_{m+n-1,m+n,i',k} \ge 1} \,. \] $\xw_n$ is the largest probability among $i'\in\edges'$ that the random walk $X=X_{N,w_{N}}$ with $N=m+n$ jumps off-horizontally at least once in the time interval $[T_{N-1,1}(X)$, $T_{N-1,0}(X)]$, under the condition that the endpoints of $X$ for this time interval forms an edge of type $i'$ in $\Fgasket_{N-1}$. By definition, $3 \le \inf_n \xa_n \le \sup_n \xa_n < \infty$. Also $0 \le \xw_n \le 1$ and is of order $w_{m+n}$, for which \prpu{wasymp} implies $\xw_n \le \cv1\,\delta^{-n}$ for some constant $\cv1>0$ and $\dsp \delta=\min_{k} \delta_k =\min_k \frac{2(1+a_k)}{2+b_k} >1$ (recall that there are only finite number of distinct pairs $(a_k,b_k)$). From graphical consideration we see that \eqsb x_{k,n} &\le& \max_{i'\in\edges'} \left\{ \prb{\sum_{j'\in\edges\setminus\edges'}Z_{m+n,m+n+1,i',j'} =0} \, x_{k,n+1}^{\xa_{n+1}} \right. \\ && \left. + \prb{\sum_{j'\in\edges\setminus\edges'}Z_{m+n,m+n+1,i',j'} \ge 1} \, y_{k,n+1}\right\} \,. \eqse We may either use $y_{k,n} \le 1$ or use $\dsp \prb{\sum_{j'\in\edges\setminus\edges'}Z_{m+n,m+n+1,i',j'} =0} \le 1$, to conclude that $x_{k,n}$ satisfies the inequality in the definition of the assumption R in \secu{s3}, with $\{w_n\}$ and $\{a_n\}$ replaced by $\{\xw_n\}$ and $\{\xa_n\}$, respectively. Similarly, we find \eqsb y_{k,n} &\le& \max_{i'\in\edges\setminus\edges'} \left\{ \prb{\sum_{j'\in\edges'}Z_{m+n,m+n+1,i',j'} \ge 1} \, x_{k,n+1} \right. \\ && \left. +\prb{\sum_{j'\in\edges'}Z_{m+n,m+n+1,i',j'} =0} \, y_{k,n+1} \right\} \,, \eqse from which we know that $y_{k,n}$ also satisfies the inequality of the assumption R. \par For $k\in\pintegers$ and $i'\in\edges'$ put \eqsb e_{k,i'} &\defd& \EE{w_{m+n_0(k)+k} \,Z_{m+k,m+n_0(k)+k,i',j}} \,,\\ v_{k,i'} &\defd& \VV{w_{m+n_0(k)+k} \,Z_{m+k,m+n_0(k)+k,i',j}} \,. \eqse \prpu{estimB}, \eqnu{EB}, \eqnu{tPi}, and $b_k\ge 2$ imply $e_{k,i'} \ge \cv2 \, w_{m+k}^2 \, 4^{n_0(k)}$, where $\cv2>0$ is a constant independent of $n_0\in\pintegers$ and $k\in\pintegers$. For each $k$, define $n_0(k)$ to be sufficiently large so that $e_{k,i'} \ge 2p$ for all $k\in\pintegers$. \prpu{Schwarz} then implies that $\dsp \prb{w_{m+n_0(k)+k} \,Z_{m+k,m+n_0(k)+k,i,j} \le p} < 1-1/(2d)$, where $d\le 1+2 \,v_{k,i'} \, e_{k,i'}^{-2}$. Applying \prpu{higher} and \eqnu{tPi} we see that $\dsp x_{k,k} < 1-\cv3\,w_{m+k} $, where $\cv3$ is a positive constant independent of $k$. \prpu{wasymp} implies $\dsp w_{m+k} \ge \cv4\,w_{m}\,\prod_{\mu=0}^{k} \delta_{m+\mu}^{-1} $ with $\delta_k=2(1+a_k)/(2+b_k)$, and for a positive constant $\cv4$ independent of $k$. Hence \[ (-\log x_{k,k}) \prod_{\mu=0}^{k} \xa_{\mu} >\cv3\,\cv4\,w_{m} \prod_{\mu=0}^k (1+b_{m+\mu}/2) \,, \] which implies $\dsp \liminf_{k\to\infty,\ x_{k,k}\ne 0} \left\{ (-\log x_{k,k}) \prod_{\mu=0}^{k} \xa_{\mu}\right\}^{1/k} \ge 2 >1$. We see that all the assumptions in \thmu{limit} are satisfied, with $e_N$ replaced by $w_{m+N}$, and $Z_{N,j}$ by $Z_{m,m+N,i,j}$. \thmu{limit} then implies $\dsp \lim_{N\to\infty} \prb{w_{N}\, Z_{mNij} \ge p} = 1\,,\ \ p>0$, which, as we noted in the first part of the proof, proves the convergence of $(W_{mNij},\ j\in\edges)$ to $(W_{mi},\cdots,W_{mi})$. Weak convergence and uniform integrability imply convergence in expectations. Therefore, from what we have proved, we obtain the statements on $\EE{W_{mi}}$ and $\EE{W_{mi}^2}$. \par Let $n\in\pintegers$. The $j$ independence of $\gamma_{ni}$ in \prpu{estimB} implies, with \eqnu{EB}, \[ \lim_{N\to\infty} \frac{\sum_j \EE{Z_{nNij}}}{\sum_j \EE{Z_{nN1j}}} =\gamma_{ni}\,. \] Also from \eqnu{EB} one sees, for $m \le n \le N$, \[ \EE{Z_{mNij}}= \sum_{k\in\edges} \EE{Z_{mnik}} \, \EE{Z_{nNkj}} \,. \] Hence, with \eqnu{LN}, we see that $\dsp \lim_{N\to\infty} L_N^{-1} \sum_j \EE{Z_{nNij}}= \frac{\gamma_{ni}}{\sum_{j,k} \EE{Z_{0njk}} \,\gamma_{nk}}$. Convergence of $(W_{nNij},\ j\in\edges)$ and \prpu{total} imply that $\dsp \frac{\sum_{j} Z_{nNij}}{\sum_{j} \EE{Z_{nNij}}}$ converges in probability to $W_{ni}$. Therefore we have the convergence in probability of $\dsp L_N^{-1} \sum_{j\in\edges} Z_{nNij}$ to $W'_{ni}$. With $\EE{W_{ni}}=1$ and \prpu{estimB}, we have \eqnb \eqna{ewp} \EE{W'_{ni}}=\frac{\gamma_{ni}}{\sum_{j,k} \EE{Z_{0njk}} \, \gamma_{nk}} \ge \cv5 \, (\sum_{j,k} \EE{Z_{0njk}})^{-1}\,, \eqne for some positive constant $\cv5$ independent of $n\ge 0$ and $i\in\edges$. Similarly, there exists a positive constant $\cv6$ such that \eqnb \eqna{ewp2} \EE{{W'_{ni}}^2} \le \cv6 \, (\sum_{j,k} \EE{Z_{0njk}})^{-2} \, w_n^{-1}\,,\ \ n\ge 0,\ i\in\edges\,. \eqne \par Let \[ \Phi_{n,i}(t) \defd \EE{\exp \left( \sqrt{-1} \, t \, W'_{n,i}\right)}\,,\ \ t\in\reals\,,\] denote the characteristic function. With obvious bound $0 \le 1- \Re \Phi_{ni}(t) \le t^2 \EE{{W'_{ni}}^2} /2$ and $|\Im \Phi_{ni}(t)-t \EE{W'_{ni}}| \le t^2 \EE{{W'_{ni}}^2} /2$, $t\in\reals$, we can proceed as in the first half of the proof of \cite[(2.45)]{HHW93}, using random walk representation \cite[(2.30)]{HHW93} for $\Phi_{ni}(t)$, to obtain \[ |\Phi_{n,i}(t)| \le 1 - \tC_{n} \, t^2 \,,\ \ -t'_n < t < t'_n\,,\ n\ge 0,\ i\in\edges'\,,\] with $\dsp \tC_n = \cv7 \, w_{n+1}^{-1} \min_j \EE{W'_{n+1,j}}^2$ and $\dsp t'_n=\frac{\min_j \EE{W'_{n+1,j}}}{\max_j \EE{{W'_{n+1,j}}^2}}$, where $\cv7$ is a positive constant independent of $n\ge0$. (Replace $6^kt$ in \cite[(2.45)]{HHW93} by $t$ and $\dsp (3/4)^{n+k}$ by $w_n$.) We may use a narrower interval $(-t_n,t_n)$ with $t_n \le t'_n$ for the estimate above, in applying \thmu{cont}. Put $t_n \defd \cv5 \cv6^{-1} \, w_n \, \sum_{j,k} \EE{Z_{njk}}\,$. Then \eqnu{ewp} and \eqnu{ewp2} imply $t_n \le t'_n\,$. With \eqnu{ewp}, \prpu{wasymp}, and \prpu{estimB}, we see that an assumption of \thmu{cont} \[ \liminf_{k\to\infty} \left( t_k^2 \tC_{k} \prod_{\mu=0}^{k-n_0} (a_{n_0+\mu+1}+1) \right)^{1/k} > 1 \,, \] is satisfied with $a_\mu$ replaced by $a_{n_0+\mu+1}+1$. \par \prpu{estimB} and \eqnu{EB} imply $\dsp \limf{k} t_k = \infty$, while boundedness of $\tA_{nij}$ implied in \eqnu{supA} with \prpu{wasymp} and \eqnu{tPi} gives $\sup_{k\ge 0} t_k^{1/k} < \infty$. Let $n\ge 0$ and $m\ge 0$. From \eqnu{EB}, \eqnu{tPi}, \prpu{estimB}, \prpu{wasymp}, and $b_k\ge 2$, we see \[ \frac{t_n}{t_{n+m}} < \frac{\cv8 \, w_n}{w_{n+m} \, \min_{\ell} \sum_{k\in\edges'} B_{n,n+m,\ell,k}} < \cv8 \, 4^{-m} \,,\] where $\cv8$ is a positive constant independent of $n$ and $m$. Therefore there exists an $m_0$ such that $\dsp \frac{t_n}{t_{n+m_0}}<1$ for all $n\ge 0$. With the boundedness of $A_{nij}$ we also see $\dsp \inf_{n\ge 0} \frac{t_n}{t_{n+m_0}} > 0$. Hence all the assumptions for $\{t_k\}$ in \thmu{cont} hold. \par Using \cite[(2.30)]{HHW93}, we can proceed with similar arguments as we did for $\dsp \prb{w_{m+n_0(k)+k}\,Z_{m+n,m+n_0(k)+k,i',j}\le p}$, from which we see that $\Phi_{n,i}$ satisfies the assumption R condition of \thmu{cont}. We have now proved that $\Phi_{n,i}$ satisfies all the assumption of \thmu{cont}, which implies that the distribution of $W'_{n,i}$ is continuous. \prfe \cvrs1 \cvrs2 \cvrs3 \cvrs4 \cvrs5 \cvrs6 \cvrs7 \cvrs8 Let $D\defd D([0,\infty);G)$ be the set of cadlag paths on the \rg\ $G$. For $n\in \integers$ and $x\in G_n$ we define a family of probability measures $\Ppt{N}{x}{\cdot}$, $N=n,n+1,\cdots$, on $D$, by $\Ppt{N}{x}{w(0)=x}=1$ and \[ \Ppt{N}{x}{w(t_{i})=x_{i},\; i=1,2,\cdots,r}= \prb{X_{N,w_N,x}([L_N\, t_{i}])=x_{i},\; i=1,\cdots,r}, \] where $X_{N,w_N,x}$ is the random walk $X_{N,w_N}$ with starting point $x$; $X_{N,w_N,x}=x$. We use abbreviations such as \[ \Ppt{N}{x}{w(0)=x} \defd \Ppt{N}{x}{\{ w \in D \mid w(0)=x\} }\,, \] and write $\Ept{N}{x}{\cdot}$ for the expectations with respect to $\Ppt{N}{x}{\cdot}$. Define $T_{n,i}(w)$, $w\in D$, similarly as we did in \secu{s1} for processes, and put $W_{n,i} \defd T_{n,i+1}-T_{n,i}$. Let $N \ge n$, $x\in G_{N}$, $i\in\pintegers$, and let $x_{0},x_{1},\cdots,x_{i}$ be a sequence of points in $G_n$ such that each adjoining pair is an $n$-neighbor pair and $x_{0}$ and $x$ are in a unit triangle of $\Fgasket_n$. Consider the distribution of $W_{n,j}$, $j=0,1,\cdots,i-1$, under the conditional probability $\Ppt{N}{x}{\cdot \mid w(T_{n,j}(w))=x_j, \; j=0,\cdots,i}$. Since the probability is based on random walks, this distribution is a direct product of the distributions of each $W_{n,j}$, and as we noted before \thmu{stepconverge}, the distribution of each $W_{n,j}$ under the conditional probability is equal to that of $L_N^{-1} \sum_{\ell\in\edges} Z_{nNk\ell}$, if $(x_{j},x_{j+1})$ forms an edge of type $k\in\edges$, and is independent of $i$, $j$, $x$, and $x_j$'s. We denote this distribution of $W_{n,j}$ by $\Qpt{N}{n,k}{\cdot}$, and their limit distributions as $N \to \infty $ by $\Qlmt{n,k}{\cdot}$, $k\in\edges$. \thmu{stepconverge} implies \eqnb \eqna{contQ} \limf{N} \Qpt{N}{n,k}{s\mid a0\,. \eqne Define a harmonic function $h:\ G\to[0,1]$ as follows; for $z\in G_{\infty}$, i.e., $z\in G_m$ for some $m\ge n$, define $h(z) \defd \prb{\tX_m(\sigma_{m,\infty})=y \mid \tX_m(0)=z}$. The assumption on the decimation property implies that $\prb{\tX_{m'}(\sigma_{m',\infty})=y \mid \tX_{m'}(0)=z}$ is constant for $m'\ge m$, hence $h$ is well-defined on $G_{\infty}$. We can see that \cite[Proposition 3.2]{HHW93} holds in our case, which implies that $h$ is continuous. In particular, $h$ is uniquely extendable as continuous function to $G$. By definition, $h(y)=1$ and $h(y')=0$, $y'\in G_n\setminus\{y\}$. $X_N$ is a simple random walk, and $h$, restricted on $G_N$, is an associated harmonic function. Therefore $h(\tX_N(t \wedge \sigma_{N,q}))$, $t\ge 0$, is a martingale ($a \wedge b \defd \min\{a,b\}$), hence $\Ept{x}{}{h(\tX_N(t \wedge \sigma_{N,q}))}=h(x)$, $N\ge n$. This with \eqnu{qnq}, $\limf{N} \tX_N =X$, and continuity of $h$ implies \[ \Ept{x}{}{\min_{\sigma_q \le s \le \sigma_{q+1}} h(X(t \wedge s))} \le h(x) \le \Ept{x}{}{\max_{\sigma_q \le s \le \sigma_{q+1}} h(X(t \wedge s))}\,.\] Continuity of $X$ implies that $\limf{q} \sigma_{q} = \sigma_{\infty}$. Hence we have $h(x)= \Ept{x}{}{h(X(t \wedge \sigma_{\infty}))}$, $t\ge 0$. Since this is independent of $t$, we have $h(x)=\Ept{x}{}{h(X(\sigma_{\infty}))}=\prb{X(\sigma_{\infty})=y \mid X(0)=x}$, which implies that the transition probability of $n$-decimated walk of $X$ is equal to that of $X_n(0)$. \prfe \prfofb{\thmu{main}} We can apply \cite[Sect. 3]{HHW93}, with \cite[Theorems 2.5, 2.8]{HHW93} replaced by \thmu{stepconverge}, \cite[(3.1)]{HHW93} by \eqnu{contQ}, and \cite[Proposition 3.1(1)]{HHW93} by \prpu{tochuuten}. Then for $x_N\in G_N$, $N\in\pintegers$, satisfying $\limf{N} x_N=x$, the sequence of measures $\Ppt{N}{x_N}{\cdot}$ (the distribution of $X_{N,w_N,x_N}([L_N t])$), $N\in\integers$, converges weakly as $N\to\infty$ to a symmetric Feller process $X$. Skorokhod's Theorem implies that there exists a probability space and $G_N$ valued processes $X_N$, $N\in\integers$, such that $X_N$ is equal in law to $X_{N,w_N,x_N}$ and converges almost surely to a process equal in law to $X$. \prpu{decimated} implies that the $n$-decimated walk of this process is equal in law to the original random walk $X_{n,w_n}$. That this random walk has the asymptotically one-dimensional (and isotropy restoration) properties, is proved in \prpu{wasymp}. \prfofe %---------------------------------------------------------------------- \bigskip\par\noindent {\em Acknowledgements.} The author would like to thank Prof.\ K.~Hattori and Prof.\ H.~Watanabe for collaborations on which the present work stands, and Prof.\ S.~Kusuoka for the proof of \prpu{decimated}. He would also like to thank Prof.\ M.~T.~Barlow and Prof.\ H.~Tasaki for valuable discussions concerning the present work, Prof.\ C.~Burdzy for the hospitality and discussions during the author's stay at University of Washington, Prof.\ T.~Nakagawa for bringing references on branching processes to the author's attention, and Prof.\ B.~M.~Hambly, Prof.\ H.~Osada, Prof.\ T.~Kumagai, and Prof.\ Z.~Vondra\v{c}ek, for kindly sending related works before publication. \appendix %---------------------------------------------------------------------- \section{Metric for scale-irregular $abb$-gaskets.} \seca{sa} % rnda (v940528) We define a metric $d$ for a \rg. Consider a sequence of vertices of pre-gaskets, $G_0 \subset G_1 \subset G_2 \subset \cdots$, and let $\dsp G_{\infty}=\bigcup G_n$, as in \secu{s1}. Let $x\in G_{\infty}$ and $y\in G_{\infty}$, i.e. $x\in G_N$, $y\in G_{N}$, for some $N$. We explain the case where $x$ and $y$ are in a unit triangle of $G_0$. The case where $x$ and $y$ are ^^ further apart' can be handled similarly. \par Let $path(x,y)$ be a collection of finite sequences $z=\{z_0=x,z_1,\cdots,z_K=y\}$ for some $K=K(z)\ge 0$, which has a property that for each $i=0,1,\cdots,K(z)-1$, there exists $s_z(i)\in\pintegers$ such that $z_i$ and $z_{i+1}$ are ${s_z(i)}$-neighbor pairs. Let $\{a_N,b_N\}$ be a bounded sequence of pair of positive integers, that determines $G_{\infty}$. Put $\dsp \lambda_n=\prod_{k=1}^{n} \min\{a_k+1,b_k+1\}^{-1}$, $n\in\pintegers$. For $z\in path(x,y)$ put $\dsp L(z)=\sum_{i=0}^{K(z)-1} \lambda_{s_z(i)}$. Then the metric $d$ is defined to be $\dsp d(x,y) \defd \inf_{z\in path(x,y)} L(z)$. It is straightforward to see that if $x$ and $y$ are an $N$-neighbor pair, then \eqnb \eqna{dxy} d(x,y)=\lambda_N\,. \eqne That $d$ is a metric is also easy to see. \par The definition of $\lambda_n$ can be replaced by $\dsp \lambda_n=\prod_{k=1}^{n} \ell_k^{-1}$, for any set of $\ell_k$ satisfying $\ell_k \le \min\{a_k+1,b_k+1\}$ and $\inf_k \ell_k >1$. The first condition implies \eqnu{dxy}. The second condition with the boundedness of $\{a_N,b_N\}$ implies that there exists a positive constant $C$ such that if $x$ and $y$ is in a unit triangle of $G_N$ then $d(x,y)\le C\,\lambda_N\,$. This property means that our definition of $d$ is compatible with our analysis in this paper based on the hierarchical (recursive) structure of the fractal. %---------------------------------------------------------------------- \section{Decay estimates from non-linear recursion relations.} \seca{sd} % rndd (v940528) The Lemma below gives a mild decay estimate from a non-linear recursion relation. We apply the Lemma to prove a Theorem which states a sharp decay estimate from another recursion relation with more involved assumptions. \lemb \lema{recineq} Let $\{w_n,\ n\in\pintegers\}$ be a sequence in $[0,1]$ satisfying $\sum_n w_n < \infty$, and $\{a_n,\ n\in\pintegers\}$ a sequence satisfying $ D\defd \inf_n a_n>1$ and $\sup_n a_n < \infty$. For each $k\in\pintegers$ define a sequence $\{x_{k,n},\ n=k,k-1,\cdots,0\}$ by a recursion relation \[ x_{k,n}=(1-w_{n+1}) \, x_{k,n+1}^{a_{n+1}}+w_{n+1}\,,\ \ n=k-1,k-2,\cdots,0\,,\] with initial condition $x_{k,k}$ satisfying $0 \le x_{k,k} \le 1$. If \[ \lim_{k\to\infty,\ x_{k,k}\ne 0} (-\log x_{k,k}) \prod_{\mu=0}^{k} a_{\mu} = \infty \] holds, then there exist positive constants $C_1$ and $k_1$ (independent of $n$ and $k$) such that \[ x_{k,n} \le C_1 \sup_{\mu \ge n} w_{\mu} + \exp\left(-D^{f_k-n-1}\right) \,,\ \ 0\le n \le f_k,\ k\ge k_1\,,\] where \[ f_k=\sup \{ n \le k-1 \mid \sqrt{D} \, (-\log x_{k,k}) \prod_{\mu=n+2}^{k} a_{\mu} > 1 \} +1 \,, \] with a convention $\prod_{\mu=k+1}^{k} a_{\mu} = 1$, and $f_k=k$ if $x_{k,k}=0$. \leme \prfb Put $C_2 = \sup_n \exp(a_n)$. $\sum_n w_n < \infty$ and $D>1$ imply that there exists a constant $n_1$ such that $\dsp \prod_{\mu \ge n} (1-C_2 \, w_{\mu}) \ge \sqrt{D}^{-1} $, $n\ge n_1\,$. By assumption, $\dsp \lim_{k\to\infty} f_k =\infty$, hence there exists a constant $k_1$ such that $\dsp f_k \ge n_1 -1$, $k \ge k_1$. Let $k \ge k_1$ in the following. We first prove that \eqnb \eqna{step1} x_{k,f_k} \le \exp\left( - D^{-1} \right) \,,\ \ \ k \ge k_1\,. \eqne If $x_{k,k}=0$ then \eqnu{step1} directly follows, so we assume $x_{k,k}>0$. Put $u_{k,n}= - \log x_{k,n}$. The assumptions and the recursion relation imply $ 0< x_{k,n} \le 1 $ for all $n$, hence $u_{k,n}$ exist and are non-negative. Furthermore, \[ u_{k,n}=a_{n+1} u_{k,n+1} - \log \left(1+ ( x_{k,n+1}^{-a_{n+1}}-1) \, w_{n+1}\right) \le a_{n+1} u_{k,n+1} \,, \] which implies \eqnb \eqna{d0} u_{k,n} \le u_{k,k} \left( \prod_{\mu=n+1}^{k} a_{\mu} \right) \,,\ \ 0\le n\le k\,. \eqne The definition of $f_k$ implies $f_k \le k$ and the following three inequalities; \eqnb \eqna{d1} u_{k,k} \ge \sqrt{D}^{-1} \,,\ \ \ \mbox{if } f_k = k \,, \eqne \eqnb \eqna{d2} \sqrt{D} \, u_{k,k} \left( \prod_{\mu=f_k+1}^{k} a_{\mu}\right) > 1\,, \eqne \eqnb \eqna{d3} \sqrt{D} \, u_{k,k} \left( \prod_{\mu=n+2}^{k} a_{\mu}\right) \le 1 \,, \ \ f_k \le n \le k-1\,. \eqne From \eqnu{d0}, \eqnu{d3}, and $D>1$ follows $ u_{k,n+1} < 1 $, $ f_k \le n \le k-1$, which, together with the recursion relation implies \[ \arrb{l} u_{k,n}=a_{n+1} u_{k,n+1} - \log (1+\exp(u_{k,n+1} a_{n+1})\, w_{n+1} (1-\exp(-u_{k,n+1} a_{n+1}))) \\ \ge a_{n+1} u_{k,n+1}-\log\left(1+C_2\, w_{n+1}\, u_{k,n+1}\, a_{n+1}\right) \\ \ge a_{n+1} (1 - C_2 w_{n+1}) \, u_{k,n+1}\,, \ \ \ \ f_k \le n \le k-1\,. \arre \] This with $k \ge k_1$ and \eqnu{d2} implies $u_{k,f_k} \ge u_{k,k} ( \prod_{\mu=f_k+1}^{k} a_{\mu} ) ( \prod_{\mu=f_k+1}^{k} (1 - C_2 w_{\mu}) ) \ge D^{-1} $, if $f_k \le k-1$. If $f_k \ge k$ then $f_k =k $, hence \eqnu{d1} implies $\dsp u_{k,f_k} > D^{-1}$. Therefore we have \eqnu{step1}. \par Put $\dsp v_n = \sup_{\mu \ge n} w_{\mu}$. $\{v_n\}$ is decreasing, bounded above by $1$, and $\dsp \lim_{n\to\infty} v_n = 0$. Define a sequence $\{z_n,\ n=f_k,f_k-1,\cdots,0\}$ by $z_{k,n} = z_{k,n+1}^D + v_{n+1} \,$, $0\le n\le f_k-1$, and $z_{k,f_k}=\exp(-D^{-1})$. Then \eqnb \eqna{d6} x_{k,n} \le z_{k,n}\,,\ \ \ \ 0\le n \le f_k\,. \eqne Put \eqnb \eqna{d7} z_{k,n}= \exp\left( -D^{f_k-n-1}\right) + v_n \, r_{k,n} \,. \eqne Taylor's Theorem implies, with $D>1$, \[ r_{k,n} \le \frac{v_{n+1}}{v_n} \, r_{k,n+1} \, D \left( \exp\left( -D^{f_k-n-2} \right) + v_{n+1} \, r_{k,n+1} \right)^{D-1} + v_{n+1} \,, \] which further is reduced with the properties of $v_n$ to \eqnb \eqna{d5} r_{k,n} \le r_{k,n+1} \, D \, (e^{-1} + v_{n+1} \, r_{k,n+1} )^{D-1} +1 \,, \ \ \ 0 \le n \le f_k-2\,. \eqne Put $\dsp \rho=\frac{1}{2} \, (1+D \, e^{-D+1})$. $D>1$ implies $0< D \, e^{-D+1} < \rho <1$. Therefore there exists a constant $k_2$ defined by \[ k_2 = \inf \{ n\ge 0 \mid D \, (e^{-1} + v_n \, (1-\rho)^{-1} )^{D-1} < \rho \} \,. \] Monotonicity of $\{v_n\}$ implies $\dsp D\, (e^{-1} + v_n \, (1-\rho)^{-1} )^{D-1} < \rho$, $n \ge k_2\,$. If $f_k \ge k_2 +1$ then we can prove by induction that $\dsp r_{k,n} \le (1-\rho)^{-1} $, $k_2 \le n \le f_k\,$. In fact, we explicitly have $\dsp r_{k,f_k}=0$ and $\dsp r_{k,f_k-1}= v_{f_k-2}/ v_{f_k-1} \le 1$. If $\dsp r_{k,n+1} \le (1-\rho)^{-1} $ holds for $n$ some with $k_2 \le n \le f_k-2$, then \eqnu{d5} and the definition of $k_2$ implies $\dsp r_{k,n} \le (1-\rho)^{-1}\rho +1 = (1-\rho)^{-1}$. Thus if $f_k \ge k_2 +1$, $r_{k,n}$ for $k_2 \le n \le f_k$ are bounded by a constant independent of $n$ and $k$. $k_2$ is independent of $n$ and $k$. Therefore $r_{k,n}$ for $0 \le n \le k_2$ are bounded by a constant independent of $n$ and $k$. If $f_k < k_2 +1$, similar argument shows, with $r_{k,f_k}=0$, that $r_{k,n}$ for $0 \le n \le f_k$ are bounded by a finite number independent of $n$ and $k$. This with \eqnu{d6} and \eqnu{d7} implies the statement. \prfe \thmb \thma{recineq} Let $\{w_n\}$, $\{w'_n\}$, $n\in\pintegers$, be sequences in $[0,1]$ satisfying \[ \max\{w_n,\ w'_n\} \le C_w \delta^{-n} \,, \ \ \ n\in\pintegers \,, \] for positive constants (independent of $n$) $C_w$ and $\delta > 1$. Also let $\{a_n,\ n\in\pintegers\}$ be a sequence satisfying $ \inf_n a_n \ge 2$ and $\sup_n a_n < \infty$. For each $k\in\pintegers$ consider a sequence in $[0,1]^2$ \[ \{(x_{k,n},y_{k,n})\,,\ \ n=k,k-1,\cdots,0\} \ \subset [0,1]^2 \,, \] and assume that it satisfies a recursive inequality \eqsb x_{k,n} &\le& x_{k,n+1}^{a_{n+1}}+w_{n+1} \, \min\{1-x_{k,n+1}^{a_{n+1}}\,,\ y_{k,n+1}\} \,,\ \ \\ y_{k,n} &\le& x_{k,n+1}+ w'_{n+1} \, y_{k,n+1} \,,\ \ n=k-1,k-2,\cdots,0\,. \eqse If \eqnb \eqna{deltap} \liminf_{k\to\infty,\ x_{k,k}\ne 0} \left\{ (-\log x_{k,k}) \prod_{\mu=0}^{k} a_{\mu}\right\}^{1/k} >1 \eqne holds, then there exist positive constants $C_1$ and $C_2$ (independent of $k$) such that \[ \max\{x_{k,0},\ y_{k,0}\} \le C_1 \, \exp(-C_2 \, k^2) \,,\ \ \ k\in\pintegers \,. \] \thme \prfb Define $\{\tilde{x}_{k,n},\ n=k,k-1,\cdots,0 \} $ by $\tilde{x}_{k,k}=x_{k,k}$ and \[ \tilde{x}_{k,n}=(1-w_{n+1}) \, \tilde{x}_{k,n+1}^{a_{n+1}}+w_{n+1}\,,\ \ n=k-1,k-2,\cdots,0\,,\] Then the recursion relation for $x_{k,n}$ and the assumption $y_{k,n} \le 1$ imply \[ x_{k,n} \le \tilde{x}_{k,n} \,,\ \ \ 0 \le n \le k,\ k\ge 0\,. \] $\{\tilde{x}_{k,n} \}$ satisfies all the assumptions of \lemu{recineq} with $D=2$, hence there exist positive constants $C_3$ and $k_1$ (independent of $n$ and $k$) such that \eqnb \eqna{x} x_{k,n} \le C_3 \sup_{\mu \ge n} w_{\mu} + \exp\left(-2^{f_k-n-1}\right) \,,\ \ 0\le n \le f_k,\ k\ge k_1\,, \eqne where \eqnb \eqna{fk} f_k=\sup \{ n \le k-1 \mid \sqrt{2} \, (-\log x_{k,k}) \prod_{\mu=n+2}^{k} a_{\mu} > 1 \} +1 \,. \eqne Since \eqnu{deltap} implies $\dsp \lim_{k\to\infty} f_k = \infty$, there exists a constant $k_2 \ge k_1$ such that for $0 \le n \le f_k /2$ and $k \ge k_2$, \[ \exp\left(-2^{f_k-n-1}\right) \le \exp\left(-2^{f_k/2-1}\right) \le C_w \delta^{-f_k/2} \le C_w \delta^{-n} \,. \] This with \eqnu{x} implies $\dsp x_{k,n} \le (C_3+1) \, C_w \, \delta^{-n} $, $0 \le n \le f_k /2 $, $k \ge k_2 $. Applying this estimate to the original recursion relations and using $w_n \le C_w \delta^{-n}$, $w'_n \le C_w \delta^{-n}$, and $a_n \ge 2$, we have \eqsb x_{k,n} &\le& C_w \,\delta^{-n-1} \, ( (C_3+1)\, x_{k,n+1} + y_{k,n+1}) \,,\ \ \\ y_{k,n} &\le& x_{k,n+1}+ C_w \, \delta^{-n-1} \, y_{k,n+1} \,,\ \ 0 \le n \le f_k /2 \,,\ k \ge k_2 \,. \eqse Iterating once, we find \[ \max\{ x_{k,n},\ y_{k,n} \} \le C_5 \, \delta^{-n-1} \, \max \{ x_{k,n+2},\ y_{k,n+2} \} \,,\ \ \ 0 \le n \le f_k /2 -1\,,\ k \ge k_2 \,, \] where $C_5$ is a positive constant independent of $n$ and $k$. Iterating this $[f_k /4]$ times, where $[x]$ is the largest integer not exceeding $x$, and using $x_{k,n} \le 1$, $y_{k,n} \le 1$, we find \eqnb \eqna{xy} {}\ \ \ \ \max\{ x_{k,0},\ y_{k,0} \} \le \exp \left\{ \left[\frac{f_k}{4}\right] \, (\log C_5) - \left[\frac{f_k}{4}\right]^2 \, (\log \delta) \right\} \,,\ \ k\ge k_2\,. \eqne The assumption \eqnu{deltap} implies that there exist positive constants $k_3 \ge k_2$ and $\delta' > 1$ (independent of $k$) such that $\dsp (-\log x_{k,k}) \prod_{\mu=0}^{k} a_{\mu} > \delta'^k$, $k\ge k_3$. The definition \eqnu{fk} then implies $\dsp f_k \ge \min \left\{ \frac{\log \delta'}{\log \sup_{\mu} a_{\mu}} \; k -1 ,\ k \right\}$, $ k\ge k_3$. Applying this to \eqnu{xy}, increasing constants for terms with $k 0 $. Then for $i\in\edges$ and $j\in\edges$, $\dsp \gamma_{i} \defd \lim_{N\to\infty} \frac{\dsp \left( A_1 \cdots A_{N} \right)_{ij}}{\dsp \left( A_1 \cdots A_{N} \right)_{1j}} $ exists, positive, and is independent of $j$. \thme \prfb For $N>n\ge0$ define \[ B_{nN} \defd A_{n+1} A_{n+2} \cdots A_{N} \] and put \[ \gamma_{Nij} \defd \frac{B_{0Nij}}{B_{0N1j}} \,,\ \ i\in\edges,\ j\in\edges\,. \] The elementwise positivity of $A_{N+1}$ and $B_{nN}$ imply for each $i$ that $\dsp \{ \min_k \gamma_{Nik} \}$ is increasing and $\dsp \{ \max_k \gamma_{Nik} \}$ is decreasing in $N$, in particular, the sequence $\{\gamma_{Nij},\ N =1,2,\cdots\}$ is compact. Therefore, for each $i$ and $j$, and for any subsequence of positive integers there exists a further subsequence $\{a_N\}$ such that the limit \eqnb \eqna{agammapre} \gamma_{ij}^{(a)} \defd \lim_{N\to\infty} \gamma_{a_N,ij} > 0\,. \eqne exists and is positive. \par For $0 < n < N$ and $i\in\edges$, $j\in\edges$, put \[ p_{nNij}\defd \frac{B_{0n1i} \, B_{nNij}}{B_{0N1j}} \,. \] The definition and the elementwise positivity of $B_{nNij}$ imply, for $0 < n < N$, $i,j\in\edges$, \eqnb \eqna{pprob} 0 < p_{nNij} < 1\,,\ \ \sum_{k\in\edges} p_{nNkj}=1 \,,\ \ \gamma_{Nij} = \sum_{k\in\edges} \gamma_{nik} \, p_{nNkj}\,. \eqne We prove a couple of Lemma for $p_{nNkj}$. \lemb \lema{l1} Fix $\{a_N\}$, and let $\gamma_{ij}^{(a)}$ be as above. If for every $i,j\in\edges$ either $\dsp \inf_{n>0} \inf_{N> n+q} p_{nNij} > 0$ or $\dsp \inf_{n>0} \inf_{N> n+q} p_{nNji} > 0$ hold, then for every $i\in\edges$, $\gamma_{ij}^{(a)}$ is independent of $j$. \leme \prfb Put $n=a_M$ and $N=a_{M'}$ in \eqnu{pprob}. We see from \eqnu{agammapre} and \eqnu{pprob} that for each $\epsilon>0$ there is an integer $M_0$ such that for any integers $M$, $M'$ satisfying $M'>M>M_0$ we have \eqnb \eqna{jgamma} \left| \sum_{k\in\edges} (\gamma_{ij}^{(a)}-\gamma_{ik}^{(a)}) p_{a_M,a_{M'},kj} \right| < \epsilon \,. \eqne Now suppose that the Lemma is wrong; $\dsp \gamma_{ik_1}^{(a)} < \gamma_{ik_2}^{(a)}$ and $\dsp \gamma_{ik_1}^{(a)} \le \gamma_{ij}^{(a)} \le \gamma_{ik_2}^{(a)}$, $ j\in\edges$. If we put $j=k_2$ in \eqnu{jgamma} and keep $k=k_1$ term in the summation we have $\dsp \epsilon > (\gamma_{ik_2}^{(a)}-\gamma_{ik_1}^{(a)}) p_{a_M,a_{M'},k_2,k_1} $, while if we put $j=k_1$ and keep $k=k_2$ term we have $\dsp \epsilon > (\gamma_{ik_2}^{(a)}-\gamma_{ik_1}^{(a)}) p_{a_M,a_{M'},k_1,k_2} $. Since $\epsilon>0$ is arbitrary, these inequalities contradicts the assumption of the Lemma. \prfe \lemb \lema{l2} \[ \inf_{n>0} \inf_{N>n+q} p_{nNij} > 0\,,\ \ \ i\in\edges,\ j\in\edges\,. \] \leme \prfb Note that each $p_{nNij}$ is positive by \eqnu{pprob}. Therefore it is sufficient to consider the cases where $N$ and $n$ are sufficiently large. For sufficiently large $N$, \[ \arrb{l} \dsp p_{1Nij} \ge \frac{A_{11i}}{\dsp \sum_{k_1} A_{11k_1}} \, \frac{\dsp \sum_{k_2} A_{2,i,k_2} \, B_{2,N,k_2,j}}{\dsp \max_{k_1} \sum_{k_2} A_{2,k_1,k_2} \, B_{2,N,k_2,j}} \ge \frac{A_{11i}}{\dsp \sum_{k_1} A_{11k_1}} \, \min_{k_2} \frac{\dsp A_{2,i,k_2}}{\dsp \max_{k_1} A_{2,k_1,k_2}}\,, \arre\] where we used an inequality among non-negative numbers $a_i$, $b_i$, $c_i$, $i\in\edges$; $\dsp \frac{\sum a_i c_i}{\sum b_i c_i} \ge \min_i \frac{a_i}{b_i}\,$. Hence $\dsp \inf_{N>1} p_{1Nij} > 0 $. If we prove $\dsp \inf_{n>0} \inf_{N> n+q} \frac{p_{nNij}}{p_{1Nij}} > 0 $, then the Lemma is proved. For sufficiently large $N$ and $n$ with $N-q > n$, \[ \arrb{l} \dsp \frac{p_{nNij}}{p_{1Nij}} \ge \frac{\dsp \min_k A_{11k} B_{1nki} B_{nNij}}{\dsp \max_{k} A_{11i} B_{1nik} B_{nNkj}} \ge \min_{\{k_i\}} \frac{\dsp \min_k A_{11k} A_{2kk_1} B_{n-q,n,k_2i} B_{n,n+q,ik_3}}{\dsp A_{11i} A_{2ik_1} \max_k B_{n-q,n,k_2k} B_{n,n+q,kk_3}}\,. \arre\] Taking the infimum of both sides with respect to $N$ and $n$, we see, with the assumptions of \thmu{Frobenius}, $\dsp \inf_{n>0} \inf_{N> n+q} \frac{p_{nNij}}{p_{1Nij}} > 0 $. \prfe Let us continue the proof of the Theorem. \lemu{l1} and \lemu{l2} imply that $\gamma_{ij}^{(a)}$ of \eqnu{agammapre} is independent of $j$. Fix $i\in\edges$, and consider two subsequences of positive integers. There are subsubsequences, $\{a_N\}$ and $\{b_N\}$, for each of the subsequences respectively, such that the limits \eqnb \eqna{agamma} \gamma_{i}^{(a)} \defd \lim_{N\to\infty} \gamma_{a_N,ij} > 0\,, \ \ \mbox{and }\ \gamma_{i}^{(b)} \defd \lim_{N\to\infty} \gamma_{b_N,ij} > 0\,, \eqne exist, positive, and are independent of $j$. Put $n=b_M$ and $N=a_{M'}$ in \eqnu{pprob}; \eqnb \eqna{abSD} \gamma_{a_{M'},ij} = \sum_{k\in\edges} \gamma_{b_M,ik} \, p_{b_M,a_{M'},kj}\,, \ \ \ a_{M'} > b_M \,,\ i\in\edges,\ j\in\edges \,. \eqne The equations \eqnu{agamma}, \eqnu{abSD}, and \eqnu{pprob} imply that for any positive $\epsilon$ there exists an integer $N_0$ such that if $a_{M'}> b_M >N_0$ hold, then \[ \left| \gamma_{i}^{(a)}-\gamma_{i}^{(b)} \right| = \left| \gamma_{i}^{(a)}-\left(\gamma_{i}^{(b)} \sum_{k\in\edges} p_{b_M,a_{M'},kj}\right) \right| < \epsilon\,,\ j\in\edges\,.\] Hence $\gamma_{i}^{(a)}=\gamma_{i}^{(b)}$, which implies that the limit is independent of subsequences. Positivity of the limit also follows from \eqnu{agamma}. \prfe %---------------------------------------------------------------------- \section{Basic estimates on generating functions.} \seca{sb} % rndb (v940527) % hh1 = \tilde{A}(a,b,w=0), h1 = hh1 (b+2)^2/(a+1), M(a,b)_{ij} = h1 % h1 from delta2 19931214(tue) We give an explicit formula for the generating function \[\gg_{a,b,i}(w,h) = \tFF_{i}(a,b,w;\tPi(w)+w\, h)\,,\] introduced in \secu{s2}. For each $i\in\edges$, $\gg_{a,b,i}(w,h)=Num_i / Den_i$, where \[ Den_i = \det W + \sum_{\alpha=1}^{3} \det \left(\arrb{c|c} 0 & O_{\alpha} \\ \hline I_{\alpha,i} & W \arre \right) \,, \] \[ Num_i = - \det \left(\arrb{c|c} 0 & O'_i \\ \hline I'_i & W \arre \right) \,. \] Put $\dsp Z(i) \defd \Pi(w)_{i} + w\, S^{-1}(w)_{ii} \,h_i$, $i\in\edges$. Then $O_1 = (Z(Ar),0,0,0,0,Z(Bq))$, $O_2 = (0,Z(Ar),Z(Bq),0,0,0)$, and $O_3 = (0,0,0,Z(Bp),Z(Bp),0)$. For $X\in\{A,B,D,E\}$ and $t\in\{p,q,r\}$, we write $Xt$ to specify an element in $\edges$, with an obvious rule. With this convention, $O'_{Xp} = O_3$, $X\in\{A,B,E\}$, $O'_{Dq} = O_1$, and $O'_i = O_2$, otherwise. $I_{1,Dq} = 0$, otherwise $I_{1,Xt} = {}^t (Z(Xr),0,0,0,0,Z(Xp))$. $I_{2,At} = {}^t (0,Z(Ar),Z(Ap),0,0,0)$, otherwise $I_{2,Xt} = 0$. $I_{3,Xt} = 0$, if $X\in\{A,E\}$, otherwise $I_{3,Xt} = {}^t (0,0,0,Z(Xq),Z(Xq),0)$. $I'_{Xq} = {}^t I_{3,Xq}$, while for $t \ne q$, $I'_{Xt} = I_{1,Xt}$. $W$ is a $6$ dimensional matrix given by \[ \arrb{l} W= {\rm I} - \\ \left( \arrb{cccccc} W_{\alpha}(1) & W_{\beta}(1) & 0&0&0& Z(Bq) \\ W_{\beta}(1) & W_{\alpha}(1) & Z(Bq) &0&0&0 \\ 0& Z(Ap) & W_{\alpha}(2) & W_{\beta}'(2) &0&0 \\ 0&0& W_{\beta}(2) & W_{{\alpha}'}(2) & Z(Br) &0 \\ 0&0&0& Z(Br) & W_{{\alpha}'}(2) & W_{\beta}(2) \\ Z(Ap) &0&0&0& W_{{\beta}'}(2) & W_{\alpha}(2) \arre \right) \,.\arre \] For $j=1,2$, $\dsp W_{\alpha}(j)+{\alpha}'(j)=W_{{\alpha}'}(j)+{\alpha}(j)= 1-\bar{{\beta}}(j) \, \frac{\Delta(j)_{n(j)}}{\Delta(j)_{n(j)-1}}\,$, $\dsp W_{\beta}(j)=\frac{\bar{{\beta}}(j)}{\Delta(j)_{n(j)-1}} \, \left(\frac{{\beta}(j)}{{\beta}'(j)}\right)^{n(j)/2}$, $\dsp W_{{\beta}'}(j)=\frac{\bar{{\beta}}(j)}{\Delta(j)_{n(j)-1}} \, \left(\frac{{\beta}'(j)}{{\beta}(j)}\right)^{n(j)/2}$, where $\dsp \bar{{\beta}}(j)=\sqrt{{\beta}(j)\,{\beta}'(j)}\,$, $2\bar{{\alpha}}(j)={\alpha}(j)+{\alpha}'(j)$, and $\dsp \Delta(j)_{n(j)} = \frac{x_+(j)^{n(j)+1} -x_-(j)^{n(j)+1}}{x_+(j) -x_-(j)}$, $\dsp x_{\pm}(j) = 1+\delta(j) \pm \sqrt{\delta(j) \, (2+\delta(j))}$, $\dsp \delta(j) = \frac{1-2\bar{{\alpha}}(j) -2\bar{{\beta}}(j)}{2\bar{{\beta}}(j)}\,$. Finally, $n(j)$, ${\alpha}(j)$, ${\alpha}'(j)$, ${\beta}(j)$, and ${\beta}'(j)$ are given by $n(1)=a-1$, $n(2)=b-1$, ${\alpha}(1)={\alpha}'(1)=Z(Ap)\, Z(Dq)$, ${\alpha}(2)=Z(Br)\, Z(Er)$, ${\alpha}'(2)=Z(Bq)\, Z(Ep)$, ${\beta}(1)={\beta}'(1)=Z(Ar)+Z(Ap)\, Z(Dq) $, ${\beta}(2)=Z(Bp)+Z(Br)\, Z(Ep) $, ${\beta}'(2)=Z(Bq)+Z(Bq)\, Z(Er) $. \par With these explicit formula, we obtain the following order estimate. Define $C_i$, $i\in\edges$, by $C_{Ar}=1/2$, $C_{Br}=C_{Er}=1$, and $C_i=0$, otherwise. \prpb \prpa{3} For all $i\in\edges$, $\dsp w^{-3} \, Den_i$ and $\dsp w^{-4} \, (Num_i -C_i\, Den_i)$ are rational in $w$ and $h$, analytic at $w=h=0$. \prpe We also find by REDUCE calculation that $O(w^3)$ terms in $Den_i$ do not vanish; \eqnb \eqna{novanish} \lim_{w\to 0} w^{-3} \, Den_i \ne 0 \,,\ \ \ i\in\edges. \eqne The matrix $\tA(a,b,w)$ defined in \secu{s2} is rational in $w$, and has no poles in $w\ge 0$. The explicit form of $\tA(a,b,w=0)$ given below is obtained by explicit calculation of the first derivatives of $\tFF$ given above, using REDUCE. \par Define, for notational simplicity, a matrix $M(a,b)$ by $M(a,b)_{ij} = (b+2)^2 (a+1)^{-1} \tA(a,b,w=0)_{ij}$, $i,j \in \edges $, and put $B_2 = b+2$. Then \[ M(a,b)=\left[ \arrb{ccc} 2 B_2 & 0 & (b^3 + 9 b^2 + 14 b + 12)/12 \\ (a B_2 + b) B_2 & (a + 1) B_2^2 & (b^2 + 4 b + 6) (b - 1)/6 \\ 2 B_2 & 0 & (b^3 + 9 b^2 + 20 b + 24)/6 \\ 0 & 0 & b (b + 4) (b - 1)/6 \\ 2 (a B_2 - 1) B_2 & 2 a B_2^2 & b (b^2 + 4 b + 7) \\ 0 & 0 & b (b + 1) B_2/4 \\ 2 B_2 & 0 & (b^3 + 9 b^2 + 14 b + 12)/6 \\ 2 (a B_2 - 1) B_2 & 2 a B_2^2 & (b^2 + 4 b + 6) (b - 1)/3 \arre \right. \] \[ \left. \arrb{ccc} b (b + 4) (b - 1)/6 & b (b + 5) (b + 1)/12 & 0 \\ b (b^2 + 6 b + 11)/3 & b (2 b^2 + 9 b + 13)/12 & (a - 1) B_2^2 \\ b (b + 4) (b - 1)/3 & b (b + 5) (b + 1)/6 & 0 \\ (b^3 + 9 b^2 + 14 b + 12)/3 & b (b + 5) (b + 1)/6 & 0 \\ 2 b (b^2 + 3 b + 5) & (2 b^2 + 5 b + 8) (b + 1)/2 & 2 (a - 1) B_2^2 \\ b (b + 1) B_2/2 & b (b + 1) B_2/4 & B_2^2 \\ b (b + 4) (b - 1)/3 & b (b + 5) (b + 1)/6 & 0 \\ 2 b (b^2 + 6 b + 11)/3 & b (2 b^2 + 9 b + 13)/6 & 2 (a - 1) B_2^2 \arre \right. \] \[ \left. \arrb{cc} (b^2 + 10 b + 12) (b - 1)/12 & b (b + 7) (b - 1)/12 \\ (b^2 + 4 b + 6) (b - 1)/6 & (2 b^2 + 11 b + 24) (b - 1)/12 \\ (b^2 + 10 b + 12) (b - 1)/6 & b (b + 7) (b - 1)/6 \\ b (b + 4) (b - 1)/6 & b (b + 7) (b - 1)/6 \\ (b^2 + 2 b + 2) (b - 1) & (2 b^2 + 3 b + 8) (b - 1)/2 \\ b (b - 1) B_2/4 & b (b - 1) B_2/4 \\ b (b + 8) (b + 1)/6 & b (b + 7) (b - 1)/6 \\ b (b^2 + 6 b + 11)/3 & b (2 b^2 + 15 b + 37)/6 \arre \right] \ . \] \par All the formula in this appendix except \eqnu{novanish} and the explicit form of $\tA$ are derived by hand. At present the only proof of \eqnu{novanish} is by REDUCE, but it is a ^^ soft' result. It is straightforward to see that \prpu{3} and \eqnu{novanish} imply the estimates in \prpu{REDUCE} for second and third derivatives of $\gg$. The explicit form of $\tA$ is also derived by REDUCE. The required estimates in \secu{s2} are \eqnu{supA}, \eqnu{infA}, and \eqnu{A22}, among which \eqnu{supA} and \eqnu{infA} reflects the network structure of the (pre-) fractal, and \eqnu{supA} is an expectation related to one-dimensional simple random walk. It therefore suffices with relatively soft estimates of $\tA$. With these considerations, presumably, we may be able to avoid computer aided proof after all. For our purpose, rigorous derivation by REDUCE is sufficient. Technical methods of derivation for the formula and estimates derived by hand in this appendix may be interesting in it's own respect, but the derivations are lengthy, and taking into account of the main interest of this paper, we omit further explanations. \begin{thebibliography}{99} \bibitem{AN} K.~B.~Athreya, P.~E.~Nay, {\it Branching processes,} Springer, Berlin Heldelberg New York, 1972. \bibitem{BB2} M.~T.~Barlow, R.~Bass, {\it Coupling and Harnack inequalities for Sierpinski carpets,} Bull.\ Amer.\ Math.\ Soc.\ {\bf 29} (1993) 208--212. \bibitem{BP} M.~T.~Barlow, E.~A.~Perkins, {\it Brownian Motion on the Sierpinski Gasket,} Probab.\ Theory Relat.\ Fields {\bf 79} (1988) 543--623. \bibitem{Cohn1} H.~Cohn, {\it A martingale approach to supercritical branching processes,} Ann.\ Probab.\ {\bf 13} (1985) 1179--1191. \bibitem{Cohn} H.~Cohn, {\it On the growth of the multitype supercritical branching process in a random environment,} Ann.\ Probab.\ {\bf 17} (1989) 1118--1123. \bibitem{FHK} P.~J.~Fitzsimmons, B.~M.~Hambly, T.~Kumagai, {\it Transition density estimates for Brownian motion on affine nested fractals,} Commun.\ Math.\ Phys., to appear. \bibitem{Ham} B.~M.~Hambly, {\it Brownian motion on a homogeneous random fractal} Probab.\ Theory Relat.\ Fields {\bf 94} (1992) 1--38. \bibitem{Ham2} B.~M.~Hambly, {\it On the limiting distribution of a supercritical branching process in a random environment} J.\ Appl.\ Prob.\ {\bf 29} (1992) 499--518. \bibitem{HHK2} K.~Hattori, T.~Hattori, S.~Kusuoka, {\it Self-avoiding paths on the three dimensional Sierpinski gasket,} Publ.\ RIMS {\bf 29} (1993) 455--509. \bibitem{HHW87} K.~Hattori, T.~Hattori, H.~Watanabe, {\it Gaussian field theories on general networks and the spectral dimensions,} Progr.\ Theor.\ Phys.\ Spplement {\bf 92} (1987) 108--143. \bibitem{HHW93} K.~Hattori, T.~Hattori, H.~Watanabe, {\it Asymptotically one-dimensional diffusions on the Sierpinski gasket and the abc-gaskets,} Probab.\ Theory Relat.\ Fields (1994), to appear. \bibitem{HHW94} K.~Hattori, T.~Hattori, H.~Watanabe, unpublished. \bibitem{HW} T.~Hattori, H.~Watanabe, {\it On a limit theorem for non-stationary branching processes,} in E. \c{C}inlar et al. (eds.), {\it Seminar on Stochastic Processes, 1992,} Birkhauser, Boston, 1993, 173--187. \bibitem{Kum} T.~Kumagai, {\it Estimates of transition densities for Brownian motion on nested fractals,} Probab.\ Theory Relat.\ Fields {\bf 96} (1993) 205--224. \bibitem{Kus} S.~Kusuoka, {\it A diffusion process on a fractal,} Proc.\ Taniguchi Symp.\ (1987) 251--274. \bibitem{KZ} S.~Kusuoka, X.~Y.~Zhou, {\it Dirichlet forms on fractals: Poincar\'{e} constant and resistance,} Probab.\ Theory Relat.\ Fields {\bf 93} (1992) 169--196. \bibitem{L} T.~Lindstr\o m, {\it Brownian motion on nested fractals,} Mem.\ Amer.\ Math.\ Soc.\ {\bf 420} (1990) 1--128. \bibitem{O} H.~Osada, {\it Self-similar diffusions on a class of infinitely ramified fractals,} Journ.\ Math.\ Soc.\ Japan, to appear. \bibitem{SB} J.~C.~D'Souza, J~.D.~Biggins, {\it The Supercritical Galton-Watson Process in Varying Environments on one-type varying environment Galton-Watson process,} Stoc.\ Proc.\ Appl.\ {\bf 42} (1992). \bibitem{V} Z.~Vondra\v{c}ek, {\it A characterization of certain diffusions on the Sierpinski gasket by the exit distributions,} preprint. \end{thebibliography} \end{document} %----- Cut here and save in a separate file for figures. ------------ %----- Compile by LaTeX. epic.sty & eepic.sty assumed. ------------- \documentstyle[epic,eepic]{article} \begin{document} \catcode`@=11 \ps@empty \catcode`@=12 \setlength{\unitlength}{1mm} \begin{figure}[h] \begin{center} \begin{picture}(120,120)(0,0) \Thicklines \drawline(0,0)(120,0)(60,103.923)(0,0) \drawline(30,0)(45,31)(60,0)(75,31)(90,0)(100,34.641)(65,34.641)(80,69.282) \drawline(80,69.282)(40,69.282)(55,34.641)(20,34.641)(30,0) \end{picture} \end{center} \end{figure} \clearpage \begin{figure}[h] \begin{center} \begin{picture}(120,120)(0,0) \Thicklines %B \drawline(0,0)(34.641,60) \drawline(51.9615,30)(17.3205,30)(34.641,0) \put(10.3205,30){\makebox(10,10)[l]{\raisebox{-7.5mm}[0mm][0mm]{\bf \LARGE B}}} \put(29.641,30){\makebox(10,10)[t]{\raisebox{-7.5mm}[0mm][0mm]{\bf\LARGE Br}}} \put(15.98,45){\makebox(10,10)[t]{\raisebox{-7.5mm}[0mm][0mm]{\bf\LARGE Bp}}} \put(25.98,15){\makebox(10,10)[r]{\raisebox{-7.5mm}[0mm][0mm]{\bf\LARGE Bq}}} %A \drawline(0,90)(69.282,90) \drawline(17.3205,120)(34.641,90)(51.9615,120) \put(29.641,90){\makebox(10,10)[b]{\raisebox{-7.5mm}[0mm][0mm]{\bf \LARGE A}}} \put(46.9615,90){\makebox(10,10)[t]{\raisebox{-7.5mm}[0mm][0mm]{\bf\LARGE Ar}}} \put(33.3,105){\makebox(10,10)[t]{\raisebox{-7.5mm}[0mm][0mm]{\bf\LARGE Ap}}} %E \drawline(102.282,50)(84.9615,20)(119.6025,20) \put(78.9615,20){\makebox(10,10)[l]{\raisebox{-7.5mm}[0mm][0mm]{\bf \LARGE E}}} \put(102.282,20){\makebox(10,10)[t]{\raisebox{-7.5mm}[0mm][0mm]{\bf\LARGE Er}}} \put(83.62,35){\makebox(10,10)[t]{\raisebox{-7.5mm}[0mm][0mm]{\bf\LARGE Ep}}} %D \drawline(85.282,90)(102.6025,120)(119.923,90) \put(97.6025,120){\makebox(10,10)[t]{\raisebox{-7.5mm}[0mm][0mm]{\bf\LARGE D}}} \put(111.26,105){\makebox(10,10)[r]{\raisebox{-7.5mm}[0mm][0mm]{\bf\LARGE Dq}}} \end{picture} \end{center} \end{figure} \end{document}