First passage time on a multifurcating hierarchical structure

Pramana- J. Phys., Vol. 38, No. 3, March 1992, pp. 219-231. © Printed in India.

First passage time on a multifurcating hierarchical structure

V SRIDHAR, K P N M U R T H Y and M C VALSAKUMAR

Theoretical Studies Section, Materials Science Division, Indira Gandhi Centre for Atomic Research, Kalpakkam 603 102, India

MS received 11 October 1991; revised 9 December 1991

Abstract. Asymptotic behaviour of the moments of the first passage time (FPT) on a one-dimensional lattice holding a multifurcating hierarchy of teeth is studied. There is a transition from ordinary to anomalous diffusion when the parameter controlling the relative sizes of the teeth, is varied with respect to the furcating number of the hierarchy. The scaling behaviour of the moments of FPT with the linear dimensions of the lattice segment indicates that in the anomalcus phase the probability density of the FPT is multifractal.

Keywords. Diffusion; ultradiffusion; first passage time; hierarchical structures; multifractals.

PACS Nos 02.50; 05.40

1. Introduction

Huberman and Kerszberg (1985) proposed a simple model for relaxation in hierarchical structures. Their model consists of random walks on a one-dimensional chain made of a uniformly bifurcating hierarchical array of barriers. Owing to the ultrametric topology (Bourbaki 1966) of the structure, their model is termed ultradiffusion model.

Ever since, various aspects of ultradiffusion have been studied. These, for example, pertain to range, autocorrelation and diffusion distance (Teitel and Domany 1985, 1986; Maritan and Stella 1986a, b; Havlin and Weissman 1986; Teitel et al 1987;

Kohler and Blumen 19~,1); relaxation and localization (Teitel 1988, 1989); biased transport (Ceccatto and Riera 1986); vibrational spectrum (Kierstead et al 1988);

electronic properties (Schneider et al 1987; Roman 1987; Ceccatto et al 1987; Ceccatto and Kierstead 1988; Livi et al 1988); multifurcating structures (Zheng et al 1989;

Herbut and Milosevic 1990; Zheng et al 1991) etc. Of particular interest to us is the study of first passage time (FPT) on such structures and to this we turn our attention below.

