  Consider the following computational problem: given a regular digraph
$G=(V,E)$, two vertices $u,v \in V$, and a walk length $t\in \mathbb{N}$,
estimate the probability that a random walk of length $t$ from $u$ ends at $v$
to within $\pm \varepsilon.$ A randomized algorithm can solve this problem by
carrying out $O(1/\varepsilon^2)$ random walks of length $t$ from $u$ and
outputting the fraction that end at $v$.
  In this paper, we study deterministic algorithms for this problem that are
also restricted to carrying out walks of length $t$ from $u$ and seeing which
ones end at $v$. Specifically, if $G$ is $d$-regular, the algorithm is given
oracle access to a function $f : [d]^t\to \{0,1\}$ where $f(x)$ is $1$ if the
walk from $u$ specified by the edge labels in $x$ ends at $v$. We assume that G
is consistently labelled, meaning that the edges of label $i$ for each $i\in
[d]$ form a permutation on $V$.
  We show that there exists a deterministic algorithm that makes
$\text{poly}(dt/\varepsilon)$ nonadaptive queries to $f$, regardless of the
number of vertices in the graph $G$. Crucially, and in contrast to the
randomized algorithm, our algorithm does not simply output the average value of
its queries. Indeed, Hoza, Pyne, and Vadhan (ITCS 2021) showed that any
deterministic algorithm of the latter form that works for graphs of unbounded
size must have query complexity at least
$\exp(\tilde{\Omega}(\log(t)\log(1/\varepsilon)))$.
