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