Consider a segment of a one-dimensioanl lattice with the sites labelled by integers i = 1, 2 .... , N. To a site i, on this backbone, we attach a tooth with ni sites, ni is modelled to have an hierarchical structure as i goes from 1 to N. This is accomplished by prescribing n~ = R k(° where R and k(i) are integers. We consider a general s-furcating hierarchy, for which, k(/) is given uniquely by the solution of

imod s k+ 1 = vs k (1)

where v is an integer between 1 and s - 1. Note that (1) is a straightforward generalization of the formula given for bifurcating structure (s = 2), see for example 219

220 V Sridhar, K P N Murthy and M C Valsakumar

Matan and Havlin (1989). Accordingly, a segment of Qth hierarchy is constructed by concatenating s segments of (Q - 1)th hierarchy separated by s - 1 teeth, each of size R Q. The iteration starts with a segment of zeroth hierarchy which consists of a backbone of (s - 1) sites, each holding a tooth of size unity.

The random walk starts at a toothless site, i = 0, introduced at the left end of the backbone. At each step, the random walk jumps to any of the nearest neighbour sites, with equal probability. Any site on the backbone has three nearest neighbours. Any site on the tooth, however, has only two nearest neighbours, except the one at the tooth end which has only one nearest neighbour. Also, the site i = 0, has only one nearest neighbour. The random walk would eventually reach the absorbing site (N + 1), another toothless site introduced at the right end of the backbone. Figure 1 shows a bifurcating lattice segment and figure 2 a trifurcating lattice segment. Let T denote the first passage time (FPT) defined as the number of steps the random walk takes to reach the site N + 1 for the first time, starting from 0.

Havlin and Matan (1988) have computed the moments of FPT, for a bifurcating lattice, (s = 2), employing an exact numerical enumeration procedure. They show that the qth moment of T asymptotically (N ~ ~ ) goes as N ~(~) and report numerical results on the exponent z(q) for various values of q ranging from - 2 to + 5. Their

e!!! !t! !!! !t!

Figure 1. Segment of a bifurcating (s = 2) hierarchical lattice with R = 3 and Q = 3.

First passage time on hierarchical structure 221

:!T_!T_!!_TT_II_!!_!!_!!_!!

I N

Figure 2. Segment of a trifurcating (s = 3) hierarchical lattice with R = 4 and Q :-- 2.

results indicate that ~(q) does not go as qz(1). This, in other words means, that different moments scale differently with the system size N, a signature of the multifractal nature of the FPT density. Subsequently, Kahng and Redner (1989) employed an exact enumeration-cum-renormalization procedure and established analytically that 3(1) = 1 + 22 where 22 = log(R)/log(2). For higher moments, they conclude, though not rigorously, that z(q) = 1 + (2q - 1)22. These studies were also confined to bifurcating hierarchy.

In this paper, we investigate FPT on a general s-furcating hierarchical lattice and calculate the asymptotic dependence of its moments on the system size. We employ a techique that builds up the FPT for the whole lattice from the FPTs for going from a site to its nearest neighbour. This technique was first proposed by Zwerger and Kehr (1980) and has since been found useful for studies of diffusion on disordered lattices, [Murthy and Kehr (1989, 1990), Matan and Havlin (1989)]. The technique is briefly described in § 2, where we derive a master equation involving quantities pertaining to the sites on the backbone only. The elimination of the sites on the tooth, through appropriate waiting time densities attached to the corresponding backbone sites, is described in the appendix 1. We obtain in this appendix, a continued fraction recursion relation for the evaluation of the waiting time density. In § 3 we calculate the mean first passage time (MFPT) and investigate its asymptotic dependence on the size of the system. We show that there is a dynamical transition from the diffusive (when R < s) to anomalous (when R > s) behaviour. For the marginal case of R = s there is a logarithmic correction multiplying the diffusive behaviour. In § 4, we present a general formulation for the evaluation of qth moment of FPT and investigate the anomalous regime further, by calculating the higher moments of FPT. We show that for the qth moment of FPT, the exponent can be expressed as, T(q) = 1 + (2q - 1)2s where 2 s = log(R)/log(s). The qth moment of FPT does not go as the qth power of the MFPT, confirming the multifractility of the FPT density for the general s-furcating

222 V Sridhar, K P N Murthy and M C Valsakumar

hierarchy. Finally in § 5 we briefly discuss the principal conclusions of our study and indicate some of the unfinished tasks in ultradiffusion that we would be taking up for further and future studies.

The applications of ultradiffusion are many and we mention a few here. Hierarchical organization plays an important role in molecular diffusion on complex macromole- cules (Austin et al 1975). Relaxation in spin glasses can be interpreted in terms of hierarchically constrained dynamics (Sompolinsky 1981; Palmer et al 1984). Also, it finds applications in a variety of fields that include, for example, computing architectures (Huberman and Hogg 1984), one-dimensional superionic conduction (Boyce and Huberman 1979) and long time behaviour of economic systems (Simon and Ando 1961).

2. Master equation for F P T density

Let d~.~+ ~(m) denote the probability for the random walk to reach the site i + 1 for the first time in m steps, starting from the site i. Both the sites i and i + 1 are on the backbone. We derive a master equation for (~,~+ 1 (m) by considering that the random walk at site i can do any of the following in its next and subsequent steps: (a) it can jump to site i - 1 in one step with probability one-third and subsequently make a first passage from i - 1 to i + 1, in the remaining m - 1 steps with probability ( ~ - ~ , ~ + l ( m - 1), (b) it can jump to the first site on the tooth, denoted by l(ti), in one step with probability one-third and subsequently make a first passage from 1 (ti) to the site i + 1, in the remaining m - 1 steps with a probability denoted by (~1,0,~+ ~(m - 1);

and (c) it can ~ump to the site i + 1 with a probability one-third and this term contributes to Gi, i+ l(m) only for m = 1. Thus, we have

1 A

d,.,+, (m) = -~{G,_ 1.i+ x(m - 1) + G,I,o.i+ 1( m -- 1) + tSm. 1 }

1 ~< i ~< N, (2a)

(~o,1 (m) = 6,,.1. (2b)

Let G(z) denote the generating function corresponding to the density (](n), defined as

6(z)= ~ z"d(n). (3)

n = l

Accordingly, (2) can be transformed to give,

G,.i+ l(z) = 5{6;- 1,i+ ~(z) + 6~.o,~+ l(z) + 1}. Z

(4)

We have Gi_l,i÷t(z)=Gi_l,i(z)Gi, i+~(z), by convolution. The tooth at site i essentially provides for the sojourn of the walk at i. Since the 'waiting time' would be dependent on hi, the number of sites on the tooth, we can formally write,

6.,o.~+ l(z) = W(z; n~)a~,~÷ 1 (z). (5)

In the appendix 1 we show that the waiting time density obeys the continued

First passage time on hierarchical structure 223 fraction recursion relation as

with

W(z; n) =

z/2

1 - ( z / 2 ) W ( z ; n - 1)

W(z; 1) = z. (7)

Then we can recast (4) as,

Gi, i+ l(z) =

z/3

1 - (z/3) [ W(z; ni) + G i_ l,i(z)]

with Go, t (z) = z. F o r first passage from the site i = 0 to the site N + 1, we have, N

GO,N+ 1(z) = I-I Gi, i+ 1(7.). (9)

i=o

Thus, in principle we can construct Go, N +1(7.) and calculate the required statistics of FPT.

2.1 Properties of the waiting time density W(z;n~)

It is readily seen that W. = W(z = 1; n) = 1 for all n. We first recast (6) as,

[ z

1

z

w ~ 1) - w ~ ~ = 2 (11)

and

q - 1

w(nq) -- Wlq) l = q" w(nq-~) "~- E qCd{d" w(nd--~) JI- w(d) 1 } W(n q-d)

dr1 ⁽¹²⁾

and

Wt~ 1) = 2n - 1 (13)

n - 1 n - 1 q - 1

W~)=q E W~ -1)+ ~ E 'Cd{d.W~ -1)+ W~ )} W,q-d),. =+a • (14) m = l m f l d = l

Substituting for W~ 1) in (14) one can calculate W~ 2). Using W~ 1) and W~ 2) one can calculate W~ 3). Thus any W~ ) can in principle be calculated using all the earlier derivatives of W(z; n) evaluated at z = 1.

