arXiv:1408.6821v3 [math.CO] 19 May 2016

Looking for vertex number one
Alan Frieze∗, Wesley Pegden†
Department of Mathematical Sciences,
Carnegie Mellon University,
Pittsburgh PA 15213,
U.S.A.
May 20, 2016

Abstract
Given an instance of the preferential attachment graph Gn = ([n], En ), we would like
to find vertex 1, using only ‘local’ information about the graph; that is, by exploring the
neighborhoods of small sets of vertices. Borgs et al. gave an an algorithm which runs in
time O(log4 n), which is local in the sense that at each step, it needs only to search the
neighborhood of a set of vertices of size O(log4 n). We give an algorithm to find vertex 1,
which w.h.p. runs in time O(ω log n) and which is local in the strongest sense of operating
only on neighborhoods of single vertices. Here ω = ω(n) is any function that goes to infinity
with n.

1

Introduction

The Preferential Attachment Graph Gn was first discussed by Barabási and Albert [2] and then
rigorously analysed by Bollobás, Riordan, Spencer and Tusnády [3]. It is perhaps the simplest
model of a natural process that produces a graph with a power law degree sequence.
The Preferential Attachment Graph can be viewed as a sequence of random graphs G1 , G2 , . . . , Gn
where Gt+1 is obtained from Gt as follows: Given Gt , we add vertex t + 1 and m random edges
{ei = (t + 1, ui ) : 1 ≤ i ≤ m} incident with vertex t + 1. Here the constant m is a parameter
of the model. The vertices ui are not chosen uniformly from Vt , instead they are chosen with
probabilities proportional to their degrees. This tends to generate some very high degree vertices,
∗
†

Research supported in part by NSF grant CCF1013110
Research supported in part by NSF grant DMS

1

compared with what one would expect in Erdős-Rényi models with the same edge-density. We
refer to u1 , u2 , . . . , um as the left choices of vertex t + 1. We also say that t + 1 is a right neighbor
of ui for i = 1, 2, . . . , m.
We consider the problem of searching through the preferential attachment graph looking for
vertex number 1, using only local information. This was addressed by Borgs, Brautbar, Chayes,
Khanna and Lucier [5] in the context of the Preferential Attachment Graph Gn = (Vn , En ). Here
Vn = [n] = {1, 2, . . . , n}. They present the following local algorithm that searches for vertex 1,
in a graph which may be too large to hold in memory in its entirety.
1: Initialize a list L to contain an arbitrary node u in the graph.
2: while L does not contain node 1 do
3:

Add a node of maximum degree in N(L) to L od;

4: return L
Here for vertex set L, we let N(L) = {w ∈
/ L : ∃v ∈ L s.t. {v, w} ∈ En }.
They show that w.h.p. the algorithm succeeds in reaching vertex 1 in O(log4 n) steps. (We
assume that an algorithm can recognize vertex 1 when it is reached.) In [5], they also show how
a local algorithm to find vertex 1 can be used to give local algorithms for some other problems.
We also note that Brautbar and Kearns [6] considered local algorithms in a more general context.
There the algorithm is allowed to jump to random vertices as well as crawl around the graph in
the search for vertices of high degree and high clustering coefficient.
We should note that, as the maximum degree in Gn is n1/2−o(1) w.h.p., one cannot hope to have a
polylog(n) time algorithm if we have to check the degrees of the neighbors as we progress. Thus
the algorithm above operates on the assumption that we can find the highest-degree neighbor of
a vertex in O(1) time. This would be the case, for example, if the neighborhood of a vertex is
stored as a linked-list which is sorted by degrees. In the same situation, we can also determine the
K highest degree neighbors of a vertex in constant time for any constant K, and in the present
manuscript we assume such a constant-time step is possible. In particular, in this setting, each
of steps 2-7 of the following Degree Climbing Algorithm takes constant time.
We let dn (v) denote the degree of vertex v ∈ Vn .
Algorithm DCA:
The algorithm generates a sequence of vertices v1 , v2 , . . . , until vertex 1 is reached.
Step 1 Carry out a random walk on G until it is mixed; i.e., until the variation distance between
the current vertex and the steady state is o(1). We let v1 be the terminal vertex of the
walk. (See Remark 1.1 for comments on this step.)
Step 2 t ← 1.
2

Step 3 repeat
Step 4


Let Ct = w1 , w2, . . . , wm/2 be the m/2 neighbors of vt of largest degree.
(In the case of ties for the m/2th largest degree, vertices will be placed randomly in Ct in
order to make |Ct | = m/2. Also m is large here and we could replace m/2 by ⌊m/2⌋ if m
is odd without affecting the analysis by very much.)

Step 5

Choose vt+1 randomly from Ct .

Step 6

t ← t + 1.

Step 7 until dn (vt ) ≥
arbitrary.

n1/2
log1/100 n

(SUCCESS) or t > 2ω log4/3 n (FAILURE), where ω → ∞ is

Step 8 Assuming Success, starting from vT , where T is the value of t at this point, do a random
1/2
walk on the vertices of degree at least logn1/20 n until vertex 1 is reached.
Remark 1.1. It is known that w.h.p. the mixing time of a random walk on Gn is O(log n), see
Mihail, Papadimitriou and Saberi [11]. So we can assume that the distribution of v1 is close to
n (v)
the steady state πv = d2mn
.
Note that Algorithm DCA is a local algorithm in a strong sense: the algorithm only requires
access to the current vertex and its neighborhood. (Unlike the algorithm from [5], it does not
need access to the neighborhood of the entire set Pt = {v1 , . . . vt } of vertices visited so far.) Our
main result is the following:
Theorem 1.2. If m is sufficiently large then then w.h.p. Algorithm DCA finds vertex 1 in Gn
in O(ω log n) time.
DCA is thus currently the fastest as well as the “most local” algorithm to find vertex 1. We
conjecture that the factor ω in the running time is unnecessary.
Conjecture 1.3. Algorithm finds vertex 1 in Gn in O(log n) time, w.h.p.
We note that w.h.p. the diameter of Gn is ∼
execution time much below O(log n).

log n
log log n

and so we cannot expect to improve the

The bulk of our proof consists of showing that the execution of Steps 2–7 requires only time
O(ω log n) w.h.p. for any ω = ω(n) → ∞. This analysis requires a careful accounting of conditional probabilities. This is facilitated by the conditional model of the preferential attachment
graph due to Bollobás and Riordan [4]. One contribution of our paper is to recast their model in
terms of sums of independent copies of the rate one exponential random variables; this will be
essential to our analysis.

3

Outline of the paper
In Section 2 we reformulate the construction of Bollobás and Riordan [4] in terms of sums of
independent copies of the exponential random variable of rate one.
Section 3 is the heart of the paper. The aim is to show that if vt is not too small, then the ratio
vt+1 /vt is bounded above by 3/4 in expectation. We deduce from this that w.h.p. the main loop,
Steps 2–7, only takes O(ω log n) rounds. The idea is to determine a degree bound ∆ such that
many of vt ’s left neighbors have degree at least ∆, while only few of vt ’s right neighbors have
degree at least ∆. In this way, vt+1 is likely to be significantly smaller than vt .
Once we find a vertex vT of high enough degree, then we know that w.h.p. vT is not very large
and lies in a small connected subgraph of vertices of high degree that contains vertex one. Then a
simple argument based on the worst-case covertime of a graph suffices to show that only o(log n)
more steps are required.
Our proofs will use various parameters. For convenience, we collect here in table form a dictionary
of some notations, giving a brief (and imprecise) description of the role each plays in our proof,
for later reference.

ω :=
λ0 :=

Definition

Role in proof

O(log log n)

An arbitrarily chosen slowly growing fucntion.

1
log

40/m

n

A (usually valid) lower bound on random variables ηi (cf. Section 2.1).

n1 :=

log1/100 n

W.h.p. the main loop never visits v ≤ n1 .

Pt :=

{v1 , . . . vt }

The set of vertices visited up to time t.

Ψ:=

(log log n)10

Vertices v > Ψvt will not be important in the search for vt+1 .

L:=

m1/5

A large constant, significantly smaller than m.

Notation: We write An ∼ Bn if An = (1 + o(1))Bn as n → ∞. We write α . β in place of
α ≤ o(1) + (1 + o(1))β.

4

2
2.1

Preliminaries
A different model of the preferential attachement graph

Bollobás and Riordan [4] gave an ingenious construction equivalent to the preferential attachment
graph model. We choose x1 , x2 , . . . , x2mn independently and uniformly from [0, 1]. We then let
{ℓi , ri } = {x2i−1 , x2i } where ℓi < ri for i = 1, 2, . . . , mn. We then sort the ri in increasing order
R1 < R2 < · · · < Rmn and let R0 = 0. We then let
Wj = Rmj and wj = Wj − Wj−1 and Ij = (Wj−1 , Wj ]
for j = 1, 2, . . . , n. Given this we can define Gn as follows: It has vertex set Vn = [n] and an
edge {x, y} , x ≤ y for each pair ℓi , ri , where ℓi ∈ Ix and ri ∈ Iy .
We recast the construction of Bollobás and Riordan as follows: we can generate the sequence
R1 , R2 , . . . , Rmn by letting
1/2

Υi
Ri =
,
(1)
Υmn+1
where Υ0 = 0 and

ΥN = ξ1 + ξ2 + · · · + ξN for N ≥ 1
and where ξ1 , ξ2, . . . , ξmn+1 are independent exponential rate one random variables i.e. Pr(ξi ≥
2
are independent and uniform in [0, 1] (as they
x) = e−x for all i. This is because r12 , r22 , . . . , rmn
are each chosen as the maximum of two uniform points) and the order statistics of N independent
uniform [0, 1] random variables can be expressed as the ratios Υi /ΥN +1 for 1 ≤ i ≤ N.
We refer to the distribution of ΥN as ERL(N), as it is known in the literature as the Erlang
distribution.

2.2

Important properties

The advantage of our modification of the variant of the Bollobàs and Riordan construction is
that if we define
ηi := ξ(i−1)m+1 + ξ(i−1)m+2 + · · · + ξim ,
then ηi is closely related to the size of Ii . It can then be used to estimate the degree of vertex i.
This will simplify the analysis since ηi is simply a sum of exponentials.
In this section, we make this claim (along with other more obscure asymptotic properties of this
model) precise. In particular, we let E denote the event that the following properties hold for
Gn . In the appendix, we prove that Gn has all these properties w.h.p.

5

(P1) For Υk,ℓ = Υk − Υℓ , we have
Υk,ℓ

"

1/2

Lθk,ℓ
∈ (k − ℓ) 1 ±
3(k − ℓ)1/2

#

for (k, ℓ) = (mn + 1, 0) or


l=0
1
k−ℓ
2
∈ {ω, ω + 1, . . . , n} and k − l ≥ log n
k ≥ log30 n, l > 0

m
 1/300
log
n 0 < l < k < log30 n.

Here, where n0 =

λ20 n
,
ω log2 n

λ0 =

θk,ℓ

1
,
log20/m n



log k



1/2


k
= (k − ℓ)1/2


(k−ℓ)3/2 log n



n1/2


n
ω 3/2 log2 n

Similarly define

θk =


1/2

k3/2
k

log n
1/2
n


n
ω 3/2 log2 n

ω ≤ l < k ≤ log30 n,
ω ≤ k ≤ n2/5 , l = 0,
log30 n < k ≤ n2/5 ,
n2/5 < k ≤ n0 ,
n0 < k.
k ≤ n2/5 ,
n2/5 < k ≤ n0 ,
n0 < k.

#  
 1/2 "
1/2
1/2
Lθi
i
i
1 ± 1/2 ∼
for ω ≤ i ≤ n.
(P2) Wi ∈
n
i
n
"
#
1/2
ηi
2Lθi
ηi
(P3) wi ∈
1 ± 1/2 1/2 ∼
for ω ≤ i ≤ n.
1/2
2m(in)
m i
2m(in)1/2
(P4) λ0 ≤ ηi ≤ 40m log log n for i ∈ [log30 n].
(P5) ηi ≤ log n for i ∈ [n].
Some properties give asymptotics for intermediate quantities in the Bollobas/Riordan model
(e.g., (P2), (P3)), while the rest give worst-case bounds on parameters in various ranges for
i. The very technical (P1) is just giving constraints on the gaps between the points Υk in the
Bollobas/Riordan model.

2.3

Inequalities

We will use the following inequalities from Hoeffding [9] at several points in the paper. Let
Z = Z1 + Z2 + . . . + ZN be the sum of independent [0, 1] random variables and suppose that
6

