  In this paper, we provide faster algorithms for computing various fundamental
quantities associated with random walks on a directed graph, including the
stationary distribution, personalized PageRank vectors, hitting times, and
escape probabilities. In particular, on a directed graph with $n$ vertices and
$m$ edges, we show how to compute each quantity in time
$\tilde{O}(m^{3/4}n+mn^{2/3})$, where the $\tilde{O}$ notation suppresses
polylogarithmic factors in $n$, the desired accuracy, and the appropriate
condition number (i.e. the mixing time or restart probability).
  Our result improves upon the previous fastest running times for these
problems; previous results either invoke a general purpose linear system solver
on a $n\times n$ matrix with $m$ non-zero entries, or depend polynomially on
the desired error or natural condition number associated with the problem (i.e.
the mixing time or restart probability). For sparse graphs, we obtain a running
time of $\tilde{O}(n^{7/4})$, breaking the $O(n^{2})$ barrier of the best
running time one could hope to achieve using fast matrix multiplication.
  We achieve our result by providing a similar running time improvement for
solving directed Laplacian systems, a natural directed or asymmetric analog of
the well studied symmetric or undirected Laplacian systems. We show how to
solve such systems in time $\tilde{O}(m^{3/4}n+mn^{2/3})$, and efficiently
reduce a broad range of problems to solving $\tilde{O}(1)$ directed Laplacian
systems on Eulerian graphs. We hope these results and our analysis open the
door for further study into directed spectral graph theory.