It can also be seen from (14) that the highest power of n in W~ ) can come only from the product of the highest power of m occurring in W~ ) and W~_~ J in the sum

n - 1 q - 1

E E ' c . w ' .

' '

m = l d = l

for q >/2. We have used the notation W~ ) to denote the rth derivative of W(z; m) with respect to z; evaluated at z = 1. The recursion relations (11) and (12) can be solved to give

224 V Sridhar, K P N Murthy and M C Valsakumar

Since the highest power of m in W~ ) is 1, the highest power of m occurring in the sum in (15) is 2 for q = 2. On carrying out the sum over rn we get the highest power o f n in VV ~2~ as 3. Similarly for q = 3 we see that highest power of m in the summand of(15) is 4 which when summed over m gives the highest power of n in W(~ 3~ as 5. Continuing in a similar fashion we find that the highest power of n in W (4~, W(~ 5), W(~ 6), W(, 7),

W(Sl ..-, W~l , are 7,9, 11, 13, 15 .... (2q - I) respectively.

The coefficient of the highest power of n can be found out as follows:

Let the coefficient of the highest power of m in W~ ~ be denoted by c,. Then, since the highest power of m in W~ I is found to be (2r - 1), we get from the sum in (15) the following relation

l q - 1

c~ = 2q - 1 d~ 1= qCacac~-a (16)

with Cl = 2. The factor 1/(2q - 1) comes because of the summation over the tooth sites.

That is, it comes from the term m t2a- ~)m t2~- 2d-11 which, when summed over m from

1 t o n - 1, gives the term with highest power as n t2~- 'J/(2q- 1).

Alternatively, (Valsakumar 1991), the continued fraction recursion relation given by (6), can be expressed as a second order difference equation which can be solved to yield,

1 1 - z 2 ~ , 1

W(z;n)- L (17)

Z n 2 rn=l 1 - - Z c o s O n ,

where Om= ( 2 m - 1)~/2n. Differentiating q times with respect to z and setting z = 1, we get

W~ )=qt-)-" ~ (COS0m)q-l(1 +COS0m) (18)

