I would like to generate discrete samples $ 0 = B(0), B(1), \ldots, B(T)$ of a Brownian motion $ B : [0,T] \to \mathbb{R}^d$ . It is possible to get $ O(\log T)$ time random access into a consistent sequence of samples $ B(k)$ by constructing the path in tree fashion. We choose $ B(T) = \sqrt{T} Z_0$ where $ Z_0$ is a standard Gaussian, then let $ B(T/2) = B(T)/2 + \frac{\sqrt{T}}{2}Z_1$ where $ Z_1$ is an independent standard Gaussian, construct $ B$ for the intervals $ [0,T/2]$ and $ [T/2,T]$ independently conditional on $ B(0), B(T/2), B(T)$ , and so on recursively.

Since any particular $ B(k)$ constructed in this fashion only depends on $ O(\log T)$ Gaussian random values, this gives us $ O(\log T)$ time random access into a consistently sampled sequence of Brownian motion as long as we have random access random numbers. The only state we need is the random seed. As long as we use the same seed, evaluations of $ B(k)$ for different $ k$ will be consistent, in that their joint statistics will be the same as if we had sampled Brownian motion in sequential fashion.

**Question**: Is it possible to do better than $ O(\log T)$ , while preserving the $ O(1)$ state requirement (only the seed must be stored)?

My sense is no, and that it would easy to prove if I found the right formalization of the question, but I don’t know how to do that.