Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-02-11T01:31:53.513Z Has data issue: false hasContentIssue false
  • English
  • Français

FRACTAL AND RESISTANCE DIMENSIONS OF RANDOM TREES

Published online by Cambridge University Press:  22 October 2007

Mokhtar H. Konsowa  and
Reem A. Al-Jarallah
Mokhtar H. Konsowa
Affiliation:
Department of Statistics and Operations Research Faculty of Science, University of Kuwait, Safat 13060Kuwait E-mail: konsowa@kuc01.kuniv.edu.kw; reema@kuc01.kuniv.edu.kw
Reem A. Al-Jarallah
Affiliation:
Department of Statistics and Operations Research Faculty of Science, University of Kuwait, Safat 13060Kuwait E-mail: konsowa@kuc01.kuniv.edu.kw; reema@kuc01.kuniv.edu.kw
Rights & Permissions [Opens in a new window]

Abstract

In this article we determine a formula for fractal and resistance dimensions of two models of uniformly bounded random trees. The type (transient or recurrent) of the random walk on such trees is ascribed, to some extent, to these dimensions. The results presented in this article generalize some of the results of [6] and [7].

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 21 , Issue 4 , October 2007 , pp. 623 - 634
Copyright
Copyright © Cambridge University Press 2007

1. INTRODUCTION

The structure of a tree plays a considerable role in the context of probability on trees. This role is essential, for instance, in determining the type of the random walk on a tree, whether it is transient or recurrent, which is equivalent to deciding whether the effective resistance is finite or infinite (if the tree is considered as an electric network by assigning conductivities to its edges). See [Reference Doyle and Snell2], [Reference Konsowa and Mitro5], [Reference Lyons8], or [Reference Lyons and Peres9]. The growth rate, GR(Γ), of a tree Γ is defined roughly as the nth root of the size of the nth generation of the tree. As is seen from its definition, GR(Γ) barely takes into account the process of branching of Γ. As such, we cannot rely much on GR(Γ). The branching number, BR(Γ), is more reliable in describing the branching process. BR(Γ) is, roughly, the mean number of branches emerging out from a vertex of tree (outdegree). It is known that the random walk on a tree Γ is transient if BR(Γ) > 1 and could be of either type if BR(Γ) = 1 see [12]. The energy as well as the capacity of a flow are closely related to the type of the random walk. In this article we study two exponent measures of the structure of the tree: the fractal dimension and the resistance dimension. These dimensions are related to the random walk dimension via the Einstein equation RWD = FD − RD + 2, where RWD, FD, and RD stand respectively for the random walk dimension, the fractal dimension, and the resistance dimension. This relation holds true for sufficiently regular (dense and smooth) trees of polynomial growth. See [Reference Telcs13] or [Reference Zhou14]. It is shown for a spherically symmetric tree SSRT (where the degree of a vertex depends only on its distance from the root) of polynomial growth that FD = RD and, as such, RWD = 2. This entails that the mean time that the random walk on SSRT, starting at the root of Γ, takes to hit its nth level is n t n ; t n → 2.

2. BACKGROUND

To cast light on the connection between probability and electric networks, we consider a finite connected graph G with edge set E, endowed with nonnegative numbers {c xy = c yx, xy ∈ E} called conductivities, and the reciprocals {r xy = 1/c xy, xy ∈ E} are called resistances. The graph G associated with the assigned conductivities is called an electrical network and it is denoted by G*. A real-valued function v defined on the vertices of G* is called harmonic at a vertex x if

$$\sum_y {c_{xy} \over c_x} \nu \lpar y\rpar = \nu \lpar x\rpar ,$$

where c x = ∑yc xy. Two vertices a and z are respectively the source and the sink of the network G*. According to the uniqueness theorem [2], the harmonic function ν on the nodes of G* is uniquely determined by its boundary values in the sense that if two harmonic functions on G*\{a, z} have the same values on the boundary {a, z}, then they are equal. The voltage function ν is harmonic on G*\{a, z}. See [2]. For this reason, we call any harmonic function on G*\{a, z} a voltage if it has the same boundary values of the voltage function ν.

