# $O(1)$ time, $O(1)$ state random access Brownian motion?

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.

• Could you be a bit more elaborate about the exact motion that you want? I assume you mean Brownian motion around the origin? What model for Brownian motion do you want? Do you simply want a discrete random walk in $\mathbb{R}^d$? I'm a bit confused about your construction as you first state $B(T) = \sqrt{T}Z_0$, are you not done there? I'm not too familiar with the exact field but would love to help if you could clarify those things. – orlp Jul 3 '19 at 18:12
• I'm glossing over details of precision, but other than precision I want true continuous Brownian motion. This means that we can construct the sequence in order by letting $Z_k, k < T$ be a sequence of standard Gaussians and letting $B_k = \sum_{i < k} Z_k$. I'm not done after $B(T) = \sqrt{T} Z_0$ since that only gives the end of the path, not the intermediate sequence, and I want random access into the full sequence. – Geoffrey Irving Jul 3 '19 at 20:59
• I'm also interested in this problem and I've tried constructing your current model in code but could not get it to work properly. I'm currently not convinced you can even do it with $\log K$. Do you have some working code or could you provide an example calculation for $B(5)$ with $T = 8$? – orlp Jul 4 '19 at 21:46
• I think I figured out the issue, I believe your scheme is incomplete. I managed to get a working model mimicking binary search using Corollary 1 from page 10 from here: math.unl.edu/~sdunbar1/MathematicalFinance/Lessons/…. – orlp Jul 5 '19 at 0:33