  For a graph $G$ on $n$ vertices, naively sampling the position of a random
walk of at time $t$ requires work $\Omega(t)$. We desire local access
algorithms supporting $\text{position}(G,s,t)$ queries, which return the
position of a random walk from some start vertex $s$ at time $t$, where the
joint distribution of returned positions is $1/\text{poly}(n)$ close to the
uniform distribution over such walks in $\ell_1$ distance.
  We first give an algorithm for local access to walks on undirected regular
graphs with $\widetilde{O}(\frac{1}{1-\lambda}\sqrt{n})$ runtime per query,
where $\lambda$ is the second-largest eigenvalue in absolute value. Since
random $d$-regular graphs are expanders with high probability, this gives an
$\widetilde{O}(\sqrt{n})$ algorithm for $G(n,d)$, which improves on the naive
method for small numbers of queries.
  We then prove that no that algorithm with sub-constant error given probe
access to random $d$-regular graphs can have runtime better than
$\Omega(\sqrt{n}/\log(n))$ per query in expectation, obtaining a nearly
matching lower bound. We further show an $\Omega(n^{1/4})$ runtime per query
lower bound even with an oblivious adversary (i.e. when the query sequence is
fixed in advance).
  We then show that for families of graphs with additional group theoretic
structure, dramatically better results can be achieved. We give local access to
walks on small-degree abelian Cayley graphs, including cycles and hypercubes,
with runtime $\text{polylog}(n)$ per query. This also allows for efficient
local access to walks on $\text{polylog}$ degree expanders. We extend our
results to graphs constructed using the tensor product (giving local access to
walks on degree $n^\epsilon$ graphs for any $\epsilon \in (0,1]$) and Cartesian
product.