A flow θ from a to z is a function on the oriented edges that is antisymmetric, θxy = −θyx and that obeys Kirchhof's node law ∑yθxy = 0 for x ∉ {a, z}. This is the requirement “flow in equals flow out” for any vertex x ∉ {a, z}.

The voltage difference between a and z induces current that flows into the network. The current flow associated with the voltage ν is defined for oriented edges by Ohm's law:

$$i_{xy} = {\nu_{x} - \nu_y \over r_{xy}}.$$

The strength of the current flowing into the circuit at vertex a is defined by

$$i_{a} = \sum_x i_{ax}.$$

If you increase the voltage difference ν a − ν z between a and z, the current i a will increase such that the ratio (ν a − ν z)/i a remains constant. This constant is called the effective resistance of the network G* and is denoted by ℜ(a ↔ z); that is,

$$\Re \lpar a\leftrightarrow z\rpar = {\nu_{a} - \nu_z \over i_{a}}.$$

It is also shown that ℜ(a ↔ z) is the power (energy) dissipation of the unit current flow; see [Reference Doyle and Snell2] or [Reference Lyons and Peres9]:

$$\Re \lpar a\leftrightarrow z\rpar = {1 \over 2} \sum_{x,y} i_{xy}^2 r_{xy}.$$

A weighted (nearest-neighbor) random walk on G is a Markov chain X n on the vertex set of G with transition probabilities:

$$p_{xy}= p\lpar X_{n+1} = y\vert X_n = x\rpar = {c_{xy} \over c_{x}}.$$

The probabilistic interpretation of the effective resistance is described as follows: Let p(a → z) denote the escape probability of the random walk that starts at a; that is

$$p\lpar a \rightarrow z\rpar = p_a\lpar X_{n} \ \hbox{hits} \ z \ \hbox{before returning to} \ a\rpar .$$

It is shown in [Reference Doyle and Snell2] that

(1)
$$p\lpar a \rightarrow z\rpar = {1 \over c_a \Re \lpar a \leftrightarrow z\rpar }.$$

We now consider an infinite leafless tree Γ for which the degree d(y), the number of edges incident with y, of every vertex y satisfies d(y) ≥ 2. If all of the vertices of level n is shorted (soldered) in one vertex z, then Eq. (1) gives the connection between the escape probability and the effective resistance of the portion of the tree between the root and the level n. Taking the limit in Eq. (1) as n → ∞, we get

(2)
$$p\lpar a \rightarrow \infty\rpar = {1 \over c_a \Re \lpar a \leftrightarrow \infty\rpar },$$

where ℜ(a ↔ ∞) stands for the effective resistance of the whole infinite tree and p(a → ∞) is the probability that the random walk will escape its starting point a. This entails that the random walk on Γ is transient if and only if ℜ(a ↔ ∞) < ∞. This is the Nash–Williams result. See [Reference Berman and Konsowa1] or [Reference Nash-Williams11]. This criterion holds true for any infinite connected graph. Eventually, according to Thomson's principle, the random walk on a denumerable graph G is transient iff there is a unit flow on G having finite energy dissipation from some (every) vertex to ∞.

Let Γn, n ≥ 0, denote the set of vertices of level n (having distance n from the root) of Γ and let |Γn| denote its cardinality. Then |Γ0| = 1. Let B n = ∑k=0n|Γk| be the number of vertices in the first n levels. The geometric, resistance, and mean hitting time exponents are involved respectively in the following definitions of fractal, resistance, and random walk dimensions.

Consider a general infinite connected graph G with a vertex r to be identified as a reference vertex. The fractal dimension of G is defined to be

(3)
$$\hbox{FD} = \limsup_{n \rightarrow \infty} {\log B_n \over \log n},$$

where B n is the number of vertices of a ball of radius n and centered at r.

If the set of all vertices of G having distance n from r is shorted in one vertex b and R n denotes the effective resistance between r and b, then the resistance dimension of G, having effective resistance R eff, is defined as

