ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH
RESTARTS

arXiv:1709.00869v1 [math.ST] 4 Sep 2017

ANNA BEN-HAMOU, ROBERTO I. OLIVEIRA, AND YUVAL PERES
Abstract. In this paper we discuss the problem of estimating graph parameters from
a random walk with restarts. In this setting, an algorithm observes the trajectory of
a random walk over an unknown graph G, starting from a vertex x. The algorithm
also sees the degrees along the trajectory. The only other power that the algorithm
has is to request that the random walk be reset to its initial state x at any given time,
based on what it has seen so far. Our main results are as follows. For regular graphs
G, one can estimate the number of vertices nG and the ℓ2 mixing time of G from x in
3/4
e √nG (tG
) steps, where tG
O(
unif )
unif is the uniform mixing time on G. The algorithm
is based on the number of intersections of random walk paths X, Y , i.e. the number of
times (t, s) such that Xt = Ys . Our method improves on previous methods by various
authors which only consider collisions (i.e. times t with Xt = Yt ). We also show that
the time complexity of our algorithm is optimal (up to log factors) for 3-regular graphs
with prescribed mixing times. For general graphs, we adapt the intersections algorithm
to compute the number of edges mG and the ℓ2 mixing time from the starting vertex
3/4
e √mG (tG
x in O(
) steps. Under mild additional assumptions (which hold e.g. for
unif )
sparse graphs) the number of vertices can also be estimated by this time. Finally,
we show that these algorithms, which may take sublinear time, have a fundamental
limitation: it is not possible to devise a sublinear stopping time at which one can be
reasonably sure that our parameters are well estimated. On the other hand, we show
that, given either mG or the mixing time of G, we can compute the “other parameter”
with a self-stopping algorithm.

1. Introduction
What can one learn about a graph from random walk trajectories on it? The (trivial)
answer is that, given enough time and resources, we can learn everything. If the graph
is connected, and one is willing to wait for long enough, eventually all edges of the graph
are crossed by the walk. Given some more time, one can even be nearly sure that no
other edges exist and it is safe to stop exploring the graph.
This paper is inspired by a more interesting question: what can one learn from the
random walk way before the graph is fully covered? Our motivation is the analysis of
large networks that can contain millions (or even billions) of nodes and edges. Direct
manipulation or full observations of such huge graphs are typically impractical. Randomwalk-based methods, which are local and lightweight, are often used in dealing with this
kind of graph (see Das Sarma et al. [8] and the references therein). Our problem, then, is
1

ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH RESTARTS

2

to determine the least number of random walk steps that are needed to compute interesting
graph parameters via random walks.
Our main contribution is to analyze this problem in an algorithmic model that we call
random walks with restarts (rwr). We assume our algorithm has black-box access to a
random walk on a graph G starting from a vertex x. At each time step t, the algorithm
sees the current vertex and its degree. It then decides whether it wants to jump to a
neighboring vertex, or to “reset” the walker back to x.
The algorithm produces an estimate γbt of a parameter γ = γ(G) of interest after t
time steps, solely by looking at the traces of the random walk and the vertex degrees
along the way. The goal is to achieve
∀t ≥ t0 :

PG
x



1
γbt
−1 ≤
γ(G)
2



≥ 1 − ε,

with t0 as small as possible.
In general, the time complexity parameter t0 will depend on the error parameter ε
and on unknown characteristics of the graph. This leads us to consider the possibility
of “self-stopping” algorithms that decide on their own when to stop exploring G.
Section 2 defines the rwr model and self stopping algorithms more precisely. For
now, we point out that our model is one of the most restrictive models for random walk
algorithms that actually make sense in real life. In practical settings, if we can simulate
a random walk over a graph G, we can most likely restart it at will, and also compute
degrees along the way.
1.1. What we do. In a nutshell, this paper gives nearly optimal algorithms for estimating the number of vertices, number of edges, and mixing time of G from the starting
point x in the rwr model. For regular graphs G, one can estimate these parameters
√ 3/4
with about n tunif random walk steps, where n is the number of vertices and tunif is the
√ 3/4
uniform mixing time of G. For general graphs, our algorithms use about m tunif steps,
where m is the number of edges (this requires minor assumptions on degrees in the case
of estimating n). For estimation of n in regular graphs, these complexity bounds on the
number of random walk steps are then shown to be optimal up to a factor of order at
most (log n)3/4 .
Let us describe our results in more detail, postponing the definition of the model to
Section 2. In Section 3, we review results by Peres et al. [17] on intersections of two
independent random walks X, Y on a regular graph. By definition, intersections are
pairs of times (t, s) with Xt = Ys . Using intersection counts givesus a simple algorithm

√
3/4 steps,
for estimating numbers of vertices nG of a regular graph G in O
nG (tG
)
unif

where tG
unif is its uniform mixing time.
In Section 4, we prove that this algorithm is optimal up to a factor of (ln nG )3/4 . More
specifically, for any pre-specified function t : N → N, we construct an infinite sequence
of 3-regular graphs G with uniform mixing time tG
unif = O(t(nG )). We then show that

ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH RESTARTS

3

any rwr algorithm !that finds the number of vertices of these graphs requires at least

3/4
√
tG
nG lnunif
time steps.
Ω
nG

