Simulating a Random Walk with Constant Error

摘要: We analyse Jim Propp's $P$-machine, a simple deterministic process that simulates random walk on ${\mathbb Z}^d$ to within constant. The proof of the error bound relies several estimates in theory walks and some careful summing. mention three intriguing conjectures concerning sign-changes unimodality functions linear span $\{p(\cdot,{\bf x}) : {\bf x} \in {\mathbb Z}^d\}$, where $p(n,{\bf x})$ is probability beginning from origin arrives at ${\bf x}$ time $n$.