n , . = 1 (1 -- cos 0,,,) z

Expanding the summand in the above in powers of m and reorganising the terms, we get

W(q~ = n2q - 1 q!23q+r~ a~ 1 ,~=1 ~ (2m - 1) 2q + 1 O(n2q-3) (19)

which can be shown to be q!23q +1 where

~ 1

is the usual zeta function. Thus to the leading order, W(~ q~ is given by

W n ,'., c q n 2q - ,

(19a)

(20)

(21)

First passaoe time on hierarchical structure 225 3. Computation of the MFPT

On differentiating (9) with respect to z and setting z = 1 we get for the M F P T

N

( T ) = G(ot,~ +~ = E G~,)+, (22)

i = O

where the superscript within braces denotes the order of differentiation.

G(I) i,i+1 can be obtained from (8) as

G(1) ~(i) t,b'(1)

i , i + l = u i - . , i -]- - JI- • " " n(i) (23)

where W~]) denotes the first derivative of W(z; n~) with respect to z, evaluated at z = 1.

The first-order recursion relation (23) can be solved to give

vi.i+c~l) x = 1 + 3i + ~ w(l),, ,u). (24)

j = !

Substituting the above in (22) we get

N N i

( T ) = G(o*,)N+I = G(ol,)~ + E (1 + 3 0 + E E W(.IJ) • (25)

i = l i = l j = l

Since 1.1/-I1) _{" n(i)} ^__ 2n i _ 1, see (13), we get

N

( T ) = I + ~ ( l + 2 0 + D (26)

i = l

where, D denotes the double sum given by,

N i

D = 2 E E n J (27)

i = 1 j = 1

and is evaluated explicitly below so that we can exploit the pattern in the subsequent section. D can be recast as

N N

O = 2(N + 1) E " , - 2 E i,,. (28)

i = 1 1 = 1

Since by the construction of the lattice we have a specific (0 ~< k ~< Q) attached to each i, we can convert the summation over i to that over k. See (B4) and (B6) of appendix 2.

We have,

whence,

• ni = ~ (s-1)SQ-kR k,

i = 1 k = 0

in~ = s ( s - 1)S2Q-kR k,

i = 1 k

k=oL S _l

(30)

(31)

226 V Sridhar, K P N Murthy and M C Valsakumar

Since the size of the system L = N + 1 = s q+ ~ and since R Q+ I can be expressed as L z~ we get,

s - 1 1 L2 for R

[ _ _ ~ L,(~, [ R - 2 s + 1

k R - s A + L --RZs d ^S

( T ) = (32)

I ~ - ~ l L2 logs L + L 2 Thus for L ~ 0% we get

Is-- 1 ]

( T ) = R ~

for R = s .

for R > s (33)

exhibiting anomalous diffusion.

For R < s,

[ R - 2s + 1 ( T ) = L R ~ - s ] L2 and the walk is diffusive.

The transition from normal to anomalous diffusion occurs at R = s, where (34)

( T ) = L21ogL~ogs. (35)

We notice that it is the double sum over w m that determines the M F P T in the _{- - N t} anomalous regime.

In the next section we calculate the higher moments of the FPT. We show that, like in the case of MFPT, it is the double sum of the qth derivative of W(z; n~) evaluated at z = 1 (denoted by w~q) ~ that determines the asymptotic behaviour of "" n(i)!

the qth moment of FPT, in the anamolous regime.

4. Calculation of higher moments of FPT 4.1 General formulation

The qth factorial moment of F P T is given by the qth derivative of Go,N ÷ 1 (z) evaluated at z = l, and let this quantity be denoted by GtJ,~ +1.

Equation (9) implies

q - - ! N / N ~(d)

"o.N+rZ'to) ~ = ",.,+rz't") x + Z q-~Ca ~ Gt"-'i.,-~[ I-I Gz~+l(z)] (36)

i=O d = l i = 0 \ j = O /

where [.]ta) denotes the dth derivative of the expression within the braces with respect to z and evaluated at z = 1.

Except for the direct term, none of the cross-terms contain the qth derivative. The cross terms contain terms like

faq~ ~ ~tq-a,t'z.<a, • vi,i+l~j,j+l, j j~i

f~e ~, Z Z Gl,qi~-nx - ~' G~, d} +1 G(ke,)k +X"" etc. (37)

i j ~ i k ~ i ~ j

with f ] , f i e .... as constant coefficients and 1 <~ q - d,q - d - e,d,e, ... <~ q.

First passage time on hierarchical structure 227 In general the rth derivative of G~,~ + 1 (z) can be obtained from the recursion relation

[ z ] z (38)

1 - ~ { W.(o(z) + G , _ Li(z)} G/,,+ 1 (z) = ~.

Applying Leibnitz rule and noting that w(o)...,) = 1 and ujjTt"(°)- = 1 we get G(r) ^{= G(r) +} W ( r ) -I- 9 , . C . ( r - I )

i , i + X i - l , i ' " n ( i ) ~ z ' ' v i , i + l "~-(~r,l r - - i

+ 2 t r P f A r - d ) I "~'dVi, i-I "~-~ ~ . t r - l p "~dlVi, i+l ~ ( r - l - d ) l t I M ( d ) ' ~ " .¢i~ + G~d)-t.i)" (39)

