Multiplicative Approximations of Random Walk Transition Probabilities

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].