Simulating a random walk with constant error

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