2011 | OriginalPaper | Chapter
Multiplicative Approximations of Random Walk Transition Probabilities
Authors : Michael Kapralov, Rina Panigrahy
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study the space and time complexity of approximating distributions of
l
-step random walks in simple (possibly directed) graphs
G
. While very efficient algorithms for obtaining
additive
ε
-approximations have been developed in the literature, no non-trivial results with multiplicative guarantees are known, and obtaining such approximations is the main focus of this paper. Specifically, we ask the following question: given a bound
S
on the space used, what is the minimum threshold
t
> 0 such that
l
-step transition probabilities for all pairs
u
,
v
∈
V
such that
$P_{uv}^l\geq t$
can be approximated within a 1±
ε
factor? How fast can an approximation be obtained?
We show that the following surprising behavior occurs. When the bound on the space is
S
=
o
(
n
2
/
d
), where
d
is the minimum out-degree of
G
, no approximation can be achieved for non-trivial values of the threshold
t
. However, if an extra factor of
s
space is allowed, i.e.
$S=\tilde \Omega(sn^2/d)$
space, then the threshold
t
is
exponentially small in the length of the walk l
and even very small transition probabilities can be approximated up to a 1±
ε
factor. One instantiation of these guarantees is as follows: any almost regular directed graph can be represented in
$\tilde O(l n^{3/2+{\epsilon}})$
space such that all probabilities larger than
n
− 10
can be approximated within a (1±
ε
) factor as long as
l
≥ 40/
ε
2
. Moreover, we show how to estimate of such probabilities faster than matrix multiplication time.
For undirected graphs, we also give small space oracles for estimating
$P^l_{uv}$
using a notion of bicriteria approximation based on approximate distance oracles of Thorup and Zwick [STOC’01].