Late points for random walks and the fluctuations of cover times
Speaker: | Roberto Imbuzeiro Oliveira |
---|---|
Affiliation: | IMPA - Rio de Janeiro |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
How
long
does
it
take
for
a
random
walk
to
visit
all
vertices
of
a
finite
graph
G?
What
is
the
distribution
of
this
so-called
cover
time?
And
what
do
the
last
k
vertices
to
be
covered
look
like?
Little
is
known
about
the
last
two
questions,
in
spite
of
great
interest
in
cover
times
(eg.
in
the
CS
community)
since
the
early
90's.
The
general
theme
of
this
talk
is
that,
under
certain
conditions,
the
late
stages
of
coverage
of
a
large
graph
G
look
like
what
one
sees
in
a
large
complete
graph.
In
particular,
we
obtain
that,
after
a
time
rescaling:
1.
the
law
of
the
cover
time
is
approximately
the
Gumbel
law;
2.
for
any
constant
k,
the
last
k
points
to
be
covered
are
essentially
uniformly
distributed;
and
3.
uncovered
points
at
a
time
t0
later
become
covered
at
times
that
are
approximatelly
independent
exponential
random
variables.
Our
results
apply
to
all
examples
where
1
was
previously
known,
including
tori
with
d≥
3
dimensions
(a
very
recent
result
by
Belius).
They
also
apply
to
other
graphs
and
digraphs
which
are
"locally
recurrent"
such
as
large-girth
expanders
and
random
regular
graphs.
Our
techniques
include
new
general
results
about
the
joint
distribution
of
hitting
time
and
of
the
point
hit
of
a
"nice"
subset
of
vertices.
(Joint
work
with
Alan
Prata.)