µ = E(Z). Then if α > 1 we have
n 2 o
 (

exp − α3µ , α ≤ 1.
α2 µ
≤
Pr(Z ≥ (1 + α)µ) ≤ exp −

2 + α/3
exp − αµ
, α > 1.
3
 βµ
e
Pr(Z ≥ βµ) ≤ e−µ
, β>1
β
 2 
α µ
, 0 ≤ α ≤ 1.
Pr(Z ≤ (1 − α)µ) ≤ exp −
2

(2)
(3)
(4)

Our main use for these inequalities is to get a bound on vertex degrees, see Section 2.4.
In addition to these concentration inequalities, we use various inequalities bounding the tails of
the random variable η. We note that the probability density φ(x) of the sum η of m independent
exponential rate one random variables is given by
φ(x) :=

xm−1 e−x
.
(m − 1)!

That is,
Pr(a ≤ η ≤ b) =

Z

b

φ(y)dy.

(5)

a

The equation (5) is a standard result, which can be verified by induction on m (for example, see
exercise 4.14.10 of Grimmett and Stirzaker [8]). Although we will frequently need to bound the
probability (5), this integral cannot be evaluated exactly in general, and thus we will often use
simple bounds on φ(η). We summarise what we need in the following lemma:
Lemma 2.1.
(a)
Pr(η ≤ xm) ≤ m(xe1−x )m

for x ≤ 1 −

1
.
m

(6)

(b)
Pr(η ≤ x) ≤ (1 − e−x )m ≤ xm .
(c)
Pr(η ≥ βm) ≤



eβ
eβ

m

≤ e−3m/10 for β ≥ 2.

(d)
2 m/3

Pr(η ≥ (1 + α)m) ≤ e−α

for 0 < α < 1.

(e)
2 m/2

Pr(η ≤ (1 − α)m) ≤ e−α

7

for 0 < α < 1.

(7)

Proof. (a) φ(η) is maximized at η = m − 1. Taking φ(mx) (x ≤ 1 − 1/m) as an upper bound on
φ(y) for y ∈ [0, mx] and m! ≥ (m/e)m in (5) gives us (6).
Q
(b) Writing η = ξ1 + ξ2 + · · · + ξm we have Pr(η ≤ x) ≤ m
i=1 Pr(ξi ≤ x).
(c) If η = ξ1 + ξ2 + · · · + ξN , then with λ = (β − 1)/β,

Pr(η ≥ βm) = Pr(eλη ≥ eλβm ) ≤ e−λβm E(eλη ) = e−λβm

m
Y

E(eλξi ) =

i=1
−λβm

e

(1 − λ)−m = (βe−(β−1) )m . (8)

(d) Putting β = 1 + α into (8) we see that
2 m/3

Pr(η ≥ (1 + α)m) ≤ ((1 + α)e−α )m ≤ e−α

.

(e) With λ = α/(1 − α) we now have
Pr(η ≤ (1 − α)m) = Pr(e−λη ≥ e−λ(1−α)m ) ≤ eλ(1−α)m E(e−λη ) = eλ(1−α)m

m
Y

E(e−λξi ) =

i=1

λ(1−α)m

e

2.4

(1 + λ)

−m

2 m/2

= ((1 − α)eα )m ≤ e−α

.

Properties of the degree sequence

We will use the following properties of the degree sequence throughout: let
!
 1/2
 n 1/2
i
5L log log n
ζ(i) =
1−
− 3/4
i
n
ω log n
!
 1/2
 n 1/2
i
5L log log n
+
.
1−
+ 3/4
ζ (i) =
i
n
ω log n

(9)
(10)

Note that
+

ζ(i) ∼ ζ (i)
ζ(i) ∼

 n 1/2
i



2 log log n
.
if i ≤ n 1 −
log n
if i = o(n).

Also, let d¯n (i) denote the expected value of dn (i) in Gn .
Lemma 2.2.
8

(11)
(12)

(a) If E occurs then d¯n − m ∈ [ηi ζ(i), ηi ζ + (i)].
2 η ζ(i)/2
i

(b) Pr(dn (i) − m ≤ (1 − α)ηi ζ(i)) ≤ e−α

for 0 ≤ α ≤ 1.

2 η ζ + (i)/3
i

(c) Pr(dn (i) − m ≥ (1 + α)ηi ζ + (i)) ≤ e−α
(d) Pr(dn (i) − m ≥ βηi ζ + (i)) ≤ (e/β)βηi ζ

+ (i)

for 0 ≤ α ≤ 1.

for β ≥ 2.

(e) W.h.p. ηi ≥ λ0 and ω ≤ i ≤ n1/2 implies that dn (i) ∼ ηi
(f ) W.h.p. ω ≤ i ≤ log30 n implies that dn (i) ∼ ηi


n 1/2
.
i

(g) W.h.p. ω ≤ i ≤ n1/2 implies dn (i) . max {1, ηi }
(h) W.h.p. n1/2 ≤ i ≤ n implies dn (i) ≤ n1/3 .
(i) W.h.p. 1 ≤ i ≤ log1/49 n implies that dn (i) ≥
(j) W.h.p. dn (i) ≥

n
log1/20 n


n 1/2
i


n 1/2
.
i

.

n1/2
.
log1/20 n

implies i ≤ log1/9 n.

Proof. We defer the proof, which is straightforward but tedious, to the appendix.
Remark 2.3. We will for the rest of the paper condition on the occurrence of E. All probabilities include this conditioning. We will omit the conditioning in the text in order to simplify
expressions.

3

Analysis of the main loop

Since the variation distance after Step 1 is o(1), it suffices to prove Theorem 1.2 under the
assumption that we begin Step 2, with v1 chosen randomly, exactly according to the stationary
distribution.
The main loop consists of Steps 2–7. Let v0 = 1 and v1 , v2 , . . . , vs for s ≥ 1 be the sequence of
vertices followed by the algorithm up to time s. Let ρt = vt+1 /vt , and define T1 , T2 by


T1 = min t : vt ≤ log30 n and T2 = T1 + 30ω log4/3 log n and T0 = min 2ω log4/3 n, T2 . (13)

We will prove, see Lemma 3.2, that

E(ρt ) ≤

3
for 1 ≤ t ≤ T0 .
4

(14)

Recalling that T is the time when Step 8 begins, we note that if T < t ≤ T0 then this statement
is meaningless. So, we will keep to the following notational convention: if Xt is some quantity
that depends on t ≤ T and t > T then Xt = XT .
9

Now, roughly speaking, if r = 2 log4/3 n and µ is the number of steps in the main loop, then we
would hope to have


1
1
Pr(µ ≥ r) ≤ Pr ρ0 ρ1 · · · ρr ≥
≤ n E(ρ0 ρ1 · · · ρr ) ≤
n
n
and so w.h.p. the algorithm will complete the main loop within 2 log4/3 n steps. Unfortunately,
we cannot justify Q
the last inequality, seeing as the ρt are not independent. I.e. we cannot replace
E(ρ0 ρ1 · · · ρr ) by ri=0 E(ρi ). We proceed instead as in the next lemma.
Lemma 3.1. Assuming (14) we have the w.h.p. DCA completes the main loop in at most T0
steps with SUCCESS.

Proof. We let s0 denote the number of vertices visited by the main loop, and then define Zs =
ρ0 ρ1 · · · ρs for s ≤ s0 , and Zs = ρ0 ρ1 · · · ρs0 ( 43 )s−s0 for s > s0 .
Suppose first that T1 > ω log4/3 n. Now (14) and Jensen’s inequality implies that for s ≥ 1,
min(s,s0 )

E(log(Zs )) =

X

E(log(ρi )) +

i=0

s
X

log 43

min(s,s0 )+1

≤

min(s,s0 )

X

log E(ρi ) +

i=0

s
X

log 43 ≤ s log(3/4). (15)

min(s,s0 )+1

Now
log(Zs ) ≥ (s − s0 ) log(3/4) − log n ≥ s log(3/4) − log n

(16)

since ρ1 ρ2 . . . ρs0 ≥ 1/n.
Now let
α = Pr(log(Zs ) ≤ (1 − β)s log(3/4))
where α, β are to be determined. Then, (15), (16) imply that
(1 − α)(1 − β)s log(3/4) + α(s log(3/4) − log n) ≤ E(log(Zs )) ≤ s log(3/4).

(17)

Equation (17) then implies that
α≥

βs log(4/3)
.
βs log(4/3) + log n

Now putting s = ω log4/3 n and β = 1/2 we see that (18) becomes
α ≥1−

2
= 1 − o(1).
ω+2

So w.h.p. after at most ω log4/3 n steps, we will have exited the main loop with SUCCESS.
10

(18)

Suppose now that T1 ≤ ω log4/3 n. Using the argument that gave us (18) we obtain
T − T1 ≤ ω log4/3 log30 n w.h.p.

To prove Lemma 3.2, we will use a method of deferred decisions, exposing various parameters of Gn as we proceed. At time t, we will consider all random variables in the model from
Section 2.1 as being exposed if they have affected the algorithm’s trajectory thus far, and condition on their particular evaluation. To reduce the conditioning necessary, we will actually
analyze a modified algorithm, NARROW-DCA(τ ), and then later show that the trajectory of
NARROW-DCA(τ ) is the same as that of the DCA algorithm, w.h.p., when identical sources
of randomness are used.
NARROW-DCA(τ ) is the same as the DCA algorithm, except that for the first τ rounds of
the algorithm, a modified version of Step 4 is used:
Modified Step 4 Let

Ct = w1 , w2 , . . . , wm/2
be the m/2 neighbors of vt of largest degree from {1, . . . , Ψvt } where Ψ := (log log n)10 .

For rounds τ + 1, τ + 2, . . . , the behavior of NARROW-DCA(τ ) is the same as for DCA.
Notice that NARROW-DCA “cheats” by using the indices of the vertices, which we do not
actually expect to be able to use. Nevertheless, we will see later that w.h.p., for τ = 2ω log4/3 n,
the path of this algorithm is the same as for the DCA algorithm, justifying its role in our analysis.

3.1

Analyzing one step

Our analysis of one step of the main loop consists of the following lemma:
Lemma 3.2. Let ρt be the ratio of vt+1 /vt which appears in a run of the algorithm NARROWDCA(t). Then for all t ≤ T0 (see (13)), we have that
E(ρt ) ≤

3
4

and

Pr (ρt ≥ Ψ) ≤

1
.
log2 n

(19)

The first statement ensures that NARROW-DCA(t) makes progress in expectation in the tth
jump. The second part of this statement implies by induction that for any t ≤ ω log n, the
behavior of NARROW-DCA(t) is identical to the behavior of the DCA algorithm for the first
t steps. Thus together these statements give (14).
To prove Lemma 3.2, we will prove a stronger statement which is conditioned on the history of
the algorithm at time t. The history Ht of the process at the end of step t consists of
11

(H1) The sequence v1 , v2 , . . . , vt .
(H2) The left-choices λ(vs , 1), λ(vs , 2), . . . , λ(vs , m), 1 ≤ s < t and the corresponding left neighbors NL (vs ) = {u1,s , u2,s , . . . , um,s }. These are the m ℓ′i s that correspond to the m ri ’s
associated with vs as defined at the beginning of Section 2.1.
(H3) The lists u′1,s , u′2,s , . . . , u′r,s of all vertices u′k,s which have the property that (i) vs ∈ NL (u′k,s)
and (ii) u′k,s ≤ Ψvs for 1 ≤ s < t. (It is important to notice that s < t here.)
(H4) The values ηvi and the intervals Ivi for i = 1, 2, . . . , t.
(H5) The values ηw and the intervals Iw and the degrees deg(w), for w ∈
Here,

St

i=1

N(vi ).

N(v) = NL (v) ∪ NR (v) where NR (v) = {w ≤ Ψv : v ∈ NL (w)} .
We note that at any step t, and for a fixed random sequence used in the NARROW-DCA(t)
algorithm, Ht contains all random variables which have determined the behavior of the algorithm
so far, in the sense that if we modify any random variables from the random graph model
described in Section 2.1 while preserving all values in the history, then the trajectory of the
algorithm will not change. We write Ht to refer to a particular evaluation of the history (so that
we will be conditioning on events of the form Ht = Ht ).
Structure of the proof
The essential structure of our proof of Lemma 3.2 is as follows:
Part 1 We will define the notion of a typical history Ht .
Part 2 We will prove that for t ≤ T0 and any typical history Ht , random variables ηv which are
not explicitly exposed in Ht are essentially unconditioned by the event Ht = Ht (Lemma
3.3).
Part 3 We will prove by induction that Ht is typical w.h.p., for t ≤ T0 .
Part 4 We will use Part 2 and Part 3 to prove that for t ≤ T0 ,
E(ρt | Ht ) ≤

L3
2 21ηvt
+
+ 2
3
mL
m

and

Pr (ρt ≥ Ψ | Ht ) ≤

1
log2 n

(20)

by using using nearly unconditioned distributions of random variables which are not revealed in Ht to estimate the probabilities of various events. Here E(ρt | Ht ) is short for
E(ρt | Ht = Ht ). (Note that ηvt in (20) is simply a real number determined by Ht .) In this
context, we always work under the assumption that Ht is typical.
12

Part 5 We will also prove for t ≤ T0 that
E(ηvt+1 ) ≤ 4m.

(21)

Now the expected value statement in (19) follows from (21) and the first part of (20), by removing
the conditioning on Ht .

Part 1
Let Pt denote the sequence of vertices v1 , v2 , . . . , vt determined by the history Ht . We now
define the notion of a typical history Ht . For this purpose, we consider the reordered values
(t)
(t)
(t)
0 ≤ λ1 < λ2 < · · · < λN (t) where
n
o
(t)
(t)
(t)
(t)
Λ0 = λ1 , λ2 , . . . , λN (t) = {λ(vs , i) : 1 ≤ s ≤ t, 1 ≤ i ≤ m} .
(t)

(t)

Given this we define v = vj to be the index such that λj ∈ Iv and then let
n
o
(t)
(t)
VL = vj : 1 ≤ j ≤ N(t) .
We also define

(t)

VR = {v : v ∈ NR (Pt )}
Now let us reorder

n
o
(t)
(t)
(t)
(t)
(t)
V (t) = x1 < x2 < · · · < xM (t) = VL ∪ VR .
(t)

(t)

We define the extreme points x0 = 0 and xM (t)+1 = n + 1 and define
M (t)+1
(t)
Xj

=

(t)
[xj−1

+

(t)
1, xj

− 1] and X

(t)

=

(t)

[

Xj = [n] \ V (t)

(t)

(t)

and Nj = |Xj |,

j=1
(t)

Uj = [Wx(t)

j−1 +1

, Wx(t) −1 ] and U (t) =
j

N
[

(t)

Uj

(t)

(t)

and Lj = |Uj |.

j=1

A typical history Ht , t ≤ T0 is now one with the following properties:
(S1) There do not exist s1 , s2 ≤ t such that either (i) s1 ≤ t − 2 and vs1 and vs2 are neighbors
or (ii) s1 ≤ t − 3 and there exists a vertex w such that w ∈ N(vs1 ) ∩ N(vs2 ). (We say that
the path is self-avoiding.)
(S2) The points of Λ(t) are well-separated, in the following sense:
(
(t)
log2 n
xj−1 ≥ log30 n.
(t)
(t)
|xj − xj−1 | ≥
log1/400 n Otherwise.
13

(22)

We observe that
(T1) If Ht is typical then vj+1 is chosen from X (j) for all j < t.
(t)

(t)

(T2) Each Uj is the union of intervals Iv , v ∈ Xj .

Part 2
We prove the following:
Lemma 3.3. For any vertex v ∈ X (t) , any interval R ⊆ R, and any typical history Ht , we have
that v ∈
/ Pt ∪ N(Pt ) implies
Pr (ηv ∈ R | Ht ) ∼ Pr (ERL(m) ∈ R) .

(23)

The following lemma is the starting point for the proof of Lemma 3.3.
(t)

Lemma 3.4. Let j ∈ [M(t)+1], let Ht be any typical history, and let X ′ be the value of Xj in Ht .
Then the distribution of the random variables ηv , v ∈ X ′ conditioned on Ht = Ht is equivalent
to
of the random variables ηv , v ∈ X ′ conditioned only on the relationship
P the distribution
2
2
v∈X ′ ηv = A1 − A0 , where A1 , A0 are the values of Wx(t) −1 and Wx(t) +1 , respectively, in Ht .
j

j−1

Proof. Suppose we fix everything except for ηv , v ∈ X ′ . By everything we mean every other ηw
and all of the λ(v, i) and the random bits we use to make our choices in Step 5 of DCA; we
′
′
′
let Ht be the corresponding
Phistory. Suppose now that we replace ηv , v ∈ X with ηv , v ∈ X
without changing the sum v∈X ′ ηv . Then Wx(t) +1 remains the same, as it depends only on ηv
j−1

for v ∈
/ X ′ , and thus Wx(t) −1 remains the same as well, since the difference A21 − A20 is unchanged.
j

In particular, this implies that Ht remains a valid history. We confirm this by induction. Suppose
that Hs , s < t remains valid. We first note that because the λ(vs , i) are unchanged, none of vs′ s
(t)
left neighbors are in Xj . Also, NR (vs ) and the vertex degrees for w ∈ NR (vs ) will not be affected
(t)
by the change, even if vs < min Xj . So Hs+1 will be unchanged, completing the induction.
We are now ready to prove Lemma 3.3.
(t)

(t)

Proof of Lemma 3.3. Suppose that v ∈ X ′ = Xj , then M = Nj
Lemma 3.4 to write
Pr(ηv ≤ x | Ht ) = Pr ηv ≤ x

X

w∈X ′

14

ηw =

A21

−

≥ ζn → ∞. We now use

A20 ,

!

where A1 and A0 are the values of Wx(t) −1 and Wx(t)
j

j−1)+1

, respectively, in Ht , so that A1 − A0 is

(t)

the value of Lj in Ht .
Now from (P1) we have that A := A21 − A22 ∈ [(1 − ε)mM, (1 + ε)mM] for M = |X ′ | w.h.p., for
any ε > 0. Thus we fix any µ ∈ [(1 − ε)mM, (1 + ε)mM] and show that
!
X
ηw = µ = (1 + O(ε)) Pr (ERL(m) ≤ x) .
Pr ηv ≤ x
w∈X ′

The lemma follows since ε is arbitrary.
We write
Pr ηv ≤ x

X

w∈X ′
x

ηw = µ

!

η m−1 e−η (µ − η)(M −1)m−1 e−(µ−η) (Mm − 1)!
·
· M m−1 −µ dη
((M − 1)m − 1)!
µ
e
η=0 (m − 1)!

(M −1)m−1 Q
Z x m−1 −η
1 − µη
eη m
i=1 (Mm − i)
η
e
·
dη
=
µm
η=0 (m − 1)!


 2  
Z x m−1 −η
 m 
η
η
η
e
dη
·
1
+
O
· exp η − ((M − 1)m − 1)
+O
=
µ
µ2
M
η=0 (m − 1)!
Z x m−1 −η
η
e
= (1 + O(ε))
dη.
η=0 (m − 1)!
=

Z

Here we used that Ht typical implies that M ≥ log1/400 n → ∞.

Part 3
In the next section we will need a lower bound on vt+1 . Let
(
1
v ≥ log30 n
log3 n
φv =
1
. v < log30 n.
(log log n)3
Lemma 3.5. W.h.p. ρt ≥ φvt for 1 ≤ t ≤ T0 .
Proof. The values of λ(vt , i), i = 1, 2, . . . , m are unconditioned by Ht , see (H2). It then follows
from (P2) that if vt ≥ log30 n then
Pr(vt+1 ≤ φvt vt | Ht ) . m

Wφvt
m
. mφ1/2
.
vt =
Wvt
log3/2 n

There are O(ω log n) choices for t and so this deals with vt ≥ log30 n.
15

(24)

Now there are O(log log n) choices of t ∈ [T1 , T0 ] for which vt ≤ log30 n. In this case we can
replace the RHS of (24) by 1/(log log n)3/2 .
We will also need to bound the size of NR (vt ) for all t.
Lemma 3.6. W.h.p., for all t ≤ T0 ,
|NR (vt )| ≤

(

log3 n
(log log n)20

vt ≥ log30 n.
vt ≤ log30 n.

Proof. The size of NR (v), v = vt is stochastically bounded by Bin(Ψv, ηv /v). This is because if
w ∈ NR (v) then w ≤ Ψv. Also, for any such w, the probability that it has v as a left neighbor
is at most mwv /Ww . ηv /(vw)1/2 ≤ ηv /v. This uses property (S1) to see that the values of
λ(w, i), i = 1, 2, . . . , m are unconditioned by Ht . Thus, if θv = log3 n if v ≥ log30 n and equal to
(log log n)20 otherwise,
  

θ
ηv θv
Ψv
eΨηv v
Pr(|NR (v)| ≥ θv | Ht ) ≤
≤
.
(25)
θv
v
θv
3

If v ≥ log30 n then the RHS of (25) is at most (e/ log n)log n which is clearly small enough to han20
dle T possible values for t. If v < log30 n then the RHS of (25) is at most (40e/(log log n)9 )(log log n)
which is small enough to handle O(ω log log n) possible values for t such that v < log30 n.
Continuing Part 3, we now show that the DCA walk doesn’t contain cycles.
Lemma 3.7. W.h.p. the path Pt , t ≤ T0 is self avoiding.
Proof. We proceed by induction and assume that the claim of the lemma is valid up to time
t − 1. Now consider the choice of vt .
Case 1: There is an edge vs vt where s ≤ t − 2:
(a): vt ∈ NL (vs ) ∩ NL (vt−1 ).
We bound the probability of this (conditional on E, Ht ) asymptotically by
X X mwv
X X
ηv
.
.
Wvt−1
2(vvt−1 )1/2
s∈[t−2] v∈NL (vs )

(26)

s∈[t−2] v∈NL (vs )

Here, and throughout the proof of Case 1, v denotes a possibility for vt and mwv /Wvt−1 bounds
the probability that vt−1 chooses v. Remember that these choices are still uniform, given the
history.
We split the sum in (26) as
X
X

s∈[t−2] v∈NL (vs )
vs >log30 n

ηv
+
2(vvt−1 )1/2

X

X

s∈[t−2] v∈NL (vs )
vs ≤log30 n

16

ηv
.
2(vvt−1 )1/2

Consider the first sum. There are less than t choices for s; m choices for v and ηv ≤ log n. Now
v ∈ NL (vs ) and Lemma 3.5 implies that v ≥ log27 n. So we can bound the first sum by


1
1
1
.
=o
(# of s) · (# of v) · (max ηv ) · 1/2 ≤ T0 · m · log n ·
v
log11 n
log27/2 n
Summing this estimate over t ≤ T0 gives o(1).
For the second sum, we bound the number of choices of s by O(ω log log n) and ηv by O(log log n),
since v ≤ vs . We use the fact (see Section 3.2) that vt−1 ≥ log1/100 n. So we can therefore bound
the second sum by


1
1
1
(# of s) · (# of v) · (max ηv ) · 1/2 ≤b ω log log n · m · log log n ·
=o
.
log1/200 n
log1/300 n
vt−1
(We use A ≤b B in place of A = O(B).)
There are O(ω log log n) choices for T0 ≥ t > s ≥ T1 and so we can sum this estimate over choices
of t.
(b): vt ∈ NL (vs ) ∩ NR (vt−1 ).
Using vt ∈ NR (vt−1 ), we bound the probability of this asymptotically by
X

X

s∈[t−2] v∈NL (vs )
vs >log30 n

ηvt−1
+
2(vvt−1 )1/2

X

X

s∈[t−2] v∈NL (vs )
vs ≤log30 n

ηvt−1
.
2(vvt−1 )1/2

For the first sum we use the argument of Case (a) without any change, except for bounding ηvt−1
by log n as opposed to bounding ηv by the same. This gives a bound


1
1
1
(# of s) · (# of v) · (max ηvt−1 ) · 1/2 ≤b T0 · m · log n ·
.
=o
v
log11 n
log27/2 n
This is small enough to inflate by the number of choices for t.
For the second sum we split into two cases: (i) vt−1 ≥ log30 n and (ii) vt−1 < log30 n. This enables
us to control ηvt−1 . For the first case we obtain


1
1
1
(# of s) · (# of v) · (max ηvt−1 ) · 1/2 ≤ ω log log n · m · log n ·
=o
.
log15 n
log13 n
vt−1
The RHS is small enough to handle the O(ω log n) choices for t.
For the second case we obtain
(# of s) · (# of v) · (max ηvt−1 ) ·

1
1/2

vt−1

≤ ω log log n · m · log log n ·

1
log1/200 n

The RHS is small enough to handle the O(ω log log n) choices for t.

17

=o



1
log1/300 n



.

(c): vt ∈ NR (vs ) ∩ NL (vt−1 ).
Using vt ∈ NL (vt−1 ), we bound the probability of this asymptotically by
X
X
X
X
ηv
ηv
+
.
1/2
2(vvt−1 )
2(vvt−1 )1/2
s∈[t−2] v∈NR (vs )
vs ≤log29 n

s∈[t−2] v∈NR (vs )
vs >log29 n

For the first sum we use v ≥ vs and the argument of Case (a) without change, but notice we
split over vs > log29 n or not here. This gives a bound of


1
1
1
(# of s) · (# of v) · (max ηv ) · 1/2 ≤ T0 · m · log n ·
=o
.
v
log12 n
log29/2 n
For the second sum we use v ≤ Ψvs to bound v by log30 n. We also use Lemma 3.6 to bound the
number of choices of v by (log log n)20 . This gives a bound of


1
1
1
20
.
(# of s)·(# of v)·(max ηv )· 1/2 ≤b ω log log n·(log log n) ·log log n· 1/200 = o
log
n
log1/300 n
vt−1
(d): vt ∈ NR (vs ) ∩ NR (vt−1 ).
Using vt ∈ NR (vt−1 ), we bound the probability of this asymptotically by
X

X

s∈[t−2] v∈NR (vs )
vs >log30 n

ηvt−1
+
2(vvt−1 )1/2

X

X

s∈[t−2] v∈NR (vs )
vs ≤log30 n

ηvt−1
.
2(vvt−1 )1/2

For the first sum we use v ≥ vs and Lemma 3.6 to bound the number of choices for v and then
we have a bound of


1
1
1
3
.
=o
(# of s) · (# of v) · (max ηvt−1 ) · 1/2 ≤ T0 · log n · log n ·
v
log15 n
log9 n
For the second sum we split into two cases: (i) vt−1 ≥ log30 n and (ii) vt−1 < log30 n. This enables
us to control ηvt−1 . We also use Lemma 3.6 to bound the number of choices for v in each case.
Thus in the first case we have the bound


1
1
1
3
(# of s) · (# of v) · (max ηvt−1 ) · 1/2 ≤b ω log log n · log n · log n ·
=o
.
log15 n
log10 n
vt−1
In the second case we have
(# of s)·(# of v)·(max ηvt−1 )·

1
1/2

vt−1

20

≤b ω log log n·(log log n) ·log log n·

1
log1/200 n

=o



1
log1/300 n



Case 2: There is a path vs , v, vt where s < t.
The calculations that we have done for Case 1 carry through unchanged. We just replace vt−1 by
vt throughout the calculation and treat v as an arbitrary vertex as opposed to a choice of vt .
18

.

(t)

The xj are separated
We now prove that w.h.p. points λi are well-separated. Let

J1 = j : vj ≥ log30 n .
Lemma 3.8. Equation (22) holds w.h.p. for all t ≤ T0 .

Proof. We consider cases.
(t)
(t)
(t)
Case 1: xj−1 , xj ∈ VR .
For this we write
ζv,w =

(

log2 n
min {v, w} ≥ log30 n.
.
log1/300 n Otherwise.

Pr(∃1 ≤ s ≤ t, v ∈ NR (vs ), w ∈ NR (vt ) : |v − w| ≤ ζv,w | E, Ht) ≤
X
X
ηvs ηvt
.
(vs vt vw)1/2
1≤s≤t≤T
0

≤
≤

X

v∈NR (vs ),w∈NR (vt )
|v−w|≤ζv,w

X

ζv,w ηvs ηvt
(v − ζv,w )(vs vt )1/2

(27)

1≤s≤t≤T0 v∈NR (vs )
∗
X ζs,t
ηvs ηvt |NR (vs )|
2
.
(vs vt )1/2
1≤s≤t≤T0

(28)

∗
Here ζs,t
will be a bound on the possible value of ζv,w in (27).

Case 1a: max {vs , vt } ≥ log29 n:
∗
In this case ζs,t
≤ log2 n and we can bound the summand of (28) by
∗
ζs,t
· log2 n · log3 n ·

1
log

29/2

n

=

1
log

15/2

n

.

Multiplying by a bound T02 on the number of summands gives a bound of o(1). Here, and in the
next case, we use Lemma 3.6 to bound |NR (vs )|.
Case 1b: max {vs , vt } < log29 n:
Here we have max {v, w} ≤ Ψ log29 n ≤ log30 n. In this case we can bound the summand of (28)
by


1
(log log n)5
1/300
2
20
log
n · (40m log log n) · (log log n) ·
.
=o
log1/100 n
log1/200
We only have to inflate this by (T0 − T1 )2 = O((ω log log n)2 ). This completes the case where
(t)
(t)
xj−1 , xj ∈ R(t) .

19

(t)

(t)

(t)

Case 2: xj−1 , xj ∈ VL
We first show that the gaps λj − λj−1 are large. Define
β1 =
and

log1/300 n
log15/2 n
and
β
=
.
2
n1/2
n1/2

(
β1
εj =
β2

and
σ1 =

λj = λ(vt , i), vt ∈ J1 .
otherwise.

1
log

15/2

n

and σ2 =

1
log

1/200

n

.

We drop the superscript t for the rest of the lemma.
Claim 3.9.
Pr(∃λj ∈ Λ0 : λj−1 > λj − εj | Ht ) = o(1).
Proof of Claim 3.9. This follows from the fact that
Pr(∃j : λj−1 > λj − εj ) ≤ o(1) + (1 + o(1))(m2 T12 σ1 + m2 (T0 − T1 )(T1 σ1 + (T0 − T1 )σ2 )).
We have fewer than m2 T12 choices for s = τ (j − 1), t = τ (j) ∈ J1 . Assume first that s < t.
Given such a choice, we have that w.h.p. Wvt & log15 n/n1/2 by (P2). Now λj will have been
chosen uniformly from 0 to ≈ Wvt and so the probability it lies in [λj−1, λj−1 + εj ] is at most
≈ β1 /Wvs , which explains the term m2 T12 σ1 . If s > t then we repeat the above argument with
[λj−1 , λj−1 + ε1 ] replaced by [λj − ε1 , λj ]
The term m2 (T0 − T1 )T1 σ1 arises in the same way with j − 1 ∈ J1 , j ∈
/ J1 or vice-versa.
The term m2 (T0 − T1 )2 σ2 arises from the case where j − 1, j ∈
/ J1 . Here we can only assume
1/200
1/2
that Wj & log
n/n . This follows from (P2), (P4) and Lemma 2.2 and the fact that
we exit the main loop with SUCCESS when we see a vertex of degree at least n1/2 / log1/100 n.
Assuming that s < t we see that the probability that λj lies in [λj−1 , λj−1 + ε2 ] is at most
β2 /Wvt ∼ β2 /(log1/200 n/n1/2 ) = o(1).
Given the Claim and (P4), (P5) we have that w.h.p.
(
n
1
β1 − log
1/2 ≥ 2 β1
n
Wv(t) −1 − Wv(t) +1 ≥
log n
j
j−1
≥ 21 β2
β2 − 40mnlog
1/2

j ∈ J1 .
j∈
/ J1

(29)

Now,
Wv(t) −1 − Wv(t)
j

j−1 +1

=



Υm(τ (j)−1)
Υmn+1

1/2

−



Υm(τ (j−1)+1)
Υmn+1

20

1/2

=

Υm(τ (j)−1) − Υm(τ (j−1)+1)
1/2

1/2

1/2

Υmn+1 (Υm(τ (j)−1) + Υm(τ (j−1)+1) )

.

Or,
(
β1 n1/2
1/2
1/2
1/2
ηu = (Wv(t) −1 − Wv(t) +1 )Υmn+1 (Υm(τ (j)−1) + Υm(τ (j−1)+1) ) ≥
j
j−1
β2 n1/2
(t)

j ∈ J1 .
.
j∈
/ J1

X

u∈Xj

It follows that w.h.p.
(t)
|xj−1
(t)

(t)

(t)

−

(t)
xj |

=

(t)
|Xj |

≥

(

β1 n1/2
log n
β2 n1/2
40m log log n

j ∈ J1 .
j∈
/ J1

.

(t)

Case 3: xj ∈ VL , xj−1 ∈ VR
Let θv = β1 , v ≥ log30 n and θv = β2 otherwise. We write
ηvs
wv + 2θv
·
1/2
(vvs )
Wvt
s,t,v,k

X  ηv ηv
2n1/2 θv ηvs
s
+
.(30)
.
v(vs vt )1/2
v(vs vt )1/2
s,t,v,k

Pr(∃s < t, v, k : v ∈ NR (vs ), λ(vt , k) ∈ Iv ± θv | E, Ht ) ≤

X

We bound the sum in the RHS of (30) as follows: If max {v, vs } ≥ log30 n then we bound the
first sum by
n
X
1
1
1
2
≤b (ω 2 log2 n) · log2 n · log n ·
= o(1).
(#s, t, k) · log n ·
·
15
v log n
log15 n
v=1

We bound the second sum by
n
X
1
1
1
15/2
(#s, t, k) · 2 log
n · log n ·
·
≤ (ω 2 log2 n) · log15/2 n · log n · log n ·
= o(1).
15
15
v
log
n
log
n
v=1
When max {v, vs , vt } < log30 n we bound the first sum by
log30 n

(#s, t, k) · (40 log log n)2 ·

X 1
1
≤b
·
1/200
v log
n
v=1

(ω log log n)2 · (log log n)2 · log log n ·

1
log

1/200

log

1/200

n

= o(1). (31)

We bound the second sum by
log30 n

(#s, t, k) · log

1/300

n · 40 log log n ·

X 1
1
≤b
·
1/200
v
log
n
v=1

(ω log log n)2 · log1/300 n · log log n ·

1
n

= o(1). (32)

Finally, if max {v, vs } < log30 n ≤ log30 n then we have to replace (#s, t, k) in (31), (32) by
1/2
O(ω 2 log n log log n). But this is compensated by a factor 1/vt ≤ 1/ log15 n.
It follows that (29) holds w.h.p. and the proof continues as for Case 2.

21

Part 4
We now assume t ≤ T0 . We begin by showing that DCA only uncovers a small part of the
distribution of the η’s.
Let Ξt = Pt ∪ N(Pt ) and
St,j =

X

wv .

v∈Ξt

Lemma 3.10. W.h.p., St,j = o(Wj ) for log1/100 n ≤ j and 1 ≤ t ≤ T0 .
Proof. Assume first that j ≥ log30 n. It follows from (P2), (P3), (P5) and Lemma 3.6 that
w.h.p.


max ηvs
T0 log n(m + log3 n)
ω log5 n
St,j ≤ T0 ×
× (m + max |NR (vs )|) .
=O
.
n1/2
2mn1/2
n1/2
 10 
 1/2
log n
j
.
=Ω
Wj ≥ (1 − o(1))
n
n1/2

This completes this case. Now assume that j ≤ log30 n. (P2), (P3), (P4) and Lemma 3.6 that
w.h.p.
 1/2
ω log4/3 log n
j
20
St,j . 40m log log n ×
× (m + (log log n) ) ≪ Wj ∼
1/2
2mn
n

for log1/100 n ≤ j ≤ log30 n.

Dealing with left neighbors
The calculation of the ratio ρt takes contributions from two cases: where vt+1 is a left-neighbor
of vt , and where vt+1 is a right-neighbor of vt .
Lemma 3.11.

2
E(ρt 1vt+1 <vt | Ht ) ≤ .
3

Proof. Let D denote the (m/2)th largest degree of a vertex in NR (vt ). We write
X
E(ρt 1vt+1 <vt | Ht | D = d) Pr(D = d)
E(ρt 1vt+1 <vt | Ht ) =
d



ζd
≤
E
vt
d
 
ζD
,
=E
vt
X



22

Pr(D = d)

where ζd is the index of the smallest degree left neighbor of vt that has degree at least d. We
let ζd = 0 if there are no such left neighbors. We now couple ζ with a random variable that is
independent of the algorithm and can be used in its place.
Going back to Section 2.1 let us associate ℓk for k ≥ ω with an index µk chosen uniformly from
[⌊k/m⌋]. In this way, vertex i ≥ ω is associated with m uniformly chosen vertices ai,1 , ai,2 , . . . , ai,m
in [i − 1]. Furthermore, we can couple these choices so that if NL (i) = {bi,1 , bi,2 , . . . , bi,m } then
given we have (i) Pr(bi,j ≤ ai,j ) ≥ 1 − o(1) and (ii) bi,j ≤ 2ai,j for all i, j. This because
Pr(bi,j ≤ k) ∼ Wk /Wi ∼ (k/i)1/2 (giving (i)) and (k/i)1/2 ≥ k/i and (1 − o(1))(k/i)1/2 ≥ k/2i
(giving (ii)).
So now let µ be the index of the uniform choice associated with the largest degree left neighbor
of vt that has degree at least D. Thus
 
 
ζD
µ
1
2
.E
= + o(1) ≤ .
E
vt
vt
2
3

Dealing with right neighbors
It will be more difficult to consider the contribution of right-neighbors. In preparation, for
λ0 ≤ γ ≤ 1 − 1/m we define
∆iγ := m + γmζ(i)
where ζ(i), ζ + (i) are defined in (9), (10) respectively. We note that ηi ζ(i) is a lower bound for
the expected degree of vertex i, i ≥ ω, see Lemma 2.2(a). Note also that ηi ζ + (i) is an upper
bound for the expected degree of vertex i, i ≥ ω.
The parameter ∆iγ is a degree threshold. For a suitable parameter γ, we wish it to be the case
that there should be many left-neighbors but few right-neighbors which have degree greater than
∆iγ . We define


γi∗ = max γ : j ∈ NL (i) : dn (j) ≥ ∆iγ ≥ m/2 .

∆vγtv∗ is a lower bound on the degree needed for vertex j > vt to be considered by DCA as the
t
next vertex; thus we proceed by analyzing the distribution of γv∗t . We first derive upper bounds
for Pr(γv∗t ≤ γ | Ht ).
Lemma 3.12. There exists c1 > 0 such that
1/2

)c1 m + me−c1 γ

Pr(γv∗t ≤ γ | Ht ) . (γ 1/2 e1−γ

1/2

)c 1 m

Pr(γv∗t ≤ 45 | Ht ) . e−c1 m .
Pr(γv∗t ≥ γ | Ht ) . γ −c1 m ,

2

1
, 0≤γ≤ .
8
1
−c1 /γ 1/2
+ me
, 0≤γ≤ .
8

Pr(γv∗t ≤ γ | Ht ) . (γ 1/2 e1−γ

2

5

γ ≥ 10 .
23

1/2 m

(33)
(34)
(35)
(36)



Proof. For j < vt , we define events Aj = ηj ≤ γ 1/2 m and Dj = dn (j) ≤ ∆vγt . We need to
T

estimate Pr
j∈S Dj for subsets S ⊆ NL (vt ) of size m/2. We write
\

j∈S

Dj ⊆

\

(Aj ∪ (Āj ∩ Dj )) ⊆

j∈S

\

Aj ∪

j∈S

[

(Āj ∩ Dj ).

(37)

j∈S

Now, using inequality (6) and equation (23), we see that if 0 ≤ γ ≤ 1/8 then for j < vt ,
Pr(ηj ≤ γ 1/2 m | Ht ) . m(γ 1/2 e1−γ

1/2

)m .

(38)

The RHS of (38) includes a factor of 1 + o(1) due to conditioning on E, Ht .
So,
Pr

\

Aj

j∈S

Ht

!

. (m(γ 1/2 e1−γ

1/2

)m )|S| .

(39)

Furthermore, because j ∈ NL (vt ) implies that i ≥ j and hence ζ(vt ) ≤ ζ(j),
Pr((dn (j) ≤ ∆iγ ) ∧ Āj | Ht ) ≤ Pr (dn (j) − m ≤ γmζ(j) | Ht ) Pr(ηj > γ 1/2 m|Ht )


(1 − γ 1/2 )2 1/2
γ mζ(j) .
. exp −
2

(40)

Explanation of (40): We remark first that the conditioning on E, Ht only adds a (1+o(1)) factor
to the upper bound on our probability estimate. We now apply Lemma 2.2(b) with 1 − α = γ
and ηj ≥ γ 1/2 m.
From (37) (summing over all m/2 subsets of NL (vt )) and (40) (summing over NL (vt )) we obtain

Pr(γv∗t ≤ γ | Ht ) = Pr(| j ∈ NL (vt ) : dn (j) ≤ ∆iγ | ≥ m/2| | Ht ) .



m/2
(1 − γ 1/2 )2 1/2
m
1/2 1−γ 1/2 m
2 (m(γ e
) )
+ m exp −
γ mζ(vt ) . (41)
2
We observe that j ∈ NL (vt ) implies that dn (j) ≥ m + 1. So,
m + 1 < ∆iγ implies ζ(vt ) >

1
.
mγ

(42)


m/2
1/2
2
1/2 1−γ 1/2 m
Using (42) in (41) verifies (34), after bounding 2 (m(γ e
) )
by (γ 1/2 e1−γ )c1 m .
m

From (37) and (40),

Pr(γv∗t ≤ γ | Ht ) . (m(γ 1/2 e1−γ

1/2

)m )m/2 +

(1 − γ 1/2 )2 1/2
γ mζ
+ Pr(A1 | Ht ) + Pr(Ā1 | Ht ) m exp −
2
−1

24





9n
10



(43)

Here
A1 =





9n
NL (vt ) ∩
10



m
≥
4



.

Explanation of (43): The first term is from (39). If Ā1 holds then vt has at least one left
neighbor j ≤ 9n/10. The final term comes from using (40) and ζ(j) ≥ ζ(9n/10). The factor
Pr(Ā1 )−1 handles the conditioning on Ā1 . The factor m is the union bound for choices of j.
 
Now NL (vt ) ∩ 9n
is dominated by the binomial Bin(m, n/10) and so Pr(A1 | Ht ) ≤ e−d1 m .
10
Now ζ(9n/10) ≥ 1/20 and plugging these facts into (43) yields (33). Here we have absorbed the
1/2
e−d1 m term into me−c1 γ m and we will do so again below.
We continue with the proof of (35). For j ∈ NL (vt ), we observe that if dn (j) ≤ ∆vγt and γ ≤ 54
then
5m
dn (j) − m ≤
ζ(vt ).
4
We now estimate the probability that a uniform random choice of j ∈ NL (vt ) (for fixed Ht , which
determines vt ) has certain properties.
We first observe that

 

W3i/5
3i
Pr j ≥
Ht . 1 −
∼
5
Wvt

 1/2 !
2
3
< .
1−
5
5

(44)

(For this we used (P2).)
Now (6) implies that
Pr(ηj ≤ 0.99m | Ht ) ≤ e−d2 m .

(45)

Moreover, for ηj > 0.99m and j < 3vt /5, we have
ζ(j)
=
ζ(vt )

 1/2
vt
j

where
ε=
Thus we have

1−
1−


j 1/2
−ε
n

1/2
vt
−ε
n

!

 1/2
vt
≥
j

5L log log n
.
ω 3/4 log n

(46)

 1/2
5
E(dn (j) − m | Ht ) ≥ ηj ζ(j) & 0.99m
ζ(vt).
3

Now 0.99 × (5/3)1/2 = 1.278.. > 1.01 × 5/4 and so



ζ(j)ηj
5ζ(vt )
Ht ≤ Pr dn (j) − m ≤
Pr dn (j) − m ≤
4
1.01
25

Ht



≤ e−d3 ηj ζ(j) ≤ e−d4 m

(47)

using Lemma 2.2(b). It follows from (44) and (45) and (47) that






5
m
2
∗
−d2 m
−d4 m
Pr γvt <
≥
≤ e−d3 m .
Ht ≤ Pr Bin m, e
+e
+
4
5
2
This completes the proof of (35).
To deal with (36) we observe that if dn (j) ≥ ∆vγt and γ ≥ 105 then
vt
j ∈ NL (vt ) and j ≤ 1/2
γ
But

or

ηj ≥ γ

1/2

 1/2
j
m
≥ γ 1/4 m or dn (j) − m ≥ γ 3/4 ηj ζ(j).
vt



vt
Pr j ∈ NL (vt ) and j ≤ 1/2
γ

Ht

And, using (P3) and γ ≥ 105 ,


Pr ηj ≥ γ

1/4

m Ht



.

vt
X

l=2vt /γ



wl
Wvt

.

Z

Wvt /γ 1/2
1
. 1/4 .
Wvt
γ

∞

ηl =γ 1/4 m

(48)

ηlm e−ηl
dηl
(m − 1)!

1/4
vt
X
e−γ m
.
2(vt l)1/2

l=2vt /γ

. e−γ

1/4 m

.

(49)

Lastly, using (44), (45) and Lemma 2.2(d) and ζ + (j) . ζ(j) for j ≤ 3n/5 we have
 2
3/4
Pr dn (j) − m ≥ γ 3/4 ηj ζ(j) | Ht ≤ + e−d2 m + e−γ η ≤ 0.41.
5

(50)

It follows from (48), (49) and (50) that






1
m
∗
−γ 1/4 m
Pr γvt ≥ γ | Ht . Pr Bin m, (1 + o(1))
. e−d3 m .
+e
+ 0.41
≥
γ 1/4
2
This completes the proof of the lemma.

Corollary 3.13. W.h.p. γv∗s ≥ 1/(log log n)2 for s = 1, 2, . . . , T = O(log n).
Proof. The value of γv∗s is determined when vs is first visited and in this case we can apply Lemma
3.12. In which case the result follows directly from (34).
We now have a handle on the distribution of γv∗t . We now put bounds on the expected number
of j > vt that can be considered to be a candidate for vt+1 , conditioned on the value of γv∗t . In
particular, we let

Dγvt = j > vt : dn (j) ≥ ∆vγt .
26

We will bound the size of Dγi by dividing Dγi into many parts bounding each part; in particular,
κ ∈ N we let
h
i
 i, i2 ∩ D i
κ = 0.
γ
γ
i
(51)
Jγi,κ = h


 i2 1 + κ−1 , i2 1 + κ ∩ D i 1 ≤ κ ≤ 2nγ 2 L .
γ
γ
L
γ
L
i

Note that Jγi,0 = ∅ if γ ≥ 1.
Finally, we let
rγi,κ

:=

|Jγi,κ |

rγi

and

:=

X

rγi,κ

and

siγ

:=

κ≥0



i X
κ + 1 i,κ
j≤ 2
rγ .
1+
γ κ≥0
L
i,κ

X X

(52)

κ≥0 j∈Jγ



Remark 3.14. We have that E m2 v1t svγt | Ht is an upper bound on the expectation of the ratio
, conditioned on the event that vt+1 > vt , since each right neighbor whose index is
ρt = vt+1
vt
included in the sum svγt has probability of at most m2 of being chosen by the algorithm.


3L3
Lemma 3.15. If vt ≤ n 1 − m then
E(rγvt | Ht ) ≤
svγt
E
| Ht
vt
Moreover,





≤


ηvt
L max {0, (1 − γ)} + 7 + 10Le−c2 γL .
γL

(53)


ηvt
L max {0, (1 − γ)} + 13 + 100Le−c2 γL .
3
γ L

If vt ≤ n/5 and κ ≥ (log log n)4 and γ ≥ 1/(log log n)2 then Pr(rγvt ,κ > 0) ≤

(54)

1
.
log2 n

(55)

Note that (55) implies the second inequality in (19).
Proof. Recall from Lemma 3.10 that w.h.p.,
ST,j = o(Wj ) for j ≥ log1/100 n.

(56)

We write
E(rγvt ,κ | Ht )
Z ∞ m−1 −ηj
X

ηj e
mwvt
.
Pr dn (j) ≥ ∆vγt | Ht , ηj dηj
ηj =0 (m − 1)!
vt ,κ Wj − St,j

(57)

j∈Jγ

. ηvt

X

v ,κ
j∈Jγ t

1
2(vt j)1/2

Z

∞

ηj =0


ηjm−1 e−ηj
Pr dn (j) ≥ ∆vγt | Ht , ηj dηj .
(m − 1)!
27

(58)

Explanation of (57) and (58): We sum over the relevant j and fix ηj . We multiply by the
density of ηj and integrate. Using (56) we see that
mwvt
ηvt
mwvt
∼
∼
.
Wj − St,j
Wj
2(vt j)1/2
This is asymptotically equal to the expected number of times j chooses vt as a neighbor.
Thus
E(rγvt ,κ | Ht ) .

X

v ,κ
j∈Jγ t

where

(59)


ηjm−1 e−ηj
Ij =
Pr dn (j) ≥ ∆vγt | Ht , ηj dηj ≤ 1.
ηj =0 (m − 1)!
Z

If m is large then

ηvt
Ij
2(vt j)1/2

∞

E rγvt ,0 | Ht
Continuing, for κ ≥ 1, we write:



(
0
. P

ηvt
v
j∈J0 t (γ) 2(vt j)1/2

.

ηvt 1−γ
γ

γ ≥ 1.
γ < 1.

Ij . A1 + A2 + A3 ,

(60)

(61)

where
A1 =

Z

A2 =

Z

A3 =

Z

(1−1/L)γm
ηj =0
(1+1/L)m


ηjm−1 e−ηj
Pr dn (j) ≥ ∆vγt | ηj dηj .
(m − 1)!

ηj =(1−1/L)m
∞
ηj =(1+1/L)m


ηjm−1 e−ηj
Pr dn (j) ≥ ∆vγt | ηj dηj
(m − 1)!


ηjm−1 e−ηj
Pr dn (j) ≥ ∆vγt | ηj dηj .
(m − 1)!

and then write rγvt ,κ = rγvt ,κ,1 + rγvt ,κ,2 + rγvt ,κ,3. Here rγvt ,κ,l is equal to the RHS of (59) with Ij
replaced by Al . The implicit
(1 + o(1)) factor in (61) arises from replacing

Pr dn (j) ≥ ∆vγt | ηj , Ht by Pr dn (j) ≥ ∆vγt | ηj in the integrals, i.e., ignoring the conditioning
due to Ht . Since j > vt , the only effect
 of Ht is on Wj through wvt . Here we have that w.h.p.

ηvt
log n
vt 1/2
Wj ∼ n
= o(Wvt ).
and wvt ∼ 2m(vt n)1/2 = O 2m(v
1/2
t n)

Case 1: n1 ≤ vt < n/5:
Note that in this case

1
ζ(vt ) ≥
2

 1/2
n
≥ 1.
vt

In the following we use Lemma 2.1 to estimate the integrals over ηj . We observe that
E(rγvt ,κ,1 | Ht )
28

(62)

.

X

ηvt
2(vt j)1/2

X

ηvt
2(vt j)1/2

v ,κ

j∈Jγ t

.

v ,κ

j∈Jγ t

Z (1− 1 )m m−1 −ηj
L

ηj e
Pr dn (j) ≥ ∆vγt | Ht , ηj dηj ,
(m − 1)!
ηj =0
(
!
Z (1− 1 )m m−1 −ηj
L
ηj e
1
1 ≤ κ ≤ 10L,
·
dηj , (63)
(m − 1)!
(e(L/κ)1/2 )d0 γmζ(vt ) κ > 10L
ηj =0

Explanation of (63): We remark first that the conditioning on Ht only adds a (1 + o(1)) factor
to the upper bound on our probability estimate. We will use Lemma 2.2 to bound the probability
that degrees are large. Now with our bound on vt and within the range of integration, the ratio
of ∆vγt − m to the mean of dn (j) − m is
∆vγt − m
ζ + (j)

 1/2 
1−
γm vnt
=
 1/2 
ηj nj
1−




vt 1/2
n

 1/2
− o(1)
γm j
≥
 &

ηj vt
j 1/2
+
o(1)
n

1/2  
κ−1
κ 1/2
L
1+
≥
when κ ≥ 10L. (64)
L−1
L
L

We then use (11) and Lemma 2.2(d) with β = (κ/L)1/2 .
Continuing, we observe that
1/2


κ 1/2
κ−1
1
1+
− 1+
≤
L
L
2L

and so
E(rγvt ,κ,1

ηv e−m/(2L
| Ht ) ≤ t
γvt 1/2

2)

ηv e−m/(2L
≤ t
γL

2)

 1/2 
 1/2 !
κ+1
κ−1
vt
vt
×
1+
−
1+
L
L
(
!
1
1 ≤ κ ≤ 10L,
(e(L/κ)1/2 )d0 γmζ(vt ) κ > 10L,
(
!
1
1 ≤ κ ≤ 10L,
(e(L/κ)1/2 )d0 γmζ(vt ) κ > 10L.

(65)



·

(66)

Continuing, it follows from (65) that
X

v ,κ
j∈Jγ t

1
j 1/2

≤

vt 1/2
.
γL

E(rγvt ,κ,2 | Ht )
Z (1+1/L)m
X

ηjm−1 e−ηj
ηvt
vt
Pr
d
(j)
≥
∆
|
H
,
η
dηj
≤
n
t
j
γ
1/2
ηj =(1−1/L)m (m − 1)!
vt ,κ 2(vt j)
j∈Jγ

29

(67)

≤

X

v ,κ
j∈Jγ t

ηvt
2(vt j)1/2




1 n
o
d1 γmζ(vt )
× exp − L2


(e(L/κ)1/2 )d0 γmζ(vt )


1
ηvt  −d1 γmζ(vt )/L2
× e
≤
γL 

(e(L/κ)1/2 )d0 γmζ(vt )

κ ≤ 3,
4 ≤ κ ≤ 10L,

(68)

κ > 10L,

1 ≤ κ ≤ 3,
4 ≤ κ ≤ 10L,
κ > 10L.

(69)

where we have used (67).
Explanation for (68): We proceed in a similar manner to (64) and use

 1/2 

vt 1/2
n


vt
1
−
−
o(1)
γm
∆γ − m
vt
n
1
1
m.
=
 ≥ 1 + if κ ≥ 4, ηj ≥ 1 −
 1/2 

ζ + (j)
L
L
j 1/2
n
1− n
+ε
ηj j

Then we use Lemma 2.2(c),(d).
Continuing,
E(rγvt ,κ,3

| Ht ) ≤

X

v ,κ
j∈Jγ t

ηvt
2(vt j)1/2

Z

∞

ηj =(1+1/L)m


ηjm−1 e−ηj
Pr dn (j) ≥ ∆vγt | Ht , ηj dηj
(m − 1)!

(70)

We bound the integral in (70) by something independent of j and then as above, there is a factor
ηvt /γL arising from the sum over j.
For all 1 ≤ κ ≤ 80L + 1, we simply use the bound


Z ∞
ηjm−1 e−ηj
d2 m
dηj ≤ exp − 2 .
1
L
ηj =m(1+ L
) (m − 1)!

(71)

For κ ≥ 80L + 2, we split the integral from (70) into pieces B1κ , B2κ (whose definition depends on
κ), which we will bound individually.
In particular, we use
B1κ

=

Z

≤

Z

∞

ηj =m(1+ κ−1
L )

1/4

∞
ηj =m(1+ κ−1
L )

1/4


ηjm−1 e−ηj
Pr dn (j) ≥ ∆vγt | Ht , ηj dηj
(m − 1)!
ηjm−1 e−ηj
dηj
(m − 1)!

1/4

≤ e−d3 m(κ/L)

(72)

and
30

B2κ

m(1+ κ−1
L )

1/4


ηjm−1 e−ηj
Pr dn (j) ≥ ∆vγt | Ht , ηj dηj
=
1
ηj =m(1+ L
) (m − 1)!

1/4 !  1/4 d4 γmζ(vt )
κ
−
1
eL
≤ Pr dn (j) ≥ ∆vγt Ht , ηj ≤ m 1 +
≤
(73)
L
κ1/4
Z

to bound the integral in (70) by B1κ + B2κ for all κ ≥ 80L + 2.
Therefore, gathering the many terms together (and using that κ ≤
on m large to allow crude upper bounding, we see that

2nLγ 2
vt

from (51)) and relying

γL
2
E(rγvt | Ht ) . L max {0, (1 − γ)} [from (60)] + 10Le−m/(2L ) [from (66)]
ηvt
2
 2nLγ

X/i  eL1/2 d0 γmζ(vt )
−d1 γmζ(vt )/L2
−m/(2L2 )
+ 10Le
[from (69)] + 2 + e
[from (66) and (69)]
1/2
κ
κ=10L


d2 m
+ 6[from (69)] + 100L exp − 2 [from (71)]
L
2
 1/4 d4 γmζ(vt ) !
2nLγ /i
X
eL
1/4
+
[from (72) and (73)]. (74)
e−d3 m(κ/L) +
1/4
κ
κ=80L+2
We first observe that if vnt < γ102 then the summations κ = 10L, . . . , 2nLγ 2 /vt etc. above are
empty. For larger n/vt we can therefore assume that γm(n/vt )1/2 ≥ m which implies (see (62))
that γmζ(vt ) ≥ m/2 and then we can assume that
2nLγ 2 /vt

X  eL1/2 d0 γmζ(vt )
1
≤
and
1/2
κ
1000
κ=10L

2nLγ 2 /vt

X  eL1/4 d4 γmζ(vt )
1
≤
.
1/4
κ
1000
κ=80L+1

(75)

Plugging these estimates into (74) and making some simplifications, we obtain (53).
Going back to (52) we have

 vt
2sγ
γ 3L
Ht ≤ L max {0, (1 − γ)}
E
ηvt
mi
−m/(2L2 )

+ 200Le

−d1 γmζ(vt )/L2

+ 100Le



2
 2nLγ
X/vt 2κ  eL1/2 d0 γmζ(vt )
L
κ1/2
κ=10L
 1/4 d4 γmζ(vt ) !
eL
1/4
e−d3 m(κ/L) +
.
κ1/4

−m/(2L2 )

+ 2+e

2
 2nLγ

X/vt 2κ
d
m
2
+ 12 + 104 L exp − 2 +
L
L
κ=80L+2

Making similar estimates to what we did for (75) gives us (54).
We obtain (55) from (P5), (66), (69), (72) and (73). Indeed, if Jγvt ,κ 6= ∅ then from its definition
2n
1/2
we must have vt ≤ 2Lγ
. Together with vt ≤ n/5 we obtain that ζ(vt ) ≥ 2Lκ1/2 γ . Thus, in this
κ−1
31

case,


eL1/2
κ1/2

d0 γmζ(vt )



eL1/2
(log log n)2

d0 m(log log n)2 /2L1/2




1
≤
=o
.
(76)
log10 n
This deals with the probabilities in (66) and (69). For (69) we rely m large to to show that
1/4
e−d3 m(κ/L) = o(1/ log10 n). Equation (72) is dealt with in a similar manner to (66). Here we
 1/4 d4 γmζ(vt )
which is the square root of (76).
have eL
κ1/4


3
Case 2: n/5 ≤ vt ≤ n 1 − 3L
:
m
The upper bound on vt implies that

mζ(vt ) ≥ L3 .

Using the same definitions of rγvt ,κ,l , l = 1, 2, 3 as above:
X

E(rγvt ,κ,1

| Ht ) ≤

X X

≤

X X

κ≥1 j∈Jγvt ,κ

κ≥1

κ≥1 j∈Jγvt ,κ

ηvt
2(vt j)1/2

Z (1− 1 )m m−1 −ηj
L
ηj e
dηj ,
(m − 1)!
ηj =0

ηvt
2
e−m/(2L ) ,
1/2
2(vt j)

from Lemma 2.1(e),

 1/2
ηvt n
2
≤
e−m/(2L )
γ vt
51/2 ηvt −m/(2L2 )
e
.
≤
γ
X

E(rγvt ,κ,2 | Ht )

κ≥1

.

X X

ηvt
2(vt j)1/2

Z

X X

ηvt
2(vt j)1/2

Z

κ≥1 j∈Jγvt ,κ

.

κ≥1 j∈Jγvt ,κ

(1+1/L)m
ηj =(1−1/L)m

(1+1/L)m
ηj =(1−1/L)m



2
X ηv  −d5 γL
t
4e
≤

d γL3

γL

κ≥1
 eL1/2 6
κ1/2

X

E(rγvt ,κ,3

| Ht ) ≤

κ ≤ 3,
4 ≤ κ ≤ 10L,
κ > 10L,

X X

κ≥1 j∈Jγvt ,κ

κ≥1

≤


ηjm−1 e−ηj
Pr dn (j) ≥ ∆vγt | ηj dηj
(m − 1)!


κ ≤ 3,
1 n
o
ηjm−1 e−ηj 
d5 γmζ(vt )
4 ≤ κ ≤ 10L,
· exp − L2
(m − 1)! 

(e(L/κ)1/2 )d6 γmζ(vt ) κ > 10L,

X X
κ≥1

v ,κ
j∈Jγ t

ηvt
2(vt j)1/2

Z

∞

ηj =(1+1/L)m

ηvt
−m/(3L2 )
e
,
2(vt j)1/2
32

ηjm−1 e−ηj
(m − 1)!
from Lemma 2.1(d),

 1/2
ηvt −m/(3L2 ) n
e
≤
γ
vt
1/2
5 ηvt −m/(3L2 )
≤
e
.
γ
The above upper bounds are small enough to give the lemma in this case, without trouble.
We are now in a position to prove (20). We confirmed the second part of the statement (20)
above, using (55), so only the first part remains. The first part follows immediately from Lemma
3.11 and the following, by addition:
Lemma 3.16.
E(ρt 1vt+1 ≥vt | Ht ) ≤
Proof. We consider cases.

Case 1: n1 ≤ vt ≤ n 1 −

3L3
m

21ηvt
L3
+ 2.
mL
m


: Then,

E(ρt 1vt+1 ≥vt | Ht ) ≤ I1 + I2 + I3 + I4 ,

where
5/4

I1 =

Z

≤

Z

γ=1/8
5/4
γ=1/8

≤

E(ρt 1vt+1 ≥vt | γv∗t = γ)d Pr(γv∗t ≤ γ),


1000ηvt
m
−c1 m

2 × 83
× ηvt ×
mL

Z

,
≤ ηvt e
Z 10000 
I2 =
γ=5/4

≤
I3 =

7L
+ 13 + 100Le−c2 γL
8



d Pr(γv∗t ≤ γ),

by Remark 3.14, Lemma 3.15,

5/4

γ=1/8

d Pr(γv∗t ≤ γ),

from (35).

(77)


2
× ηvt × (13 + 100Le−c2 γL ) d Pr(γv∗t ≤ γ),
mγ 3 L

20ηvt
.

ZmL
∞
γ=10000



(78)


2
× ηvt × (13 + 100Le−c2 γL ) d Pr(γv∗t ≤ γ)
mγ 3 L

Z ∞
27ηvt
γ −cm dγ,
from (36),
≤ 15
10 Lm γ=100
27ηv
1
= 15 t × 2(cm−1)
.
10 Lm 10
(cm − 1)
Z 1/8
I4 =
E(ρt 1vt+1 ≥vt | γv∗t = γ)d Pr(γv∗t ≤ γ)
γ=0

33

(79)

1/2

≤ e−d0 m

,

(80)

1/2

To obtain the term e−d0 m in (80) we use (33) and (34) to obtain

max γ ∈ [0, 1/8] : γ −2 Pr(γ ∗ ≤ γ) ≤
o
n
2
1/2
2
max γ ∈ [0, 1/8] : (γ 1/2−4/(c1 m ) e1−γ )c1 m +
oo
n
n
−2
−c1 mγ 1/2 −c1 /γ 1/2
max γ ∈ [0, 1/8] : mγ min e
,e
2 )−1/2

≤ (84/(c1 m

1/2

e1−1/8

2

1/2

)c1 m + m2 e−c1 m

.

The first case of the lemma now follows from (77), (78), (79) and (80).


3
:
Case 2: vt > n 1 − 3L
m


3
We observe first that n ≤ vt 1 + 4L
. Then we let Z = dn (vt ) − m be the number of right
m
neighbors of vt . Furthermore,
n
X
wi
.
E(Z | Ht ) .
W
j
j=v +1
t



3
vt 1+ 4L
m

X

j=vt +1

ηvt
. ηvt
2(vt j)1/2

!

1/2
4L3
4L3
1+
− 1 ≤ ηvt
.
m
m

Case 2a: ηvt ≥ 1/L1/2 .
We use (81) and Lemma 2.2(d) to prove


ηvt
1/2
Pr Z ≥
Ht ≤ e−d1 ηvt L ≤ e−d1 L .
L

(81)

(82)

Then we can write


4L3
2ηvt
3ηvt
1/2
E(ρt 1vt+1 ≥vt | Ht ) ≤ 1 +
× e−d1 L +
≤
.
m
Lm
Lm


3
Explanation: ρt will be at most 1 + 4L
if the unlikely event in (82) occurs. Failing this, the
m

chance that ρt > 1 is at most

2Z
m

≤

2ηvt
.
Lm

Case 2b: ηvt < 1/L1/2 .
It follows from (81) that E(Z | Ht ) . 4L5/2 /m. It then follows from Lemma 2.2(d) that


L3
1/2
Ht ≤ e−d2 L .
Pr Z ≥
3m
We then have
E(ρt 1vt+1 ≥vt | Ht ) ≤



4L3
1+
m



34

× e−d2 L

1/2

+

2L3
L3
≤
.
3m2
3m2

Part 5
We now prove (21). To do this, we will obtain a recurrence for E(ηvt+1 | Ht ), and, at the end,
obtain the bound 4m by averaging over the possible histories Ht .
We begin by writing
E(ηvt+1 | Ht ) = E(ηvt+1 1vt+1 <vt | Ht ) + E(ηvt+1 1vt+1 >vt | Ht )

(83)

We consider each term in (83) separately. For the first term, since
ηvt+1 1vt+1 <vt ≤ max {ηl : 1 ≤ l < vt , l ∈ NL (vt )} 1vt+1 <vt ≤ max {ηl : 1 ≤ l < vt , l ∈ NL (vt )} ,
we have that
E(ηvt+1 1vt+1 <vt | Ht ) ≤ E (max {ηl : 1 ≤ l < vt , l ∈ NL (vt )} | Ht )
Z ∞
=
Pr(max {ηl : 1 ≤ l < vt , l ∈ NL (vt )} ≥ η | Ht )dη
η=0
Z ∞
=
Pr(∃1 ≤ l < vt , l ∈ NL (vt ) : ηl ≥ η | Ht )dη
η=0

≤
.

Z

t −1
∞ vX

η=0 l=1
Z ∞ vX
t −1

η=0 l=1
vX
t −1 Z ∞

Pr(l ∈ NL (vt ) and ηl ≥ η | Ht )dη
wl
Wvt
Z ∞

Z

∞

ηl =η

ηlm−1 e−ηl
dηl dη
(m − 1)!

ηlm−1 e−ηl
ηl
dηl dη
1/2 (m − 1)!
2m(lv
t)
η=0
η
=η
l
l=1
Z ∞ Z ∞
ηlm e−ηl
dηl dη
. 2m + (1 + o(1))
η=2m ηl =η (m − 1)!
Z ∞
. 2m +
4e−3η/10 dη, from Lemma 2.1(c),
.

η=2m
−3m/5

. 2m + 20e
≤ 3m.

(84)

We now bound the second term of (83). We consider two cases, according to properties of the
history Ht (which determines vt and ηvt ).

1
Case 1: Ht is such that vt ≤ 1 − ω1/2
n.
In this case, we have that
E(ηvt+1 1vt+1 >vt | Ht )

o

n
≤ E max ηl : vt < l ≤ n, vt+1 ∈ NL (l), dn (l) ≥ ∆vγtv∗ 1vt+1 >vt | Ht
t

35

o


n
≤ E max ηl : vt < l ≤ n, vt+1 ∈ NL (l), dn (l) ≥ ∆vγtv∗ | Ht .
t

So we have that

E(ηvt+1 1vt+1 >vt | Ht )
o


n
vt
≤ E max ηl : vt < l ≤ n, vt+1 ∈ NL (l), dn (l) ≥ ∆γv∗ | Ht
t
Z ∞
o
n
vt
=
Pr(max ηl : vt < l ≤ n, vt ∈ NL (l), dn (l) ≥ ∆γv∗ ≥ η | Ht )dη
t
η=0
Z ∞


=
Pr ∃vt < l ≤ n, vt ∈ NL (l) : ηl ≥ η, dn (l) ≥ ∆vγtv∗ | Ht dη
≤

η=0
n
X

l=vt +1
n
X

t

Z

∞

η=0



Pr (vt ∈ NL (l)) ∧ (ηl ≥ η) ∧ (dn (l) ≥ ∆vγtv∗ ) | Ht , ηl dη

ηvt
.
2(lvt )1/2
l=v +1
t

t

Z

∞

η=0

Z

∞

ηl =η



ηlm−1 e−ηl
Pr dn (l) ≥ ∆vγtv∗ | Ht , ηl dηl dη.
t
(m − 1)!

(85)

Recall that in the final two lines, vt and ηvt are not random variables, but are the actual values of these random variables in the history Ht , so this is a deterministic upper bound on
E(ηvt+1 1vt+1 >vt | Ht ).
We split the sum in the RHS of (85) into E1 + E2 + E3 + E4 according to the ranges of l and η,
and bound each separately. The first part consists of
Z
Z
n


X
ηvt 1l≤4m2 vt /(γv∗t )2 2m ∞ ηlm−1 e−ηl
vt
|
H
,
η
Pr
d
(l)
≥
∆
E1 =
∗
t l dηl dη.
n
γvt
1/2
2(lv
(m
−
1)!
t)
η=0
η
=η
l
l=v +1
t

Even though vt and ηvt are constants (determined by Ht ), we caution that γv∗t and so also E1 are
random variables.
Observe that we have that
Z ∞ m−1 −ηl
Z ∞ m−1 −ηl


ηl e
ηl e
vt
Pr dn (l) ≥ ∆γv∗ | Ht , ηl dηl ≤
dηl ≤ 1
t
ηl =η (m − 1)!
ηl =η (m − 1)!
which allows us to write
E1 1γv∗t ≤5/4 ≤ 1γv∗t ≤5/4

n
X
2mηvt 1l≤4m2 vt /(γv∗t )2

l=vt +1

2(lvt )1/2

≤

5m2 ηvt
1γv∗t ≤5/4 .
γv∗t

(86)

We will use this expression when we take the expectation over γv∗t ≤ 5/4.
We also have that
Z ∞ m−1 −ηl

ηl e
Pr (dn (l) ≥ ∆vγt∗ ) ∧ (γv∗t > 5/4) | Ht , ηl dηl ≤ I1 + I2 + I3 ,
ηl =η (m − 1)!
36

(87)

where
I1 =

Z

7m/8

ηl =η
Z ∞

ηlm−1 e−ηl
dηl ≤ m
(m − 1)!



7 1/8
e
8

m

≤ e−d0 m ,

from Lemma 2.1(a),

ηlm−1 e−ηl
dηl ≤ e−d1 m , from Lemma 2.1(d).
I2 =
ηl =9m/8 (m − 1)!


Z 9m/8

ηlm−1 e−ηl
∗
∗
Pr dn (l) − m ≥ γvt mζ(vt ) ∧ (γvt > 5/4) Ht , ηl dηl ,
I3 =
ηl =7m/8 (m − 1)!


Z 9m/8
ηlm−1 e−ηl
5
≤
Pr dn (l) − m ≥ mζ(vt ) Ht , ηl dηl .
4
ηl =7m/8 (m − 1)!

(88)

We bound I3 with two subcases:
Subcase 1a: ζ(l) > 0.


Z 9m/8
8
10ζ(vt)
ηlm−1 e−ηl
I3 ≤
Pr dn (l) − m ≥
ηl ζ(l) Ht , ηl dηl [since m ≥ ηl ],
9ζ(l)
9
ηl =7m/8 (m − 1)!

n
o
2
(10ζ(vt )−9ζ(l)) ηl
Z 9m/8
10ζ(vt) ≤ 18ζ(l)
ηlm−1 e−ηl exp n−
81ζ(l)
o
[from (2) and ℓ ≥ vt + 1],
≤
(10ζ(vt )−9ζ(l))ηl
10ζ(vt) > 18ζ(l)
ηl =7m/8 (m − 1)! exp −
27

≤

Z

9m/8
ηl =7m/8


n
o
exp − 7mζ(vt )
10ζ(vt ) ≤ 18ζ(l)
648
n
o
(m − 1)! exp − 7mζ(vt )
10ζ(vt ) > 18ζ(l)
216

ηlm−1 e−ηl

≤ e−mζ(vt )/100 .

(89)

Subcase 1b: ζ(l) ≤ 0.
In this case, we go back to (88) and use ζ + (l) in place of ζ(l), see (10).


Z 9m/8
10ζ(vt) +
ηlm−1 e−ηl
Pr dn (l) − m ≥
ηl ζ (l) Ht , ηl dηl ,
I3 ≤
9ζ + (l)
ηl =7m/8 (m − 1)!

(90)

For ε as in (46) we see that ζ(l) ≤ 0 implies that l ≥ n(1 − ε)2 . In which case
ζ + (l) ≤
On the other hand, vt ≤ 1 −

1
ω 1/2

2ε
≤ 3ε.
1−ε

(91)

implies that
ζ(vt ) ≥

1
ω 1/2

− 2ε ≥

1
.
2ω 1/2

t)
≥
Comparing (91) and (92), we see that ζ(vt ) ≫ ζ + (l). From this and (3) with β = 10ζ(v
9ζ + (l)
we deduce that


10ζ(vt ) +
ηl ζ (l) Ht , ηl ≤ (6εω 1/2)10ηl ζ(vt ) ≤ (6εω 1/2 )35mζ(vt )/36 .
Pr dn (l) − m ≥
9ζ + (l)

37

(92)
1
6εω 1/2

Plugging this estimate into (90) we obtain something stronger than (89), finishing Subcase 1b
and giving that I3 ≤ e−mζ(vt )/100 in all cases.
Having bounded the three terms in (87), we then have that
E1 1γv∗t >5/4 ≤

n
X
ηvt 1l≤4m2 vt /(γv∗t )2

(lvt )1/2

l=vt +1

5m
e−d2 m ∗
γvt

≤ ηvt


−d2 m

e−d2 m + e−mζ(vt )/100

n
e−mζ(vt )/100 X 1
+
vt 1/2
l1/2
l=v +1
t

−mζ(vt )/100

≤ ηvt 4me

+e

!



(n + 1)1/2 − (vt + 1)1/2
·
vt 1/2

≤ ηvt (4me−d2 m + 2ζ(vt)e−mζ(vt )/100 )


200
−d2 m
.
+
≤ ηvt 4me
m


(93)

It follows from (86) and (93) that


 2
200
5m
−d2 m
.
1γ ∗ ≤5/4 + 4me
+
E1 ≤ ηvt
γv∗t vt
m
We continue with the other parts of the RHS of (85):
Z
Z ∞ m−1 −ηl
n
X
ηvt 1l≤4m2 vt /(γv∗t )2 ∞
ηl e
E2 =
Pr(dn (l) ≥ ∆vγt∗ | Ht , ηl )dηl dη
1/2
2(lv
)
(m
−
1)!
t
η=2m ηl =η
l=v +1
t

4m2 vt /(γv∗t )2

≤

X

ηvt
2(lvt )1/2

Z

∞

X

ηvt
2(lvt )1/2

Z

∞

X

ηvt
×m
2(lvt )1/2

l=vt +1
4m2 vt /(γv∗t )2

≤

l=vt +1
4m2 vt /(γv∗t )2

≤

l=vt +1
4m2 vt /(γv∗t )2

=
≤

X

l=vt +1
−d3 m
e
ηvt
.
γv∗t

η=2m

Z

∞



eη/m
eη/m

ηl =η

η=2m

Z

ηlm−1 e−ηl
dηl dη
(m − 1)!
m

dη

from Lemma 2.1(c),

∞

e−3mx/10 dx

x=2

10ηvt e−3m/5
6(lvt )1/2
(94)

Note that we aborbed an O(m) factor into the expression in (94). This is valid because m is
large. We continue to do this where possible.
Z
Z
n
X
ηvt 1l>4m2 vt /(γv∗t )2 γv∗t (l/vt )1/2 ∞ ηlm−1 e−ηl
Pr(dn (l) ≥ ∆vγtv∗ | Ht )dηl dη
E3 =
1/2
t
2(lv
)
(m
−
1)!
t
η=0
ηl =η
l=v +1
t

38

n
X

γv∗t (l/vt )1/2

∞

ηlm−1 e−ηl
dηl dη
∗ (l/v )1/2 (m − 1)!
η=0
η
=γ
t
l
2
∗
2
v
t
l=4m vt /(γvt )
(
)
Z γv∗ (l/vt )1/2
n
X
t
3γv∗t (l/vt )1/2
ηvt
exp −
dη from Lemma 2.1(c),
≤
2(lvt )1/2 η=0
10
2
∗
2
l=4m vt /(γvt )
)
(
n
X
3γv∗t (l/vt )1/2
ηvt
≤
,
exp −
2(lvt )1/2
10
2
∗
2
l=4m vt /(γvt )
)
(
Z
ηvt γv∗t n
3γv∗t (x/vt )1/2
≤
dx,
exp −
vt
10
x=4m2 vt /(γv∗t )2
Z ∞
ηvt γv∗t
8vt
≤
× ∗ 2
ye−3y/5 dy,
vt
(γvt ) y=m
≤

ηvt
2(lvt )1/2

Z

Z

ηvt e−d4 m
=
.
γv∗t
Z
Z ∞ m−1 −ηl
n
X
ηvt 1l>4m2 vt /(γv∗t )2 ∞
ηl e
Pr(dn (l) ≥ ∆vγtv∗ | Ht , ηl )dηl dη
E4 =
1/2
t
2(lvt )
η=γv∗t (l/vt )1/2 ηl =η (m − 1)!
l=i
Z ∞
Z ∞ m−1 −ηl
n
X
ηl e
ηvt
dηl dη
≤
1/2
2(lvt )
η=γv∗ (l/vt )1/2 ηl =η (m − 1)!
2
∗ 2
l=4m vt /(γvt )

≤

n
X

l=4m2 vt /(γv∗t )2

t

ηvt
2(lvt )1/2

Z

∞

e−3η/10 dη
η=γv∗t (l/vt )1/2

)
(
3γv∗t (l/vt )1/2
5ηvt
,
≤
exp −
3(lvt )1/2
10
2
2
∗
l=4m vt /(γvt )
)
(
Z
1/2
∗
(x/j)
3γ
2ηvt ∞
≤ 1/2
dx,
x−1/2 exp − vt
i
10
2
∗
2
x=4m vt /(γvt )
Z
4ηvt ∞ −3y/10
e
dy,
= ∗
γvt y=2m
n
X

≤

ηvt e−d5 m
.
γv∗t

Thus,
E(ηvt+1 1vt+1 >vt



 5m∗ 2 + e−d∗6 m ηvt ≤
γvt
γvt

| Ht ) ≤ E1 + E2 + E3 + E4 ≤  −d
m
7
200
e

ηvt
+
∗
γvt

m

7m2
η
γv∗t vt

γv∗t ≤ 5/4
γv∗t > 5/4.

We now integrate with respect to the value of γv∗t . (Note that γv∗t is actually a discrete random
variable, so that Pr(γv∗t ≤ γ | Ht ) is discontinuous, but one can view this as a Riemann-Stieltjes
integral. We write Pr† (γv∗t ≤ γ) below in place of Pr(γv∗t ≤ γ | Ht ).) Using Lemma 3.12 we see
39

that if m is large then integrating over γ,
E(ηvt+1 1vt+1 >vt | Ht )
!
Z ∞
Z 5/4
−d7 m
e
200
7m2
d Pr† (γv∗t ≤ γ) +
d Pr† (γv∗t ≤ γ) +
≤ ηvt
γ
γ
m
γ=5/4
γ=0
!
Z 5/4
7m2
200
≤ ηvt
d Pr† (γv∗t ≤ γ) + e−d8 m +
γ
m
γ=0
!
Z 1/m
Z 5/4
2
7m2
200
7m
= ηvt
d Pr† (γv∗t ≤ γ) +
d Pr† (γv∗t ≤ γ) + e−d8 m +
γ
γ
m
1/2
γ=0
γ=1/m
1/m Z 1/m1/2
 2
7m2
7m
† ∗
+
Pr (γvt ≤ γ)
Pr† (γv∗t ≤ γ)dγ
≤ ηvt
2
γ
γ
γ=0
0
!
Z 5/4
7m2
200
+
d Pr† (γv∗t ≤ γ) + e−d8 m +
γ
m
γ=1/m
Z 1/m
7m2
−d9 m1/2
Pr† (γv∗t ≤ γ)dγ+
+
≤ ηvt e
2
γ
γ=0
!
Z 5/4
7m3
200
,
from (34),
d Pr† (γv∗t ≤ γ) + e−d8 m +
m
γ=1/m γ




200
1
†
∗
−d8 m
−d9 m1/2
−d10 m1/2
4
,
≤ γvt ≤ 5/4 + e
+
+e
+ 7m Pr
≤ ηvt e
m
m


200
−d9 m1/4
−d10 m1/2
4 −c1 m
−d8 m
+e
+ 7m e
+e
+
≤ ηvt e
,
from (35)
m


200
−d12 m1/4
+
≤ ηvt e
.
m

(95)

Combining (84) and (95) via (83), we have that
E(ηvt+1



200
−cm1/4
ηvt .
| Ht ) ≤ 3m + e
+
m

This completes Case 1. Case 2 is much shorter.

1
Case 2: Ht is such that vt > 1 − ω1/2
n.
E(ηvt+1 | Ht ) .

∼
∼

n
X

l=vt +1
n
X

l=vt +1
n
X

ηvt
2(lvt )1/2

Z

ηvt
2(lvt )1/2

Z

mηvt
2(lvt )1/2
l=v +1
t

40

∞
η=0

Z

∞
ηl =η

∞
−η

e
η=0

ηlm−1 e−ηl
dηl dη
(m − 1)!

m
X
i=1

η m−i
dη
(m − i)!

(96)

. mηvt
≤

(n + 1)1/2 − (vt + 1)1/2
(vt + 1)1/2

mηvt
.
ω 1/2

This completes Case 2. In particular, for sufficiently large n we see that for any typical Ht (i.e.,
in both Case 1 and Case 2), the bound from (96) is valid. Putting
Et = E ∩ {Ht is typical}
we deduce from (96) that
E(ηvt+1



200
−cm1/4
| Et ) ≤ 3m + e
+
E(ηvt | Et )
m


200
−cm1/4
E(ηvt | Et−1 ).
. 3m + e
+
m

(97)
(98)

We obtain (98) from (97) because Et ⊆ Et−1 and so
E(ηvt | Et−1 ) ≥ E(ηvt | Et ) Pr(Et | Et−1 ) ∼ E(ηvt | Et ).
Because m is large, (21) will follow by induction once we have shown that
E(ηv1 ) ≤ 3m.

(99)

Here we will use the assumption that v1 is chosen exacty according to the stationary distribution
for a simple random walk on Gn . In particular, we have
!
n
X
dn (i)
Pr(ηv1 ≥ η) ≤ E
1η ≥η ,
2mn v1
i=1
and Lemma 2.2 implies that if η ≥ 2m
E((dn (i) − m)1ηv1 ≥η ) .

 n 1/2 Z
i

∞

η=2m

 n 1/2
η m e−η
dη .
× 4me−η/2 .
(m − 1)!
i

Furthermore,
E(m1ηvt ≥η ) = m Pr(ηv1 ≥ η) ≤ 5me−η/2 .
So, if η ≥ 2m, then
Pr(ηv1
Therefore,
E(ηv1 ) ≤ 2m +

Z

n
9e−η/2 X 1
≤ 10e−η/2 .
≥ η) .
2n1/2 i=1 i1/2
∞

Pr(ηv1 ≥ η)dη ≤ 2m + 10

η=2m

Z

∞

η=2m

and (99) follows.
41

e−η/2 dη

3.2

Exiting the main loop with success

In summary, it follows that w.h.p. DCA reaches Step 7 in O(ω log n) time. Also, at this time
vT ≤ log1/49 n. This follows from Lemma 2.2(g), 2.2(h) and (P4). Furthermore, this justifies
using n1 as a lower bound on vertices visited during the main loop. The random walk of Step
8 will w.h.p. take place on [log1/9 n]. This follows from Lemma 2.2(j). Vertex 1 will be in the
1/2
same component as vt in the subgraph of Gn induced by vertices of degree at least logn1/20 n . This
is because there is a path from vT to vertex 1 through vertices in [vT ] only and furthermore it
1/2
follows from Lemma 2.2(i) that w.h.p. every vertex on this path has degree at least logn1/20 n .
The expected time to visit all vertices of a graph with ν vertices is O(ν 3 ), see for example
Aleliunas, Karp, Lipton, Lovász and Rackoff [1]. Consequently, vertex 1 will be reached in a
further O((log1/9 n)3 ) = o(log n) steps w.h.p, completing the proof of Theorem 1.2.

4

Concluding remarks

We have described an algorithm that finds a distinguished vertex quickly and which is local in a
strong sense. There are some natural questions that are left unanswered:
• Can the running time be improved from O(ω log n) to O(log n)?
• Can we get polylog expected running time for DCA if m = 2?
• Can we extend the analysis to other more general models of web graphs e.g. Cooper and
Frieze [7]. In this case, we would not be able to use the model described in Section 2.
As a final observation, the algorithm DCA could be used to find the vertex of largest degree: if
we replace Step 8 by “Do the random walk for log n steps and output the vertex of largest degree
encountered” then w.h.p. this will produce a vertex of highest degree. This is because log n will
be enough time to visit all vertices v ≤ log1/39 n, where the maximum degree vertex lies.

References
[1] R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lovász and C. Rackoff, Random Walks, Universal
Traversal Sequences, and the Complexity of Maze Problems. Proceedings of the 20th Annual
IEEE Symposium on Foundations of Computer Science (1979) 218-223.
[2] A. Barabási and R. Albert, Emergence of scaling in random networks, Science 286 (1999)
509-512.
[3] B. Bollobás, O. Riordan, J. Spencer and G. Tusnády, The degree sequence of a scale-free
random graph process, Random Structures and Algorithms 18 (2001) 279-290.
42

[4] B. Bollobás and O. Riordan, The Diameter of a Scale-Free Random Graph, Combinatorica
24 (2004) 5-34.
[5] C. Borgs, M. Brautbar, J. Chayes, S. Khanna and B. Lucier, The Power of Local Information
in Social Networks, http://arxiv.org/abs/1212.0884.
[6] M. Brautbar and M. Kearns, Local Algorithms for Finding Intersting Individuals in Large
Networks, in Innovations in Computer Science (ITCS) (2010) 188-199.
[7] C. Cooper and A.M. Frieze, On a general model of web graphs, Random Structures and
Algorithms 22 (2003) 311-335.
[8] G. Grimmett and D. Stirzaker, Probability and Random Processes, Third Edition, Oxford
University Press, Oxford UK, 2001.
[9] W. Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the
American Statistical Association 58 (1963) 13-30.
[10] M. Jerrum and A. Sinclair. The Markov chain Monte Carlo method: an approach to approximate counting and integration. In Approximation Algorithms for NP-hard Problems.
(D. Hochbaum ed.) PWS (1996) 482-520.
[11] M. Mihail, C. Papadimitriou and A. Sabeeri, On Certain Connectivity Properties of the
Internet Topology, Journal of Computer and System Sciences 72 (2006) 239251.

A

Proofs of properties (P1)–(P5)

In this section we give proofs of (P1)–(P5), which we list here for convenience.
(P1) For Υk,ℓ = Υk − Υℓ , we have
Υk,ℓ

"

1/2

Lθk,ℓ
∈ (k − ℓ) 1 ±
3(k − ℓ)1/2

#

for (k, ℓ) = (mn + 1, 0) or


l=0
1
k−ℓ
2
∈ {ω, ω + 1, . . . , n} and k − l ≥ log n
k ≥ log30 n, l > 0

m
 1/300
log
n 0 < l < k < log30 n.

43

Here n0 =

λ20 n
,
ω log2 n

λ0 =

1
,
log20/m n



log k



1/2


k
= (k − ℓ)1/2


(k−ℓ)3/2 log n



n1/2


n

θk,ℓ

ω ≤ l < k ≤ log30 n, l > 1
ω ≤ k ≤ n2/5 , l = 0
log30 n < k ≤ n2/5
n2/5 < k ≤ n0 .
n0 < k.

ω 3/2 log2 n

#  
 1/2 "
1/2
1/2
i
Lθi
i
(P2) Wi ∈
1 ± 1/2 ∼
for ω ≤ i ≤ n.
n
i
n
(P3) wi ∼

ηi
for ω ≤ i ≤ n.
2m(in)1/2

(P4) λ0 ≤ ηi ≤ 40m log log n for i ∈ [log30 n].
(P5) ηi ≤ log n for i ∈ [n].

Proof of (P1)
Applying Lemma 2.1(d),(e) to (1) for i ≥ 1 we see that
Pr(¬(P1))


n
X
L2 θk,0
≤2
exp −
+2
27
k=ω
n2/5

L2 k 1/2
exp −
=2
27
k=ω
X



30



n
X

k−ℓ=log1/300 n

+2

n0
X

k=n2/5 +1

L2 θk,ℓ
exp −
27




L2 θmn+1,0
+ 2 exp −
27

L2 k 3/2 log n
exp −
27n1/2






+2

n+1
X

k=n0

L2 n
exp −
27ω 3/2 log2 n
+1





n2/5
X
L2 log k
L2 (k − ℓ)1/2
exp −
+2
+2
exp −
+
27
27
30
1/300
k−ℓ=log n
k−ℓ=log
n




n
n
0
X
X
L2 n
L2 (k − ℓ)3/2 log n
+2
exp −
2
exp −
27n1/2
27ω 3/2 log2 n
2/5
k−ℓ=n +1
log

k−ℓ=n

Xn



+1

0

= o(1).

Proof of (P2)
For this we use
Wi =



Υmi
Υmn+1
44

1/2

.




Then,
#
 1/2 "
1/2
Lθi
i
Wi ∈
/
1 ± 1/2
n
i
implies that either
Υmn+1

"

1/2

Lθi
∈
/ (mn + 1) 1 ±
3(mn + 1)1/2

#

or Υmi

"

1/2

Lθi
∈
/ mi 1 ± 1/2
3i

#

.

These events are ruled out w.h.p. by (P1).

Proof of (P3)
We use (1 + x)1/2 ≤ 1 +
wi =



x
2

for 0 ≤ |x| ≤ 1. Then,

Υmi
Υmn+1

1/2

−



Υm(i−1)
Υmn+1

1/2

!


1/2
Υm(i−1) 1/2
ηi
=
1+
−1
Υmn+1
Υm(i−1)
1/2


1/2
Lθi
m(i − 1) 1 + 3m1/2 (i−1)1/2
η
 i
≤ 
1/2

1/2
Lθi
2m(i − 1) 1 −
(mn + 1) 1 −
1/2


3(mn+1)

ηi
≤
2m(in)1/2

1/2

2Lθ
1 + 1/2i 1/2
m i

!

1/2

Lθi
3m1/2 (i−1)1/2



.

A similar calculation gives
1/2

ηi
wi ≥
2m(in)1/2

2Lθ
1 − 1/2i 1/2
m i

!

.

Proof of (P4)
The upper bound follows from Lemma 2.1(c). For the lower bound, we observe by (7) that the
expected number of i ≤ log30 n with ηi ≤ λ0 is at most log30 n × λm
0 = o(1).

Proof of (P5)
This follows from Lemma 2.1(c).
45

B

Proof of Lemma 2.2

We restate the lemma for convenience.
Lemma B.1.
(a) If E occurs then d¯n − m ∈ [ηi ζ(i), ηi ζ + (i)].
2 η ζ(i)/2
i

(b) Pr(dn (i) − m ≤ (1 − α)mζ(j)) ≤ e−α

for 0 ≤ α ≤ 1.

2 η ζ + (i)/3
i

(c) Pr(dn (i) − m ≥ (1 + α)mζ + (j)) ≤ e−α
(d) Pr(dn (i) − m ≥ βmζ + (j)) ≤ (e/β)βηi ζ

+ (i)

for 0 ≤ α ≤ 1.

for β ≥ 2.

(e) W.h.p. ηi ≥ λ0 and ω ≤ i ≤ n1/2 implies that dn (i) ∼ ηi
(f ) W.h.p. ω ≤ i ≤ log30 n implies that dn (i) ∼ ηi


n 1/2
.
i

(g) W.h.p. ω ≤ i ≤ n1/2 implies that dn (i) . max {1, ηi }
(h) W.h.p. n1/2 ≤ i ≤ n implies dn (i) ≤ n1/3 .
(i) W.h.p. 1 ≤ i ≤ log1/49 n implies that dn (i) ≥
(j) W.h.p. dn (i) ≥

n
log1/20 n


n 1/2
.
i


n 1/2
i

.

n1/2
.
log1/20 n

implies i ≤ log1/9 n.

Proof. (a) Suppose that we fix the values for W1 , W2 , . . . , Wn . Then the degree dn (i) of vertex i
can be expressed
n X
m
X
dn (i) = m +
ζj,k
j=i k=1

where the ζj,k are independent Bernouilli random variables such that


wi wi
Pr(ζj,k = 1) ∈
,
.
Wj Wj−1

So, putting

d¯n (i) = E(dn (i))

we have
mwi

n
n
X
X
1
1
≤ d¯n (i) − m ≤ mwi
.
W
W
j
j
j=i−1
j=i

Now assuming that (P2), we have for ω ≤ i ≤ n,

n  1/2
n
X
X
n
1
≥
Wj
j
j=i
j=i

46

1/2

2Lθj
1 − 1/2
j

!

.

But
1/2
n
X
θj
j=ω

j

2/5

n
X
1
≤
+
3/4
j
j=ω

n0
X

j=n2/5 +1

n
X
n1/2
log1/2 n
+
n1/4 j 1/4 j=n +1 jω 3/4 log n
0

3n1/2 log log n
4n1/2
+
3ω 3/4 log n
ω 3/4 log n
4n1/2 log log n
≤
.
ω 3/4 log n

≤ 4n1/10 +

It follows that


9Ln1/2 log log n
1/2
1/2
1/2
¯
2(n − (i + 1) ) −
dn (i) ≥ m + mwi n
ω 3/4 log n
!
 1/2
 n 1/2
i
9L log log n
1
1−
,
− 1/2 1/2 −
≥ m + ηi
i
n
n i
2ω 3/4 log n
after using (P3).
A similar calculation gives a similar upper bound for d¯n (i) and this proves that
"
#
 1/2
 n 1/2
i
5L
log
log
n
i ≥ ω implies that d¯n (i) ∈ m + ηi
1−
.
± 3/4
i
n
ω log n
It follows from (2) and (4) that




L2 ηi n1/2
Pr dn (i) − m ≤ (1 − α)ηi ζ(i) ηi ≤ exp − 1/2 1/2 .
4i ω




L2 ηi n1/2
Pr dn (i) − m ≥ (1 + α)ηi ζ(i) ηi ≤ exp − 1/2 1/2 .
4i ω
(a) For ηi ≥ λ0 and ω ≤ i ≤ n0 we have


L2 ηi n1/2
2
exp − 1/2 1/2 ≤ e−L log n/4 .
4i ω
(b) This follows from (a) and (4).
(c) This follows from (a) and (2).
(d) This follows from (a) and (3).
(e) This follows from (a), (b), (c) and (12).
(f) This follows from (e) and (P4).
47

(g) This follows from (c) and (12).
(h) The degree of i ≥ n1/2 is stochastically dominated by the degree of n1/2 . Also, the probability
that dn (n1/2 ) exceeds the stated upper bound is o(1/n). So (h) follows from (g).
(i) For ω ≤ i ≤ log1/49 n, this follows from (f) and (P4). For 1 ≤ i < ω we can use (b) with
ηi ≥ λ0 and α = n−1/10 .
(j) This follows from (e), (f) and (g) and (P4).

48

