We present a deterministic logspace algorithm for solving
S-T CONNECTIVITY on directed graphs if (i) we are given a stationary
distribution of the random walk on the graph in which both of the input
vertices s and t have nonnegligible probability mass and (ii) the random walk which
starts at the source vertex s has polynomial mixing time. This result generalizes the recent
deterministic logspace algorithm for S-T CONNECTIVITY on undirected graphs (Reingold,
STOC `05). It identifies knowledge of
the stationary distribution as the gap between the S-T CONNECTIVITY problems we
know how to solve in logspace (L) and those that capture all of randomized
logspace (RL).