Deterministic Approximation of Random Walks via Queries in Graphs of Unbounded Size

Edward Pyne, Salil Vadhan

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 rand…