d = l

By substituting iteratively for wtd) ~_ r=(d) from the same equation one can express r , n(i) - - " J i - l , i

G{O i , i + l in terms of w{,) and all lower order derivatives of G~,~+ 1 (z) at z = 1. Note that . "" n(i)

this also means that each derivative of Gi,~+ ~ (z) implies the same derivative of W.o)(z) plus products of other lower order derivatives of W.t0(z ) evaluated at z = 1.

The recursion relation (39) can be solved to give G(') j , j + l = 6 , 1 + ~ { uv(') , ' ' n(i)'q" ~ ' ~ i , i + ") vg~'-(r -- 1 ) -JC (~r 1 l ,

i = l

)}

+ ~ t , r c(,-a> "-'d'-'i,i- 1 + "~ ,.tr-lc" ~C(,-1-,~)~tW(,l) "-'a~'-'i,i+ ~ '~ "" "<0 + G ~ m (40)

d = X

which for r = 1 reduces to (24) as indeed it should.

4.2 Asymptotic behaviour of higher moments in the anomalous regime From (21) we see that the highest power of ni in W (q).~ is c~.n~ ~-x.

Equation (40) shows that the term with the highest power of ni in r.(~) • -q,i + x comes

i Cq" n 2 q - 1.

only from Z ~ j = I " ' n j W(~) which goes as E j= 1

The remaining terms contain only summations of n~ raised to the power 2 q - 2 and less. Even though the calculation of higher derivatives of G~,~+l(Z) and W(z; ni) look similar, the leading behaviour of c(~) ,~,i+ ~ comes from the direct term, while the leading behaviour of W(n~) came from the cross terms. This difference is due to the fact the summation in the former is over backbone sites which are dissimilar, while.

the summation in the latter is over the tooth sites which are identical (except at the end points).

Therefore substituting,

i

G(q) i , i + 1 ~ ~ r n2q -1 ~ q " j (41)

i = 1

in (36) and carrying out the summation in a manner similar to that in § (3), we see that the direct term goes as U (q), where z(q)= 1 + ( 2 q - 1)logRflogs.

The contribution to --o.Nr'(e) + 1 from the cross-terms shown in (37) are respectively less than L raised to the power z(q) - (logsR - 1), z(q) - 2(logsR - 1), etc.

Therefore only the direct term contributes to (36) for large size of the system. Thus for L ~ ~ , since only the qth moment would dominate the factorial moment obtained from (36), and we get,

I s - 1 ] L "(''. (42)

( T ~ ) " C q R ~ q _ l _ s

228 V Sridhar, K P N Murthy and M C Valsakumar