(4)
$${\rm RD} = \left\{\matrix{2 - \limsup\limits_{n \rightarrow \infty} \displaystyle{\log R_n \over \log n}\hfill &\quad\hbox{if} \ R_{eff} = \infty \hfill\cr 2 - \limsup\limits_{n \rightarrow \infty} \displaystyle{\log\lpar R - R_n\rpar \over \log n} &\quad\hbox{if} \ R_{eff} = R \lt \infty.}\right.$$

The random walk dimension of G is defined to be

(5)
$$\hbox{RWD} = \limsup_{n \rightarrow \infty} {\log E\lpar T_n\rpar \over \log n},$$

where E(T n) is the mean time that the random walk takes to exit a ball of radius n and centered at r.

Note 1: We notice that if RD < 2, R eff = ∞ and the random walk on G is recurrent, whereas if RD > 2, R eff < ∞ and the random walk on G is transient.

It is assumed in [Reference Telcs13, Reference Zhou14] that the G is of polynomial growth and it is shown for dense graphs that FD ≥ RD and hence RWD ≥ 2. For smooth graphs, the three exponents dimensions are related by the Einstein equation: RWD = FD + 2 − RD. It can easily be shown for the binary tree (every vertex has degree 3 except the root has degree 2) that RWD = 1. This is due to the exponential growth of that tree. One important remark is that the random walk on all integer cubical lattices Z d has RWD = 2, whereas the random walk on Z d is transient if and only if d > 2.

3. AUXILIARY LEMMAS

The following three lemmas are presented in [Reference Konsowa and Oraby6].

Lemma 1

Suppose that X n, n ≥ 1, are independent random variables such that0 ≤ X n ≤ K for some constant K. Set S n = ∑j=1nX j. If E(S n)→ ∞ as n → ∞, then

$${S_n \over E\lpar S_n\rpar } \, \,1 \quad a.s.\; as\; n \, \,\infty. $$

Lemma 2

Let {b n} be a sequence of real numbers such that limnn b nexists.

  1. (i) If b n > 0, then

    $$\lim_n nb_n = \lim_n {{\displaystyle\sum\limits_{i = 1}^n} b_j \over \log n}$$

  2. (ii) If b n > −1 and b n → 0, then

    $$\lim_n nb_n = \lim_n {{\displaystyle\sum\limits_{j = 1}^n} \log\lpar 1 + b_j\rpar \over \log n}.$$

Lemma 3

Let {b n} be a positive sequence such that

$$\lim_n { \log b_n \over\log n} = L \lt \infty.$$

  1. (i) If L ≥ −1, then

    $$\lim_n {\log {\displaystyle\sum\limits_{j=1}^n} b_j \over \log n} = L + 1.$$

  2. (ii) If L < −1, then

    $$\lim_n {\log {\displaystyle\sum\limits_{j=n}^\infty} b_j \over \log n} = L + 1.$$

The following lemma is presented in [Reference Lyons8]. We now need to introduce two models of random trees. As mentioned in Section 1, a tree is called spherically symmetric if the degree of any vertex depends only on its distance from the root and this type of trees will be denoted by Γ. Let d n stand for the outdegree of any vertex of level n. This sequence is called the degree sequence of Γ. It will be assumed that d n, n ≥ 0, are independent random variables having a probability distribution that depends on n. To introduce a tree that corresponds to a branching process in random environments, let us consider a doubly-indexed family of independent random variables {d nk, n ≥ 0, k ≥ 1} such that for fixed n, they are identically distributed following the same distribution of d n. If we let d nk denote the out degree of the kth vertex of level n, the resulting tree is called branching process in random environments tree, which will be abbreviated as BPRET and will be denoted by Γ*.

Obviously for Γ, |Γn+1| = ∏j=0nd j, and for Γ*, |Γ*n+1| = ∑j=0|Γn*|d nj. It is also straightforward that E|Γn+1| = E|Γn+1*| = ∏j=0nEd j.

The following lemma is extracted from [Reference Lyons8].

Lemma 4

If the degree sequence {d nk} of Γ* is uniformly bounded, then

$${\vert {\Gamma^{\ast}_n\vert} \over E\vert\Gamma^{\ast}_n\vert} \, \,W \; a.s.{\it\comma}$$

where W > 0 a.s.

The shorting principle decides that shorting together some nodes will not increase the effective resistance of the network. Nevertheless, the effective resistance remains unchanged if nodes of the same potential are shorted. For Γ and Γ*, assign one unit resistance to each edge. Let R n and R n* denote respectively the effective resistance between the roots of Γ and Γ* and their respective nth levels, after being shorted in one vertex. The following lemma is represented in [Reference Konsowa and Mitro5] and follows from the shorting principle.

Lemma 5

For Γ, R n = ∑j=1n (1/|Γj|), whereas for Γ*, R n* ≥ ∑j=1n (1/|Γj*|).

The following result is presented in [Reference Konsowa4].

Lemma 6

For Γ and Γ*, E(R n) ≥ E(R n*). However, no stochastic domination between R nand R n* exists.

4. FRACTAL DIMENSIONS

Theorem 7

Consider a spherically symmetric tree with a degree sequence {d n} such that for n ≥ 0,

(6)
$$d_n= \left\{\matrix{1& with\;probability\;1 - q_{n2} - q_{n3}-\cdots-q_{nk} \cr 2& with\; probability\; q_{n2}\hfill\cr 3& with\; probability\; q_{n3}\hfill\cr \cdot \cr \cdot \cr\cdot \cr k& with\;probability\; q_{nk}{\it\comma}\hfill}\right.$$

where for 2 ≤ j ≤ k, 0 <q nj < 1, q nj ↓ 0, and ∑nq nj = ∞. Then, FD = 1 + limnnE log d n.

Proof

We can assume, without loss of generality, that k = 3. Hence,

$$\eqalign{E \log d_n &= \lpar \log 2\rpar q_{n2} + \lpar \log3\rpar q_{n3}\cr &= \log \lpar 2^{q_{n2}}\rpar \lpar 3^{q_{n3}}\rpar .}$$

Consequently,

$$\eqalign{E \log \vert \Gamma_n \vert &= E \sum\limits_{j=0}^{n-1} \log d_j = \sum\limits_{j=0}^{n-1} \log 2^{q_{j2}}3^{q_{j3}} \cr &= \log \prod\limits_{j=0}^{n-1} 2^{q_{j2}}3^{q_{j3}}\cr& = \log\; 2 ^{\sum\limits_{j=0}^{n-1} q_{j2}} \;3^{\sum\limits_{j=0}^{n-1} q_{j3}}}$$

It follows from Lemma 1 that

$$t_n = {\log \vert \Gamma_n\vert \over E \log \vert \Gamma_n\vert} \,\, 1\quad \hbox{a.s.}\; \hbox{as}\; n \,\, \infty,$$

from which we obtain

$$\log \vert \Gamma_n \vert = t_{n} \left( \sum_{j=0}^{n-1} q_{j2}\right) \log 2+ t_{n}\left( \sum_{j=0}^{n-1} q_{j2}\right) \log 3.$$

This implies, using Lemma 2(i), that

$$\lim_n {\log \vert \Gamma_n \vert \over \log n}= \lpar \log 2\rpar \lpar \lim_n nq_{n2}\rpar + \lpar \log 3\rpar \lpar \lim_n nq_{n3}\rpar .$$

As such, Lemma 3(i) ensures that

$$\eqalign{\hbox{FD} &= \lim_n {\log b_{n} \over \log n}\cr&= 1 + \lpar \log 2\rpar \lpar \lim_{n} nq_{n2}\rpar + \lpar \log 3\rpar \lpar \lim_{n} nq_{n3}\rpar \cr &= 1 + \lim_{n} nE \log d_{n}.}$$

■

It is shown in [Reference Konsowa and Oraby6] for SSRT that FD = RD. As such, we have the following result.

Theorem 8

For SSRT, defined by Eq. ( 6), RD = 1 + limnnE log d n.

Theorem 9

The random walk on SSRT is transient if limnnE log d n > 1 and recurrent if limnnE log d n<1 and it could be of either type if limnnE log d n = 1.

Proof

The result follows from Theorem 8 and Note 1. Two examples are presented in [Reference Konsowa3] showing that the random walk could be transient or recurrent at the critical value. ■

We now turn our attention to branching process in random environments tree.

Theorem 10

Consider a BPRET Γ* with a degree sequence {d nj} such that for all n, $d_{nj}\mathop{=} \limits^{D}d_n$; That is,

(7)
$$d_{ni}=\openup1pt \left\{\matrix{1 & with \ probability \ 1 - q_{n2} - q_{n3}-\cdots - q_{nk} \cr 2 & with \ probability \ q_{n2}\hfill\cr 3& with \ probability \ q_{n3}\hfill\cr \cdot &\cr \cdot &\cr\cdot &\cr k& with \ probability \ q_{nk}{\it\comma}\hfill}\right.$$

where k ≥ 2, i = 1, 2, … , |Γn−1*|, and 0 < q nj < 1. In addition, let q nj ↓ 0 as n → ∞, and ∑nq nj = ∞ for all j. Then FD = 1 + limnn(Ed nj − 1).

Proof

It follows from the definition of d nj that

$$E\vert \Gamma^{\ast}_n \vert = E\vert \Gamma_n \vert = \prod_{j=0}^{n-1} Ed_j = \prod_{j=0}^{n-1} \lpar 1 + q_{j2} + 2q_{j3} + \cdots + \lpar k -1\rpar q_{jk}\rpar $$

and, hence,

$$\log E \vert\Gamma^{\ast}_n \vert \!= \sum_{j=0}^{n-1} \log\lpar 1 + q_{j2} + 2q_{j3} + \cdots + \lpar k -1\rpar q_{jk}\rpar. $$

This entails, using Lemmas 4 and 2(i), that

(8)
$$\eqalignno{\lim_{n} {\log \vert\Gamma^{\ast}_n \vert \over \log_{n}} &= \lim_{n} n \lpar q_{n2} + 2q_{n3} + \cdots + \lpar k -1\rpar q_{nk}\rpar \cr &= \lim_{n} n \lpar Ed_{ni} -1\rpar.}$$

Hence, the result follows from Lemma 3(i). ■

The following lemma is in [Reference Lyons8].

Lemma 11

The random walk on Γ* is recurrent if and only if ∑n(1/E|Γn*|) = ∞.

The following lemma is straightforward.

Lemma 12

For a positive sequence {a n, n ≥ 1} of real numbers, ∑n(1/∏k=1na k) = ∞ if and only if limnn(a n − 1) ≤ 1.

As a consequence of Lemmas 11 and 12, we have the following lemma.

Lemma 13

The random walk on Γ* is recurrent if and only if limnn(Ed ni − 1) ≤ 1.

Theorem 14

Consider a tree Γ* defined by Eq. ( 7). Then RD* ≤ 1 + limnnE(d ni − 1) a.s. Moreover, if the random walk is recurrent, then E(RD*) ≥ 1 + limnn(1 − E(1/d ni)). The same last inequality holds true for transient random walk provided that

(9)
$$\lim_n n\left( 1 - E{1 \over d_{nj}}\right) \gt 1.$$

Proof

We first consider the case that the random walk on Γ* is recurrent. Then from Lemma 13,

(10)
$$\lim_n n\lpar Ed_{nj} - 1\rpar \le 1.$$

It follows from Eq. (8) and inequality (10) that

(11)
$$\lim_n {\log {\frac{1}{\vert \Gamma^{\ast}_n \vert}} \over \log n} = -\lim_n n\lpar Ed_{ni} - 1\rpar \ge -1.$$

Then by applying Lemmas 5 and 3(i) we get

$$\eqalign{\hbox{RD}^{\ast} &= 2 - \lim_n {\log R^{\ast}_n \over \log n} \le 2 -\lim_n {\log {\displaystyle\sum\limits_{j=0}^{n}} { 1\over \vert \Gamma^{\ast}_j \vert} \over \log n}\cr &= 2 - \lpar 1 - \lim_n n\lpar Ed_{ni} - 1\rpar \rpar \cr &= 1 + \lim_n n\lpar Ed_{ni} - 1\rpar \quad{\rm a.s.}}$$

On the other hand,

(12)
$$\eqalignno{E\lpar {\rm RD}^{\ast}\rpar &= 2 - E\left( \lim_n {\log R^{\ast}_n \over \log n}\right) \cr &\ge 2 -\lim_n E\left( {\log R_{n}^{\ast} \over \log n}\right) \cr &\ge 2 - \lim_n {\log E\lpar R^{\ast}_n\rpar \over \log n}\cr &\ge 2 - \lim_n {\log E\lpar R_{n}\rpar \over \log n},}$$

where the last three inequalities follow respectively from Fatou's lemma, Jensen's inequality, and Theorem 6. For SSRT,

$$E{1 \over \vert \Gamma_n\vert} = \prod_{j=0}^{n-1} \left[1 - \left( {1 \over 2} q_{j2} + {2 \over 3} q_{j3} + \cdots + \left( 1 -{1 \over k}\right) q_{jk}\right) \right].$$

It follows from Lemma 2(ii) that

(13)
$$\eqalignno{\lim_n {\log E \big({1\over\Gamma_n}\big) \over \log n} &= \lim_n {{\displaystyle\sum\limits_{j=0}^{n-1}} \log \left[1 - \left( {1 \over 2} q_{j2} + {2 \over 3} q_{j3} + \cdots + \big( 1 -{1\over k}\big)\Big) q_{jk}\right.\right] \over \log n}\cr &= -\lim_{n} n \left( {1 \over 2} q_{n2} + {2 \over 3} q_{n3} + \cdots + \left( 1 -{1 \over k}\right) q_{nk}\right) \cr &=-\lim_{n} n \left( 1- E{1 \over d_{nj}}\right).}$$

Since d nj + 1/d nj ≥ 2 a.s., then E(d nj) + E(1/d nj) ≥ 2. As such, 1 − E(1/d nj) ≤ Ed nj − 1. This implies, using inequality (10), that limnn(1 − E(1/d nj)) ≤ 1. Now, Eq. (13) entails that

$$\lim_n {\log E \left({ 1 \over \vert \Gamma_n\vert} \right) \over \log n} \ge -1.$$

From Lemma 5, R n = ∑j=1n(1/|Γj|) a.s. Thus, Lemma 3(i) and Eq. (13) assure that

$$\lim_n {\log E\lpar R_n\rpar \over \log n} = \lim_n {\log {\displaystyle\sum\limits_{j=1}^{n}} E\big( 1/\vert \Gamma_j \vert\big) \over \log n} = 1 - \lim_n n\left( 1 - E{1 \over d_{nj}}\right) .$$

This ensures that

$$\eqalign{E\lpar {\rm RD}^{\ast}\rpar &= 2 - E\left( \lim_n {\log R_{n} \over \log n}\right) \cr &\ge 2 - \lim_n {\log E\lpar R_n\rpar \over \log n}\cr &= 1 + \lim_n n\left( 1 - E{1 \over d_{nj}}\right) .}$$

This completes the proof in the case that the random walk is recurrent.

We now consider the case where the random walk is transient. Hence, limnR n* = R* < ∞ and from Lemma 13,

(14)
$$\lim_n n\lpar Ed_{nj} -1\rpar \gt 1,$$

in which case,

(15)
$$\eqalignno{\hbox{RD}^{\ast} &= 2 - \lim_n {\log\lpar R^{\ast} - R_n^{\ast}\rpar \over \log n}\cr &\le 2 - \lim_n {\log {\displaystyle\sum\limits_{j=n+1}^\infty} \left({ 1 \over \vert \Gamma_j^{\ast} \vert}\right) \over \log n}.}$$

It follows from Eq.(8) and Lemma 3(ii) that

$$\lim_n {\log {\displaystyle\sum\limits_{j=n+1}^{\infty}} \left({ 1\over \vert \Gamma_j^{\ast} \vert}\right) \over \log n} = 1 - \lim_n n\lpar Ed_{nj} - 1\rpar .$$

Hence, inequality (15) implies that

$$\hbox{RD}^{\ast} \le 1 + \lim_n n\lpar Ed_{nj} -1\rpar \quad\hbox{a.s.}$$

On the other hand,

(16)
$$\eqalignno{E\lpar \hbox{RD}^{\ast}\rpar &= 2 - E\left( \lim_n {\log\lpar R^{\ast} - R_n^{\ast}\rpar \over \log n}\right) \cr &\ge 2 -\lim_n E\left( {\log\lpar R^{\ast} - R_{n}^{\ast}\rpar \over \log n}\right) \cr &\ge 2 - \lim_n {\log E\lpar R^{\ast} - R_{n}^{\ast}\rpar \over \log n}\cr &\ge 2 - \lim_n {\log E\lpar R - R_{n}\rpar \over \log n}\cr &= 2 - \lim_n {\log {\displaystyle\sum\limits_{k=n+1}^\infty} E \left({1 \over \vert \Gamma_k \vert}\right) \over \log n}\cr & = 1 - \lim_n {\log E \left({ 1 \over \vert \Gamma_n \vert} \right) \over \log n}}$$
(17)
$$\qquad= 1 + \lim_n n \left( 1 - E{1 \over d_{nj}}\right),$$

where Eq. (16) follows from inequality (9) and Lemma 3(ii), whereas Eq. (17) follows from Eq. (13). ■

References

1.Berman, K. & Konsowa, M. (1989). Random paths and cuts, electrical networks, and reversible Markov chains. SIAM Journal of Discrete Mathematics 3(3): 311–319.CrossRefGoogle Scholar
2.Doyle, P. & Snell, L. (1984). Random walks and electric networks. The Carus Mathematical Monographs. Washington, DC: Mathematical Association of America.Google Scholar
3.Konsowa, M. (2005). Random walks and dimensions of random trees. Submitted.Google Scholar
4.Konsowa, M.H. (2003). A note on the conductivity of random trees. Probability in the Engineering and Informational Sciences 17: 571–576.Google Scholar
5.Konsowa, M.H. & Mitro, J. (1991). The type problem for random walks on trees. Journal of Theoretical Probability 4(3): 535–550.Google Scholar
6.Konsowa, M.H. & Oraby, T.F. (2003). Dimensions of random trees. Statistics and Probability Letters 62: 49–60.Google Scholar
7.Konsowa, M.H. & Oraby, T.F. (2003). Fractal dimensions and random walks on random trees. Journal of Statistical Planning and Inference 116: 333–342.CrossRefGoogle Scholar
8.Lyons, R. (1992). Random walks, capacity, and percolation on trees. Annals of Probability 20: 2043–2088.Google Scholar
9.Lyons, R. & Peres, Y. (2004). Probability on trees and networks. Cambridge: Cambridge University Press. Available from http//php.indiana.edu/~rdlyons.Google Scholar
10.Lyons, T. (1983). A simple criterion for transience of a reversible Markov chain. Annals of Probability 11: 393–402.Google Scholar
11.Nash-Williams, C.st. J.A. (1959). Random walks and electric currents in networks. Proceeding of Cambridge Philosophical Society 55: 181–194.CrossRefGoogle Scholar
12.Peres, Y. (1999). Probability on trees. Lectures Notes in Mathematics Vol. 1717. Berlin: Springer, pp. 193–280.Google Scholar
13.Telcs, A. (1989). Random walks on graphs, electric networks, and fractals. Probability Theory and Related Fields 82: 435–449.CrossRefGoogle Scholar
14.Zhou, X.Y. (1993). Resistance dimension, random walk dimension, and fractal dimension. Journal of Theoretical Probability 6(4): 635–652.Google Scholar