Our next step is to consider arbitrary graphs G. In Section 5, we adapt the intersections algorithm to show that the number of edges mG of G can be estimated in time
√
3/4 ). Under simple assumptions – for instance, if G is sparse –, the same
O( mG (tG
unif )
bounds apply to estimating the number of vertices nG .
Up to this point all algorithms we described are essentially optimal for our model.
They are also space-efficient. They just need to store a single real number and maintain
a list of visits to each vertex, which is only read or changed during visits. Another
desirable trait of our algorithms is that they run in sub-linear time when the mixing
2/3
time is small (less than o(mG )). This property of (relatively) fast mixing is expected
to hold in social networks [12] and other large graphs.
However, our algorithms also suffer from a serious drawback: they are not selfstopping. As it turns out, this is unavoidable. We argue in Section 6 that self-stopping
algorithms for the number of vertices must cover nearly all edges of the graph. This is
true even if our graph is guaranteed to be 3-regular and have polylog mixing time. We
deduce that, while it may be possible to know the size of a graph after sub-linear time,
knowing that we already know the size may take much longer.
We complement these results by showing that if either mG or the mixing time is
known, the other parameter can be estimated with few steps via a self-stopping algorithm. In Section 7, we show how one can use an upper-bound τ on the mixing
time to compute
the number of
 edges √via a self-stopping algorithm with time com√
3/4
mG τ log log mG (or O( nG τ 3/4 log log nG ) steps if G is regular). Secplexity O
tion 8 then presents a result for estimating tx (δ), the ℓ2 -mixing time from x, with time
√
3/4 log log m ), assuming a good estimate for the number of
complexity O( mG (tG
G
unif )
edges is available. A corollary is that both the mixing time from x and the number
of edges m can be approximated
by a self-stopping algorithm with time complexity

√
O
mG τ 3/4 log log mG , assuming an upper-bound τ on the uniform mixing time is
available.
1.2. Background. Our result relates to the a large body of work on inferring graph (or
Markov chain) parameters from random walks. We give here a brief overview of these
papers, with a focus on results most closely resembling ours.
In some cases, one has to estimate parameters from a single path of the random walk.
One possibility is to use return times to the initial vertex to estimate nG or mG , as
proposed by Cooper et al. [7] and Benjamini et al. [3]. Other parameters, such as the
spectral gap, may be quite challenging to estimate (see Hsu et al. [9] and Levin and
Peres [13]). In any case, all of these algorithms require time that is at least of the order
of the number of vertices, whereas our own algorithms are sublinear in certain cases.
Another line of work, which is similar to our random walks with restarts, is to consider
several random walks on the same graph. Typically, estimators in this case rely on

ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH RESTARTS

4

collisions of random walks at their endpoints. Assume for instance that G is regular
and an upper bound for the mixing time is known. In order to find the number of
vertices of G, one can then run k random walks from point x for a time larger then
tmix . The endpoints form an independent sample with nearly uniform distribution over
the vertex set. There are then multiple methods for estimating the number of vertices,
most of which take advantage of the birthday paradox (see [6] for a review). As the
first collision in an i.i.d. drawn from the uniform distribution occurs at time of order
√
√
n, the running time of such procedures on regular graphs is typically O(tmix n). Less
√
brutal strategies allow to improve this upper-bound up to O(trel n), where trel is the
relaxation time of the walk. Similar methods may be designed to estimate the number of
edges and vertices in non-regular graphs Katzir et al. [11] and to estimate mixing times
Benjamini and Morris [2]. Our results show that random walk intersections, which take
whole trajectories into account, give strictly more information than collisions, and lead
to nearly optimal time dependence on the mixing time.
1.3. Future directions. Our results are just a first step towards understanding estimation via random walks. It would be interesting to understand what other graph
parameters can be computed efficiently in our model. Extensions of our results to oriented graphs and other models of access to the graph (including distributed access as in
[8]) would also be worthwhile.
2. Notation and definitions
Let G = (V, E) be a finite connected graph on nG vertices and mG edges. For u ∈ V ,
we let N (u) be the set of neighbors of u in G, and deg(u) = |N (u)| be the degree of u.
Let also
V=

∞
[

Vt,

t=0

the set of finite length sequences of elements of V .
2.1. Patterns of sequences. For t ≥ 0 and for a sequence of vertices ut0 = (u0 , . . . , ut ) ∈
V t+1 , let r(ui ) be the index of the first occurrence of ui in ut0 and define the pattern of ut0 as the length-(t + 1) sequence (r(u0 ), . . . , r(ut )), each vertex being replaced
by its rank of occurrence in ut0 . For instance, the pattern of (g, a, a, c, g, d, a, b, d) is
(1, 2, 2, 3, 1, 4, 2, 5, 4). Note that the pattern is invariant under vertex-relabelling. Also
let Φ be the map defined on V by: for all t ≥ 0, for all ut0 ∈ V t+1 ,


t

Φ(ut0 ) = (r(ui ), deg(ui ))

i=0

.

In other words, for each finite length sequence of vertices ut0 , the function Φ captures
the pattern and the sequence of degrees, and takes values in
S=

[

t≥0

(N × N)t .

From now on, the term pattern will actually refer to the function Φ.

ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH RESTARTS

5

2.2. Random walk with restarts and estimators. Fix x ∈ V and a map restart :
S → {0, 1}, and generate a sample as follows: initially X0 = x and for all s ≥ 0,
conditionally on X0s = (X0 , . . . , Xs ), the distribution of Xs+1 is given by: for all y ∈ V ,
P (Xs+1 = y | X0s ) =


1

{y=x}
 1
deg(Xs ) {y∈N (Xs )}

1

if restart (Φ(X0s )) = 1 ,
if restart (Φ(X0s )) = 0 ,

The sample X0t = (X0 , . . . , Xt ) will be called a random walk with restarts (rwr) at
x, and we denote by PG
x the corresponding probability measure over trajectories. To
avoid periodicity issues, it will be convenient to consider the lazy version of a rwr: if
restart (Φ(X0s )) = 0, the walk stays at its current position with probability 1/2, and
moves to a uniformly chosen neighbor with probability 1/2.
An estimator is a pair (restart, est) with restart : S → {0, 1} and est : S → R,

which returns the value est Φ(X0t ) for a rwr X0t characterized by restart. More
precisely, letting γ(G) be some parameter of interest (e.g. γ(G) = nG or γ(G) = mG ),
the goal is to produce a map restart : S → {0, 1} and an estimator est : S → R such
that, for all graph G = (V, E) for all starting point x ∈ V , for all t ≥ t(ε, G)
(2.1)

PG
x



1
est Φ(X0t )
−1 >
γ(G)
2

!

≤ ε,

for t(ε, G) as small as possible.
2.3. Lower bounds. The lower bound problem can be formalized as follows: we say
that t(G) is a lower bound for the estimation of γ(G) if there exists δ > 0 such that for
all function restart, for all estimator est, there exists an infinite sequence of graphs
G and x ∈ V (G) such that for all t ≤ δt(G),
(2.2)

PG
x



1
est Φ(X0t )
−1 >
γ(G)
2

!

≥

1
.
4

To obtain more refined lower bound, one may further require that all graphs in the
infinite sequence belong to some specified class.
2.4. Self-stopping algorithms. The time t(ε, G) above which inequality (2.1) holds
usually depends on unknown parameters of the graph, possibly on γ(G) itself. This
prompts the search for self-stopping algorithms.
In addition to the functions restart and est, self-stopping algorithms also rely on
a function stop : S → {0, 1}. Defining, for a rwr X0t (for a given function restart),




τ = inf{t ≥ 0, stop Φ(X0t ) = 1} ,
then the self-stopping algorithm defined by restart, stop and est returns the value
est (Φ(X0τ )). One then has to control the deviations of est (Φ(X0τ )) with respect to
γ(G) and the expectation of the stopping time τ .

ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH RESTARTS

6

3. Intersections and regular graphs
3.1. Definitions and preliminary results. Let G = (V, E) be a finite connected
regular graph with n vertices. Let X and Y be two independent lazy random walks
started at the same vertex x ∈ V . Define
It =

t−1 X
t−1
X

1{Xi =Yj } ,

i=0 j=0

i.e. It is the number of intersections between the trajectories of X and Y up to time
t − 1. Let also
gt (x, u) =

t−1
X

Px (Xi = u)

i=0

be the expected number of visits to vertex u before time t (also known as the Green’s
function). It is not hard to see that
(3.1)

Ex It =

X

gt (x, u)2 .

u∈V

Denote by tunif the uniform mixing time of the chain, i.e.


1
Px (Xt = y)
−1 ≤
,
tunif = inf t ≥ 0, max
x,y∈V
π(y)
4
where π is the stationary distribution of the chain. Also, letting 1 = λ1 > λ2 ≥ . . . ≥
λn ≥ 0 be the eigenvalues of the transition matrix of the walk, in decreasing order (the
fact that all eigenvalues are positive is by laziness of the walk), the relaxation time is
defined as
1
·
trel =
1 − λ2
For regular graphs, the following inequalities were established by Peres et al. [17].
Lemma 1 ([17]). Assume that G = (V, E) is a finite connected d-regular graph. Let
t⋆ = min {tunif , trel (log(trel ) + 1)} .
Then for all x ∈ V ,

t2
5t2
3/2
≤ Ex It ≤ Ct⋆ +
,
n
4n
for some universal constant C ≥ 0. Moreover
Ex It2

.

3/2
t⋆

t2
+
n

!

Ex It .

Here and throughout the paper, for two functions f, g, the notation f (n) . g(n) means
that there exists an absolute constant C > 0 such that f (n) ≤ Cg(n) for all n ≥ 1.
Let us note that a critical element in the proof of Lemma 1 is Aldous and Fill [1,
Proposition 6.16], which establishes that on regular graphs, for all t ≤ 5n2 ,
√
gt (x, x) ≤ 5 t .
(3.2)

ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH RESTARTS

7

3.2. A simple estimator for the number of vertices. Lemma 1 suggests the following simple estimator for the number of vertices in a regular graph: consider 2K
independent lazy random walks X (1) , Y (1) , . . . , X (K) , Y (K) all started at the same vertex
(k)
x ∈ V . For each k between 1 and K, let It be the number of intersections of X (k) and
Y (k) between 0 and t − 1, and define
(3.3)

bt =
n

t2

1
K

PK

(k)

k=1 It

·

This estimator clearly falls into the rwr model, the function restart being simply
given by




restart Φ(X0T ) =


1
0

if T + 1 ≡ 0

(mod t) ,

otherwise.

3/4 √
For t & t⋆
n and K large enough, this estimator starts returning a faithful value for
3/4 √
n, we have
n. Indeed, using Lemma 1, for a large enough constant A and t ≥ At⋆
3t2
t2
2
n ≤ Ex It ≤ 2n and Varx It . (Ex It ) . Hence, by Chebyshev’s Inequality

PG
x



bt
n
1
−1 >
n
2



≤

PG
x

K
2t2
1 X
(k)
It >
K k=1
n

!

+

K
2t2
1 X
(k)
It <
K k=1
3n

PG
x

!



1
= O
K



.

The case of the cycle on n vertices gives an example where this bound is tight. Indeed,
3/4 √
n ≍ n2 . And any procedure based on random
in this case, tunif ≍ trel ≍ n2 , and thus t⋆
walks requires at least order n2 steps to distinguish between a cycle of size n and a cycle
of size 2n. Section 4 is devoted to the elaboration of a more refined lower bound.
4. Lower bounds for regular graphs
For a given function t : N → N, let us denote by C(t) the class of connected 3-regular
graphs with uniform mixing time tG
unif smaller than t(nG ). Note that for the class C(t)
to be non-empty, one has at least to assume t(n) ≥ log(3n/4)
log(3) , which is a general lower
bound for the mixing time of 3-regular graphs (see [14, Chapter 7]).
Proposition 2. There exists δ > 0 such that for any function t : N → N with
t(·) ≥ 5 log(·), for any functions restart : S → {0, 1} and est : S → N, there exists an infinite sequence of 3-regular graphs G ∈ C(t) and x ∈ V (G) such that, for all

3/4
√
tG
t ≤ δ logunif
nG ,
nG
PG
x



est Φ(X0t )
1
−1 >
nG
2

!

≥

1
,
4

where X0t is a rwr characterized by restart.
Before proving Proposition 2, we first establish the following lemma.

ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH RESTARTS

8

Lemma 3. There exists k0 ≥ 1 such that for all even k ≥ k0 , there exists a connected
3-regular graph Ek with |V (Ek )|= k and x ∈ V (Ek ) satisfying
• tunif (Ek ) ≤ 5 log k,
• denoting Gt the subgraph spanned by the edges visited by a√random walk on Ek
with restarts at x (for any function restart), then, if t ≤ k/3,
PExk (Gt is a tree) ≥

(4.1)

3
·
4

Proof of Lemma 3. To establish Lemma 3, it is sufficient to show that, with positive
probability, a uniform random 3-regular graphs satisfy those properties. First, by the
results of [5], we know that, with probability tending to 1 with k, a uniform random
3-regular graph is an expander, and thus the mixing time of the simple random walk on
such a graph is of order log k. Lubetzky et al. [15] actually determine the precise order
of the mixing time: with probability tending to 1, a uniform random d-regular graphs
log k
d
on k vertices has mixing time equivalent to d−2
log(d−1) . For d = 3, we see that the first
property in Lemma 3 easily follows. Now, to establish (4.1), we use a common method to
generate a uniform 3-regular random graph, known as the configuration model (see [4]).
One initially considers k isolated vertices, each vertex v being endowed with 3 half-edges
(v, 1), (v, 2), (v, 3). A random matching on the half-edges is then chosen uniformly, and
each pair of half-edges is interpreted as an edge between the corresponding vertices. It is
well-known that Gk is simple with probability bounded away from 0 (see for instance [10]),
and that, conditionally on being simple, its distribution is uniform over simple 3-regular
graphs. One nice feature of this model is that it allows to generate sequentially and
simultaneously the graph and the random walk (with restarts), as follows. Let restart
be any function from S to {0, 1}. Initially, all half-edges are unpaired and X0 = x. Then,
at each step s ≥ 0,
• either restart (Φ(X0s )) = 1 and we set Xs+1 = x,
• or restart (Φ(X0s )) = 0 and we then choose with probability 1/3 a half-edge
(Xs , ∗) attached to Xs . If (Xs , ∗) has already been paired to some half-edge
(v, ∗), we let Xs+1 = v. Otherwise, we choose uniformly at random an unpaired
half-edge (u, ∗), match (Xs , ∗) and (u, ∗), and let Xs+1 = u.

With this procedure, it is not hard to see that the first cycle is formed at time s with
3s
(by time s, we have exposed at most 3s half-edges). Hence,
probability smaller than 3k−3s
√
3t2
. For t = k/3,
the (annealed) probability that Gt contains a cycle is smaller than 3k−3t
k
this probability is smaller than 1/8. If PG
x denotes the (quenched) probability associated
with the random walk on Gk with restarts at x, then, by Markov’s Inequality,
P



k
PG
x

1
(Gt is not a tree) >
4



≤

1
·
2

This entails that, with positive probability, a uniform 3-regular random graph satisfies (4.1).


ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH RESTARTS

9

In particular, it means that for any function restart, one can find a coupling (X, Y )
where X (resp. Y ) is a random
√ walk on Ek with restarts at x (resp. on E4k with restarts
at y), such that for all t ≤ k/3,
(4.2)





Px,y Φ(X0t ) = Φ(Y0t ) ≥

3
,
4

since, with probability 3/4, none of the walks is able to distinguish its base-graph from
a 3-regular infinite tree.
Let us now turn to the proof of Proposition 2.
Proof of Proposition 2. For k ≥ 1, consider a 3-regular graph Ek satisfying the properties
of Lemma 3. Now, in place of each edge e ∈ E(Ek ), put a path of length m ≥ 1. To
make the graph 3-regular, we add edges between pairs of interior vertices at distance 2
within the same path (assuming m − 1 is even). Let Gk,m be the resulting graph (see
Figure 1). Note that

Figure 1. The graph Gk,m (k = 8, m = 5). The
green star-shaped vertices are the original vertices
of Ek .
(4.3)

n(Gk,m ) = k + (m − 1)

3k
,
2

and, as the time needed to cross one path is of order m2 , the mixing time on Gm,k is
(4.4)





tunif (Gk,m ) = Θ m2 log k .

For any target function t (with t(·) ≥ 5 log(·)), and for an infinity of integers n, the
parameters k and m may be adjusted so that n(Gk,m ) = n and tunif (Gk,m ) ≤ t(n).
We now consider the graphs Gk,m on n vertices and G4k,m on 4n vertices. Combining
equation (4.2) and the m2 -slow down induced by paths, we get that we can find δ > 0,
starting points (x, y) ∈ V (Gk,m ) × V (G4k,m ), and a coupling (X, Y ) of random walks

ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH RESTARTS

10

with restarts at x and y (for the same function restart) such that
n
o
√
2
and t = δm2 k .
(4.5)
Px,y (At ) ≥ , with At = Φ(X0t ) = Φ(Y0t )
3
Let est : S → N be an estimator, and define
BtX

=

(



1
est Φ(X0t )
3
≤
≤
2
n
2

)

,

BtY

and


=



(



est Φ(Y0t )
3
1
≤
≤
2
4n
2




)

.

Assume that it holds simultaneously that Px BtX ≥ 3/4 and Py BtY ≥ 3/4. Then,
by (4.5),






Px,y BtX ∩ At
1 − Px BtX
5
≥1−
≥ ,
Px,y BtX | At =
Px,y (At )
Px,y (At )
8




and similarly, Px,y BtY | At ≥ 58 , so that




1
.
4
Y
However, on the event At , the events BtX and
 implying


 Bt cant not occur simultaneously,
est(Φ(Y0t ))
est(Φ(X0 ))
1
1
1
− 1| > 2 ≥ 4 or Py |
− 1| > 2 ≥
a contradiction. Hence, we either have Px |
n
4n
1
4.

Px,y BtX ∩ BtY | At

≥

The proof is then concluded by noticing that, thanks to (4.3) and (4.4),


√
tunif 3/4 √
m2 k &
n.
log n


5. Computing parameters of general graphs
5.1. Intersections on general graphs. To deal with non-regular graphs, it will be
convenient to consider a weighted version of the number of intersections, which we call
the weighted number of intersections, defined as
It =

t−1 X
t−1
X

1
,
1
deg(Xi ) {Xi =Yj }
i=0 j=0

where X and Y are two independent lazy simple random walks on G.
As in the previous section, tunif and trel are respectively the uniform mixing time and
the relaxation time of the walk, and t⋆ = min {tunif , trel (log(trel ) + 1)}. The following
Lemma is an analogue of Lemma 1 for non-regular graphs..
Lemma 4. For all x ∈ V ,

5t2
t2
3/2
≤ Ex It ≤ 12t⋆ +
·
2m
8m

Moreover
Ex It2

.

3/2
t⋆

t2
+
2m

!

Ex It .

ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH RESTARTS

11

Let us first state the following generalization to general graphs of inequality (3.2), as
established by Lyons [16, Lemma 3.4].
Lemma 5 (Lyons [16]). For a lazy random walk X on G, for all t ≥ 0,
4 deg(x)
Px (Xt = x) ≤ π(x) + √
·
t+1

√
Note that Lemma 5 implies that gt (x, x) ≤ tπ(x) + 8 deg(x) t for all t ≥ 0, which in
turn yields that
√
(5.1)
∀t ≤ 16m2 , gt (x, x) ≤ 10 deg(x) t .
Let us also recall the following alternative bound on the return probabilities, which
follows for instance from [14, Inequality 12.11].
Claim 6. For all x ∈ V and t ≥ 0,

Px (Xt = x) ≤ π(x) + λt2 .

We are now ready to prove Lemma 4.
Proof of Lemma 4. Using Jensen’s Inequality,
Ex It =

X gt (x, u)2
u

≥ 2m

deg(u)
X
u

π(u)

= 2m

X

π(u)

u

gt (x, u)
deg(u)

!2

=



gt (x, u)
deg(u)

2

t2
,
2m

establishing the lower bound on the first moment. For the upper bound, the weighting
in the definition of It allows us to use reversibility and obtain that
Ex It =
(5.2)

=

t−1 X
X
1
Px (Xi = u)Pu (Xj = x)
deg(x) i,j=0 u
t−1
X
1
Px (Xi+j = x) .
deg(x) i,j=0

Dividing the sum according to whether i + j ≥ t⋆ , we obtain
(5.3)

Ex It ≤

tX
t−1
⋆ −1
X
1
1
(k + 1)Px (Xk = x) +
Px (Xi+j = x) .
deg(x) k=0
deg(x) i,j=0
i+j≥t⋆

For the first term in the right-hand side of (5.3), we note that as t⋆ ≤ tunif and as,
on all connected graphs tunif ≤ 8mn (combining for instance [1, Corollary 6.8] and [14,
Theorem 10.14]), we may resort to inequality (5.1) and get
tX
⋆ −1
1
(k + 1)Px (Xk = x) ≤
deg(x) k=0

t⋆ gt⋆ (x, x)
3/2
≤ 10t⋆ .
deg(x)

ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH RESTARTS

12

For the second term in the right-hand side of (5.3), we consider two cases. The first
case is when t⋆ = tunif . Then, we use that for all i, j such that i + j ≥ tunif , we have
Px (Xi+j = x) ≤ 5 deg(x)
8m , which gives
t−1
X
1
Px (Xi+j = x) ≤
deg(x) i,j=0

5t2
.
8m

i+j≥t⋆

In the second case, t⋆ = trel (log(trel ) + 1). Then, we use Claim 6, and obtain
t−1
X
1
Px (Xi+j = x) ≤
deg(x) i,j=0
i+j≥t⋆

≤

+∞
X
t2
+
(k + 1)λk2
2m k=t
⋆

t2
+ λt2⋆
2m



t⋆
1
+
1 − λ2 (1 − λ2 )2

t2
+ 2t⋆ .
2m
Altogether, we have checked that for all x ∈ V and t ≥ 0,



≤

3/2

Ex It ≤ 12t⋆

+

5t2
,
8m

as desired.
Moving on to the bound on the second moment, we have
Ex It2 =
.

X
u,v

X gt (x, u)2 gt (u, v)2

deg(u) deg(v)

u,v

=

X gt (x, u)2
u

.

2



X
1

Px (Xi = u, Xk = v)
deg(u) deg(v) 0≤i,k≤t−1

deg(u)

3/2
t⋆

t2
+
2m

Eu It

!

Ex It ,

by the previously established upper-bound on the first moment.



5.2. A simple estimator for the number of edges. Lemma 4 suggests the following
simple estimator for the number of edges, namely:
(5.4)
n

o
(k) K

bt =
m

t2

2
K

PK

(k)
k=1 It

,

where It
are independent copies of It , the weighted number of intersections
k=1
between to independent random walks started at some x ∈ V . Using Lemma 4, for a large

ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH RESTARTS
3/4 √
t2
m, we have 2m
≤ Ex It ≤
enough constant A and t ≥ At⋆
Hence, by Chebyshev’s Inequality

 

bt
1
1
m
G
−1 >
=O
.
Px
m
2
K

3t2
4m

13

and Varx It . (Ex It )2 .

Remark 1. Note that once we have a good estimate for the number of edges, it is quite
easy to deduce an estimate for the number of vertices. Indeed, what remains to estimate
1
is just the mean degree. Consider the function f : x ∈ V 7→ f (x) = deg(x)
, and note
n
that Eπ f = 2m . Applying [14, Proposition 12.19] to the function f , we know that for
Varπ f
r ≥ tmix (ε/2) and t ≥ η24ε(E
2 trel , for all x ∈ V ,
πf)
Px

t−1
1X
f (Xr+s ) − Eπ f > ηEπ f
t s=0

!

≤ ε.

1 X
deg(u)−1 , we see that estimating the mean de2m u∈V
m X
deg(u)−1 . Under some weak assumpgree can be done in time of order tmix + trel 2
n u∈V
tion on the degrees’ heterogeneity, or assuming that the graph is sparse (m = O(n)), the
3/4 √
m (see [17, Claim 4.4]).
dominant term in this sum is tmix , which is smaller than t⋆

Observing that Varπ f ≤ Eπ f 2 =

b t and m
b t defined at (3.3) and (5.4) thus start “being right” after times
The estimators n
3/4 √
and t⋆
m respectively. In practice however, a user would want to know when
to stop the random walks. This prompts the search for self-stopping procedures. The
next section, however, is devoted to establishing a negative result: there is no sublinear
self-stopping algorithm for the estimation of the number of vertices.
3/4 √
n
t⋆

6. No self-stopping algorithms in general
In this section, we show that one can not hope for a general sublinear self-stopping
algorithm, even with the restriction that the graphs have polylog mixing time.
3
Let C be the class of graphs G such that tG
unif ≤ (log nG ) .
Proposition 7. There exists δ > 0, such that, for all functions restart, stop and
est, there is an infinite sequence of graphs G ∈ C and x ∈ V (G) such that
PG
x



{τ ≥ δnG } ∪



1
est (Φ(X0τ ))
−1 >
nG
2



≥

1
,
4

where X0t is a rwr characterized by restart and τ = inf{t ≥ 0, stop (Φ(X0τ )) = 1}.
Proof of Proposition 7. Consider a 3-regular expander G on nG = n vertices and another
n
graph H obtained from G as follows: let G(1) , . . . , G(2 ) be 2n identical copies of G. For
all i ∈ {1, . . . , 2n }, choose three distinct vertices (ui1 , ui2 , ui3 ) uniformly at random in
e be some other 3-regular expander on 2n vertices, labelled from 1 to
V (G(i) ). Now let G
e by a label in {1, 2, 3} in such a way that no pair of
2n . One may mark each edge of G
edges incident to the same vertex have the same label. Now if there is an edge between

ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH RESTARTS

14

e and if this edge has label k ∈ {1, 2, 3}, then we create an edge
vertices i and j in G
i
e
between vertices uk and ujk . Let H be the resulting graph (nH = n2n ). Note that, as G
is an expander, and as the random walk on H needs order n steps to go from some ui1
n
to either ui2 or ui3 , we have tH
unif . n log(2 ), so that both G and H belong to the class
C. It is not hard to check that one can find y ∈ V (G(1) ) and δ > 0, such that for any
function restart,
!
δn n
o
\
2
H
1 1 1
Py
Ys 6∈ {u1 , u2 , u3 }
≥ ·
3
s=0

Therefore, there exist starting points (x, y) ∈ V (G) × V (H), and a coupling (X, Y ) of
random walks with restarts at x and y (for the same function restart) such that
n
o
2
, with At = Φ(X0t ) = Φ(Y0t )
and t = δn .
3
Let est : S → N be an estimator and stop : S → {0, 1}. Define

(6.1)

Px,y (At ) ≥

X
BG
= {τ X < δnG } ∩

and
Y
BH
= {τ Y < δnH } ∩




X
 est Φ(X0τ )


nG



nH




Y
 est Φ(Y0τ )



1
−1 ≤
,
2


1
−1 ≤
,
2

Y
s
inf {s ≥ 0, stop (Φ(Y0s )) = 1}. Aswhere τ X = inf {s ≥ 0, stop(Φ(X
 0 )) = 1} and τ  = 
X ≥ 3/4 and P
Y
sume that we both have Px BG
y BH ≥ 3/4. Then, by (6.1),





X
| At =
Px,y BG







X ∩A
Px,y BG
t

Px,y (At )



≥1−

5
Y |A
and similarly, Px,y BH
t ≥ 8 , so that



X
Y
∩ BH
| At
Px,y BG



≥



X
1 − P x BG

Px,y (At )



≥

5
,
8

1
.
4

Y
X < δn } ∩ {τ Y =
However, on the event
At ,we have{τ X < δn
G } ∩ {τ < δnH } = {τ
G


Y
X
X and B Y can not occur
τ X }, so that est Φ(X0τ ) = est Φ(Y0τ ) and the events BG
H
simultaneously, implying a contradiction.


7. A self-stopping algorithm for the number of edges
Let G = (V, E) be a finite connected graph. Initially, the only information we have
about G is an upper-bound τ on the uniform mixing time tunif (1/4), and access to a
random walk with restarts at a fixed vertex x ∈ V . The goal is to estimate m = |E|.
The algorithm is as follows (and borrows several ideas from [2]). For q = 0, 1, . . . ,
iterate the following procedure until stopped:
√
b = 2q be the current guess for the number of edges and let t = tq = τ 3/4 2m.
b
• let m

ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH RESTARTS

15

• let R = Rq = ⌈8 log(2/ε) + 8C log q⌉ (for a constant C to be specified later) and
repeat the following experiment R times.
– let X (1) , Y (1) , . . . , X (K) , Y (K) be 2K independent random walks started
from x (for a fixed integer K ≥ 1 to be specified later) and define
K
1 X
(ℓ)
I ,
K ℓ=1 t

Wt =

(ℓ)

where

It

=

t−1
X

1

(ℓ)
i,j=0 deg(Xi )

1n

(ℓ)

(ℓ)

Xi =Yj

o.

– If Wt ≥ 8τ 3/2 , call the experiment a success.
• If the number of successes is larger than R/2, then stop and estimate m by
b = 2q ; otherwise, go from q to q + 1.
m

This algorithm satisfies the two following properties.

Fact 1. The probability that the algorithm stops at a value of q such that 2q ≤ m/2 is
smaller than ε.
√

mτ 3/4 log log m .
Fact 2. The expected running time of the algorithm is O
Proof of Fact 1. Note that, by Lemma 4, it always holds that

b 3/2
b
m
m
τ
≤ Ex Wt ≤ 14 τ 3/2 .
m
m
b = 2q ≤ m/2, the expectation of Wt is smaller
Hence, assuming that q is such that m
than 7τ 3/2 . By Chebyshev’s Inequality,

(7.1)



Px Wt ≥ 8τ 3/2





Now by Lemma 4, Varx It . τ 3/2 +


such that Px Wt ≥ 8τ 3/2





≤ Px Wt − Ex Wt ≥ τ 3/2
t2
m

2



.

Varx It
.
Kτ 3

. τ 3 . Hence, we may choose K large enough

≤ 1/4. Using Hoeffding’s Inequality, the probability that

there are more than R/2 successes is smaller than exp (−R/8) = 2ε q −C . Choosing C
large enough and taking a union bound, we obtain that the probability for the algorithm
to return an estimate smaller than m/2 is smaller than ε.

Proof of Fact 2. Let q be such that 2q ≥ m. By equation (7.1), the expectation of Wt is
larger than 14τ 3/2 . Hence


Px Wt ≤ 8τ

3/2



≤ Px



4
Wt ≤ E x Wt
7



.

Varx It
·
K (Ex It )2

Again, Lemma 4 entails that the constant K may be chosen such that the above probability is smaller than 1/4. If q ⋆ = inf{q ≥ 0, 2q ≥ m}, then, for all q > q ⋆ , the probability
⋆
that the algorithm stops at step q is smaller than (1/4)q−q . Now when the algorithm
stops at step q, the running time is smaller, up to constant factors, than
q
X
i=0

Ri t i . Rq t q ,

ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH RESTARTS

16

so that the expected running time is smaller up to constant factors, than
Rq ⋆ t q ⋆ +

X  1 q−q ⋆

4

q>q ⋆

Rq t q = O

√



mτ 3/4 log log m .


Remark 2. On d-regular graphs, one may simplify this algorithm using the unweighted
number of intersections and resorting to Lemma 1, and obtain an algorithm
which es
√
timates n, the number of vertices, in expected time O τ 3/4 n log log n , without any
further dependence in d than the one which might comes from τ .
8. Algorithms for the mixing time
The number of intersections may also be used to estimate the mixing time from a
given vertex x ∈ V . Assume that the number of edges m in G = (V, E) is known. Let
dx (t) =

v
u
2

uX
Px (Xt = y)
t
−1
π(y)

π(y)

y

be the ℓ2 -distance between Px (Xt ∈ ·) and π(·). Our goal now is to estimate
n

o

tx (δ) = inf t ≥ 0, dx (t)2 ≤ δ ,

for 0 < δ < 1. By reversibility, dx (t)2 =
(8.1)

Ex It =

Px (X2t =x)
π(x)

t−1 d
X
x

i,j=0



− 1, so that, using (5.2),


i+j 2
2

+1

2m

·

Equation (8.1) suggests the following self-stopping algorithm. For q = 0, 1, . . . , iterate
the following procedure until stopped:
• Let t = tq = 2q be the current guess for the mixing time tx (δ) and let
( √ )'
&
m
C1
max 1, 1/4
,
K = Kq =
2
δ
t
for a constant C1 > 0 to be specified later.
• Let R = Rq = ⌈8 log(2/ε) + 8C2 log q⌉ (for a constant C2 to be specified later)
and repeat the following experiment R times.
– Let X (1) , . . . , X (K) be K independent random walks started from x and
define
Jt =

1

X

K
2 1≤ℓ<k≤K



(ℓ,k)

Jt



2

,

where

(ℓ,k)

Jt

=

2t−1
X

1
(ℓ)

i,j=t deg(Xi )

1n

(ℓ)

(k)

Xi =Xj

o.

t
, call the experiment a success.
– If Jt ≤ 1 + 2δ 2m
• If the number of successes is larger than R/2, then stop and estimate tx (δ) by
t = 2q ; otherwise, go from q to q + 1.

ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH RESTARTS

17

This algorithm satisfies the two following properties.
Fact 3. The probability that the algorithm stops at a value of q such that 2q ≤ tx (δ)/2
is smaller than ε.
Fact 4. The expected running time of the algorithm is
!
√
m
3/4
tx (δ/4) log log tx (δ/4) .
O
δ2
Before analysing this self-stopping algorithm, we prove the following useful lemma.
Lemma 8. Let X, Y, Z be three independent random walks started at x and let
(X,Y )
Jt

2t−1
X

1
.
1
deg(Xi ) {Xi =Yj }
i,j=t

=

(X,Z)

Define similarly Jt
to be the weighted number of intersections of X and Z between
time t and 2t. Then for all t ≥ 0,
(X,Y )

(8.2)

(X,Y )

Varx Jt

and
Covx

(8.3)



. max {Eu It } Ex Jt

,

u∈V

(X,Z)
(X,Y )
, Jt
Jt



.

r




(X,Y ) 3/2

max {Eu It } Ex Jt
u∈V

.

Proof of Lemma 8. Let us define
2t−1
X

gt→2t (x, u) =

i=t

One easily checks that

Px (Xi = u) = g2t (x, u) − gt (x, u) .

(X,Y )

=

Ex Jt
and that
Ex




(X,Y ) 2
Jt



.

X gt→2t (x, u)2
u

deg(u)

X gt→2t (x, u)2 gt (u, v)2

deg(u) deg(v)

u,v

=

,

X gt→2t (x, u)2
u

deg(u)

Eu It .

Taking the maximum over u ∈ V of Eu It establishes inequality (8.2). Moving on to the
covariance, we have


(X,Y )

Ex Jt

(X,Z)

Jt



.

u,v

and, by Cauchy-Schwarz Inequality,
Ex



(X,Y ) (X,Z)
Jt
Jt



X gt→2t (x, u)2 gt (u, v)gt→2t (x, v)

.

(X,Y )
Ex Jt

deg(u) deg(v)

s
X gt→2t (x, u)2
u

deg(u)

Again, maximizing Eu It over u ∈ V establishes inequality (8.3).

,

Eu It .


ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH RESTARTS

18

Remark 3. By the results of Section 5, we know that for all t ≤ 16m2 ,
max {Eu It } . t3/2 ,
u∈V

whereas for t ≥ 16m2 , as tunif ≤ 8m2 ,
max {Eu It } .
u∈V

t2
·
2m

We are now ready to prove Facts 3 and 4.
Proof of Fact 3. Assume that q is such that t = 2q ≤ tx (δ)/2. By equation (8.1), the
t2
. By Chebyshev’s Inequality,
expectation of Jt is larger than (1 + δ) 2m
Px



δ
Jt ≤ 1 +
2



t2
2m

!

Varx Jt
·
2
x Jt )

.

We have

δ2 (E


(X,Y )

(X,Z)



(X,Y )
, Jt
Covx Jt
Varx Jt
Varx Jt .
+
·
K2
K
Now combining Lemma 8 and Remark 3, we see that the constant C1 in the definition
of K can be made large enough so that the above probability is smaller than 1/4. Using
Hoeffding’s Inequality, the probability that there are more than R/2 successes is then
smaller than exp (−R/8) = 2ε q −C2 . Choosing C2 large enough and taking a union bound,
we obtain that the probability for the algorithm to return an estimate smaller than
tx (δ)/2 is smaller than ε.

2

t
and by
Proof of Fact 4. Let q be such that t = 2q ≥ tx (δ/4). Then Ex Jt ≤ (1 + δ/4) 2m
Chebyshev’s Inequality

Px



δ
Jt > 1 +
2



t2
2m

!

.

Varx Jt
.
2
x Jt )

δ2 (E

As in the proof of Fact 3, combining Lemma 8 and Remark 3, and taking C1 large enough,
the above probability is smaller than 1/4. Hence, if q ⋆ = inf{q ≥ 0, 2q ≥ tx (δ/4)}, then
⋆
for all q > q ⋆ , the probability that the algorithm stops at q is smaller than (1/4)q−q .
Now, the running time up to some step q is smaller, up to constant factors, than
√
q
X
m
Ri Ki ti .
(tq )3/4 log q .
2
δ
i=0
Altogether, the expected running time is less, up to constant factor, than
√
√
X
m
m
⋆
3/4
⋆
q−q
(tq⋆ ) log q +
(tq )3/4 log q ,
(1/4)
2
2
δ
δ
⋆
q>q
which is O

√

m

δ2



tx (δ/4)3/4 log log tx (δ/4) .



ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH RESTARTS

19

Remark 4. On d-regular graphs, one may simplify this algorithm using the unweighted
number of intersections, and obtain an algorithm that estimates tx (δ) in expected time
!
√
n
3/4
tx (δ/4) log log tx (δ/4) .
O
δ2
We assume, for simplicity, that the true value of m is known. However, our estimation
scheme can easily be extended to the case where only a good approximation of m is
available. In Section 7, we showed how an upper-bound on the uniform mixing could be
used to devise a self-stopping algorithm returning a faithful estimate for the number of
edges, entailing the following.
Corollary 9. An upper-bound τ on the uniform mixing time can be used to precisely estimate both the number of
time from x, via a self-stopping algorithm
√edges and the mixing

mτ 3/4 log log m .
with time complexity O

Acknowledgement. The question of estimating the mixing time with random walks
trajectories was posed by Gábor Lugosi, during the Eleventh annual workshop in Probability and Combinatorics, Barbados, April 1-8, 2016. We are grateful to him for bringing
this problem to our attention, and we thank the Bellairs Institute where this work was
initiated. RO was funded by a Bolsa de Produtividade em Pesquisa from CNPq, Brazil
and a Cientista do Nosso Estado grant from FAPERJ, Rio de Janeiro, Brazil. His work
in this article is part of the activities of FAPESP Center for Neuromathematics (grant
# 2013/ 07699-0 , FAPESP - S.Paulo Research Foundation). AB was funded by a
post-doctoral scholarship from CNPq, Brazil.
References

[1] D. Aldous and J. Fill. Reversible Markov chains and random walks on graphs, 2002.
URL https://www.stat.berkeley.edu/~aldous/RWG/book.html.
[2] I. Benjamini and B. Morris. The birthday problem and markov chain monte carlo.
arXiv preprint math/0701390, 2007.
[3] I. Benjamini, G. Kozma, L. Lovász, D. Romik, and G. Tardos. Waiting for a bat
to fly by (in polynomial time). Combinatorics, Probability and Computing, 15(5):
673–683, 2006. doi: 10.1017/S0963548306007590.
[4] B. Bollobás. A probabilistic proof of an asymptotic formula for the number of
labelled regular graphs. European Journal of Combinatorics, 1(4):311–316, 1980.
[5] A. Broder and E. Shamir. On the second eigenvalue of random regular graphs. In
Foundations of Computer Science, 1987., 28th Annual Symposium on, pages 286–
294. IEEE, 1987.
[6] J. Bunge and M. Fitzpatrick. Estimating the number of species: a review. Journal
of the American Statistical Association, 88(421):364–373, 1993.
[7] C. Cooper, T. Radzik, and Y. Siantos. Estimating network parameters using random
walks. Social Network Analysis and Mining, 4(1):168, 2014.

ESTIMATING GRAPH PARAMETERS VIA RANDOM WALKS WITH RESTARTS

20

[8] A. Das Sarma, D. Nanongkai, G. Pandurangan, and P. Tetali. Distributed random
walks. J. ACM, 60(1):2:1–2:31, feb 2013. ISSN 0004-5411. doi: 10.1145/2432622.
2432624. URL http://doi.acm.org/10.1145/2432622.2432624.
[9] D. J. Hsu, A. Kontorovich, and C. Szepesvári. Mixing time estimation in reversible
markov chains from a single sample path. In Advances in neural information processing systems, pages 1459–1467, 2015.
[10] S. Janson. The probability that a random multigraph is simple. Combinatorics,
Probability and Computing, 18(1-2):205–225, 2009.
[11] L. Katzir, E. Liberty, O. Somekh, and I. A. Cosma. Estimating sizes of social
networks via biased sampling. Internet Mathematics, 10(3-4):335–359, 2014.
[12] J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney. Community structure in
large networks: Natural cluster sizes and the absence of large well-defined clusters.
Internet Mathematics, 6(1):29–123, 2009. doi: 10.1080/15427951.2009.10129177.
URL http://dx.doi.org/10.1080/15427951.2009.10129177.
[13] D. A. Levin and Y. Peres. Estimating the spectral gap of a reversible markov chain
from a short trajectory. arXiv preprint arXiv:1612.05330, 2016.
[14] D. A. Levin, Y. Peres, and E. L. Wilmer. Markov chains and mixing times. American
Mathematical Soc., 2009.
[15] E. Lubetzky, A. Sly, et al. Cutoff phenomena for random walks on random regular
graphs. Duke Mathematical Journal, 153(3):475–510, 2010.
[16] R. Lyons. Asymptotic enumeration of spanning trees. Combinatorics, Probability
and Computing, 14(04):491–522, 2005.
[17] Y. Peres, T. Sauerwald, P. Sousi, A. Stauffer, et al. Intersection and mixing times
for reversible chains. Electronic Journal of Probability, 22, 2017.
A. Ben-Hamou
IMPA, Estrada Dona Castorina, 110, Rio de Janeiro 22460-320, Brazil.
E-mail address: benhamou@impa.br
R. Oliveira
IMPA, Estrada Dona Castorina, 110, Rio de Janeiro 22460-320, Brazil.
E-mail address: rimfo@impa.br
Y. Peres
Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA.
E-mail address: peres@microsoft.com