Thus we find that the qth moment of FPT does not go as the qth power of the first moment. In fact the relative values of the higher moments become unbounded as the linear dimension of the lattice segment increases. In particular, the fluctuations, defined as the standard deviation divided by the M F P T increases with the system size as L raised to the power (As- 1)/2.

5. Conclusions

The principal and new findings of our study are stated briefly below.

We have obtained exact results on the mean first passage time as a function of the linear dimension L for a multifurcating hierarchical structure. When the parameter R controlling the relative sizes of the teeth is less than the furcating number s of the hierarchy, the random walk is purely diffusive. There is a transition to anomalous diffusion when R becomes greater than s. Thus our work extends and generalizes the recent study on a bifurcating structure, reported by Kahng and Redner (1989).

In the anomalous regime, R > s, we have derived expressions for the asymptotic dependence o f the higher moments of FPT on L. We find that the scaling exponent z(q) for the qth moment is given by z(q)= 1 + ( 2 q - 1 ) l o g R / l o g s . Our work thus establishes rigorously the expression for z(q) for a bifurcating hierarchical structure, besides generalizing it to multifurcating hierarchy. This has become possible because in our formulation, the dominant behaviour separates out naturally. In the renormaliza- tion scheme adopted by Kahng and Redner (1989) the dominant behaviour does not separate out neatly, though one can guess the leading behaviour intuitively.

Thus we show that in the anomalous regime, the qth moment of FPT does not go as the qth power of the first moment. In particular, we see that the fluctuations of the FPT--defined as the square root of the second cumulant divided by the MFPT--increase with the system size as square root of L raised to the power of (As- i).

The above scaling behaviour of the moments suggests that the probability density of FPT is a multifractal, as reported first by Havlin and Matan (1988) for a bifurcating structure. This aspect needs further investigation. It would indeed be interesting to calculate the different fractal dimensions to characterize the multifractality of F P T probability density. This problem can be approached in two ways. One could invert the generating function Go,.N + 1 (z) and obtain the F P T probability density, (~om + 1 (m).

The fractal dimension of G0,N+l(m) can then be calculated. Alternatively, one could analyse the generating function Go.N+t(z) directly and calculate the multifractal dimension. The recent work of Godreche and Luck (1990) on multifractal analysis in reciprocal space should prove useful in this context. Another interesting problem is the interplay of bias and ultradiffusion and their influence on the scaling properties of the FPT moments. Lin and Tao (1990) have obtained some interesting results and it would be useful to extend their studies to multifurcating structures.

There are other ways of organizing the hierarchical structures, besides the construction in figures 1 and 2 that we have investigated in this paper. It would be interesting to study ultradiffusion in some alternate hierarchical structures (Sridhar

1991).

First passage time on hierarchical structure 229 Appendix 1

Master equation for the tooth

Let us consider the tooth at backbone site i. The sites on this tooth are denoted by l(ti), 2(ti) .... j(ti) .... n(ti). Let t~jta~,i + l(m) denoted by t~(m) be the FPT density from the tooth sitej to the backbone site i + 1. The generating functions G~(z), (1 ~ j ~< n)"

obey a set of n coupled equations given below:

Odz)

G2(z) = 2{G3(z) + Gl(z)}

G~(z) = z { o , ( z ) + O~(z)}

z;

G.(z) = zG._ 1 (z).

Substituting for G.(z), G._x(Z),...G3(z), Gz(z), and Gl(z) from the last equation upwards up to the first equation we see that,

G1 (z) = W(z; n)Gi,i+ t (z) (AI)

where the waiting time density W(z; n), obeys a continued fraction recursion relation given by

(z/2)

W(z;n)

1 - ( z / 2 ) W ( z ; n - 1) with

W(z;

Appendix 2

Some useful properties of s-furcatinfl hierarchical lattice

In our calculation of the moments of FPT we need expressions for

(i) N(Q), the number of sites on the backbone of a segment of hierarchy Q, (ii) N(k, Q), the number of times tooth of size R ~ occurs in a segment of hierarchy Q, (iii) W(k, Q) the sum of all the backbone site indices that support tooth Of size R k in a segment of hierarchy Q.

a) Calculation of N(Q)

