Sampling a random walk is a fundamental primitive in many graph applications. In the streaming model, it is known that sampling an $L$-step random walk on an $n$-vertex directed graph requires $\Omega(n L)$ space, implying that no sublinear-space streaming algorithm exists for general graphs.

We show that sublinear algorithms are possible for the case of dense graphs, where every vertex has out-degree at least $\Omega(n)$. In particular, we give a one-pass turnstile streaming algorithm that uses only $\tilde{\mathcal{O}}(L)$ memory for such graphs. More broadly, for graphs with minimum out-degree at least $d$, our streaming algorithm samples a random walk using $\tilde{\mathcal{O}}(\frac{n}{d} \cdot L)$ memory.

We show that our algorithm is optimal in a strong ``beyond worst-case'' sense. To formalize this, we introduce the notion of universal optimality for graph streaming algorithms. Informally, a streaming algorithm is universally optimal if it performs (almost) as well as possible on every graph, assuming a worst-case choice of the streaming order. This notion of universal optimality is a key conceptual contribution of our work.