Biased random walks on random combs
Tanya M Elliott and John F Wheater
Department of Physics, University of Oxford
Rudolf Peierls Centre for Theoretical Physics,
1 Keble Road,
Oxford OX1 3NP, UK
E-mail: t.elliott1@physics.ox.ac.uk, j.wheater@physics.ox.ac.uk
Abstract. We develop rigorous, analytic techniques to study the behaviour of biased
random walks on combs. This enables us to calculate exactly the spectral dimension
of random comb ensembles for any bias scenario in the teeth or spine. Two specific
examples of random comb ensembles are discussed; the random comb with nonzero
probability of an infinitely long tooth at each vertex on the spine and the random comb
with a power law distribution of tooth lengths. We also analyze transport properties
along the spine for these probability measures.
PACS numbers: 05.40.Fb, 04.60.Nc, 05.45.Df
1. Introduction
The behaviour of random walks on random combs is of interest from a number of points
of view. Condensed matter physicists have studied such structures because they serve
as a model for diffusion in more complicated fractals and percolation clusters [1, 2, 3, 4].
In the context of quantum gravity, random combs are a tractable example of a random
manifold ensemble and understanding their geometric properties can provide insight
into higher dimensional problems [5, 6, 7]. Most of the literature concerns approximate
analytical techniques and numerical solutions, although there are exact calculations of
leading order behaviour in some cases [8]. To this end, it is desirable to have rigorous
methods for determining the geometric quantities of interest and that is the purpose of
this paper.
One such quantity is the dimensionality of the ensemble. On a sufficiently smooth
manifold all definitions of dimension will agree, but for fractal geometries like random
combs this is not necessarily true. The spectral dimension is defined to be ds provided
the ensemble average probability of a random walker being back at the origin at time t,
takes the asymptotic form t−ds/2. This concept of dimension does not in general agree
with the Hausdorff dimension dH , which is defined when the expectation value of the
volume enclosed within a geodesic distance R from a marked point scales like RdH as
R → ∞.
http://arxiv.org/abs/0704.0188v2
Biased random walks on random combs 2
We know that for diffusion on regular structures the mean square displacement at
large times is proportional to t, but for a fractal substrate there is anomalous diffusion
and the mean square displacement behaves like t2/dw , where dw represents the fractal
dimension of the walk and depends sensitively on the nature of the random structure.
Biased random walks on combs have also been studied in connection with disordered
materials, since such a system is a paradigm for diffusion on fractal structures in the
presence of an applied field [9, 10]. As we discuss later there are several different bias
regimes. Topological bias, where at every vertex in the comb there is an increased
probability of moving away from the origin was first studied for a random comb with a
power-law distribution of tooth lengths in [11]. Other works have discussed the effects
of bias away from the origin only in the teeth [12] and only in the spine [13]. The effect
of going into the teeth can be viewed as creating a waiting time for the walk along the
spine; the distribution of the waiting time depends on both the bias and the length of
the teeth and the outcome is the result of subtle interplay between the two.
In [14] some new, rigorous techniques were developed to study random walks on
combs. This enabled an exact, but very simple calculation of the spectral dimension of
random combs. The principal idea is to split both random combs and random walks
into subsets that give either strictly controllable or exponentially decaying contributions
to the calculation of physical characteristics. These methods were later reinforced to
prove that the spectral dimension of generic infinite tree ensembles is 4/3 [15, 16]. In
this paper we use and extend the techniques of [14] to deal with biased walks on combs.
Some of our results are new; some qualify statements made in the literature; and some
merely confirm results already derived by other, usually less rigorous, methods.
The random combs, the bias scenario, some useful generating functions and the
critical exponents are defined in the next section. In Section 3 we introduce some
deterministic combs, discuss general properties of the generating functions and establish
bounds that will be instrumental when studying random ensembles. Section 4 looks at
regions of bias where the large time behaviour is independent of the comb ensemble or
simply dependent on the expectation value of the first return generating function in the
teeth. In Section 5 we compute the spectral dimension in regions of bias where it is
influenced by the probability measure on the teeth. Two specific cases are considered:
the random comb with nonzero probability of an infinitely long tooth at each vertex on
the spine and the random comb with a power law distribution of tooth lengths. Section
6 examines transport properties along the spine for these same probability measures and
in the final section we review the main results, compare with the literature and discuss
their significance. Some exact calculations and proofs omitted from the main text are
outlined in the appendices.
2. Definitions
Wherever possible we use the definitions and notation of [14]; we repeat them here for
the reader’s convenience but mostly refer back to [14] for proofs and derived properties.
Biased random walks on random combs 3
2.1. Random combs
LetN∞ denote the nonnegative integers regarded as a graph so that n has the neighbours
n ± 1 except for 0 which only has 1 as a neighbour. Let Nℓ be the integers 0, 1, . . . , ℓ
regarded as a graph so that each integer n ∈ Nℓ has two neighbours n± 1 except for 0
and ℓ which only have one neighbour, 1 and ℓ− 1, respectively. A comb C is an infinite
Figure 1. A comb.
rooted tree-graph with a special subgraph S called the spine which is isomorphic to N∞
with the root, which we denote r, at n = 0. At each vertex of S, except the root r, there
is attached by their endpoint 0 one of the graphs Nℓ or N∞. The linear graphs attached
to the spine are called the teeth of the comb, see figure 1. We will denote by Tn the
tooth attached to the vertex n on S, and by Ck the comb obtained by removing the links
(0, 1), . . . , (k − 1, k), the teeth T1, . . . , Tk and relabelling the remaining vertices on the
spine in the obvious way. An arbitrary comb is specified by a list of its teeth {T1, . . .}
and |Tk| denotes the length of the tooth. Note that we have excluded the possibility
of a tooth of zero length. This is for technical convenience in what follows and can be
relaxed [17].
In this paper we are interested in random combs for which the length ℓ of each
tooth is identically and independently distributed with probability µℓ. This induces a
probability measure µ on the positive integers and expectation values with respect to
this measure will be denoted 〈·〉µ. In particular we will consider the two measures
µAℓ =
p, ℓ = ∞,
1− p, ℓ = 1,
0, otherwise;
µBℓ =
, a > 1. (1)
Biased random walks on random combs 4
However, the results proved for µB apply to any measure with the same behaviour at
large ℓ and we note in passing that the methods used here will work for any distribution
that is reasonably smooth, for example the exponential distribution. The measure µB
has been discussed quite extensively in the literature but µA has not.
2.2. Biased random walks
We regard time as integer valued and consider a walker who makes one step on the
graph for each unit time interval. If the walker is at the root or at the end-point of a
tooth then she leaves with probability 1. If at any other vertex the probabilities are
parametrized by two numbers ǫ1 and ǫ2 as shown in figure 2a and the allowed range of
these parameters is shown in figure 2b. For walks in the teeth there is bias away from or
towards the spine depending on whether ǫ2 is positive or negative; similarly a walk on
the spine is biased away from or towards the root depending on whether ǫ1 is positive
or negative. When there is no bias we say that the walk is ‘critical’; the fully critical
case ǫ1 = ǫ2 = 0 was covered in [14]. The notation
b− = 1− ǫ1 − ǫ2,
b+ = 1 + ǫ1 − ǫ2,
bT = 1 + 2ǫ2, (2)
will be used where applicable since these combinations appear often in our analysis. We
denote by B,B′, B1, B2 etc constants which depend on ǫ1 and ǫ2 and may vary from line
to line but are positive and finite on the relevant range; other constants will be denoted
c, c′ etc.
The generating function for the probability pC(t) that the walker on C is back at
the root at time t having left it at t = 0 is defined by
QC(x) =
(1− x)t/2pC(t). (3)
Letting ω be a walk on C starting at r, ω(t) the vertex where the walker is to be found
at time t, and ρω(t) the probability for the walker to step from ω(t) to ω(t+1), we have
QC(x) =
ω:r→r
(1− x)
|ω|−1
ρω(t). (4)
A similar relation gives the generating function for probabilities for first return to the
root, PC(x), except that the trivial walk of duration 0 is excluded. The two functions
are related by
QC(x) =
1− PC(x)
, (5)
and it is straightforward to show that PC(x) satisfies the recurrence relation
PC(x) =
(1− x)b−
3− b+PC1(x)− bTPT1(x)
. (6)
Biased random walks on random combs 5
PSfrag replacements
(1 + 2ǫ2)
(1− 2ǫ2)1
(1 + 2ǫ2)
(1− ǫ1 − ǫ2) 13(1 + ǫ1 − ǫ2)
PSfrag replacements
(1 + 2ǫ2)
(1− 2ǫ2)
(1 + 2ǫ2)
(1− ǫ1 − ǫ2)
(1 + ǫ1 − ǫ2) ǫ1
Figure 2. Bias parameterisation.
Note that PC(x) and QC(x) depend upon ǫ1 and ǫ2; to avoid clutter we will normally
suppress this dependence but if necessary it will appear as superscripts. It is important
for what follows that QC is a convex function of PC which is itself a convex function of
PT1 , ...PTk , PCk for any k > 0.
For an ensemble of combs, we will denote the expectation values of the generating
functions for return and first return probabilities as
Q(x) = 〈QC(x)〉µ
P (x) = 〈PC(x)〉µ . (7)
We will say that g(x) ∼ f(x) if there exist positive constants c, c′, σ, σ′ and x0 such
c f(x) exp
−σ(log |f(x)|)1/a
< g(x) < c′ f(x)| log f(x)|σ′ (8)
for 0 < x ≤ x0. The tactic of this paper is to prove bounds of this form for the generating
functions; in almost all cases our results are in fact a little stronger having σ = σ′ = 0
Biased random walks on random combs 6
when we will say that g(x) ≈ f(x).
The random walk on C is recurrent if PC(0) = 1 in which case we define the
exponent β through
1− PC(x) ∼ xβ . (9)
If β is an integer then we expect logarithmic corrections and define β̃ if
1− PC(x) ≈ xβ | log x|−β̃. (10)
It follows that QC(x) diverges as x → 0 and we define α by
QC(x) ∼ x−α, (11)
and if α is an integer, α̃ when
QC(x) ≈ x−α| log x|α̃. (12)
If PC(0) < 1 then the random walk is non-recurrent, or transient, and QC(x) is finite
as x → 0. Then if, as x → 0, the first k − 1 derivatives of QC(x) are finite but the kth
derivative diverges we define the exponent αk by
C (x) ∼ x
−αk , (13)
and if αk is an integer, α̃k when
C (x) ≈ x
−αk | log x|α̃k . (14)
In considering the ensemble of combs µ, we define all these exponents in exactly
the same way simply replacing PC(x) with 〈PC(x)〉µ and so on. Note that for a single
recurrent comb β = α but in an ensemble this is no longer necessarily the case; applying
Jensen’s inequality to (5) we see that β ≤ α.
If Q(k)(x) ∼ x−αk then it is straightforward to show that
Rk(λ) =
tk 〈pC(t)〉µ ∼ λ
−αk . (15)
It follows that if the sequence decays uniformly at large t, which we do not prove, then
it falls off as tαk−1−k. Thus we define ds = 2(1 + k − αk). Similarly if Q(x) ≈ | log x|α̃
then R(λ) ≈ | log λ|α̃ and, again assuming uniformity, p(t) falls off as t−1 | log t|α̃−1.
2.3. Two-point functions
Let p1C(t;n) denote the probability that the walker on C, having left r at t = 0 and not
subsequently returned there, is at point n on the spine at time t. The corresponding
generating function, which we will call the two-point function, is defined by
GC(x;n) =
(1− x)t/2p1C(t;n). (16)
Letting ω be a walk on C starting at r and ending at n without returning to r we have
GC(x;n) =
ω:r→n
(1− x)
|ω|−1
ρω(t). (17)
Biased random walks on random combs 7
Following the discussion in section 2.2 of [14] this leads us to the representation
GC(x;n) =
b+(1− x)n/2
PCk(x). (18)
2.4. The Heat kernel
Let KC(t;n, ℓ) denote the probability that the walker on C, having left r at t = 0, is at
point ℓ in tooth Tn at time t. KC(t;n, ℓ) satisfies the diffusion equation on C so we call
it the heat kernel. The probability that the walker has travelled a distance n along the
spine at time t is given by
KC(t;n) =
KC(t;n, ℓ), (19)
and has generating function
HC(x;n) =
(1− x)t/2KC(t;n). (20)
HC(x;n) can be written as
HC(x;n) =
GC(x;n)
1− PC(x)
D|Tn|(x), (21)
where
Dℓ(x) = 1 +
GNℓ(x; k), (22)
and we define
H(x;n) = 〈HC(x;n)〉µ . (23)
Note that, because KC(t;n) is a probability,
H(x;n) =
. (24)
The exponent dk is defined through the moments in n
nk H(x;n) ≈ x−1−dk , (25)
and in the case dk = 0 the exponent d̃k is defined when
nk H(x;n) ≈ x−1 | log x|d̃k . (26)
If ǫ1 ≥ 0 one can show that on any comb 〈n〉ω:|ω|=t is a non-decreasing sequence and
thus that there is some constant T0 such that for T > T0
| log T |
〈n〉ω:|ω|=T + 〈n〉ω:|ω|=T+1
< c T d1, d1 6= 0
c | log T |d̃1 <
〈n〉ω:|ω|=T + 〈n〉ω:|ω|=T+1
< c | log T |d̃1, d1 = 0.
Biased random walks on random combs 8
If ǫ1 < 0 (for which we always have d̃1 = 0) then we have only the weaker result that
for T > T0
| log T |
)1+d1
〈n〉ω:|ω|=t
< c T 1+d1 . (28)
3. Basic properties
3.1. Results for simple regular combs
The relation (6) can be used to compute the generating functions for a number of simple
regular graphs which will be important in our subsequent analysis [14].
(i) An infinitely long tooth, N∞:
P∞(x) =
2 if ǫ2 = 0;
1− 2|ǫ2|
4|ǫ2|
(1− 2ǫ2) +O(x2) otherwise.
(ii) A tooth of length ℓ, Nℓ:
Pℓ(x) = P∞(x)
1 +XY 1−ℓ
1 +XY −ℓ
where
bT (1− P∞(x))
2− bT (1 + P∞(x))
, Y =
2− bTP∞(x)
bTP∞(x)
. (31)
(iii) The comb ♯ given by {Tk = N1, ∀k} has all teeth of length 1, and
P♯(x) =
1− B1x
2 +O(x) if ǫ1 = 0;
1− ǫ2 − |ǫ1|
− x B2
+O(x2) otherwise.
Note that ♯ is non-recurrent if ǫ1 > 0. It is also convenient to define ℓ♯ to be
{T1 = Nℓ, C1 = ♯}.
(iv) The comb ∗ given by {Tk = N∞, ∀k} has all teeth of length ∞ and is non-recurrent
for ǫ2 > 0,
P∗(x) =
1 + ǫ2 −
4ǫ2 + ǫ
− x B1√
4ǫ2 + ǫ
+O(x2). (33)
Otherwise
P∗(x) =
1− |ǫ1|
1 + ǫ1
2 +O(x) if ǫ2 = 0, ǫ1 6= 0;
1− ǫ2 − |ǫ1|
+O(x2) if ǫ2 < 0, ǫ1 6= 0;
1− B4x
2 +O(x) if ǫ2 < 0, ǫ1 = 0.
Biased random walks on random combs 9
(v) The comb ♭ℓ given by {Tk = Nℓ, ∀k} has all teeth of length ℓ and
P♭ℓ(x) =
1− |ǫ1|
1 + ǫ1
(ℓ+ 1 + |ǫ1|)x+O(x2ℓ2) if ǫ2 = 0, ǫ1 6= 0;
1− ǫ2 − |ǫ1|
|ǫ1ǫ2|
+O(xY −ℓ) if ǫ2 < 0, ǫ1 6= 0;
2 +O(x
2Y −ℓ) if ǫ2 < 0, ǫ1 = 0;
where, as x → 0,
Y → 1 + 2|ǫ2|
1− 2|ǫ2|
. (36)
When ǫ2 > 0 let ℓ̄ = ⌊| log x|/ log Y ⌋, where ⌊z⌋ denotes the integer below z. For
ℓ > 2ℓ̄ the teeth are long enough that P♭ℓ(x) behaves like (33). For ℓ̄ < ℓ ≤ 2ℓ̄,
P♭ℓ(x) is non-recurrent with the leading power of x being fractional. For ℓ ≤ ℓ̄
P♭ℓ<ℓ̄(x) =
1− ǫ2 − |ǫ1|
|ǫ1ǫ2|
+O(x) if ǫ1 6= 0;
ℓ +O(x
ℓ, xY −ℓ) if ǫ1 = 0,
where the notation O(a, b) means O(max (a, b)).
3.2. General properties of the generating functions
The generating functions for any comb satisfy three simple properties which can be
derived from (6):
(i) Monotonicity The value of PC(x) decreases monotonically if the length of a tooth
is increased.
(ii) Rearrangement If the comb C ′ is created from C by swapping the adjacent teeth
Tk and Tk+1 then PC′(x) > PC(x) if |Tk+1| < |Tk|.
(iii) Inheritance If walks on Ck or Tk are non-recurrent for finite k then walks on C are
non-recurrent.
The proof of the first two follows that given in [14] for the special case ǫ2 = ǫ1 = 0. The
third can be shown by assuming that either PC1(0) < 1 or PT1(0) < 1; it then follows
immediately from (6) that PC(0) < 1 and the result follows by induction.
3.3. Useful elementary bounds
By monotonicity GC(x;n) is always bounded above by G♯(x;n) from which we get
GC(x;n) <
exp(−nΛǫ1,ǫ2(x)), (38)
Biased random walks on random combs 10
where
Λǫ1,ǫ2(x) =
2 + ǫ2
if ǫ1 > 0,
2 + ǫ2
1− ǫ2
if ǫ1 = 0,
if ǫ1 < 0.
Now let P
C (x) denote the contribution to PC(x) from walks that reach beyond n = N
on the spine. It is straightforward to show using the arguments of section 2.5 of [14]
C (x) ≤
ǫ1,ǫ2
C (x;N)G
−ǫ1,ǫ2
C (x;N). (40)
Combining this with (38) we obtain the useful bound
C (x) ≤
exp(−N(Λǫ1,ǫ2(x) + Λ−ǫ1,ǫ2(x))). (41)
Now consider the ensemble µ′ of combs C for which: Tk = N1, k = 1..K − 1,
TK = Nℓ; at k > K teeth are short, Tk = N1, with probability 1 − p or long, Tk = Nℓ,
with probability p; and the nth tooth is short, Tn = N1. Then using the representation
(18) GC(x;n) can be bounded above by noting that if Tk+1 = Nℓ then PCk < Pℓ♯,
otherwise PCk < P♯. This gives
GC(x, n) ≤
(1− x)−n/2
Pℓ♯(x)
n−K−kP♯(x)
k+K , (42)
and hence
〈GC(x, n)〉µ′ =
n−K−1
n−K−1
pn−K−1−k(1− p)kGC(x, n)
P♯(x)
KPℓ♯(x)
(1− x)n/2
((1− p)P♯(x) + pPℓ♯(x))n−K−1 . (43)
4. Results independent of the comb ensemble µ
In this section we show that in some regions of ǫ1,2 the behaviour at large time is
essentially independent of the comb ensemble, or else simply dependent upon 〈PT (x)〉µ.
The leading, and where different, the leading non-analytic, behaviour of 〈PT (x)〉µ as
x → 0 for the measures studied here is given in table 1. The results for µA are trivial,
as are those for any measure when ǫ2 < 0, while the case µ
B and ǫ2 = 0 can be derived
using the techniques in [14]. The calculation for µB and ǫ2 > 0 is somewhat subtle and
is included in Appendix A.
Biased random walks on random combs 11
Table 1. Leading and leading non-analytic behaviour of 1− 〈PT 〉µ in various cases.
ensemble ǫ2 < 0 ǫ2 = 0 ǫ2 > 0
µA Bx Bx
2 B +B′x
µB, a < 2 Bx Bxa/2 B(| log x|a−1)−1
µB, a = 2k Bx Bx+ . . . B′xk| log x| B(| log x|a−1)−1
µB, a > 2, a 6= 2k Bx Bx+ . . . B′xa/2 B(| log x|a−1)−1
4.1. ds when ǫ2 < 0
First we show that for any comb ensemble
0 if ǫ1 < 0 and ǫ2 < 0;
1 if ǫ1 = 0 and ǫ2 < 0.
By monotonicity we have that for any comb C
P∗(x) ≤ PC(x) ≤ P♯(x). (45)
Taking expectation values and using (32) and (34) it follows that for ǫ2 < 0
P (x) = 〈PC(x)〉µ =
1−B1x
2 +O(x) if ǫ1 = 0,
1− ǫ2 − |ǫ1|
+O(x2) otherwise.
Similarly
Q∗(x) ≤ QC(x) ≤ Q♯(x) (47)
and so
Q(x) = 〈QC(x)〉µ =
+O(1) if ǫ1 = 0,
B2|ǫ1|
+O(1) if ǫ1 < 0,
and (44) follows.
4.2. ds when ǫ1 > 0
When ǫ1 > 0 all combs are non-recurrent and so we must examine the derivatives of
Q(x). Differentiating (5) and (6) gives
C (x) = QC(x)
C (x), (49)
C (x) =
−PC(x)
PC(x)
(1− x)b−
(x) + b+P
. (50)
Biased random walks on random combs 12
By monotonicity (50) can be bounded above and below by replacing PC with P∗ and
P♯ respectively. Taking the expectation value and using translation invariance to note
that 〈PC〉µ = 〈PC1〉µ shows that, if
T (x)
diverges as x → 0, then
Q(1)(x) ∼ B
T (x)
T (x)
, 1). (51)
As can be seen from table 1, in some cases 〈PT (x)〉µ is analytic, or only higher derivatives
diverge. For the measures considered here it can be shown that if 〈PT (x)〉µ is analytic
at x = 0 then so is Q(x). If on the other hand 〈PT (x)〉µ is not analytic but the k’th
derivative diverges then
Q(k)(x) = B
T (x)
T (x)
, 1). (52)
The proof is a straightforward but tedious generalization of (49) and (50) and is relegated
to Appendix B. If a derivative of Q(x) diverges then ds can be read off using (14) and
(52). Otherwise if all finite order derivatives are finite then pC(t) decays at large t faster
than any power and ds is not defined.
4.3. dk when ǫ2 < 0 or ǫ1 < 0
We show that for any comb ensemble
d̃k = 0, dk =
0 if ǫ1 < 0,
k/2 if ǫ1 = 0 and ǫ2 < 0,
k if ǫ1 > 0 and ǫ2 < 0.
It is trivial to show that
1 ≤ Dℓ ≤
, ǫ2 < 0, (54)
and then by monotonicity we get
G∗(x;n)
1− P∗(x)
≤ H(x;n) ≤ B
G♯(x;n)
1− P♯(x)
. (55)
Combining this with (32) and (34) yields the results for ǫ2 < 0.
To deal with ǫ1 < 0 and ǫ2 ≥ 0 note that monotonicity gives
D|Tn|(x)
1− PC(x)
G∗(x;n) ≤ H(x;n) ≤
D|Tn|(x)
1− PC(x)
G♯(x;n). (56)
Using the lower bound and (18), (24) and (33) we get after summing over n
D|Tn|(x)
1− PC(x)
4ǫ2 + ǫ
1 − ǫ1 − 2ǫ2
H(x;n) ≤
. (57)
Inserting this into the upper bound of (56) gives
H(x;n) ≤
4ǫ2 + ǫ
1 − ǫ1 − 2ǫ2
G♯(x;n). (58)
Biased random walks on random combs 13
It is a trivial consequence of (24) that
nkH(x;n) >
, k > 0, (59)
and the results then follow by using (38).
5. The spectral dimension when ǫ2 ≥ 0 and ǫ1 ≤ 0
Here and in some of the sections to follow we will need to sum over the location of the
first long tooth to determine the spectral dimension. Most generally we call a tooth
long when it has length ≥ ℓ and short when it has length < ℓ. Consider combs for
which the first L− 1 teeth are short but the Lth tooth is long; the probability for this
is p(1− p)L−1, where p is the probability of a tooth being long. Denoting by ℓL a comb
having the first long tooth at vertex L gives
Q(x) =
〈QℓL(x)〉µ p(1− p)
L−1. (60)
QℓL(x) is bounded above by the comb in which all teeth at n ≥ L + 1 are short, and
below by the comb in which all teeth at n ≥ L+ 1 are infinite,
Q{Tn<L=Nℓ′ ,ℓ′≤ℓ;Tn≥L=N∞}(x) < QℓL(x) < Q{Tn6=L=N1;TL=Nℓ}(x). (61)
5.1. µA – Infinite teeth at random locations
5.1.1. ǫ2 = 0, ǫ1 < 0 We first show that the exponent β =
– so it is unchanged from
the comb ∗. This result follows from the inequalities
1− pBx
+O(x) ≤ P (x) ≤ 1− pB′x
2 +O(x). (62)
The lower bound is obtained by applying Jensen’s inequality to (6). To get the upper
bound we average over the first tooth and then by monotonicity we obtain
P (x) ≤ pPℓ♯(x) + (1− p)P♯(x), (63)
with ℓ = ∞ and using (6) and (32) gives the bound required.
The spectral dimension is given by
1 if p ≥ 2|ǫ1|(1 + |ǫ1|)−1,
log(1− p)
1−|ǫ1|
1+|ǫ1|
) otherwise.
This result follows from estimating the sum in (60) using the bounds in (61) with ℓ = ∞
and short teeth being N1. PC(x) for these bounding combs is computed in Appendix C
and using (C.3) we get upper and lower bounds on Q∞L(x) of the form
Bx+B′x
1−|ǫ1|
1+|ǫ1|
. (65)
Biased random walks on random combs 14
5.1.2. ǫ2 > 0, ǫ1 < 0 The probability that C is non-recurrent is at least p, the
probability that T1 = N∞, and hence
P (0) < 1. (66)
In fact it follows from the lemma of Appendix B that P (k)(x) is finite for all finite k so
the exponent β is undefined.
The spectral dimension is given by
2 log(1− p)
1−|ǫ1|−ǫ2
1+|ǫ1|−ǫ2
) . (67)
To show this we start by estimating Q(x) in exactly the same way as in 5.1.1 except
that the behaviour of the limiting combs is now given by (C.5) so that there are upper
and lower bounds on Q∞L(x) of the form
Bx+B′
1−|ǫ1|−ǫ2
1+|ǫ1|−ǫ2
. (68)
When p ≤ 1 − b+/b− this sum diverges at x = 0 and it is then straightforward
to obtain (67). For larger p the sum is convergent at x = 0 so we next examine
Q(1)(x) =
. Note that −P (1)C ≥ 13b−; then letting Z be a very large integer
and using Hölder’s inequality
QC(x)
≤ −Q(1)(x) ≤
QC(x)
2+1/Z
−P (1)C (x)
. (69)
By the lemma of Appendix B the second factor in the upper bound is finite as x → 0
so we need an estimate of 〈Q2C〉µ. This is provided by (68) modified by squaring the
denominator; when p ≤ 1 − (b+/b−)2 this sum diverges at x = 0 and once again we
obtain (67). For still larger p both Q and Q(1) are finite at x = 0 and we examine
the second and higher derivatives. This uses (B.4), (−1)kP (k)C ≥ bk−b
2k−1, Hölder’s
inequality and the lemma; the term with the highest power of QC dominates and the
result is always (67). ‡
5.1.3. ǫ2 > 0, ǫ1 = 0 By the same argument as in 5.1.2 we find P (0) < 1, so β is again
undefined. An upper bound on Q(x) may be obtained as in 5.1.1 using (C.9) to get
Q∞L(x) ≤ (L+ (1− ǫ2)/4ǫ2) (70)
which means the upper bound of (60) is finite. A proof that all derivatives of Q(x) are
finite is given in Appendix B.2, so pC(t) decays faster than any power at large t.
‡ Strictly speaking when 1− (b+/b−)k < p ≤ 1− (b+/b−)k+1/Z the upper bounds diverge so our proof
does not work for these arbitrarily small intervals.
Biased random walks on random combs 15
5.2. µB – Teeth of random length
In this subsection we are concerned with random combs that have a distribution of tooth
lengths. The general strategy for determining quantities of interest is to identify teeth
that are long enough to affect the critical behaviour of the biased random walk and
consider the probability with which they occur. It will be useful to define the function
λ(δ, η, ζ) = ⌊
δ| log x|η − ζ(a− 1) log | log x|
log Y
⌋, (71)
which will be used to denote a tooth length, and the function
(ℓ) =
(a− 1)ℓa−1
1 +O(ℓ−1)
, (72)
which is the probability that a tooth has length greater than ℓ− 1.
5.2.1. ǫ2 = 0, ǫ1 < 0 We first show that
if a < 2,
1 otherwise.
The proof follows the lines described in section 5.1.1 with a slight modification for
the upper bound on P (x). Note that, from (30), teeth of length ℓ > ⌊x− 12 ⌋ have
PT (x) ≤ 1− Bx
2 . We then proceed as in (63) but with ℓ = ⌊x− 12 ⌋+ 1.
The exponent β is non-trivial if a < 2 but, as we now show, ds = 0 for all a > 1 so
mean field theory does not apply when a < 2. This result follows from the inequalities
x| log x|
≤ Q(x) ≤ B
. (74)
The upper bound is a consequence of Q(x) < Q♯(x). To obtain the lower bound consider
the combs for which at least the first N teeth are all shorter than ℓ0. Then using
monotonicity and (41)
Q(x) ≥ (1− p>(ℓ0))
1− P♭ℓ0(x) +O(exp(−N(Λǫ1,ǫ2(x) + Λ−ǫ1,ǫ2(x))))
. (75)
Setting ℓ0 = λ(1, (a− 1)−1, 0), N = ⌊2(Λǫ1,ǫ2 +Λ−ǫ1,ǫ2)−1| log x|⌋+ 1 and using (35) the
result follows for small enough x.
5.2.2. ǫ2 > 0, ǫ1 < 0 The exponent β = 0 but there are computable logarithmic
corrections and we find that
| log x|a−1
≤ P (x) ≤ 1− B
| log x|a−1
. (76)
The lower bound follows from applying Jensen’s inequality to (6). For the upper bound
note that teeth of length ℓ > λ(1, 1, 0) have PT < B. Again proceed as in (63) with
ℓ = λ(1, 1, 0) + 1.
Biased random walks on random combs 16
Table 2. 〈Dℓ〉µ in various cases.
ensemble ǫ2 < 0 ǫ2 = 0 ǫ2 > 0
µA B +O(x) Bx−
2 +O(1) Bx−1 +O(1)
µB, a ≥ 2 B +O(x) B +O(x) B(x| log x|a−1)−1 +O(1)
µB, a < 2 B +O(x) Bxa/2−1 +O(1) B(x| log x|a−1)−1 +O(1)
The spectral dimension is ds = 0 showing again that mean field theory does not
apply. This follows from the inequalities
B′ exp
−B′′| log x|1/a
≤ Q ≤ B
, (77)
for small enough x. The upper bound is a consequence of Q(x) < Q♯(x) and the lower
bound follows from (75) by setting ℓ0 = λ(1, 1/a, 0), N = ⌊2(Λǫ1,ǫ2+Λ−ǫ1,ǫ2)−1| log x|⌋+1
and using (37).
5.2.3. ǫ2 > 0, ǫ1 = 0 The exponent β = 0, but there are logarithmic corrections which
follow from the inequalities
| log x|(a−1)/2
≤ P (x) ≤ 1− B
| log x|(a−1)/2
. (78)
The lower bound comes from applying Jensen’s inequality to the recurrence relation (6).
The upper bound is obtained by requiring unitarity of the heat kernel and its proof is
relegated to Appendix D.
The spectral dimension and logarithmic exponent are given by
ds = 2,
α̃ = a− 1, (79)
which shows that mean field theory does not apply. This result follows from
B′ | log x|a−1 < Q(x) < B | log x|a−1 (80)
for small enough x which is obtained by a modified version of the argument in 5.1.1.
First let ℓ0 = λ(1, 1, ζ), so that
Pℓ0(x) = 1−
| log x|ζ(a−1)
| log x|2ζ(a−1)
. (81)
To obtain (80) we use (60) and (61) with p = p>(ℓ0), ℓ = ℓ0 and for the lower bound
set Tn<L = Nℓ0. Then using the bounds in (C.8) with ζ = 1 and (C.7) with ζ = 2 and
estimating the sums gives the result.
6. Heat Kernel when ǫ1 ≥ 0, ǫ2 ≥ 0
These calculations require 〈Dℓ〉µ in the various cases which are tabulated in table 2 for
convenience.
Biased random walks on random combs 17
6.1. µA – Infinite teeth at random locations
We show that
0 if ǫ2 > 0 and ǫ1 ≥ 0,
k/2 if ǫ2 = 0 and ǫ1 > 0.
These results follow from (85), (86) and (87) below.
Noting that for ǫ1 > 0 all combs have 1 − B−1− − < PC(x) < 1 − B−1+ and using
monotonicity gives
D|Tn|(x)
G∗(x;n) ≤ H(x;n) ≤
D|Tn|(x)
GC′(x;n)
1− PC′(x)
, (83)
D|Tn|(x)
〈GC′(x;n)〉µ , (84)
where C ′ is constructed from C by forcing Tn = N1. If ǫ2 > 0 then using (43) with
K = 0, ℓ = ∞ gives the upper bound
H(x;n) <
exp(−B′n). (85)
If ǫ2 = 0 then exactly the same calculation gives
H(x;n) <
exp(−B′x
2n) (86)
and evaluating the left hand side of (83) gives a lower bound of the same form. If ǫ2 > 0
and ǫ1 = 0 it is necessary to sum over the location of the first infinite tooth. Using
(C.9), (43) and introducing C ′ as in (83) gives
H(x;n) <
exp(−B′n). (87)
6.2. µB – Teeth of random length
We show that
0 if ǫ2 > 0 and ǫ1 ≥ 0;
ka/2 if ǫ2 = 0, ǫ1 > 0 and a < 2;
k if ǫ2 = 0, ǫ1 > 0 and a ≥ 2.
These results follow from
H(x;n) <
x| log x|a−1
exp(−B′n/| log x|a−1) if ǫ2 > 0 and ǫ1 ≥ 0;
x1−a/2
exp(−B′nxa/2) if ǫ2 = 0, ǫ1 > 0 and a < 2;
B exp(−nB′x) if ǫ2 = 0, ǫ1 > 0 and a ≥ 2,
when x is small enough and lower bounds of the same form.
The upper bounds are obtained by proceeding as in subsection 6.1: for ǫ1 > 0 and
ǫ2 > 0 setting ℓ = λ(1, 1, 0) + 1 and for ǫ1 > 0 and ǫ2 = 0 setting ℓ = ⌊x−
2 ⌋ + 1. For
ǫ1 = 0 and ǫ2 > 0 we start with the upper bound of (83); let ℓ1 = λ(1, 1, 2), p1 = p>(ℓ1)
and ℓ2 = λ(2, 1, 0), p2 = p>(ℓ2). The latter shall be called long teeth and we denote by
Biased random walks on random combs 18
(ℓ2K♯) the comb with a single long tooth at vertex K. We now sum over the location
of the first long tooth using (18), (43) and (C.8) and taking account of the fact that the
first long tooth may be before or after the nth tooth
H(x;n) ≤
D|Tn|(x)
p2(1− p1)K−1
1− P(ℓ2K♯)(0)
P(ℓ2K♯)m
× ((1− p1)P♯ + (p1 − p2)Pℓ1♯ + p2Pℓ2♯)
n−K−1
θ(ℓ2 − |Tn|)D|Tn|(x)
p2(1− p1)K−1
1− P(ℓ2K♯)(0)
P(ℓ2K♯)m . (90)
In the first sum we use the value given in Table 2 for
D|Tn|(x)
. In the second sum
θ(ℓ2 − |Tn|)D|Tn|(x)
= B(x| log x|2(a−1))−1+O(1) for |Tn| < ℓ2 and the result follows.
To obtain the lower bounds when ǫ1 > 0 we note that
H(x;n) ≥ B−
D|Tn|(x)GC(x;n)
D|Tn|(x)
〈GC(x;n)〉µ (91)
where the measure µ is defined by
µℓ = µℓ, for teeth Tk, k 6= n,
〈Dℓ〉µ
, for tooth Tn. (92)
Using the decomposition (18) and Jensen’s inequality
〈GC(x;n)〉µ ≥
3(1− x)n/2
exp(−Sn), (93)
where
− PCk+1(x)
1− PTk+1(x)
. (94)
Now applying Jensen’s inequality with the measure µ to (6) shows that the lower bounds
satisfy a recursion formula of exactly the same form as discussed in Appendix C. So
from (C.1) we find that
Sn ≤ n
− P (x) +
〈1− PT (x)〉µ
(〈PT (x)〉µ − 〈PT (x)〉µ) +
P (x)(1− A(x))
A(x)k−1(P̄ (x)− A(x)P (x))/(P̄ (x)− P (x))− 1
, (95)
where
P (x) =
(1− x)b−
3− bT 〈PT (x)〉µ − b+P (x)
P̄ (x) =
(1− x)b−
3− bT 〈PT (x)〉µ − b+P (x)
A(x) =
(1− x)b−
P (x)2 b+
. (96)
Biased random walks on random combs 19
For ǫ1 > 0 it is straightforward to check that A(x) > c > 1 and that the sum in (95) is
bounded above by an n independent constant. Lower bounds of the form of (89) then
follow by inserting the appropriate 〈PT 〉µ in (96) and (95).
When ǫ1 = 0
H(x;n) ≥
D|Tn|(x)
GC′(x;n)
1− PC′(x)
, (97)
where C ′ is constructed from C by setting Tk≥n = N∞. Choosing ℓ0 = λ(1, 1, 2) and
using (18) and (C.7) gives
H(x;n) ≥
D|Tn|(x)
(1− p>(ℓ0))n−13(1− x)−n/2P∗(x)2
P♭ℓ0(x)− 1k−1
1− P♭ℓ0(x) + 1n−1
D|Tn|(x)
(1− p>(ℓ0))n−13(1− x)−n/2P∗(x)2
1− P♭ℓ0(x) + 1n−1
(n− 3)2(1− P♭ℓ0(x))
2P♭ℓ0(x)− 1
, (98)
for n ≥ 4 which gives the result.
7. Results and discussion
Figure 3 outlines the results that we have computed for µA. These are new and show
that the most interesting regime is actually when the bias along the spine is towards
the origin, a circumstance which has not been studied much in the literature. When
ǫ1 ≥ 0 and ǫ2 > 0 the walker disappears rapidly, never to return, and p(t) decays faster
than any power. When ǫ1 < 0 the bias along the spine is keeping the walker close
to the origin but if there are any infinite teeth present the walker can spend a lot of
time in the teeth; the conflict between these effects leads to a non-trivial ds. The fact
that d1 = 0 whenever ǫ2 > 0 shows that the walker never gets far down the spine; if
she disappears then it is up a tooth that she is lost. The Hausdorff dimension for µA
is dH = 2, regardless of bias and so we have here several examples of violation of the
bound 2dH/(1 + dH) ≤ ds ≤ dH , which applies for unbiased diffusion [19].
Figure 4 shows our results for µB as well as the results for the unbiased case studied
in [14]. This length distribution has been studied quite extensively in the literature but
usually under the assumption that ǫ2 ≥ 0. As can be seen the interesting behaviour
displayed by µA when ǫ1 < 0 does not occur here – essentially because very long teeth
are not common enough. We believe that with more work α̃ when ǫ1 < 0, ǫ2 ≥ 0 can be
found using our methods, but as this will not give further physical insight we leave the
calculations to elsewhere [17]. The case ǫ1 > 0, ǫ2 > 0 (often called topological bias) was
originally studied using mean field theory, which gave the mean square displacement
〈n2(t)〉 ∼ (log t)2(a−1), (99)
and this is in fact correct since the walker spends much of the time in the teeth. However
the claim in [3] that (99) holds for ǫ2 > 0 regardless of ǫ1 is false. The mean field method
gives the correct result when ǫ1 = 0 only because the walk on the spine is ignored, which
Biased random walks on random combs 20
amounts to using PT (x) for PC(x) in (21) and naively applying Jensen’s inequality. The
case ǫ1 > 0, ǫ2 = 0 was studied by Pottier [13] who computed the leading contribution
exactly, but without complete control over the sub-leading terms; she also calculated
the leading behaviour 〈n2〉 − 〈n〉2 which we have not. Of course our results for ds and
d1 agree with hers. The Hausdorff dimension for µ
B is dH = 3 − a when a < 2 and
dH = 1 when a ≥ 2 and so again we see that, as expected, a biasing field intensifies
the difference between the purely geometric definition of dimension and that which is
related to particle propagation.
The results for ǫ2 < 0 are intuitively obvious and, as we have proved, apply for any
model with identically and independently distributed tooth lengths. The walker never
gets far into the tooth and therefore combs have long time behaviour characteristic of
the spine alone.
This paper has given a comprehensive treatment of biased random walks on combs
using rigorous techniques – namely recursion relations for generating functions combined
with unitarity and monotonicity arguments. It serves to put in context many previous
results as well as present new ones. In the unbiased case [14] and in some bias regimes
mean field theory is sufficient to compute the leading order behaviour because the walker
either does not reach the ends of the longest teeth or does not travel far enough down
the spine for variations from average to be important. But, as is illustrated in many
examples here, a full treatment is needed when such fluctuations cannot be ignored.
Finally, while the results are of interest in themselves, an important point of the paper
was to demonstrate that rigorous analytic methods can be used to treat biased diffusion
on random geometric structures and it is to be hoped that these tools can be extended
to higher dimensional problems.
Acknowledgments
We would like to thank Bergfinnur Durhuus and Thordur Jonsson for valuable
discussions. This work is supported in part by Marie Curie grant MRTN-CT-2004-
005616 and by UK PPARC grant PP/D00036X/1. T.E. would like to acknowledge an
ORS award and a Julia Mann Graduate Scholarship from St Hilda’s College, Oxford.
Appendix A. Calculation of 〈PT (x)〉µB for ǫ2 > 0
First we rewrite (30) as
Pℓ(x) = P∞(x)Y − (Y − 1)P∞(x)X−1
X−1 + Y −ℓ
, (A.1)
so that
〈PT (x)〉µB = P∞(x)Y − (Y − 1)P∞(x)X
X−1 + Y −ℓ
(A.2)
Biased random walks on random combs 21
PSfrag replacements
(1 + 2ǫ2)
(1− 2ǫ2)
(1 + 2ǫ2)
(1− ǫ1 − ǫ2)
(1 + ǫ1 − ǫ2)
ds = 0
dk = 0
dk = 0dk = 0
dk = 0
dk = 0
ds = 1
ds = 1 ds = 3
dk = k
ds n.d. ds n.d.
ds n.d.
ds = 2 log(1− p) Ω−1
ds = log(1− p) Ω−1 p < p∗
p ≥ p∗
Figure 3. Results for µA where Ω = log
1−|ǫ1|−ǫ2
1+|ǫ1|−ǫ2
and p∗ = 2|ǫ1|(1 + |ǫ1| − ǫ2)−1.
The logarithmic exponents α̃ and d̃k are always zero for µ
PSfrag replacements
(1 + 2ǫ2)
(1− 2ǫ2)
(1 + 2ǫ2)
(1− ǫ1 − ǫ2)
(1 + ǫ1 − ǫ2)
ds = 0
ds = 0
ds = 0
dk = 0
dk = 0 dk = 0
dk = 0
dk = 0
ds = 1
ds = 3
dk = k
dk = k
ds n.d.
ds = 2 log(1− p) Ω−1
ds = log(1− p) Ω−1
p < p∗
p ≥ p∗
ds = 2 ds = 2
ds = 2 + a
α̃ ≤ 0
α̃k = 1
α̃k = 0
α̃ = a− 1 α̃ = −a
d̃k = 0
d̃k = 0
d̃k = 0 d̃k = k(a− 1) d̃k = k(a− 1)
≤ α̃ ≤ 0
if a < 2
if a < 2
if a < 2
if a ≥ 2
if a ≥ 2
if a ≥ 2
if a = 2k
if a 6= 2k
Figure 4. Results for µB . When ǫ2 < 0 the logarithmic exponents α̃ and d̃k are
always zero.
Biased random walks on random combs 22
X−1 + Y −ℓ
X−1 + Y −ℓ
≡ S. (A.3)
Since for ǫ2 > 0, Y > 1 we let log Y = ρ and write
| log x|
X−1 + e−ρℓ
| log x|
X−1 + e−ρℓ
, (A.4)
where σ is an arbitrary constant < 1. This is bounded above by taking ℓ in the
exponential to be its value at the top of each sum to give
S ≤ Ca
X−1 + xσ
| log x|
ℓ−a +
| log x|
| log x|a−1
. (A.5)
Noting that as x → 0, X−1 → Bx we get a lower bound on 〈Pℓ(x)〉µB of
〈PT (x)〉µB ≥ 1−
| log x|a−1
, (A.6)
for small enough x. An equivalent upper bound is calculated in the same manner by
ignoring the first term in (A.4) and setting σ = 1, which leads to the result quoted in
table 1. A similar procedure leads to bounds of the form B/x| log x|a on
T (x)
which we also need, at small enough x.
Appendix B. Proof of results for non-recurrent regime
First we define a structure of ordered lists of ordered integers. Let S denote an ordered
list of hS integers
[n1, n2, . . . nhS ], n1 ≥ n2 ≥ . . . ≥ nhS ≥ 1, hS ≥ 1,
[ ], hS = 0.
(B.1)
Define
|S| =
ni, hS ≥ 1,
0, hS = 0,
(B.2)
and let SN denote the set of all distinct lists S with |S| = N . Within SN the lists S
and S ′ are ordered by letting j = min(i : ni 6= n′i) and then setting S > S ′ if nj > n′j .
Finally if S ∈ SN and S ′ ∈ SN ′ with N > N ′ then S > S ′. It is convenient to denote by
S + 1 the lowest list above S, and by S ∪ S ′ the list obtained by concatenating S and
S ′ and then ordering as above.
Biased random walks on random combs 23
Now define
H(S; f(x)) = (−1)|S|
f (ni)(x), (B.3)
and for the empty list H([ ]; f(x)) = 1. We need the following lemma, which is proved
in Appendix B.1:
Lemma
(i) If 〈H(S;PT (x))〉µ is finite as x → 0 for all S ≤ S̄ then 〈H(S;PC(x))〉µ is finite as
x → 0 for all S ≤ S̄ and ǫ1 6= 0.
(ii) If the conditions of part (i) apply and, as x → 0,
H(S̄ + 1, PT (x))
diverges as
x−γ , γ > 0, then
H(S̄ + 1, PC(x))
also diverges as x−γ.
Differentiating (5) k times gives
C (x) =
C (x)
(1− PC(x))2
+ (−1)k
S∈Sk/[k]
C(S)H(S;PC(x))
(1− PC(x))hS+1
(B.4)
where C(S) is a combinatorial coefficient. It is straightforward to check for any S
that 〈H(S;PT (x))〉µA is analytic for ǫ2 6= 0, and that 〈H(S;PT (x))〉µB is analytic when
ǫ2 < 0. When ǫ2 = 0
H(S;Pℓ(x))|x=0 = cSℓ2|S|−hS
1 +O(l−2)
(B.5)
from which 〈H(S;Pℓ(x))〉µB is divergent for S = [⌈a/2⌉], and with smaller degree for
[⌈a/2⌉ − 1, 1] if 2k < a ≤ 2k + 1, k ∈ Z, but always convergent for any inferior S. The
results given in section 4.2 then follow from noting that P∗(x) < PC(x) < P♯(0) < 1 and
using the lemma.
Appendix B.1. Proof of lemma
To prove the lemma note that
H(S; f + g) =
S′∪S′′=S
H(S ′; f)H(S ′′; g) (B.6)
and differentiate (6) n times to get
(−1)nP (n)C (x) = (1− x)F
C (x) + nF
(n−1)
C (x) (B.7)
where
C (x) =
PC(x)
PC(x)b+
(1− x)b−
S′∪S′′=S
)hS′′
H(S ′;PC1(x))H(S
′′;PT1(x)).
(B.8)
Biased random walks on random combs 24
It is then straightforward to generalise this formula to
H(S, PC(x)) = R+ (PC(x))hS
S′∈S|S|
C(S, S ′)
PC(x)b+
(1− x)b−
S′′∪S′′′=S′
)hS′′′
H(S ′′;PC1(x))H(S
′′′;PT1(x)),
(B.9)
where the leading terms are written out explicitly and R contains contributions
depending only on lists inferior to S |S|. Every term on the right hand side is positive so
it can be bounded above by using PC(x) < P♯(0) and then the expectation value taken;
moving the S ′′ = S term to the left hand side gives
〈H(S, PC(0))〉µ
P♯(0)
R+ (P♯(0))hS
S′∈S|S|
C(S, S ′)
P♯(0)b+
S′′∪S′′′=S′
S′′ 6=S
)hS′′′
〈H(S ′′;PC1(0))〉µ 〈H(S
′′′;PT (0))〉µ .
(B.10)
Part (i) is true for S̄ = [1] so the lemma then follows immediately by induction on S.
To prove part (ii) use part (i) to isolate the potentially divergent terms in (B.9) leaving
H(S̄, PC(x)) =
PC(x)
(1− x)b−
H(S̄;PC1(x)) +
H(S̄;PT1(x))
+ finite terms. (B.11)
For small enough x,
PC(x)
(1− x)b−
< 1, ∀C (B.12)
and part (ii) follows upon taking expectation values.
Appendix B.2. ǫ1 = 0, ǫ2 > 0
We will show that
H(S, PC(x))
(1− PC(x))hS+1
(B.13)
is finite at x = 0, which together with (B.4) gives the result. Using (61) and (C.9) gives
C H(S, PC(x))
, (B.14)
Biased random walks on random combs 25
where nC is the location of the first infinite tooth of C. Applying (B.9) iteratively we
find that the right hand side is bounded above by terms of the form
〈H(S ′, PT (x))〉µA . (B.15)
The maximum value of K occurring is hS + 1 + ΦS where ΦS is the number of strings
inferior to S. As remarked before 〈H(S ′, PT (x))〉µA is analytic and
is trivially
finite which completes the proof.
Appendix C. Calculation of PC(x) for some useful combs
Let the comb C have Tk = Nℓ, k < L and arbitrary TL and CL. Then following the
method of Appendix A of [14] we find
P ǫ1ǫ2C (x) = P
(1−A)(P ǫ1ǫ2CL−1(x)− P
AL−1(P ǫ1ǫ2CL−1(x)−AP
(x))− (P ǫ1ǫ2CL−1(x)− P
(C.1)
where
(1− x)b−
(P ǫ1ǫ2
(x))2b+
. (C.2)
Setting ǫ2 = 0, ǫ1 < 0, ℓ = 1, TL = N∞ and CL = ♯ we find after some algebra that
P ǫ10C (x) = P
♯ (x)
1 + A−L
+O(x)
(C.3)
and, as x → 0,
1 + |ǫ1|
1− |ǫ1|
. (C.4)
Repeating the exercise but with CL = ∗ yields a similar result.
If instead we set ǫ2 > 0, ǫ1 < 0, ℓ = 1, TL = N∞ and CL = ♯ we find
P ǫ1ǫ2C (x) = P
♯ (x)
2ǫ2(A− 1)A−L
ǫ1 − 2ǫ2(1− A−L)
(1 +O(x))
(C.5)
and, as x → 0,
A → 1 + |ǫ1| − ǫ2
1− |ǫ1| − ǫ2
. (C.6)
Again, repeating the exercise but with CL = ∗ yields a similar result.
With ǫ2 > 0, ǫ1 = 0, and C = {Tk<L = Nℓ, Tk≥L = N∞} we find that
P 0ǫ2C (x) > P
(x)− 1
, L > 2, (C.7)
(it is good enough to use P∗(x) for k = 2); and for C = {Tk 6=L = N1, TL = Nℓ}, x < x0,
P 0ǫ2C (x) < P
♯ (x)
1− 1
AL−1−1
 (C.8)
where A = (1− x)(P 0ǫ2♯ (x))−2 and B is a positive constant depending on x0, A and ǫ2.
Finally for ǫ2 > 0, ǫ1 = 0, and C = {Tk 6=L = N1, TL = N∞} we find that
P 0ǫ2C (0) = 1−
L+ (1− ǫ2)/4ǫ2
. (C.9)
Biased random walks on random combs 26
Appendix D. Upper bound on P (x) when ǫ1 = 0, ǫ2 > 0
We start by writing
H(x;n) =
D|Tn|(x)
GC(x;n)
1− PC(x)
, (D.1)
where the measure µ̄ is defined in (92). Applying Jensen’s inequality with this measure
to (6) results in a recursion formula of the same form as discussed in Appendix C and
it is easy to verify that 〈PCk(x)〉µ ≥ 〈PCk(x)〉µ to give
GC(x;n)
1− PC(x)
GC(x;n)
1− PC(x)
b+(1− x)n/2
−n 〈1− PC(x)〉µ
〈1− PC(x)〉µ
, (D.2)
where in the last line we have again used Jensen’s inequality when averaging over the
ensemble. Applying this result to (D.1), summing over n, and using (24) we obtain the
inequality
D|Tn|(x)
〈1− PC(x)〉2µ
. (D.3)
Using the value for 〈Dℓ(x)〉µ given in table 2 and rearranging gives the upper bound on
P (x) quoted in 5.2.3.
References
[1] G. H. Weiss and S. Havlin, Some properties of a random walk on a comb structure, Physica 134A
(1986) 474-484
[2] S. Revathi, V. Balakrishnan, S. Lakshmibala and K. P. N. Murthy, Validity of the mean-field
approximation for diffusion on a random comb, Phys. Rev. E 54 (1996) 2298-2302
[3] D. ben-Avraham and S. Havlin, Diffusion and reactions in fractals and disordered systems,
Cambridge University Press, Cambridge (2000)
[4] S. Havlin, J. E. Kiefer and G. H. Weiss, Anomalous diffusion on a random comblike structure,
Phys. Rev. A 36 (1987) 1403-1408
[5] J. Ambjørn, B. Durhuus and T. Jonsson, Quantum geometry: a statistical field theory approach,
Cambridge University Press, Cambridge (1997)
[6] J. Ambjørn and Y. Watabiki, Scaling in quantum gravity, Nucl. Phys. B445 (1995) 129-144,
hep-th/9501049
[7] J. Ambjørn, J. Jurkiewicz and R. Loll, Spectral dimension of the universe, Phys. Rev. Lett. 95
(2005) 171301, hep-th/0505113
[8] C. Aslangul, P. Chvosta and N. Pottier, Analytic study of a model of diffusion on a random
comblike structure, Physica A 203 (1994) 533-565
[9] S. Havlin, A. Bunde, H. E. Stanley and D. Movsholvitz, Diffusion on percolation clusters with a
bias in topological space: non-universal behaviour, J. Phys. A 19 (1986) L693-L698
[10] V. Balakrishnan and C. Van den Broeck, Transport properties on a random comb, Physica A 217
(1995) 1-21
[11] S. Havlin, A. Bunde, Y. Glaser and H. E. Stanley, Diffusion with a topological bias on random
structures with a power-law distribution of dangling ends, Phys. Rev. A 34 (1986) 3492-3495
http://arxiv.org/abs/hep-th/9501049
http://arxiv.org/abs/hep-th/0505113
Biased random walks on random combs 27
[12] N. Pottier, Diffusion on random comblike structures: field-induced trapping effects, Physica A 216
(1995) 1-19
[13] N. Pottier, Analytic study of a model of biased diffusion on a random comblike structure, Physica
A 208 (1994) 91-123
[14] B. Durhuus, T. Jonsson and J. F. Wheater, Random walks on combs, J. Phys. A 39 (2006) 1009-
1038, hep-th/0509191
[15] B. Durhuus, T. Jonsson and J. F. Wheater, The spectral dimension of generic trees,
math-ph/0607020
[16] B. Durhuus, T. Jonsson and J. F. Wheater, On the spectral dimension of generic trees, DMTCS
proc. AG (2006), 183-192
[17] T.M. Elliott, Oxford University D.Phil Thesis, in preparation.
[18] W. Feller, An introduction to probability theory and its applications, Vol.2, Wiley, London (1968)
[19] A. Grigoryan and T. Coulhon, Pointwise estimates for transition probabilities of random walks
in infinite graphs, in: Trends in mathematics: Fractals in Graz 2001, Ed. P. Grabner and W.
Woess. Birkhäueser (2002)
http://arxiv.org/abs/hep-th/0509191
http://arxiv.org/abs/math-ph/0607020
	Introduction
	Definitions
	Random combs
	Biased random walks
	Two-point functions
	The Heat kernel
	Basic properties
	Results for simple regular combs
	General properties of the generating functions
	Useful elementary bounds
	Results independent of the comb ensemble 
	ds when 2<0 
	ds when 1>0
	dk when 2<0 or 1<0
	The spectral dimension when 20 and 10
	A – Infinite teeth at random locations
	2= 0, 1< 0
	2> 0, 1< 0
	2> 0, 1= 0
	B – Teeth of random length
	2= 0, 1< 0
	2> 0, 1 <0 
	2> 0, 1 =0 
	Heat Kernel when 1 0, 2 0
	A – Infinite teeth at random locations
	B – Teeth of random length
	Results and discussion
	Calculation of "426830A PT(x) "526930B B for 2>0
	Proof of results for non-recurrent regime
	Proof of lemma
	1=0, 2>0
	Calculation of PC(x) for some useful combs
	Upper bound on P(x) when 1=0, 2>0

  We develop rigorous, analytic techniques to study the behaviour of biased
random walks on combs. This enables us to calculate exactly the spectral
dimension of random comb ensembles for any bias scenario in the teeth or spine.
Two specific examples of random comb ensembles are discussed; the random comb
with nonzero probability of an infinitely long tooth at each vertex on the
spine and the random comb with a power law distribution of tooth lengths. We
also analyze transport properties along the spine for these probability
measures.

Introduction
The behaviour of random walks on random combs is of interest from a number of points
of view. Condensed matter physicists have studied such structures because they serve
as a model for diffusion in more complicated fractals and percolation clusters [1, 2, 3, 4].
In the context of quantum gravity, random combs are a tractable example of a random
manifold ensemble and understanding their geometric properties can provide insight
into higher dimensional problems [5, 6, 7]. Most of the literature concerns approximate
analytical techniques and numerical solutions, although there are exact calculations of
leading order behaviour in some cases [8]. To this end, it is desirable to have rigorous
methods for determining the geometric quantities of interest and that is the purpose of
this paper.
One such quantity is the dimensionality of the ensemble. On a sufficiently smooth
manifold all definitions of dimension will agree, but for fractal geometries like random
combs this is not necessarily true. The spectral dimension is defined to be ds provided
the ensemble average probability of a random walker being back at the origin at time t,
takes the asymptotic form t−ds/2. This concept of dimension does not in general agree
with the Hausdorff dimension dH , which is defined when the expectation value of the
volume enclosed within a geodesic distance R from a marked point scales like RdH as
R → ∞.
http://arxiv.org/abs/0704.0188v2
Biased random walks on random combs 2
We know that for diffusion on regular structures the mean square displacement at
large times is proportional to t, but for a fractal substrate there is anomalous diffusion
and the mean square displacement behaves like t2/dw , where dw represents the fractal
dimension of the walk and depends sensitively on the nature of the random structure.
Biased random walks on combs have also been studied in connection with disordered
materials, since such a system is a paradigm for diffusion on fractal structures in the
presence of an applied field [9, 10]. As we discuss later there are several different bias
regimes. Topological bias, where at every vertex in the comb there is an increased
probability of moving away from the origin was first studied for a random comb with a
power-law distribution of tooth lengths in [11]. Other works have discussed the effects
of bias away from the origin only in the teeth [12] and only in the spine [13]. The effect
of going into the teeth can be viewed as creating a waiting time for the walk along the
spine; the distribution of the waiting time depends on both the bias and the length of
the teeth and the outcome is the result of subtle interplay between the two.
In [14] some new, rigorous techniques were developed to study random walks on
combs. This enabled an exact, but very simple calculation of the spectral dimension of
random combs. The principal idea is to split both random combs and random walks
into subsets that give either strictly controllable or exponentially decaying contributions
to the calculation of physical characteristics. These methods were later reinforced to
prove that the spectral dimension of generic infinite tree ensembles is 4/3 [15, 16]. In
this paper we use and extend the techniques of [14] to deal with biased walks on combs.
Some of our results are new; some qualify statements made in the literature; and some
merely confirm results already derived by other, usually less rigorous, methods.
The random combs, the bias scenario, some useful generating functions and the
critical exponents are defined in the next section. In Section 3 we introduce some
deterministic combs, discuss general properties of the generating functions and establish
bounds that will be instrumental when studying random ensembles. Section 4 looks at
regions of bias where the large time behaviour is independent of the comb ensemble or
simply dependent on the expectation value of the first return generating function in the
teeth. In Section 5 we compute the spectral dimension in regions of bias where it is
influenced by the probability measure on the teeth. Two specific cases are considered:
the random comb with nonzero probability of an infinitely long tooth at each vertex on
the spine and the random comb with a power law distribution of tooth lengths. Section
6 examines transport properties along the spine for these same probability measures and
in the final section we review the main results, compare with the literature and discuss
their significance. Some exact calculations and proofs omitted from the main text are
outlined in the appendices.
2. Definitions
Wherever possible we use the definitions and notation of [14]; we repeat them here for
the reader’s convenience but mostly refer back to [14] for proofs and derived properties.
Biased random walks on random combs 3
2.1. Random combs
LetN∞ denote the nonnegative integers regarded as a graph so that n has the neighbours
n ± 1 except for 0 which only has 1 as a neighbour. Let Nℓ be the integers 0, 1, . . . , ℓ
regarded as a graph so that each integer n ∈ Nℓ has two neighbours n± 1 except for 0
and ℓ which only have one neighbour, 1 and ℓ− 1, respectively. A comb C is an infinite
Figure 1. A comb.
rooted tree-graph with a special subgraph S called the spine which is isomorphic to N∞
with the root, which we denote r, at n = 0. At each vertex of S, except the root r, there
is attached by their endpoint 0 one of the graphs Nℓ or N∞. The linear graphs attached
to the spine are called the teeth of the comb, see figure 1. We will denote by Tn the
tooth attached to the vertex n on S, and by Ck the comb obtained by removing the links
(0, 1), . . . , (k − 1, k), the teeth T1, . . . , Tk and relabelling the remaining vertices on the
spine in the obvious way. An arbitrary comb is specified by a list of its teeth {T1, . . .}
and |Tk| denotes the length of the tooth. Note that we have excluded the possibility
of a tooth of zero length. This is for technical convenience in what follows and can be
relaxed [17].
In this paper we are interested in random combs for which the length ℓ of each
tooth is identically and independently distributed with probability µℓ. This induces a
probability measure µ on the positive integers and expectation values with respect to
this measure will be denoted 〈·〉µ. In particular we will consider the two measures
µAℓ =
p, ℓ = ∞,
1− p, ℓ = 1,
0, otherwise;
µBℓ =
, a > 1. (1)
Biased random walks on random combs 4
However, the results proved for µB apply to any measure with the same behaviour at
large ℓ and we note in passing that the methods used here will work for any distribution
that is reasonably smooth, for example the exponential distribution. The measure µB
has been discussed quite extensively in the literature but µA has not.
2.2. Biased random walks
We regard time as integer valued and consider a walker who makes one step on the
graph for each unit time interval. If the walker is at the root or at the end-point of a
tooth then she leaves with probability 1. If at any other vertex the probabilities are
parametrized by two numbers ǫ1 and ǫ2 as shown in figure 2a and the allowed range of
these parameters is shown in figure 2b. For walks in the teeth there is bias away from or
towards the spine depending on whether ǫ2 is positive or negative; similarly a walk on
the spine is biased away from or towards the root depending on whether ǫ1 is positive
or negative. When there is no bias we say that the walk is ‘critical’; the fully critical
case ǫ1 = ǫ2 = 0 was covered in [14]. The notation
b− = 1− ǫ1 − ǫ2,
b+ = 1 + ǫ1 − ǫ2,
bT = 1 + 2ǫ2, (2)
will be used where applicable since these combinations appear often in our analysis. We
denote by B,B′, B1, B2 etc constants which depend on ǫ1 and ǫ2 and may vary from line
to line but are positive and finite on the relevant range; other constants will be denoted
c, c′ etc.
The generating function for the probability pC(t) that the walker on C is back at
the root at time t having left it at t = 0 is defined by
QC(x) =
(1− x)t/2pC(t). (3)
Letting ω be a walk on C starting at r, ω(t) the vertex where the walker is to be found
at time t, and ρω(t) the probability for the walker to step from ω(t) to ω(t+1), we have
QC(x) =
ω:r→r
(1− x)
|ω|−1
ρω(t). (4)
A similar relation gives the generating function for probabilities for first return to the
root, PC(x), except that the trivial walk of duration 0 is excluded. The two functions
are related by
QC(x) =
1− PC(x)
, (5)
and it is straightforward to show that PC(x) satisfies the recurrence relation
PC(x) =
(1− x)b−
3− b+PC1(x)− bTPT1(x)
. (6)
Biased random walks on random combs 5
PSfrag replacements
(1 + 2ǫ2)
(1− 2ǫ2)1
(1 + 2ǫ2)
(1− ǫ1 − ǫ2) 13(1 + ǫ1 − ǫ2)
PSfrag replacements
(1 + 2ǫ2)
(1− 2ǫ2)
(1 + 2ǫ2)
(1− ǫ1 − ǫ2)
(1 + ǫ1 − ǫ2) ǫ1
Figure 2. Bias parameterisation.
Note that PC(x) and QC(x) depend upon ǫ1 and ǫ2; to avoid clutter we will normally
suppress this dependence but if necessary it will appear as superscripts. It is important
for what follows that QC is a convex function of PC which is itself a convex function of
PT1 , ...PTk , PCk for any k > 0.
For an ensemble of combs, we will denote the expectation values of the generating
functions for return and first return probabilities as
Q(x) = 〈QC(x)〉µ
P (x) = 〈PC(x)〉µ . (7)
We will say that g(x) ∼ f(x) if there exist positive constants c, c′, σ, σ′ and x0 such
c f(x) exp
−σ(log |f(x)|)1/a
< g(x) < c′ f(x)| log f(x)|σ′ (8)
for 0 < x ≤ x0. The tactic of this paper is to prove bounds of this form for the generating
functions; in almost all cases our results are in fact a little stronger having σ = σ′ = 0
Biased random walks on random combs 6
when we will say that g(x) ≈ f(x).
The random walk on C is recurrent if PC(0) = 1 in which case we define the
exponent β through
1− PC(x) ∼ xβ . (9)
If β is an integer then we expect logarithmic corrections and define β̃ if
1− PC(x) ≈ xβ | log x|−β̃. (10)
It follows that QC(x) diverges as x → 0 and we define α by
QC(x) ∼ x−α, (11)
and if α is an integer, α̃ when
QC(x) ≈ x−α| log x|α̃. (12)
If PC(0) < 1 then the random walk is non-recurrent, or transient, and QC(x) is finite
as x → 0. Then if, as x → 0, the first k − 1 derivatives of QC(x) are finite but the kth
derivative diverges we define the exponent αk by
C (x) ∼ x
−αk , (13)
and if αk is an integer, α̃k when
C (x) ≈ x
−αk | log x|α̃k . (14)
In considering the ensemble of combs µ, we define all these exponents in exactly
the same way simply replacing PC(x) with 〈PC(x)〉µ and so on. Note that for a single
recurrent comb β = α but in an ensemble this is no longer necessarily the case; applying
Jensen’s inequality to (5) we see that β ≤ α.
If Q(k)(x) ∼ x−αk then it is straightforward to show that
Rk(λ) =
tk 〈pC(t)〉µ ∼ λ
−αk . (15)
It follows that if the sequence decays uniformly at large t, which we do not prove, then
it falls off as tαk−1−k. Thus we define ds = 2(1 + k − αk). Similarly if Q(x) ≈ | log x|α̃
then R(λ) ≈ | log λ|α̃ and, again assuming uniformity, p(t) falls off as t−1 | log t|α̃−1.
2.3. Two-point functions
Let p1C(t;n) denote the probability that the walker on C, having left r at t = 0 and not
subsequently returned there, is at point n on the spine at time t. The corresponding
generating function, which we will call the two-point function, is defined by
GC(x;n) =
(1− x)t/2p1C(t;n). (16)
Letting ω be a walk on C starting at r and ending at n without returning to r we have
GC(x;n) =
ω:r→n
(1− x)
|ω|−1
ρω(t). (17)
Biased random walks on random combs 7
Following the discussion in section 2.2 of [14] this leads us to the representation
GC(x;n) =
b+(1− x)n/2
PCk(x). (18)
2.4. The Heat kernel
Let KC(t;n, ℓ) denote the probability that the walker on C, having left r at t = 0, is at
point ℓ in tooth Tn at time t. KC(t;n, ℓ) satisfies the diffusion equation on C so we call
it the heat kernel. The probability that the walker has travelled a distance n along the
spine at time t is given by
KC(t;n) =
KC(t;n, ℓ), (19)
and has generating function
HC(x;n) =
(1− x)t/2KC(t;n). (20)
HC(x;n) can be written as
HC(x;n) =
GC(x;n)
1− PC(x)
D|Tn|(x), (21)
where
Dℓ(x) = 1 +
GNℓ(x; k), (22)
and we define
H(x;n) = 〈HC(x;n)〉µ . (23)
Note that, because KC(t;n) is a probability,
H(x;n) =
. (24)
The exponent dk is defined through the moments in n
nk H(x;n) ≈ x−1−dk , (25)
and in the case dk = 0 the exponent d̃k is defined when
nk H(x;n) ≈ x−1 | log x|d̃k . (26)
If ǫ1 ≥ 0 one can show that on any comb 〈n〉ω:|ω|=t is a non-decreasing sequence and
thus that there is some constant T0 such that for T > T0
| log T |
〈n〉ω:|ω|=T + 〈n〉ω:|ω|=T+1
< c T d1, d1 6= 0
c | log T |d̃1 <
〈n〉ω:|ω|=T + 〈n〉ω:|ω|=T+1
< c | log T |d̃1, d1 = 0.
Biased random walks on random combs 8
If ǫ1 < 0 (for which we always have d̃1 = 0) then we have only the weaker result that
for T > T0
| log T |
)1+d1
〈n〉ω:|ω|=t
< c T 1+d1 . (28)
3. Basic properties
3.1. Results for simple regular combs
The relation (6) can be used to compute the generating functions for a number of simple
regular graphs which will be important in our subsequent analysis [14].
(i) An infinitely long tooth, N∞:
P∞(x) =
2 if ǫ2 = 0;
1− 2|ǫ2|
4|ǫ2|
(1− 2ǫ2) +O(x2) otherwise.
(ii) A tooth of length ℓ, Nℓ:
Pℓ(x) = P∞(x)
1 +XY 1−ℓ
1 +XY −ℓ
where
bT (1− P∞(x))
2− bT (1 + P∞(x))
, Y =
2− bTP∞(x)
bTP∞(x)
. (31)
(iii) The comb ♯ given by {Tk = N1, ∀k} has all teeth of length 1, and
P♯(x) =
1− B1x
2 +O(x) if ǫ1 = 0;
1− ǫ2 − |ǫ1|
− x B2
+O(x2) otherwise.
Note that ♯ is non-recurrent if ǫ1 > 0. It is also convenient to define ℓ♯ to be
{T1 = Nℓ, C1 = ♯}.
(iv) The comb ∗ given by {Tk = N∞, ∀k} has all teeth of length ∞ and is non-recurrent
for ǫ2 > 0,
P∗(x) =
1 + ǫ2 −
4ǫ2 + ǫ
− x B1√
4ǫ2 + ǫ
+O(x2). (33)
Otherwise
P∗(x) =
1− |ǫ1|
1 + ǫ1
2 +O(x) if ǫ2 = 0, ǫ1 6= 0;
1− ǫ2 − |ǫ1|
+O(x2) if ǫ2 < 0, ǫ1 6= 0;
1− B4x
2 +O(x) if ǫ2 < 0, ǫ1 = 0.
Biased random walks on random combs 9
(v) The comb ♭ℓ given by {Tk = Nℓ, ∀k} has all teeth of length ℓ and
P♭ℓ(x) =
1− |ǫ1|
1 + ǫ1
(ℓ+ 1 + |ǫ1|)x+O(x2ℓ2) if ǫ2 = 0, ǫ1 6= 0;
1− ǫ2 − |ǫ1|
|ǫ1ǫ2|
+O(xY −ℓ) if ǫ2 < 0, ǫ1 6= 0;
2 +O(x
2Y −ℓ) if ǫ2 < 0, ǫ1 = 0;
where, as x → 0,
Y → 1 + 2|ǫ2|
1− 2|ǫ2|
. (36)
When ǫ2 > 0 let ℓ̄ = ⌊| log x|/ log Y ⌋, where ⌊z⌋ denotes the integer below z. For
ℓ > 2ℓ̄ the teeth are long enough that P♭ℓ(x) behaves like (33). For ℓ̄ < ℓ ≤ 2ℓ̄,
P♭ℓ(x) is non-recurrent with the leading power of x being fractional. For ℓ ≤ ℓ̄
P♭ℓ<ℓ̄(x) =
1− ǫ2 − |ǫ1|
|ǫ1ǫ2|
+O(x) if ǫ1 6= 0;
ℓ +O(x
ℓ, xY −ℓ) if ǫ1 = 0,
where the notation O(a, b) means O(max (a, b)).
3.2. General properties of the generating functions
The generating functions for any comb satisfy three simple properties which can be
derived from (6):
(i) Monotonicity The value of PC(x) decreases monotonically if the length of a tooth
is increased.
(ii) Rearrangement If the comb C ′ is created from C by swapping the adjacent teeth
Tk and Tk+1 then PC′(x) > PC(x) if |Tk+1| < |Tk|.
(iii) Inheritance If walks on Ck or Tk are non-recurrent for finite k then walks on C are
non-recurrent.
The proof of the first two follows that given in [14] for the special case ǫ2 = ǫ1 = 0. The
third can be shown by assuming that either PC1(0) < 1 or PT1(0) < 1; it then follows
immediately from (6) that PC(0) < 1 and the result follows by induction.
3.3. Useful elementary bounds
By monotonicity GC(x;n) is always bounded above by G♯(x;n) from which we get
GC(x;n) <
exp(−nΛǫ1,ǫ2(x)), (38)
Biased random walks on random combs 10
where
Λǫ1,ǫ2(x) =
2 + ǫ2
if ǫ1 > 0,
2 + ǫ2
1− ǫ2
if ǫ1 = 0,
if ǫ1 < 0.
Now let P
C (x) denote the contribution to PC(x) from walks that reach beyond n = N
on the spine. It is straightforward to show using the arguments of section 2.5 of [14]
C (x) ≤
ǫ1,ǫ2
C (x;N)G
−ǫ1,ǫ2
C (x;N). (40)
Combining this with (38) we obtain the useful bound
C (x) ≤
exp(−N(Λǫ1,ǫ2(x) + Λ−ǫ1,ǫ2(x))). (41)
Now consider the ensemble µ′ of combs C for which: Tk = N1, k = 1..K − 1,
TK = Nℓ; at k > K teeth are short, Tk = N1, with probability 1 − p or long, Tk = Nℓ,
with probability p; and the nth tooth is short, Tn = N1. Then using the representation
(18) GC(x;n) can be bounded above by noting that if Tk+1 = Nℓ then PCk < Pℓ♯,
otherwise PCk < P♯. This gives
GC(x, n) ≤
(1− x)−n/2
Pℓ♯(x)
n−K−kP♯(x)
k+K , (42)
and hence
〈GC(x, n)〉µ′ =
n−K−1
n−K−1
pn−K−1−k(1− p)kGC(x, n)
P♯(x)
KPℓ♯(x)
(1− x)n/2
((1− p)P♯(x) + pPℓ♯(x))n−K−1 . (43)
4. Results independent of the comb ensemble µ
In this section we show that in some regions of ǫ1,2 the behaviour at large time is
essentially independent of the comb ensemble, or else simply dependent upon 〈PT (x)〉µ.
The leading, and where different, the leading non-analytic, behaviour of 〈PT (x)〉µ as
x → 0 for the measures studied here is given in table 1. The results for µA are trivial,
as are those for any measure when ǫ2 < 0, while the case µ
B and ǫ2 = 0 can be derived
using the techniques in [14]. The calculation for µB and ǫ2 > 0 is somewhat subtle and
is included in Appendix A.
Biased random walks on random combs 11
Table 1. Leading and leading non-analytic behaviour of 1− 〈PT 〉µ in various cases.
ensemble ǫ2 < 0 ǫ2 = 0 ǫ2 > 0
µA Bx Bx
2 B +B′x
µB, a < 2 Bx Bxa/2 B(| log x|a−1)−1
µB, a = 2k Bx Bx+ . . . B′xk| log x| B(| log x|a−1)−1
µB, a > 2, a 6= 2k Bx Bx+ . . . B′xa/2 B(| log x|a−1)−1
4.1. ds when ǫ2 < 0
First we show that for any comb ensemble
0 if ǫ1 < 0 and ǫ2 < 0;
1 if ǫ1 = 0 and ǫ2 < 0.
By monotonicity we have that for any comb C
P∗(x) ≤ PC(x) ≤ P♯(x). (45)
Taking expectation values and using (32) and (34) it follows that for ǫ2 < 0
P (x) = 〈PC(x)〉µ =
1−B1x
2 +O(x) if ǫ1 = 0,
1− ǫ2 − |ǫ1|
+O(x2) otherwise.
Similarly
Q∗(x) ≤ QC(x) ≤ Q♯(x) (47)
and so
Q(x) = 〈QC(x)〉µ =
+O(1) if ǫ1 = 0,
B2|ǫ1|
+O(1) if ǫ1 < 0,
and (44) follows.
4.2. ds when ǫ1 > 0
When ǫ1 > 0 all combs are non-recurrent and so we must examine the derivatives of
Q(x). Differentiating (5) and (6) gives
C (x) = QC(x)
C (x), (49)
C (x) =
−PC(x)
PC(x)
(1− x)b−
(x) + b+P
. (50)
Biased random walks on random combs 12
By monotonicity (50) can be bounded above and below by replacing PC with P∗ and
P♯ respectively. Taking the expectation value and using translation invariance to note
that 〈PC〉µ = 〈PC1〉µ shows that, if
T (x)
diverges as x → 0, then
Q(1)(x) ∼ B
T (x)
T (x)
, 1). (51)
As can be seen from table 1, in some cases 〈PT (x)〉µ is analytic, or only higher derivatives
diverge. For the measures considered here it can be shown that if 〈PT (x)〉µ is analytic
at x = 0 then so is Q(x). If on the other hand 〈PT (x)〉µ is not analytic but the k’th
derivative diverges then
Q(k)(x) = B
T (x)
T (x)
, 1). (52)
The proof is a straightforward but tedious generalization of (49) and (50) and is relegated
to Appendix B. If a derivative of Q(x) diverges then ds can be read off using (14) and
(52). Otherwise if all finite order derivatives are finite then pC(t) decays at large t faster
than any power and ds is not defined.
4.3. dk when ǫ2 < 0 or ǫ1 < 0
We show that for any comb ensemble
d̃k = 0, dk =
0 if ǫ1 < 0,
k/2 if ǫ1 = 0 and ǫ2 < 0,
k if ǫ1 > 0 and ǫ2 < 0.
It is trivial to show that
1 ≤ Dℓ ≤
, ǫ2 < 0, (54)
and then by monotonicity we get
G∗(x;n)
1− P∗(x)
≤ H(x;n) ≤ B
G♯(x;n)
1− P♯(x)
. (55)
Combining this with (32) and (34) yields the results for ǫ2 < 0.
To deal with ǫ1 < 0 and ǫ2 ≥ 0 note that monotonicity gives
D|Tn|(x)
1− PC(x)
G∗(x;n) ≤ H(x;n) ≤
D|Tn|(x)
1− PC(x)
G♯(x;n). (56)
Using the lower bound and (18), (24) and (33) we get after summing over n
D|Tn|(x)
1− PC(x)
4ǫ2 + ǫ
1 − ǫ1 − 2ǫ2
H(x;n) ≤
. (57)
Inserting this into the upper bound of (56) gives
H(x;n) ≤
4ǫ2 + ǫ
1 − ǫ1 − 2ǫ2
G♯(x;n). (58)
Biased random walks on random combs 13
It is a trivial consequence of (24) that
nkH(x;n) >
, k > 0, (59)
and the results then follow by using (38).
5. The spectral dimension when ǫ2 ≥ 0 and ǫ1 ≤ 0
Here and in some of the sections to follow we will need to sum over the location of the
first long tooth to determine the spectral dimension. Most generally we call a tooth
long when it has length ≥ ℓ and short when it has length < ℓ. Consider combs for
which the first L− 1 teeth are short but the Lth tooth is long; the probability for this
is p(1− p)L−1, where p is the probability of a tooth being long. Denoting by ℓL a comb
having the first long tooth at vertex L gives
Q(x) =
〈QℓL(x)〉µ p(1− p)
L−1. (60)
QℓL(x) is bounded above by the comb in which all teeth at n ≥ L + 1 are short, and
below by the comb in which all teeth at n ≥ L+ 1 are infinite,
Q{Tn<L=Nℓ′ ,ℓ′≤ℓ;Tn≥L=N∞}(x) < QℓL(x) < Q{Tn6=L=N1;TL=Nℓ}(x). (61)
5.1. µA – Infinite teeth at random locations
5.1.1. ǫ2 = 0, ǫ1 < 0 We first show that the exponent β =
– so it is unchanged from
the comb ∗. This result follows from the inequalities
1− pBx
+O(x) ≤ P (x) ≤ 1− pB′x
2 +O(x). (62)
The lower bound is obtained by applying Jensen’s inequality to (6). To get the upper
bound we average over the first tooth and then by monotonicity we obtain
P (x) ≤ pPℓ♯(x) + (1− p)P♯(x), (63)
with ℓ = ∞ and using (6) and (32) gives the bound required.
The spectral dimension is given by
1 if p ≥ 2|ǫ1|(1 + |ǫ1|)−1,
log(1− p)
1−|ǫ1|
1+|ǫ1|
) otherwise.
This result follows from estimating the sum in (60) using the bounds in (61) with ℓ = ∞
and short teeth being N1. PC(x) for these bounding combs is computed in Appendix C
and using (C.3) we get upper and lower bounds on Q∞L(x) of the form
Bx+B′x
1−|ǫ1|
1+|ǫ1|
. (65)
Biased random walks on random combs 14
5.1.2. ǫ2 > 0, ǫ1 < 0 The probability that C is non-recurrent is at least p, the
probability that T1 = N∞, and hence
P (0) < 1. (66)
In fact it follows from the lemma of Appendix B that P (k)(x) is finite for all finite k so
the exponent β is undefined.
The spectral dimension is given by
2 log(1− p)
1−|ǫ1|−ǫ2
1+|ǫ1|−ǫ2
) . (67)
To show this we start by estimating Q(x) in exactly the same way as in 5.1.1 except
that the behaviour of the limiting combs is now given by (C.5) so that there are upper
and lower bounds on Q∞L(x) of the form
Bx+B′
1−|ǫ1|−ǫ2
1+|ǫ1|−ǫ2
. (68)
When p ≤ 1 − b+/b− this sum diverges at x = 0 and it is then straightforward
to obtain (67). For larger p the sum is convergent at x = 0 so we next examine
Q(1)(x) =
. Note that −P (1)C ≥ 13b−; then letting Z be a very large integer
and using Hölder’s inequality
QC(x)
≤ −Q(1)(x) ≤
QC(x)
2+1/Z
−P (1)C (x)
. (69)
By the lemma of Appendix B the second factor in the upper bound is finite as x → 0
so we need an estimate of 〈Q2C〉µ. This is provided by (68) modified by squaring the
denominator; when p ≤ 1 − (b+/b−)2 this sum diverges at x = 0 and once again we
obtain (67). For still larger p both Q and Q(1) are finite at x = 0 and we examine
the second and higher derivatives. This uses (B.4), (−1)kP (k)C ≥ bk−b
2k−1, Hölder’s
inequality and the lemma; the term with the highest power of QC dominates and the
result is always (67). ‡
5.1.3. ǫ2 > 0, ǫ1 = 0 By the same argument as in 5.1.2 we find P (0) < 1, so β is again
undefined. An upper bound on Q(x) may be obtained as in 5.1.1 using (C.9) to get
Q∞L(x) ≤ (L+ (1− ǫ2)/4ǫ2) (70)
which means the upper bound of (60) is finite. A proof that all derivatives of Q(x) are
finite is given in Appendix B.2, so pC(t) decays faster than any power at large t.
‡ Strictly speaking when 1− (b+/b−)k < p ≤ 1− (b+/b−)k+1/Z the upper bounds diverge so our proof
does not work for these arbitrarily small intervals.
Biased random walks on random combs 15
5.2. µB – Teeth of random length
In this subsection we are concerned with random combs that have a distribution of tooth
lengths. The general strategy for determining quantities of interest is to identify teeth
that are long enough to affect the critical behaviour of the biased random walk and
consider the probability with which they occur. It will be useful to define the function
λ(δ, η, ζ) = ⌊
δ| log x|η − ζ(a− 1) log | log x|
log Y
⌋, (71)
which will be used to denote a tooth length, and the function
(ℓ) =
(a− 1)ℓa−1
1 +O(ℓ−1)
, (72)
which is the probability that a tooth has length greater than ℓ− 1.
5.2.1. ǫ2 = 0, ǫ1 < 0 We first show that
if a < 2,
1 otherwise.
The proof follows the lines described in section 5.1.1 with a slight modification for
the upper bound on P (x). Note that, from (30), teeth of length ℓ > ⌊x− 12 ⌋ have
PT (x) ≤ 1− Bx
2 . We then proceed as in (63) but with ℓ = ⌊x− 12 ⌋+ 1.
The exponent β is non-trivial if a < 2 but, as we now show, ds = 0 for all a > 1 so
mean field theory does not apply when a < 2. This result follows from the inequalities
x| log x|
≤ Q(x) ≤ B
. (74)
The upper bound is a consequence of Q(x) < Q♯(x). To obtain the lower bound consider
the combs for which at least the first N teeth are all shorter than ℓ0. Then using
monotonicity and (41)
Q(x) ≥ (1− p>(ℓ0))
1− P♭ℓ0(x) +O(exp(−N(Λǫ1,ǫ2(x) + Λ−ǫ1,ǫ2(x))))
. (75)
Setting ℓ0 = λ(1, (a− 1)−1, 0), N = ⌊2(Λǫ1,ǫ2 +Λ−ǫ1,ǫ2)−1| log x|⌋+ 1 and using (35) the
result follows for small enough x.
5.2.2. ǫ2 > 0, ǫ1 < 0 The exponent β = 0 but there are computable logarithmic
corrections and we find that
| log x|a−1
≤ P (x) ≤ 1− B
| log x|a−1
. (76)
The lower bound follows from applying Jensen’s inequality to (6). For the upper bound
note that teeth of length ℓ > λ(1, 1, 0) have PT < B. Again proceed as in (63) with
ℓ = λ(1, 1, 0) + 1.
Biased random walks on random combs 16
Table 2. 〈Dℓ〉µ in various cases.
ensemble ǫ2 < 0 ǫ2 = 0 ǫ2 > 0
µA B +O(x) Bx−
2 +O(1) Bx−1 +O(1)
µB, a ≥ 2 B +O(x) B +O(x) B(x| log x|a−1)−1 +O(1)
µB, a < 2 B +O(x) Bxa/2−1 +O(1) B(x| log x|a−1)−1 +O(1)
The spectral dimension is ds = 0 showing again that mean field theory does not
apply. This follows from the inequalities
B′ exp
−B′′| log x|1/a
≤ Q ≤ B
, (77)
for small enough x. The upper bound is a consequence of Q(x) < Q♯(x) and the lower
bound follows from (75) by setting ℓ0 = λ(1, 1/a, 0), N = ⌊2(Λǫ1,ǫ2+Λ−ǫ1,ǫ2)−1| log x|⌋+1
and using (37).
5.2.3. ǫ2 > 0, ǫ1 = 0 The exponent β = 0, but there are logarithmic corrections which
follow from the inequalities
| log x|(a−1)/2
≤ P (x) ≤ 1− B
| log x|(a−1)/2
. (78)
The lower bound comes from applying Jensen’s inequality to the recurrence relation (6).
The upper bound is obtained by requiring unitarity of the heat kernel and its proof is
relegated to Appendix D.
The spectral dimension and logarithmic exponent are given by
ds = 2,
α̃ = a− 1, (79)
which shows that mean field theory does not apply. This result follows from
B′ | log x|a−1 < Q(x) < B | log x|a−1 (80)
for small enough x which is obtained by a modified version of the argument in 5.1.1.
First let ℓ0 = λ(1, 1, ζ), so that
Pℓ0(x) = 1−
| log x|ζ(a−1)
| log x|2ζ(a−1)
. (81)
To obtain (80) we use (60) and (61) with p = p>(ℓ0), ℓ = ℓ0 and for the lower bound
set Tn<L = Nℓ0. Then using the bounds in (C.8) with ζ = 1 and (C.7) with ζ = 2 and
estimating the sums gives the result.
6. Heat Kernel when ǫ1 ≥ 0, ǫ2 ≥ 0
These calculations require 〈Dℓ〉µ in the various cases which are tabulated in table 2 for
convenience.
Biased random walks on random combs 17
6.1. µA – Infinite teeth at random locations
We show that
0 if ǫ2 > 0 and ǫ1 ≥ 0,
k/2 if ǫ2 = 0 and ǫ1 > 0.
These results follow from (85), (86) and (87) below.
Noting that for ǫ1 > 0 all combs have 1 − B−1− − < PC(x) < 1 − B−1+ and using
monotonicity gives
D|Tn|(x)
G∗(x;n) ≤ H(x;n) ≤
D|Tn|(x)
GC′(x;n)
1− PC′(x)
, (83)
D|Tn|(x)
〈GC′(x;n)〉µ , (84)
where C ′ is constructed from C by forcing Tn = N1. If ǫ2 > 0 then using (43) with
K = 0, ℓ = ∞ gives the upper bound
H(x;n) <
exp(−B′n). (85)
If ǫ2 = 0 then exactly the same calculation gives
H(x;n) <
exp(−B′x
2n) (86)
and evaluating the left hand side of (83) gives a lower bound of the same form. If ǫ2 > 0
and ǫ1 = 0 it is necessary to sum over the location of the first infinite tooth. Using
(C.9), (43) and introducing C ′ as in (83) gives
H(x;n) <
exp(−B′n). (87)
6.2. µB – Teeth of random length
We show that
0 if ǫ2 > 0 and ǫ1 ≥ 0;
ka/2 if ǫ2 = 0, ǫ1 > 0 and a < 2;
k if ǫ2 = 0, ǫ1 > 0 and a ≥ 2.
These results follow from
H(x;n) <
x| log x|a−1
exp(−B′n/| log x|a−1) if ǫ2 > 0 and ǫ1 ≥ 0;
x1−a/2
exp(−B′nxa/2) if ǫ2 = 0, ǫ1 > 0 and a < 2;
B exp(−nB′x) if ǫ2 = 0, ǫ1 > 0 and a ≥ 2,
when x is small enough and lower bounds of the same form.
The upper bounds are obtained by proceeding as in subsection 6.1: for ǫ1 > 0 and
ǫ2 > 0 setting ℓ = λ(1, 1, 0) + 1 and for ǫ1 > 0 and ǫ2 = 0 setting ℓ = ⌊x−
2 ⌋ + 1. For
ǫ1 = 0 and ǫ2 > 0 we start with the upper bound of (83); let ℓ1 = λ(1, 1, 2), p1 = p>(ℓ1)
and ℓ2 = λ(2, 1, 0), p2 = p>(ℓ2). The latter shall be called long teeth and we denote by
Biased random walks on random combs 18
(ℓ2K♯) the comb with a single long tooth at vertex K. We now sum over the location
of the first long tooth using (18), (43) and (C.8) and taking account of the fact that the
first long tooth may be before or after the nth tooth
H(x;n) ≤
D|Tn|(x)
p2(1− p1)K−1
1− P(ℓ2K♯)(0)
P(ℓ2K♯)m
× ((1− p1)P♯ + (p1 − p2)Pℓ1♯ + p2Pℓ2♯)
n−K−1
θ(ℓ2 − |Tn|)D|Tn|(x)
p2(1− p1)K−1
1− P(ℓ2K♯)(0)
P(ℓ2K♯)m . (90)
In the first sum we use the value given in Table 2 for
D|Tn|(x)
. In the second sum
θ(ℓ2 − |Tn|)D|Tn|(x)
= B(x| log x|2(a−1))−1+O(1) for |Tn| < ℓ2 and the result follows.
To obtain the lower bounds when ǫ1 > 0 we note that
H(x;n) ≥ B−
D|Tn|(x)GC(x;n)
D|Tn|(x)
〈GC(x;n)〉µ (91)
where the measure µ is defined by
µℓ = µℓ, for teeth Tk, k 6= n,
〈Dℓ〉µ
, for tooth Tn. (92)
Using the decomposition (18) and Jensen’s inequality
〈GC(x;n)〉µ ≥
3(1− x)n/2
exp(−Sn), (93)
where
− PCk+1(x)
1− PTk+1(x)
. (94)
Now applying Jensen’s inequality with the measure µ to (6) shows that the lower bounds
satisfy a recursion formula of exactly the same form as discussed in Appendix C. So
from (C.1) we find that
Sn ≤ n
− P (x) +
〈1− PT (x)〉µ
(〈PT (x)〉µ − 〈PT (x)〉µ) +
P (x)(1− A(x))
A(x)k−1(P̄ (x)− A(x)P (x))/(P̄ (x)− P (x))− 1
, (95)
where
P (x) =
(1− x)b−
3− bT 〈PT (x)〉µ − b+P (x)
P̄ (x) =
(1− x)b−
3− bT 〈PT (x)〉µ − b+P (x)
A(x) =
(1− x)b−
P (x)2 b+
. (96)
Biased random walks on random combs 19
For ǫ1 > 0 it is straightforward to check that A(x) > c > 1 and that the sum in (95) is
bounded above by an n independent constant. Lower bounds of the form of (89) then
follow by inserting the appropriate 〈PT 〉µ in (96) and (95).
When ǫ1 = 0
H(x;n) ≥
D|Tn|(x)
GC′(x;n)
1− PC′(x)
, (97)
where C ′ is constructed from C by setting Tk≥n = N∞. Choosing ℓ0 = λ(1, 1, 2) and
using (18) and (C.7) gives
H(x;n) ≥
D|Tn|(x)
(1− p>(ℓ0))n−13(1− x)−n/2P∗(x)2
P♭ℓ0(x)− 1k−1
1− P♭ℓ0(x) + 1n−1
D|Tn|(x)
(1− p>(ℓ0))n−13(1− x)−n/2P∗(x)2
1− P♭ℓ0(x) + 1n−1
(n− 3)2(1− P♭ℓ0(x))
2P♭ℓ0(x)− 1
, (98)
for n ≥ 4 which gives the result.
7. Results and discussion
Figure 3 outlines the results that we have computed for µA. These are new and show
that the most interesting regime is actually when the bias along the spine is towards
the origin, a circumstance which has not been studied much in the literature. When
ǫ1 ≥ 0 and ǫ2 > 0 the walker disappears rapidly, never to return, and p(t) decays faster
than any power. When ǫ1 < 0 the bias along the spine is keeping the walker close
to the origin but if there are any infinite teeth present the walker can spend a lot of
time in the teeth; the conflict between these effects leads to a non-trivial ds. The fact
that d1 = 0 whenever ǫ2 > 0 shows that the walker never gets far down the spine; if
she disappears then it is up a tooth that she is lost. The Hausdorff dimension for µA
is dH = 2, regardless of bias and so we have here several examples of violation of the
bound 2dH/(1 + dH) ≤ ds ≤ dH , which applies for unbiased diffusion [19].
Figure 4 shows our results for µB as well as the results for the unbiased case studied
in [14]. This length distribution has been studied quite extensively in the literature but
usually under the assumption that ǫ2 ≥ 0. As can be seen the interesting behaviour
displayed by µA when ǫ1 < 0 does not occur here – essentially because very long teeth
are not common enough. We believe that with more work α̃ when ǫ1 < 0, ǫ2 ≥ 0 can be
found using our methods, but as this will not give further physical insight we leave the
calculations to elsewhere [17]. The case ǫ1 > 0, ǫ2 > 0 (often called topological bias) was
originally studied using mean field theory, which gave the mean square displacement
〈n2(t)〉 ∼ (log t)2(a−1), (99)
and this is in fact correct since the walker spends much of the time in the teeth. However
the claim in [3] that (99) holds for ǫ2 > 0 regardless of ǫ1 is false. The mean field method
gives the correct result when ǫ1 = 0 only because the walk on the spine is ignored, which
Biased random walks on random combs 20
amounts to using PT (x) for PC(x) in (21) and naively applying Jensen’s inequality. The
case ǫ1 > 0, ǫ2 = 0 was studied by Pottier [13] who computed the leading contribution
exactly, but without complete control over the sub-leading terms; she also calculated
the leading behaviour 〈n2〉 − 〈n〉2 which we have not. Of course our results for ds and
d1 agree with hers. The Hausdorff dimension for µ
B is dH = 3 − a when a < 2 and
dH = 1 when a ≥ 2 and so again we see that, as expected, a biasing field intensifies
the difference between the purely geometric definition of dimension and that which is
related to particle propagation.
The results for ǫ2 < 0 are intuitively obvious and, as we have proved, apply for any
model with identically and independently distributed tooth lengths. The walker never
gets far into the tooth and therefore combs have long time behaviour characteristic of
the spine alone.
This paper has given a comprehensive treatment of biased random walks on combs
using rigorous techniques – namely recursion relations for generating functions combined
with unitarity and monotonicity arguments. It serves to put in context many previous
results as well as present new ones. In the unbiased case [14] and in some bias regimes
mean field theory is sufficient to compute the leading order behaviour because the walker
either does not reach the ends of the longest teeth or does not travel far enough down
the spine for variations from average to be important. But, as is illustrated in many
examples here, a full treatment is needed when such fluctuations cannot be ignored.
Finally, while the results are of interest in themselves, an important point of the paper
was to demonstrate that rigorous analytic methods can be used to treat biased diffusion
on random geometric structures and it is to be hoped that these tools can be extended
to higher dimensional problems.
Acknowledgments
We would like to thank Bergfinnur Durhuus and Thordur Jonsson for valuable
discussions. This work is supported in part by Marie Curie grant MRTN-CT-2004-
005616 and by UK PPARC grant PP/D00036X/1. T.E. would like to acknowledge an
ORS award and a Julia Mann Graduate Scholarship from St Hilda’s College, Oxford.
Appendix A. Calculation of 〈PT (x)〉µB for ǫ2 > 0
First we rewrite (30) as
Pℓ(x) = P∞(x)Y − (Y − 1)P∞(x)X−1
X−1 + Y −ℓ
, (A.1)
so that
〈PT (x)〉µB = P∞(x)Y − (Y − 1)P∞(x)X
X−1 + Y −ℓ
(A.2)
Biased random walks on random combs 21
PSfrag replacements
(1 + 2ǫ2)
(1− 2ǫ2)
(1 + 2ǫ2)
(1− ǫ1 − ǫ2)
(1 + ǫ1 − ǫ2)
ds = 0
dk = 0
dk = 0dk = 0
dk = 0
dk = 0
ds = 1
ds = 1 ds = 3
dk = k
ds n.d. ds n.d.
ds n.d.
ds = 2 log(1− p) Ω−1
ds = log(1− p) Ω−1 p < p∗
p ≥ p∗
Figure 3. Results for µA where Ω = log
1−|ǫ1|−ǫ2
1+|ǫ1|−ǫ2
and p∗ = 2|ǫ1|(1 + |ǫ1| − ǫ2)−1.
The logarithmic exponents α̃ and d̃k are always zero for µ
PSfrag replacements
(1 + 2ǫ2)
(1− 2ǫ2)
(1 + 2ǫ2)
(1− ǫ1 − ǫ2)
(1 + ǫ1 − ǫ2)
ds = 0
ds = 0
ds = 0
dk = 0
dk = 0 dk = 0
dk = 0
dk = 0
ds = 1
ds = 3
dk = k
dk = k
ds n.d.
ds = 2 log(1− p) Ω−1
ds = log(1− p) Ω−1
p < p∗
p ≥ p∗
ds = 2 ds = 2
ds = 2 + a
α̃ ≤ 0
α̃k = 1
α̃k = 0
α̃ = a− 1 α̃ = −a
d̃k = 0
d̃k = 0
d̃k = 0 d̃k = k(a− 1) d̃k = k(a− 1)
≤ α̃ ≤ 0
if a < 2
if a < 2
if a < 2
if a ≥ 2
if a ≥ 2
if a ≥ 2
if a = 2k
if a 6= 2k
Figure 4. Results for µB . When ǫ2 < 0 the logarithmic exponents α̃ and d̃k are
always zero.
Biased random walks on random combs 22
X−1 + Y −ℓ
X−1 + Y −ℓ
≡ S. (A.3)
Since for ǫ2 > 0, Y > 1 we let log Y = ρ and write
| log x|
X−1 + e−ρℓ
| log x|
X−1 + e−ρℓ
, (A.4)
where σ is an arbitrary constant < 1. This is bounded above by taking ℓ in the
exponential to be its value at the top of each sum to give
S ≤ Ca
X−1 + xσ
| log x|
ℓ−a +
| log x|
| log x|a−1
. (A.5)
Noting that as x → 0, X−1 → Bx we get a lower bound on 〈Pℓ(x)〉µB of
〈PT (x)〉µB ≥ 1−
| log x|a−1
, (A.6)
for small enough x. An equivalent upper bound is calculated in the same manner by
ignoring the first term in (A.4) and setting σ = 1, which leads to the result quoted in
table 1. A similar procedure leads to bounds of the form B/x| log x|a on
T (x)
which we also need, at small enough x.
Appendix B. Proof of results for non-recurrent regime
First we define a structure of ordered lists of ordered integers. Let S denote an ordered
list of hS integers
[n1, n2, . . . nhS ], n1 ≥ n2 ≥ . . . ≥ nhS ≥ 1, hS ≥ 1,
[ ], hS = 0.
(B.1)
Define
|S| =
ni, hS ≥ 1,
0, hS = 0,
(B.2)
and let SN denote the set of all distinct lists S with |S| = N . Within SN the lists S
and S ′ are ordered by letting j = min(i : ni 6= n′i) and then setting S > S ′ if nj > n′j .
Finally if S ∈ SN and S ′ ∈ SN ′ with N > N ′ then S > S ′. It is convenient to denote by
S + 1 the lowest list above S, and by S ∪ S ′ the list obtained by concatenating S and
S ′ and then ordering as above.
Biased random walks on random combs 23
Now define
H(S; f(x)) = (−1)|S|
f (ni)(x), (B.3)
and for the empty list H([ ]; f(x)) = 1. We need the following lemma, which is proved
in Appendix B.1:
Lemma
(i) If 〈H(S;PT (x))〉µ is finite as x → 0 for all S ≤ S̄ then 〈H(S;PC(x))〉µ is finite as
x → 0 for all S ≤ S̄ and ǫ1 6= 0.
(ii) If the conditions of part (i) apply and, as x → 0,
H(S̄ + 1, PT (x))
diverges as
x−γ , γ > 0, then
H(S̄ + 1, PC(x))
also diverges as x−γ.
Differentiating (5) k times gives
C (x) =
C (x)
(1− PC(x))2
+ (−1)k
S∈Sk/[k]
C(S)H(S;PC(x))
(1− PC(x))hS+1
(B.4)
where C(S) is a combinatorial coefficient. It is straightforward to check for any S
that 〈H(S;PT (x))〉µA is analytic for ǫ2 6= 0, and that 〈H(S;PT (x))〉µB is analytic when
ǫ2 < 0. When ǫ2 = 0
H(S;Pℓ(x))|x=0 = cSℓ2|S|−hS
1 +O(l−2)
(B.5)
from which 〈H(S;Pℓ(x))〉µB is divergent for S = [⌈a/2⌉], and with smaller degree for
[⌈a/2⌉ − 1, 1] if 2k < a ≤ 2k + 1, k ∈ Z, but always convergent for any inferior S. The
results given in section 4.2 then follow from noting that P∗(x) < PC(x) < P♯(0) < 1 and
using the lemma.
Appendix B.1. Proof of lemma
To prove the lemma note that
H(S; f + g) =
S′∪S′′=S
H(S ′; f)H(S ′′; g) (B.6)
and differentiate (6) n times to get
(−1)nP (n)C (x) = (1− x)F
C (x) + nF
(n−1)
C (x) (B.7)
where
C (x) =
PC(x)
PC(x)b+
(1− x)b−
S′∪S′′=S
)hS′′
H(S ′;PC1(x))H(S
′′;PT1(x)).
(B.8)
Biased random walks on random combs 24
It is then straightforward to generalise this formula to
H(S, PC(x)) = R+ (PC(x))hS
S′∈S|S|
C(S, S ′)
PC(x)b+
(1− x)b−
S′′∪S′′′=S′
)hS′′′
H(S ′′;PC1(x))H(S
′′′;PT1(x)),
(B.9)
where the leading terms are written out explicitly and R contains contributions
depending only on lists inferior to S |S|. Every term on the right hand side is positive so
it can be bounded above by using PC(x) < P♯(0) and then the expectation value taken;
moving the S ′′ = S term to the left hand side gives
〈H(S, PC(0))〉µ
P♯(0)
R+ (P♯(0))hS
S′∈S|S|
C(S, S ′)
P♯(0)b+
S′′∪S′′′=S′
S′′ 6=S
)hS′′′
〈H(S ′′;PC1(0))〉µ 〈H(S
′′′;PT (0))〉µ .
(B.10)
Part (i) is true for S̄ = [1] so the lemma then follows immediately by induction on S.
To prove part (ii) use part (i) to isolate the potentially divergent terms in (B.9) leaving
H(S̄, PC(x)) =
PC(x)
(1− x)b−
H(S̄;PC1(x)) +
H(S̄;PT1(x))
+ finite terms. (B.11)
For small enough x,
PC(x)
(1− x)b−
< 1, ∀C (B.12)
and part (ii) follows upon taking expectation values.
Appendix B.2. ǫ1 = 0, ǫ2 > 0
We will show that
H(S, PC(x))
(1− PC(x))hS+1
(B.13)
is finite at x = 0, which together with (B.4) gives the result. Using (61) and (C.9) gives
C H(S, PC(x))
, (B.14)
Biased random walks on random combs 25
where nC is the location of the first infinite tooth of C. Applying (B.9) iteratively we
find that the right hand side is bounded above by terms of the form
〈H(S ′, PT (x))〉µA . (B.15)
The maximum value of K occurring is hS + 1 + ΦS where ΦS is the number of strings
inferior to S. As remarked before 〈H(S ′, PT (x))〉µA is analytic and
is trivially
finite which completes the proof.
Appendix C. Calculation of PC(x) for some useful combs
Let the comb C have Tk = Nℓ, k < L and arbitrary TL and CL. Then following the
method of Appendix A of [14] we find
P ǫ1ǫ2C (x) = P
(1−A)(P ǫ1ǫ2CL−1(x)− P
AL−1(P ǫ1ǫ2CL−1(x)−AP
(x))− (P ǫ1ǫ2CL−1(x)− P
(C.1)
where
(1− x)b−
(P ǫ1ǫ2
(x))2b+
. (C.2)
Setting ǫ2 = 0, ǫ1 < 0, ℓ = 1, TL = N∞ and CL = ♯ we find after some algebra that
P ǫ10C (x) = P
♯ (x)
1 + A−L
+O(x)
(C.3)
and, as x → 0,
1 + |ǫ1|
1− |ǫ1|
. (C.4)
Repeating the exercise but with CL = ∗ yields a similar result.
If instead we set ǫ2 > 0, ǫ1 < 0, ℓ = 1, TL = N∞ and CL = ♯ we find
P ǫ1ǫ2C (x) = P
♯ (x)
2ǫ2(A− 1)A−L
ǫ1 − 2ǫ2(1− A−L)
(1 +O(x))
(C.5)
and, as x → 0,
A → 1 + |ǫ1| − ǫ2
1− |ǫ1| − ǫ2
. (C.6)
Again, repeating the exercise but with CL = ∗ yields a similar result.
With ǫ2 > 0, ǫ1 = 0, and C = {Tk<L = Nℓ, Tk≥L = N∞} we find that
P 0ǫ2C (x) > P
(x)− 1
, L > 2, (C.7)
(it is good enough to use P∗(x) for k = 2); and for C = {Tk 6=L = N1, TL = Nℓ}, x < x0,
P 0ǫ2C (x) < P
♯ (x)
1− 1
AL−1−1
 (C.8)
where A = (1− x)(P 0ǫ2♯ (x))−2 and B is a positive constant depending on x0, A and ǫ2.
Finally for ǫ2 > 0, ǫ1 = 0, and C = {Tk 6=L = N1, TL = N∞} we find that
P 0ǫ2C (0) = 1−
L+ (1− ǫ2)/4ǫ2
. (C.9)
Biased random walks on random combs 26
Appendix D. Upper bound on P (x) when ǫ1 = 0, ǫ2 > 0
We start by writing
H(x;n) =
D|Tn|(x)
GC(x;n)
1− PC(x)
, (D.1)
where the measure µ̄ is defined in (92). Applying Jensen’s inequality with this measure
to (6) results in a recursion formula of the same form as discussed in Appendix C and
it is easy to verify that 〈PCk(x)〉µ ≥ 〈PCk(x)〉µ to give
GC(x;n)
1− PC(x)
GC(x;n)
1− PC(x)
b+(1− x)n/2
−n 〈1− PC(x)〉µ
〈1− PC(x)〉µ
, (D.2)
where in the last line we have again used Jensen’s inequality when averaging over the
ensemble. Applying this result to (D.1), summing over n, and using (24) we obtain the
inequality
D|Tn|(x)
〈1− PC(x)〉2µ
. (D.3)
Using the value for 〈Dℓ(x)〉µ given in table 2 and rearranging gives the upper bound on
P (x) quoted in 5.2.3.
References
[1] G. H. Weiss and S. Havlin, Some properties of a random walk on a comb structure, Physica 134A
(1986) 474-484
[2] S. Revathi, V. Balakrishnan, S. Lakshmibala and K. P. N. Murthy, Validity of the mean-field
approximation for diffusion on a random comb, Phys. Rev. E 54 (1996) 2298-2302
[3] D. ben-Avraham and S. Havlin, Diffusion and reactions in fractals and disordered systems,
Cambridge University Press, Cambridge (2000)
[4] S. Havlin, J. E. Kiefer and G. H. Weiss, Anomalous diffusion on a random comblike structure,
Phys. Rev. A 36 (1987) 1403-1408
[5] J. Ambjørn, B. Durhuus and T. Jonsson, Quantum geometry: a statistical field theory approach,
Cambridge University Press, Cambridge (1997)
[6] J. Ambjørn and Y. Watabiki, Scaling in quantum gravity, Nucl. Phys. B445 (1995) 129-144,
hep-th/9501049
[7] J. Ambjørn, J. Jurkiewicz and R. Loll, Spectral dimension of the universe, Phys. Rev. Lett. 95
(2005) 171301, hep-th/0505113
[8] C. Aslangul, P. Chvosta and N. Pottier, Analytic study of a model of diffusion on a random
comblike structure, Physica A 203 (1994) 533-565
[9] S. Havlin, A. Bunde, H. E. Stanley and D. Movsholvitz, Diffusion on percolation clusters with a
bias in topological space: non-universal behaviour, J. Phys. A 19 (1986) L693-L698
[10] V. Balakrishnan and C. Van den Broeck, Transport properties on a random comb, Physica A 217
(1995) 1-21
[11] S. Havlin, A. Bunde, Y. Glaser and H. E. Stanley, Diffusion with a topological bias on random
structures with a power-law distribution of dangling ends, Phys. Rev. A 34 (1986) 3492-3495
http://arxiv.org/abs/hep-th/9501049
http://arxiv.org/abs/hep-th/0505113
Biased random walks on random combs 27
[12] N. Pottier, Diffusion on random comblike structures: field-induced trapping effects, Physica A 216
(1995) 1-19
[13] N. Pottier, Analytic study of a model of biased diffusion on a random comblike structure, Physica
A 208 (1994) 91-123
[14] B. Durhuus, T. Jonsson and J. F. Wheater, Random walks on combs, J. Phys. A 39 (2006) 1009-
1038, hep-th/0509191
[15] B. Durhuus, T. Jonsson and J. F. Wheater, The spectral dimension of generic trees,
math-ph/0607020
[16] B. Durhuus, T. Jonsson and J. F. Wheater, On the spectral dimension of generic trees, DMTCS
proc. AG (2006), 183-192
[17] T.M. Elliott, Oxford University D.Phil Thesis, in preparation.
[18] W. Feller, An introduction to probability theory and its applications, Vol.2, Wiley, London (1968)
[19] A. Grigoryan and T. Coulhon, Pointwise estimates for transition probabilities of random walks
in infinite graphs, in: Trends in mathematics: Fractals in Graz 2001, Ed. P. Grabner and W.
Woess. Birkhäueser (2002)
http://arxiv.org/abs/hep-th/0509191
http://arxiv.org/abs/math-ph/0607020
	Introduction
	Definitions
	Random combs
	Biased random walks
	Two-point functions
	The Heat kernel
	Basic properties
	Results for simple regular combs
	General properties of the generating functions
	Useful elementary bounds
	Results independent of the comb ensemble 
	ds when 2<0 
	ds when 1>0
	dk when 2<0 or 1<0
	The spectral dimension when 20 and 10
	A – Infinite teeth at random locations
	2= 0, 1< 0
	2> 0, 1< 0
	2> 0, 1= 0
	B – Teeth of random length
	2= 0, 1< 0
	2> 0, 1 <0 
	2> 0, 1 =0 
	Heat Kernel when 1 0, 2 0
	A – Infinite teeth at random locations
	B – Teeth of random length
	Results and discussion
	Calculation of "426830A PT(x) "526930B B for 2>0
	Proof of results for non-recurrent regime
	Proof of lemma
	1=0, 2>0
	Calculation of PC(x) for some useful combs
	Upper bound on P(x) when 1=0, 2>0