The above is calculated by noting that the segment of hierarchy Q consists of s segments of hierarchy Q - 1 plus s - 1 sites each having a tooth of size R k. This

230 V Sridhar, K P N M u r t h y and M C Valsakumar implies that N(Q) obeys the following difference equation

N(Q) = sN(9. - i) + ( s - 1) with

NO) = s - 1.

This difference equation can be solved and we get, N (Q) = s o-+ 1.

(m)

(B2) b) Calculation of N(k, Q)

From the construction of the segment of hiearchy Q, it is clear s N ( k , Q - 1 ) for k < Q

N(k, Q) = s - 1 k = Q

0 k > Q

from which it follows,

(B3)

N ( k , Q ) = s Q - k ( s - 1) for k <<. Q. (B4)

c) Calculation of W(k, Q)

An expression for T(k, Q) is derived as follows. The lattice indices of the backbone sites that hold teeth of size R k are given by

vi,~(k; Q) = skj + s k+ t (i -- 1) (a5)

with j running from 1 to ( s - 1) and i running from 1 to s e-k.

Summing vi, j over i and j, we get

qJ(k, Q) = l s ( s - 1)s zo--k. (B6)

A

References

Austin R H, Berson K W, Frauenfelder L H and Gunslauss I C 1975 Biochemistry 14 5355 Bourbaki N 1966 Espaces Vectorials Topologiques (Paris: Hermann)

Boyce J B and Huberman B A 1979 Phys. Rep. 51 189 Ceccatto H A and Kierstead W P 1988 J. Phys. A21 L75

Ceccatto H A, Kierstead W P and Huberman B A 1987 Phys. Rev. A36 5509 Ceccatto H A and Riera J A 1986 J. Phys. A19 L721

Godreche C and Luck J M 1990 J. Phys. A23 3769 Havlin S and Matan H 1988 J. Phys. A21 L307 Havlin S and Weissman H 1986 J. Phys. AI9 L1021 Herbut I and Milesovic 1990 J. Phys. A23 99

Huberman B A and Hogg T t984 Phys. Rev. Lett. 52 1048 Huberman B A and Kerszberg M 1985 J. Phys. A18 L331 Kahng B and Redner S 1989 J. Phys. A22 887

Kierstead W P, Ceccatto H A and Huberman B A 1988 J.Stat. Phys. 53 733

First passage time on hierarchical structure 231 Kohler G and Blumen A 1991 J. Phys. A24 2807

Livi R, Maritan A and Raffo S 1988 J. Stat. Phys. 52 595 Lin Z and Tao R 1990 J. Phys. A23 L29

Maritan A and Stella A L 1986a J. Phys. AI9 L269 Maritan A and Stella A L 1986b Phys. Rev. Lett. 56 1754 Matan O and Havlin S 1989 Phys. Rev. A40 6573 Murthy K P N and Kehr K W 1989 Phys. Rev. A40 2082 Murthy K P N and Kehr K W 1990 Phys. Rev. A41 1160(E)

Palmer R G, Stein D L, Abrahams E and Anderson P W 1984 Phys. Rev. Lett. 53 958 Roman H E 1987 Phys. Rev. B36 71

Schneider T, Wurts D, Politi A and Zanetti M 1987 Phys. Rev. B36 1789 Simon H A and Ando A 1961 Econometrica 29 111

Sompolinsky H 1981 Phys. Rev. Lett. 47 935

Sridhar V 1991 F P T on an alternate hierarchical structure, Paper under preparation Teitel S 1988 Phys. Rev. Lett. 60 1154

Teitel S 1989 Phys. Rev. B39 7045

Teitel S and Domany E 1985 Phys. Rev. Lett. 55 2176 Teitel S and Domany E 1986 Phys. Rev. Lett. 56 1755 Teitel S, Kutasov D and Domany E 1987 Phys. Rev. B36 684 Valsakumar M C 1991 unpublished notes

Zheng D, Lin Y, Deng W and Zou N 1991 J. Phys. A2,4 L123 Zheng D, Lin Z and Tao R 1989 J. Phys. A22 L287

Zwerger W and Kehr K W 1980 Z. Phys. !140 157