0
$\begingroup$

Let $X_0,X_1,X_2,\dots$ be the simple random walk, i.e., $X_0=0$ and each $X_{t+1}$ is sampled uniformly at random from $X_t-1,X_t+1$ independently of everything else.

Given a very large $t$, I want to efficiently sample from the distribution of $X_t$. I am OK with an approximate algorithm, i.e., where the distribution of the output from the algorithm is close to the true distribution of $X_t$.

Is there an efficient algorithm for this? "Efficient" means the running time should be something like $\log t$ rather than something like $t$ steps of computation.

One approach I know of is to efficiently sample from the normal distribution $\mathcal{N}(0,t)$ (e.g., using the Box-Muller transform), then round to the nearest odd/even integer. Is there a better method? "Better" could mean a tighter approximation.

Equivalently, I want to efficiently approximate sampling from the binomial distribution Binomial($t$,$1/2$).

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ The reference for R's implementation of binomial sampling gives an elegant, efficient answer. See Catherine Loader (2000). Fast and Accurate Computation of Binomial Probabilities; available as r-project.org/doc/reports/CLoader-dbinom-2002.pdf $\endgroup$ Commented Oct 20 at 14:01
  • $\begingroup$ @whuber, Thank you. Maybe I missed something, but I don't see how that answers the question. If I understand correctly, that describes how to compute $\Pr[X_t=x]$ for a given $x$, i.e., how to compute a single binomial probability. That doesn't provide an efficient way to sample from $X_t$, i.e., to sample from a binomial. You could compute all $t$ binomial probabilities and then sample, but that's very inefficient for large $t$. I'm asking for a more efficient algorithm (one that requires far fewer than $t$ steps -- imagine $t$ being exponentially large). $\endgroup$ Commented Oct 22 at 6:30
  • $\begingroup$ The paper describes an algorithm for computing "tail probabilities," which amounts to the CDF. That permits one to sample reasonably efficiently. The sense of "efficiently" depends on how large a sample you intend to take: large samples allow for precomputation of data structures to assist in the sampling, whereas small samples do not benefit from such precomputation. $\endgroup$ Commented Oct 22 at 12:39
  • 1
    $\begingroup$ @whuber, Unfortunately, as I understand it, their method for computing tail probabilities is very slow when $t$ is very large. It requires summing over a number of terms proportional to $t$. As I write in the question, I'm asking if there are methods that requires a number of steps proportional to $\log t$ rather than proportional to $t$. I already know how to do this in a number of steps proportional to $t$. I'm looking to sample a single value (not large samples). $\endgroup$ Commented Oct 22 at 17:20
  • $\begingroup$ For very large $t,$ the Normal approximation is excellent, with relative accuracy c. $1/t$ for all probabilities in the center of the distribution. Otherwise, you might consider using the percentile point function (given by an incomplete Gamma integral), using high-precision calculations when $t$ is huge. Ultimately its timing will depend on the size of the numerical representation of $t,$ which is proportional to $\log t,$ allowing you to achieve (theoretically) timing as a polynomial in $\log t.$ $\endgroup$ Commented Oct 22 at 18:46

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.