Fractal Dimensions and Martin Boundary of Graphs

András Telcs IBS-B Tárogató u. 2-4 H-1021 Budapest, HUNGARY atelcs@tech.ibs-b.hu

January 5, 2000

Abstract

This paper shows large deviation theorem for Markov chains with spatial symmetric Green’s function. Spatial symmetry and behaviour of the Martin boundary is investigated.

1 Introduction

This paper can be considered the fifth in a series of studies on random walks (RW) on graphs and fractal dimensions. The main goal of the previous papers, among others, was to give a ”nice” condition for the logarithmic form of the Einstein relation

d_{R} = d + 2 − d_{Ω}.  (1)

The relation states that the exponent of the mean exit time from a finite ball d_{R} simply the sum of the upper mass dimension d (which coincides in many cases with the Hausdorff dimension) and the exponent of the asymptotic behavior of the graph resistance 2 − d_{Ω} . This relation holds for a wide class of graphs, on smooth graphs (c.f. [T1] and definition below). This relation was already stated by [RT] together with the relation of the spectral density exponent (for the definition see [T4])

d_{s} = \frac{2d}{d_{R}}  (2)

and the local behavior of the n-step transition function

P_{n}(0, 0) ≍ n^{− \frac{ds}{2}} .  (3)

All these relations were studied on many particular fractals, first of all on the deterministic and randomized version of Z^{d} in [XYZ], on the Sierpinski gasket (c.f.[Ha]) and by Barlow and his co-authors in several papers, [BB][BP] on the Sierpinski carpet(for further literature see [B]). Kigami introduced a new approach and studied a wide class of fractals [K1], [K2], [K3] but the important relations (1-3) he proved under some conditions for strongly recurrent (d_{Ω} < 2) fractals. The systematic development of techniques to study random walks in different environments can be found in [R].

In this paper nearest neighbor RWs on graphs are considered. The underlying structure is a locally finite connected graph without loops, and the transition probabilities define a nearest neighbor RW with spatially symmetric Green’s function with polynomial behavior at the infinity. This property is referred in the literature with the notion of Greenian index. Let us call a graph Greenian if it has Greenian index.

The results of this paper are the following

• If a graph has Greenian index then the large deviation theorem for the nearest neighbor RW on it is true.

• Examples are given for nonsmooth (or non-Greenian) graphs for which (1 -3) do not hold.

• (1) holds for a nonsmooth recurrent graphs with finitely many smooth components

• smoothness equivalent with the existence of Greenian index

The paper ends with some conjectures on recurrent boundary theory.

2 Definitions and statement of the results

Definition 1 Two sequences a_{n,}b_{n} are asymptotically equal if there is 0 < c ≤ C < ∞ such that c <\frac{a_{n}}{b_{n}} < C, and this will be denoted by

a_{n} ≍ b_{n.}

Definition 2 An integer sequence N_{k} is exponentially growing if there is a constant Q, 1 < Q < ∞ for which

N_{k} ≍ Q^{k}  (4)

2.1 Graph objects

Let G = (V, E) be a graph with vertex set V and edge set E, throughout the paper the graph is countable infinite, locally finite connected without loops and multiple edges. We shall use the graph distance ρ(x, y) for x, y ∈ V the length of the shortest connecting path. Using this metric, we can define the geometric ball B_{N} = B_{x,N} = {y ∈ V : ρ(x, y) ≤ N}, its volume by b_{N} = b_{x,N} = |B_{x,N}| and its surface S_{N} = S_{x,N} = B_{x,N} − B_{x,N−1} for N > 0, x ∈ V. The degree of a vertex x ∈ V is deg(x) = b_{x,1}−1, the number of its neighbors. The maximal degree is denoted by D = max_{x∈V} deg(x) < ∞.

Definition 3 A sequence a_{n} has exponent a if

lim sup_{n} \frac{log a_{n}}{log n} = a.

Let us use the notation a_{n} ≈ n^{a} for this relation.

In general, uniformity will be used to refer to the situation that the constants contained in the estimates are uniformly bounded away from zero and infinity on the vertex set, i.e. there are nonzero constants independent of the vertices in the consideration.

The main object is the process X_{n} ∈ V, a discrete Markov chain, defined on the graph G. It is a simple symmetric RW on the graph with transition probability

