Approximating Random Walks in $\tilde{O}(\log n+{\log }^2\kappa )$ Space for $\kappa$-Conditioned Graphs

Abstract

For $\kappa >1$, a directed graph is $\kappa$-conditioned if it is $\kappa$-mixing and its stationary distribution is approximated by the uniform distribution within a factor of $\kappa$. We present a deterministic algorithm that approximates the stationary distribution of a $\kappa$-conditioned graph to inverse polynomial relative error in $O((\log n+{\log }^2\kappa )\log \log n)$ space. In the regime $\kappa =\exp (\Theta ({\log }^{\alpha }n))$ for any $\alpha \in (0,2/3)$, our result improves the best-known $O(\log n\sqrt{\log \kappa }/\sqrt{\log \log n})$ space bound for approximating $\kappa$-step random walks in general directed graphs by [Hoza, RANDOM 2021]. We release this preliminary version due to recent rumors of LLM-based progress on related problems and uncertainty about when those results may appear. Further implementation details will be provided in a subsequent version.