P (x, y) = \{ \begin{matrix}\frac{1}{deg(x)} if (x, y) ∈ E \\ 0 otherwise \end{matrix}

It is assumed during the whole paper that the RW is aperiodic. For the n-step transition probabilities P_{n}(x, y) will be used.

Definition 4 Denote R(x, y) for x, y ∈ V is the resistance between the given vertices if the edges considered as unit resistors.

Similarly for arbitrary (not necessarily but in this paper always finite) sets A, B ⊂ V, R(A, B) the resistance between the nodes after short cutting the sets, i.e. shrinking them into single points. (For the shorting method see [T1] and for the rigorous definition of the resistance [K1].)

2.2 Fractal exponents and dimensions

The basic exponents we study are the following

Definition 5 The fractal dimension of the graph is d if

b_{N} ≈ N^{d}.

Definition 6 Denote R_{x,N} = R(x, S_{x,N}). Sometimes it will be denoted by R_{N} if this does not cause confusion. Denote R_{x} = lim_{N→∞} R_{x,N} if it is finite and ρ_{x,N} = R_{x} − R_{x,N} .

Definition 7 For shortness introduce

r_{N} = r_{x,N} = \{ \begin{matrix}R_{x,N} if it goes to infinity \\ ρ_{x,N} otherwise \end{matrix}

Definition 8 The resistance dimension is d_{Ω} if

r_{x,N} ≈ N^{2−d_{Ω}}

Definition 9 The exit time T_{x,N} = min{k : X_{k} ∈ S_{x,N}} has random walk exponent d_{R} if

E(T_{x,N} | X_{0} = x) ≈ N^{d_{R}}

Remark 1 It was shown in [T4] that the above defined exponents do not depend on the reference vertex.

Let us define Q_{N} = Q_{x,N} the finite submatrix of the transition matrix P of the simple symmetric RW on G restricted to B_{x,N} . (This is clearly a substochastic matrix.)

The Laplace operator plays an important role in the analysis of diffusion processes as well as in the description of Dirichlet spaces (c.f. [RT], [K1] ). The density of its eigenvalues determined by the previous exponents (as it was conjectured for fractals in [RT], proved for Sierpinski structures in [BP], [B] and for p.c.f. self-similar sets (generalization of finitely ramified fractals and nested fractals) in [K2]). It is worth to mention that the RW is deg(x)−reversible and hence the eigenvalues of P and Q_{N} are real. This observation makes possible to drop the graph regularity condition (deg(x) = deg(y) = r for all x, y ∈ V) in Theorem 1. [T4], and in the results of this paper.

Definition 10 Δ_{N} = I − Q_{N} is the Laplace operator of the subgraph G_{N} = G|_{B_{N}} .

The condition below is a bit simplified (more restrictive but general enough for the present context) version of that is given in [T4] or [XYZ] to ensure the Einstein relation.

Definition 11 (C_{s}) G is smooth with respect to x ∈ V if there are a sequence of integers N_{i} and constants C(x), Q(x) ∈ (0, ∞) for which (4) holds and for the voltage, v, defined on B_{N_{m}} is zero at the boundary and 1 at the reference vertex

C(x)Γ_{k}^{(n)} ≤ γ_{k−1}^{(n)}

holds for all 1 < k < n, where

Γ_{k}^{(n)} = max{v(y) : y ∈ (B_{N_{k}}\B_{N_{k−1}}) ∪ S_{N_{k−1}}},
γ_{k}^{(n)} = min{v(y) : y ∈ (B_{N_{k}}\B_{N_{k−1}})},
γ_{1}^{(n)} = 1.

G is said to be uniformly smooth if C(x) and Q(x) are uniformly bounded.

For later use a partial order of surfaces is introduced.

Definition 12 If a potential function is given on a ball B_{N}, as in Definition 11. (C_{s}), a partial ordering is defined on potential surfaces and geometric surfaces by

Γ < S_{i} < Γ′

if S_{i} is the boundary of B_{i} = B_{x,i} and Γ ⊂ B_{i}\S_{i} and Γ′ ⊂ V \B_{i} .

The following conditions will be used

Definition 13 (C_{0}) G is a connected locally finite graph without loops on which (for sake of simplicity) the RW is non cyclic

(C_{1}) b_{N} ≍ N^{d} and r_{N} ≍ N^{2−d_{Ω}}

(C_{2}) d_{Ω} ≠ 2

(C_{3}) G is uniformly smooth.

2.3 Main results

Theorem 1 If conditions (C_{0}-C_{3}) hold then for all x ∈ V with a suitable constant c_{1} > 0

P (T_{x,N} < ϵE(T_{x,N})) ≤ exp −c_{1}ϵ^{− \frac{1}{d_{R}−1}}  (5)
P ( max_{0≤k≤n} ρ(0, X_{k}) > tn^{\frac{1}{d_{R}}}) < exp −c_{1}t^{\frac{d_{R}}{d_{R}−1}}  (6)

The condition d_{Ω} ≠ 2 seems to be a bit restrictive but it will be quite evident from the proofs that it can be eliminated if more information is given on the behavior of the slowly nonpolinomially behaving resistance.

Theorem 2 A transient graph (2 < d_{Ω} < ∞)

is smooth if and only if

G(x, y) = ∑_{n} P_{n}(x, y)

satisfies uniform convergence, i.e.

G(x, y) ≍ G(x′, y′)

if ρ(x, y) ≍ ρ(x′, y′) and ρ(x, y), ρ(x′, y′) → ∞.

The corresponding statement for strongly recurrent graphs (d_{Ω} < 2) holds

Theorem 3 Assume that the graph is strongly recurrent (d_{Ω} < 2) and the kernel

g(x, y) = lim_{N→∞} ∑ Q_{N}^{k}(x, x)\frac{d(y)}{d(x)} − Q_{N}^{k}(x, y)

exists then

the graph is smooth if and only if the kernel satisfies uniform divergence condition, i.e.,

g(x, y) ≍ g(x′, y′)

if ρ(x, y) ≍ ρ(x′, y′) as ρ(x, y), ρ(x′, y′) → ∞.

3 Proof of the Large Deviation Theorem

Proposition 1 If conditions C_{0} − C_{3} hold then

E_{x}(T_{x,N}) ≍ b_{x,N}r_{x,N}

The proof is basically contained in [XYZ, Proposition 3.2 and 3.3] or in [T1] and can be proved with elementary modifications.

Remark 2 Zhou’s result uses a slight weaker assumptions (H_{3}, H_{4} or H_{5}) but basically contains the same technical conditions which ensures the integrability in a closed form of the potential over a finite ball. The important assumption is still about the control of the potential surfaces, i.e., the smoothness of the graph. In this respect, there is no difference between the above mentioned two results and Proposition 1. The detailed analysis of the smoothness condition is postponed to Section 4.

The proposition above is stated in a bit weaker form for sake of simplicity but we need only this one.

The next statements provide transient conterpart of the spectral results of [T4].

The Lemma below follows in a similar way as in the recurrent case in [T2].

Lemma 1 For all transient graph

μ_{N}^{−1} ≥ c\frac{E_{w}^{2}(T_{w,N/4})}{R(S_{N/2}, S_{N}) (b_{N} − b_{N/2−1})}  (7)

with the suitable constant c and E_{w}(T_{w,N/4}) = min_{y∈S_{x,3N/4}} E_{y}(T_{y,N/4}).

Proof of Lemma 1 Let us follow the idea of the cited proof.

μ_{N} = inf_{Φ} \frac{(Φ, (I − Q_{N})Φ)}{(Φ, Φ)}.

Define the potential w by w(x) = R(S_{N/2}, S_{N}) for x ∈ S_{N/2} and w(x) = 0 for x ∈ S_{N}. The resulting potential corresponds to the local times spent in B_{N}\B_{\frac{1}{2} N−1} by the RW starting on S_{N/2} till it reaches S_{N}. The numerator expresses the flowing current multiplied by the voltage in the source i.e.

(w, (I − Q_{N})w) = R(S_{N/2}, S_{N}) < cρ_{N};

The denominator can be estimated as follows

(w, w) ≥ ∑_{B_{N} \B_{N/2−1}} w^{2}(x) ≥ \frac{(∑_{B_{N} \B_{N/2−1}} w(x))^{2}}{D^{2}(B_{N}\B_{N/2−1})}

but the sum of the local times is greater than the time the RW needs starting from the first hitting point of z ∈ S_{3N/4} before it reaches the surface of the ball S_{z,N/4} and the statement is proven. It is worth observing that here the triangular inequality was used in an implicit way.□

For exhausting analysis of the local times of RWs see [R]. Here we present the comparison of local time and smalles eigenvalue of Laplacian for transient graphs. Analogous statement was given for recurrent graphs in [T2, Proof of Theorem 2.].

Proposition 2 Under the condition (C_{0}−C_{3}).

μ_{x,N} ≍ \frac{1}{E_{x}(T_{x,N})}  (8)

uniformly on the graph.

Proof of Proposition 1 Recalling Lemma 3. from[T4]

μ_{x,N}^{−1} = ∑_{y∈B_{x,N}} α_{y}E_{y}(T_{x,N}) ≤ max_{y∈B_{x,N}} E_{y}(T_{x,N}) ≤ max_{y∈B_{x,N}} E_{y}(T_{y,2N})

and by Lemma 1. and Proposition 1. applied in (??) follows the statement.

The proof of the next Proposition corrects the proof of Lemma 6.3 in [T4]. Proposition 3 If C_{0} − C_{3} holds then with a proper choice of c

P (T > n) ≥ \frac{1}{c′} − \frac{cn}{c′E(T)}  (9)

if n ≤ cE_{x}(T_{x,N}) where the constants are independent of N and x. Proof of Proposition 2 From the easy estimate

T ≤ n + I(T ≥ n)(T − n)

E(T) ≤ n + E (I(T > n)E_{X_{n}}(T))

and using the strong Markov property and the fact that X_{n} ∈ B_{x,N} and the upper estimate of the exit time□ Remark 3 This observation has the useful consequence that

P_{x}(T_{x,N} > n) > c^{∗}.

if n ≤ cE_{x}(T_{x,N}). Proof of Theorem 1 The proof is given in the transient case, the recurrent case works in the same way, it is even simpler so it is left to the reader.

Using the triangular inequality for the graph distance metric, T_{N} the hitting time of S_{0,N} can be decomposed. Let r > 0 and l = {N/r} integers and define r hitting times in the following way. Let

τ_{1} = s_{1} = min{k : X_{k} ∈ S_{0,l}},

Y_{1} = X_{τ_{1}}

τ_{i} = min{k > τ_{i−1} : X_{k} ∈ S_{y_{i−1},N/r}},
Y_{i} = X_{τ_{i}} ,
s_{i} = τ_{i} − τ_{i−1}

for r ≥ i > 1. It is clear that

T_{N} > ∑_{1}^{r} s_{i}.  (10)

from (9) we have

P_{x}(T_{x,l} ≤ s) < 1 − c_{7}(1 − \frac{1}{c_{4}E_{x}})^{s} < 1 − c_{7} + c_{8} \frac{s}{E_{x}} =: p + \frac{s}{b}  (11)

with 0 ≤ p < 1, b > 0. Elementary calculation leads to the same consequence as from (11) it follows by the application of [BB, Lemma 1.1] which states

P (T_{N} < t) < exp (2(\frac{brt}{p})^{2} − n log \frac{1}{p})

if t = ϵE_{N}, r = c_{8}ϵ^{− \frac{1}{d_{R}−1}} where the choice of c_{8} ensures that in the above exponent the second term is the dominant and the first statement follows.

The second statement of Theorem 1. is already straightforward from the first one.□

Remark 4 The sequence of estimates hide the key of the proof which is in fact

min_{w∈S_{0, \frac{3N}{4}}} E_{w}(T_{w, \frac{N}{4}} ) ≍ max_{z∈B_{0,N}} E_{z}(T_{2N})

and consequently

min_{w∈S_{0, \frac{3N}{4}}} E_{w}(T_{0,N}) ≍ max_{z∈B_{0,N}} E_{z}(T_{0,N}).

This reminds to a weak form of the Harnack’s inequality.

Remark 5 Under the conditions (C_{0} −C_{3}) a lower diagonal estimate for the RW comes just as in [T4]

P_{2n}(x, x) ≥ Q_{N}^{2n}(x, x) ≥ c_{5}n^{− \frac{d}{d_{R}}}

4 Compactification, smoothness and Martin Boundary

At the beginning of the series of papers ([T1]-[T4]) the notions of fractal dimension and resistance dimension where introduced using the approximation of V the infinite vertex set with its finite balls B_{N}. The conductivity properties were tested with the potential surfaces generated by connecting unit voltage to a reference point 0 while S_{0,N} was grounded. This approach led to the whole machinery and to the smoothness condition but did not provide answer what is the nature of this smoothness. Instead of the voltages let us consider the currents on B_{N}. Let a unit current pumped in at 0 and flow out at S_{N}. The resulting out-coming current is not uniform, and the decay of the local flux as we move away from 0 may depend on the direction. If the direction dependence is strong, the graph is not smooth in some sense. But what does direction mean in a graph? Is the S_{N}− approximation is correct? This S_{N}−approximation carries the implicit assumption that there is no direction dependence. The surface S_{N} was short-cutted into a single end-node of the finite subgraph and the current flows out from it regardless of the fine details of the flux on different parts of the surface. This limitation of the model can be removed with the study of the boundary behavior of the graph and the RW. It will turn out that the S_{N} approximation is finally not so bad and smoothness is a quite natural condition. In this section examples are given for nonsmoth transient graphs, some steps taken to develope the electric network interpretation of the boundary theory. In the recurrent case, a slight generalization of Proposition 1. is also shown.

4.1 Transient graphs

4.1.1 Example for a nonsmooth graph

Example 1.

It will be shown in Proposition 5. that the smoothness is equivalent with the equi-convergence of G(0, x) if x → ω for all ω ∈ Ω. This gives the natural base for the construction of a nonsmooth graph. Simply let us consider two smooth graphs G, G′ on separate vertex sets. Two fixed reference points x, x′ are chosen and connected with single edges to a new external one denoted by O. Let us suppose that their dimensions are d, d_{Ω}, d_{R}, d′, d′_{Ω}, d′_{R} respectively. Assume that d < d′, 2 < d′_{Ω} < d_{Ω} and from these it follows that

d_{R} < d′_{R}.

It is easy to see that the potential levels formed by the usual setting has very different distances from 0 in G and G′ i.e. G′′ is not smooth.

On the other hand, from the transience it follows that the RW sooner or later will start to wander in one of the components and never returns to 0, i.e., never walks on the other subgraph. It is also clear that the new graph, G′′, has the dimensions,

d′′ = max{d, d′} = d′;  (12)
d′′_{Ω} = max{d_{Ω}, d′_{Ω}} = d_{Ω};  (13)
d′′_{R} = max{d_{R,}d′_{R}} = d′_{R} = d′ + 2 − d′_{Ω};  (14)

The third row follows from two elementary observations.

E(T′′_{N}) < E(T_{N}) + E(T′_{N})

and

E(T′′_{N}) > E (T′_{N}I(X_{T_{N}} ∈ G′)) = E (T′_{N}|I(X_{T_{N}} ∈ G′)) P (X_{T_{N}} ∈ G′)

> E (T_{N}^{∗}) P (X_{1}...X_{T_{N}} ∈ G′) ,

where the last probability is bounded from below by a fixed constant due to the transience and T_{N}^{∗} is the hitting time in the separate G′ with exponent d′_{R}. The last equality in (14) comes from the smoothness of G .

But, consequently,

d′′_{R} ≠ d′′ + 2 − d′′_{Ω},

since

d′′_{R} = d′_{R} = d′ + 2 − d′_{Ω} > d′ + 2 − d_{Ω}. = d′′ + 2 − d′′_{Ω}

Remark 6 For a more particular example one can consider simply G = Z^{3}, and G′ is Sierpinski tree of the appropriate dimensions (c.f. [TW] )

Remark 7 Similar construction can lead to a nonsmooth G′′ with dimensions d = d′ − δ; 2 < d_{Ω} = d′_{Ω} − δ; d_{R} = d′_{R}, where δ > 0, which ensures the Einstein relation, though the smoothness does not hold.

Example 2.

Another construction shows that for a nonsmooth graph the diagonal estimate fails. Consider two uniformly smooth graphs G and G′ with the dimensions d < d′; d_{Ω} < d′_{Ω}; d_{R} = d′_{R}, i.e., d − d_{Ω} = d′ − d′_{Ω}. The diagonal estimate gives that

P′_{2n} = o(P_{2n}).

On the other hand, it is clear that

P′′_{2n} ≍ P_{2n}.

but

d′′ = d′ > d;
d′′_{R} = d_{R} = d′_{R}

and hence

n^{− \frac{d′′}{d{′′ \atop R}}} = o(P′′_{2n}),

i.e., the diagonal estimate does not hold.

4.1.2 Analysis of the boundary, transient graphs

In this section the transient case will be studied when the total number of returns is finite:

G(0, 0) = ∑_{n} P_{n}(0, 0).  (15)

The increasing sequence of balls, B_{N}, can be considered and we have the relation

G(0, 0) = lim_{N} ∑_{k} Q_{N}^{k}(0, 0) = lim_{N} R(0, S_{N})

The first equality follows from the monotone convergence and from the fact that P_{n} ≥ Q_{N}^{n} always holds and P_{n} = Q_{N}^{n} if n ≤ N.

The potential kernel is well defined in the case of transient graphs.

G(x, y) = ∑_{n} P_{n}(x, y)

which can be interpreted as

G(0, x) = lim_{N} R(0, Γ_{x}^{0,S_{0,N}}) =: lim_{N} v_{N}(x) = v(x).

One can prove easily by the monotonicity of v_{N}(x) in N that the above limit exists. The main tool we gain with this interpretation is the system of Γ_{ϵ} = Γ_{ϵ}^{0,ω} potential surfaces.

Γ_{ϵ} = {w ∈ W | v(w) = ϵ}

B_{ϵ} = {x ∈ V | v(x) ≥ ϵ}.

Introducing the analogous objects, the diffusion can be studied in the growing system of this ”balls”. Two problems are to be considered. It is known that the Dirichlet problem solvable on the one point compactification of V [W1, Section 6.] but it is not clear what is the connection of this solution to the diffusion process. Let us denote by M the limit point of the process (in the sence of the Martin boundary theory). Thanks to the transience M ∩ V = ∅. the limit points of the process at the boundary, i.e., the exit measure is concentrated to the boundary. But does it coincide with the ”end” of the graph?

The ”end ” of the graph is Ω, the set of equivalence classes of infinite paths leaving all finite sets. Two paths are equivalent if there is a third which meets them infinitely often.

The topology is defined as an inverse limit, the neighborhood of ω ∈ Ω consist of the infinite connected component containing the paths belonging to it after removing a finite set from V.

Woess studied the connection of this end to the Martin boundary. (c.f. Cartwright and Woess ([CSW]) )

Proposition 4 For a graph with boundary |Ω| > 1 if the Green function vanishes at the infinity ( i.e. all B_{ϵ} are finite) then Dirichlet problem solvable with respect to Ω.

As the S_{N}−approximation is the shrinking (in electric network sense shortcutting) of this surface to a single absorbing boundary, the ω boundary is the shrinking of Ω, the graph boundary, to a single boundary point. Does this shrinking preserves all the important properties of the diffusion or not? As it will be shown, the answer is yes if and only if the graph is smooth. If it is not the case, still there are some possibility to control the diffusion.

4.1.3 The extended electric network model

To prove Theorem 2. we need the extension of the electric network model in two sense. Consider V^{∗} = V ∪ {ω}, the one point compactification of V, and introduce the extension of the electric network to it in the following way. A unit voltage connected to the points 0, ω and the potential v is well defined by the boundary conditions v(0) = 1, v(ω) = 0 since

R(x, ω) defined as the limit of the monotone increasing and bounded sequence of R(x, S_{x,N})

R(x, ω) = lim_{N→∞} R(x, S_{x,N}).

There is a right potential on V ∪ {ω}with respect to P one at 0 and vanishing at ω.

It is clear that

v_{N}(y) = \frac{R(Γ_{y,}S_{N})}{R(0, S_{N})}

is right potential on B_{N} and from the monotonicity follows that v_{N} is non-decreasing in N and hence the limit

v(y) = lim_{N→∞} v_{N}(y)

exists.

This v inherits the right potential property of v_{N}, so we have a right potential on V vanishing at infinity, i.e. in ω. The probabilistic interpretation is also inherited by this and the analogous right potential u = c_{.}v. v(x) = F (x, 0) is the probability of visiting of 0 starting at x and u(x) is the total number of returns to x starting at 0 on the unlimited graph.

The other direction of extension is introducing the model of the physical electric network on W = E × [0, 1] with a fixed orientation on each edge. For (y, z) ∈ E, α ∈ [0, 1], η= (y, 0), ζ = (z, 1) we define the resistance for the internal vertex ξ = ((y, z), α) ∈ W on the edge oriented from y to z and identified on the unit interval by α. In in other word its ”distance” from y is α and the resistance is

R(y, ξ) = R(η, ξ) = αR(y, z)

consequently a potential given on y and z extends to it as

v(ξ) = αv(z) + (1 − α)v(y).

We can consider the equipotential surface on level γ

Γ_{γ} = {ξ ∈ W : v(ξ) = γ}.

We need the concept of the balls surrounded by equipotential surfaces. (c.f. [T1])

B_{0,ϵ} = {ξ ∈ W : v(ξ) ≥ ϵ}.

and furthermore T_{ϵ} = T_{0,ϵ} the exit time from this ball.

4.2 The smoothness condition

The next definition given by Zhou (H_{3} [XYZ]) is a somewhat stronger form of the smoothness.

Definition 14 (H_{3}) There is a sequence of integers N_{i} and constant C_{0} ∈ (0, ∞) for which the voltage v defined on B_{N_{m}}\B_{N_{l}} zero at the outer boundary and 1 at the inner boundary satisfies for all l and n

C_{0}Γ_{k}^{(n,l)} ≤ γ_{k−1}^{(n,l)}

for all l ∨ 1 < k < n, where

Γ_{k}^{(n,l)} = max{v(y) : y ∈ (B_{N_{k}}\B_{N_{k−1}}) ∪ S_{N_{k−1}};

γ_{k}^{(n,l)} = min{v(y) : y ∈ (B_{N_{k}}\B_{N_{k−1}});

γ_{l}^{(n,l)} = 1.

It is clear that H_{3} ⊂ C_{3} since in the later one l = 1 is used, i.e., Proposition 1. is a slight generalization of Proposition 3.2, 3.3 [XYZ].

The next definition comes from the one point compactification using the potential v defined above.

Definition 15 Define the sequence of pairs as follows. N_{0} = 0, ϵ_{0} = R_{G}, ϵ_{1} = min{v(y) : y ∈ S_{1}} and for k > 1

N_{k} = min{m : Γ_{ϵ_{k−1}} < S_{0,m}}

ϵ_{k} = min{v(y) : y ∈ B_{N_{k}}}

.

From the definition it follows that if Γ_{k} := Γ_{ϵ_{k}}

S_{k−1} < Γ_{k−1} < S_{k}.

The system above satisfies condition Definition 16 (C_{ω}) if for the N_{k} sequence above there is a Q ∈ (1, ∞) such that \frac{N_{k}}{N_{k−1}} < Q for k > 1.

Proof of Theorem 2

It is clear that C_{s} ⊂ C_{ω} so it is enough to see that C_{ω} ⊂ C_{s}. The definition of C_{ω} provide a sequence of concentric, non intersecting and alternating sequence of equipotential surfaces Γ_{i} and geometric surfaces S_{i}. Without loss of generality we can assume that N_{i} is quasi exponential, i.e., q <N_{i}/N_{i−1} < Q for a fixed 1 < q ≤ Q < ∞ constants. From the monotonicity of ρ_{i} it can also be assumed that the subsequence N_{i} ensures

ρ_{i} > 3ρ_{i+1}.

It will be proven that this sequence of integers provide smoothness for G. Suppose that the smoothness fails for G for a given k > 0. The surface S_{k} is now grounded to potential 0 and the origin kept on voltage R_{k}. For any given 0 < i < k the condition is violated if

Γ_{i}^{k} ≥ γ_{i−1}^{k}

i.e. ∃y ∈ B_{i−1} such that v(y) = v_{k}(y) = Γ_{i−1}^{k} and ∃z ∈ S_{i} such that v(z) = v_{k}(z) = Γ_{i}^{k},

v_{k}(z) ≥ v_{k}(y)

From the monotonicity

v_{k}(z) ≥ v(z)

and from H_{ω},

v(z) > v(y)

On the other hand

v_{N_{k}}(y) + Γ_{N_{k+1}}^{N_{k+1}} > v_{N_{k+1}}(y).

as it is pointed out by Zhou in [XYZ, proof of Theorem 2.1]

If Γ_{k+1}^{k+1} denotes the potential surface of the potential level Γ_{k+1}^{k+1} = Γ_{N_{k+1}}^{N_{k+1}}than the observation Γ_{k+1}^{k+1} = R(Γ_{k+1}^{k+1}, S_{k+1}) leads to the estimate

Γ_{k+1}^{k+1} ≤ R(Γ_{k+1}^{k+1}, Γ_{k+2}) ≤ R(Γ_{k}, Γ_{k+2}),

where the last inequality follows from the separation property ensured by H_{ω} . Summing q from k it follows that

v_{k}(y) + ∑_{q=k+1} R(Γ_{q}, Γ_{q+2}) > v(y)

which means that

v_{k}(y) + 2ρ_{k} > v(y).

However, the condition on the subsequence N_{i} ensures that

v(y) − v(z) > 2ρ_{k}

which leads to

v_{k}(y) > v(y) − 2ρ_{k} > v(z) ≥ v_{k}(z)

that contradicts to the assumption, so the statement is proven.□

The proof of Theorem 3. is placed here though it is about the recurrent case, since the proof uses very similar arguments as the previous one.

Proof of Theorem 3 In the recurrent case it is clear again that from the smoothness the uniform divergence of the kernel g follows.

The opposite direction needs more attention. Let us consider the sequence N_{i} controlling the resistance exponent. Choose k so that, the \frac{R(0,Γ_{i})}{R(0,Γ_{i−k})} > C^{2−d_{Ω}} for all i > k if d_{Ω} ≠ 2. We state that the N_{jk} j > 0 sequence gives smoothness. Let it be assumed that this is not the case, i.e. there are z ∈ S_{i−k} and y ∈ S_{i} for which v_{N}(z) ≥ v_{N}(y) where v_{N} is the potential function defined by v_{N}(0) = 0, v_{N}(w) = R_{N} for w ∈ S_{N} and N = N_{jk} for a given j. Using v(x) = g(0, x) define

\underline{v} = v \frac{R_{N}}{R(0, Γ_{N})}

and

\overline{v} = v \frac{R_{N}}{R(0, Γ_{N+1})},

where the equipotential surface Γ_{N}, S_{N} < Γ_{N} < S_{N+1} comes from the assumption.

From the maximum principle it follows that

v_{N}(y) ≥ \underline{v}(y);
v_{N}(z) ≤ \overline{v}(z),

and using the notation γ_{i} =R(0, Γ_{i}) it follows that

v_{N}(y) ≥ γ_{i} \frac{R_{N}}{γ_{N}};

v_{N}(z) ≤ γ_{i−k} \frac{R_{N}}{γ_{N−1}}

but it concludes in contradiction if

\frac{γ_{i}}{γ_{i−k}} > \frac{γ_{N}}{γ_{N−1}}

for all k < i ≤ N. On the other hand, this inequality holds by the proper choice of k and using the condition d_{Ω} < 2.□

Remark 8 If d_{Ω} ≠ 2 , \frac{γ_{i}}{γ_{i−k}} > \frac{γ_{N}}{γ_{N−1}} should be controlled using \frac{R_{N}}{R_{N−1}} > \frac{γ_{N}}{γ_{N−1}}

and \frac{γ_{i}}{γ_{i−k}} > \frac{R_{i−1}}{R_{i−k+1}} , i.e.\frac{R_{i−1}}{R_{i−k+1}} > \frac{R_{N}}{R_{N−1}} . This might be possible in several particular cases if more is known about the behavior of the subpolynomially growing resistance R_{l}.

In the light of this result the question arises what can be said about the diffusion if the Green function vanishes tending to the boundary, i.e. the Martin and end boundary coincide (or the end is a single point). What to do if this condition fails? This latter possibility can not be excluded either during this study since for finitely ramified fractals or their generalizations like the nested fractals or p.c.f. self-similar sets the Green function may stay positive on a subsequence of vertices namely on some cutting sets.

4.2.1 Nonsmooth graph

Assume that the graph has finitely many ends ( Ω < ∞). In this case removing a finite set (large enough) G is decomposed into finitely many connected components having single end. In the transient case the finite return number ensures that the RW will spent all the lifetime after a given time in a connected component not leaving it any more. On the other hand if M = Ω, the limit points are at the boundary. If this is the case, the components (and the ends) can be classified by the fractal and resistance exponent d(ω), d_{Ω}(ω) defined on the sequence of components containing ω. Two boundary points ω, ω′ are equivalent if d(ω) = d(ω′) and d_{Ω}(ω) = d_{Ω}(ω′). In this way Ω is partitioned into equivalence classes Ω = ∪_{i=1}Ω_{i} where the connected components belonging to a given class form a smooth graphs. If this is a finite partition, the diffusion can be studied on the subgraphs as it was done in Example 1. In general, if the graph can be decomposed into finitely many smooth subgraphs, the diffusion can be controlled separately on these subgraphs. In other word, if G has finitely many connected smooth (or uniformly smooth) subgraphs covering the whole graph then the diffusion can be studied on these subgraphs separately. The infinite case brings new difficulties and is not yet solved.

The above classification can be modified to decrease the number of classes saying that two boundary points ω, ω′ are equivalent if d(ω)−d_{Ω}(ω) = d(ω′)− d_{Ω}(ω′), i.e., one can expect that the diffusion rate is the same. In this case the subgraphs corresponding to the equivalence classes are not necessarily smooth, but the above argument can be repeated on them. If this procedure comes to an end then the diffusion on the components is well understood.

4.2.2 Finitely ramified fractals

These are the most studied cases in the physical and mathematical literature (c.f. Bibliography of [B]) and in the typical cases the smoothness can be easily checked contrary to the infinitely ramified cases (c.f. Introduction of [XYZ]). The general method could be similar to the S_{N}−approximation but instead of the geometric balls one have to consider the naturally given finite cutsets C_{k} − s and try to repeat the technique developed for the S_{N}-approximation. If a graph is finitely ramified then it has finitely many connected components after a removal of a finite set. It means that the graph end is finite as well but does not necessarily coincide with the Martin boundary. As the literature shows, in most of the cases the high symmetry of the structures ensures this and the smoothness of this subgraphs or the above sketched method works on the finitely many components of the fractal, but no general method is known.

4.3 Recurrent graphs

4.3.1 Nonsmooth graphs

It was demonstrated in the transient case that there are nonsmooth transient graphs on which the Einstein relation or its stronger version given in Proposition 1 does not hold. If the graph is not smooth but can be decomposed into finitely many smooth subgraphs then the diffusion can be studied piece by piece on the subgraphs since the transient RW sooner or later choose one of them and will spend its whole life in it. This is the reason why the Einstein relation fails in general. Recurrent RWs visit all the subgraphs infinitely many times again, and hence such a choice forever do not exist. In this case, the Einstein relation and its stronger form still true.

Proposition 5 If the recurrent graph G = (V, E) can be decomposed into finitely many subgraphs on V = ∪_{i=1}^{k}V_{i} and (C_{0} − C_{3}) hold for the subgraphs G_{i} on V_{i} then

E(T_{N}) ≈ R_{N}b_{N}.

Proof of Proposition 3 As it is well known

E(T_{N}) ≤ R_{N}b_{N}

and from the cutting method it is clear that

R_{N} ≤ R_{N}^{(i)},

where from now on the notation (i) A^{(i)} refers to the quantity or object of the i-th subgraph on V_{i}. But if a large enough finite set is removed from V, the subgraphs will be cut to unconnected components, which gives that their subnetworks are parallely connected. More formally, if C is the removed finite set, there is a finite l > 1 such that C ⊂ B_{l}

R_{N} ≥ R(S_{l},_{N} ) = (∑_{i=1}^{k} R^{−1}(S_{l−1}^{(i)}, S_{l}^{(i)})) ≈ R^{(1)}(S_{l}^{(1)}, S_{N}^{(1)})

if

d_{Ω}^{(1)} > d_{Ω}^{(i)}

for all i = 1, ...k .It means that the largest resistance dimension, i.e., the smallest resistance determine the whole resistance behavior, as expected .

It is interesting to observe that the RW will reach S_{N} in the subgraph on V_{1} since

P_{0}(X_{T_{N}} ∈ ∪_{i=2}^{k}V_{i}) ∼ \frac{R_{N}^{(2)}}{R_{N}^{(1)} + R_{N}^{(2)}} → 0,

while

P_{0}(X_{T_{N}} ∈ V_{1}) ∼ \frac{R_{N}^{(1)}}{R_{N}^{(1)} + R_{N}^{(2)}} → 1

if for sake of simplicity d_{Ω}^{(2)} ≥ d_{Ω}^{(i)} for i = 3, ...k.

The second statement is proven if

E(T_{N}) ≥ R_{N}^{(1)}b_{N}

is shown. The question arises why b_{N} and not b_{N}^{(1)} is in the upper and lower estimate. It follows from the fact that though the RW finally reaches S_{N} in V_{1} but spends almost the same amount of time in the other B_{N}\B_{N}^{(1)} part till T_{N}. The rest of the proof is based on the observation that the potential v_{N} typically smaller in V_{1} than in the other parts. The more precise technical and formal argument uses all the constants appearing in the condition of the Proposition 1. Choose integer s so that

C^{(i)}(Q^{(1)})^{−(2−d_{Ω}^{(i)})s} =: Ĉ^{(i)} < c^{(i)}.

E(T_{N}) ≥ ∑_{x∈B_{k−l−1}} v(x)

As usual, the smoothness is used as follows on each subgraphs. If x ∈ B_{k−l−1}^{(i)}

v(x) ≥ R(S_{k−l−1}, S_{k}) = R(0, S_{k}) − R(0, Γ_{k−l−1}^{(k)})

≥ R(0, S_{k})−R(0, S_{k−l}) ≥ c^{(i)}N_{k}^{2−d_{Ω}^{(i)}}−C^{(i)}N_{k}^{2−d_{Ω}^{(i)}} ≥ (c^{(i)}−ĉ^{(i)})N_{k}^{2−d_{Ω}^{(i)}} ≥ cN_{k}^{2−d_{Ω}^{(1)}}

if k is large enough. Putting the estimates together, the statement follows. The Einstein relation (1) comes along the same line of the proof if only smoothness is assumed on the subgraphs, the details are omitted. □

4.3.2 A conjecture on recurrent boundary theory

To complete the picture of RW on recurrent graphs the better understanding of the connection of the Martin entrance boundary to the graph end needed. A kernel for the RW on G can be defined as

g(x, y) = lim_{N→∞} ∑_{k} \frac{deg(y)}{deg(x)}Q_{N}^{k}(x, x) − Q_{N}^{k}(x, y)  (16)

as it was introduced in the introduction. It is easy to show that

g(x, y) = lim_{N→∞} R(x, Γ_{y}^{(N)})  (17)

.

G graph can be called normal if (16) has sense. This definition seems to be in strong connection to normal Markov chain (c.f. [KSK] ). A reversible Markov chain is normal if

G_{x,y} = lim_{N→∞} ∑_{k} \frac{deg(y)}{deg(x)}P_{k}(x, x) − P_{k}(x, y)  (18)

exists. It is known that this kernel exists for all x ∈ V, if exists for a given vertex say 0 ∈ V (c.f. Theorem 9-26. [KSK] ) In the light of this result it is plausible to assume that the following conjectures are valid.

1. g(x, y) = G_{x,y} if both exist.

2. The RW (as a Markov chain) is normal if and only if G is normal. Consequently if the graph is normal with respect to a reference point 0 ∈ V it is normal with respect to all vertices similarly to normal Markov chains.

Our final remark comments Theorem 4. Consider the potential surfaces of the normal graph as defined in the transient case Γ_{x} = lim_{N} Γ_{x}^{(N)} = {y ∈ V : g(0, y) = g(0, x)} exist for normal graphs by definition. In the extended electric network model it is possible to define alternating sequence of potential surfaces and geometric surfaces:

S_{0} < Γ_{1} < S_{1} < Γ_{2} < ...

It is easy to show that the uniform divergence condition holds if and only if the corresponding sequence N_{k} is not super exponential (in analogy to condition C_{ω}).

5 Acknowledgments:

I am deeply indebted to András Schubert for his friendly encouragement and restless correction and revision of the manuscript. Thanks are due to Bálint Tóth, Nándor Simányi and Gábor J. Székely for the inspiring questions and discussions.

References

[B] Barlow, M.T. Random Walks and Diffusion on Fractals, Proc. Int. Congress Math. Kyoto, 1990

[BB] Barlow, M.T., Bass, F.R., The Construction of the Brownian Motion on the Sierpisnki Carpet, Ann. Inst. H. Poincare, 25, (1989) 225-257

[BP] Barlow, M.T., Perkins, E.A. Brownian Motion on the Sierpinski Gasket, Prob. Th. Rel. Fields, 79, (1988) 543-623

[BIPY] Benjamini, I., Peres, Y., Tree Indexed Random Walks on Groups and First Passage Percolation, preprint [CSW] Cartwright, D.I. Soardi, P.M., Woess, W. Martin and end compact-

ification for non locally finite graphs, Trans. Amer. Math. Soc. (in print)

[Ha] Hambly, B.M., Brownian motion on a homogeneous random fractal, Prob. Th. Rel. Fields,

[H] Harris, T.E. (1963), The Theory of Branching Processes, Springer-Verlag and Prentice Hall.

[K1] Kigami, J.,Harmonic calculus on Limits of Networks and its Application to Dendrites, preprint

[K2] Kigami, J., Effective Resistance for Harmonic Structures on P.C.F. Self-similar Sets, preprint

[K3] Kigami, J., Harmonic Calculus on P.C.F. Self-similar Sets, preprint

[KSK] Kemeny, J.G., Snell, J.L., Knapp, A.W., Denumerable Markov Chains, Springer, 1976

[R] Révész, P., Random Walks in Random and Non-random Environments, World Scientific Press, Singapure, 1990

[RT] Rammal, R. Toulouse G.., Random walks on fractal structures and percolation clusters, J. Physique Letters, 44, (1983), L13-L22

[S] Schinazi, R., On multiple phase transition for Branching Markov chains, preprint

[T1] Telcs, A., Random Walks on Graphs, Electric Networks and Fractals, Prob. Th. and Rel. Fields (1089), 82,435-449

[T2] Telcs, A., Spectra of Graphs and Fractal Dimensions I., Prob. Th. and Rel. Fields, (1990), 85 489-497

[T3] Telcs, A., A note on Recurrent Random Walks on Graphs, J. Stat. Phys. (1990), 60, 801-807

[T4] Telcs, A., Spectra of Graphs and Fractal Dimensions II., J. Theor. Prob. (1995), 8, 77-96 [TW] Telcs, A., Wormald, N.C., Branching and Tree Indexed Random

Walks on Fractals, appear in J. Applied Probability dec.1999.

[W1] Woess, W., Random Walks on Infinite Graphs and Groups - a Survey on Selected Topics,Bull. London. Math. Soc. 26 (1994), 1-60

[XYZ] Zhou, X. Y., Resistance Dimension, Random Walk Dimension and Fractal Dimension, J. Theor. Prob. (1993), 4, 635-652