Assume there's a random walk $S_k = X_1 + \dots + X_k$ where $X_i \in \{1, -1\}$ are uniformly iid.
I want Alice and Bob to share a function $S(k) = S_k$. A straightforward approach would be to let them share a function $h(i) = X_i$, allowing them to compute $S(k)$ at will. However, my $k$ can be very large, so I'm looking for a function that behaves like $S_k$ and can be computed in (something like) constant time.
If Alice and Bob were only to look at the value once, we could sample the binomial distribution Binom($k$, $1/2$) using just $O(\log n)$ bits or approximate it with a Gaussian distribution. However, this wouldn't be consistent, as looking at $S(k-1)$ or $S(k+1)$ would yield completely independent values instead of values from the same random walk.
More generally, I'm interested in consistently sampling continuous processes, such as Wiener processes or Brownian motion. For some simple discrete processes like Poisson processes, disjoint intervals are independent, making it easy to sample consistently. However, for a simple random walk like the one described above, I'm unsure what can be done.
Is there an efficient method to compute such a function $S(k)$ consistently, with constant time complexity or close to it, without precomputing and storing the entire sum up to a large value of $k$? Any suggestions or insights would be greatly appreciated.
Update: Assuming Alice and Bob access $S$ using the same access pattern I think the following approach works: For simplicity let's say the random walk is shifted to $X_i\in\{0,1\}$ instead of $\{1,-1\}$. Assume they have already sampled/computed $S(t_1), S(t_2), \dots, S(t_n)$ for $t_1\le t_2\le\dots\le t_n$. (1) If they want to sample a new $t>t_n$ they take $$S(t) = S(t_n) + \mathrm{Binom}(t-t_n, 1/2),$$ where the binomial is seeded using the hash of $t$. And (2) if they want to sample $t$ between two previous values $t_i < t < t_{i+1}$ they interpolate $$S(t) = S(t_i) + \mathrm{HyperGeom}(N=t_{i+1}-t_i,\, n=S(t_{i+1})-S(t_i),\, k=t-t_i),$$ using the Hypergeometric distribution.
This is much better, but the downside is that the access patterns have to be equal. We can do better by building a binary tree over the domain. This works because the value of $S(t)$ is independent of $S(t_{i-1})$ if $t_{i}<t<t_{i+1}$ and $S(t_i)$ and $S(t_{i+1})$ are known. However, this is still logarithmic time (in the domain) rather than constant.
Update 2: I should mention the way we can do this for a Poisson Process in expected constant time, used in Manasse et al. in Consistent Weighted Sampling: To find the nearest point from the random process to some point $x$, we simple pick a small interval around $x$ and sample the number of random points in this interval. Since the number of points in any non-overlapping interval, we can do this easily by seeding a Poisson random variable with the hash of the interval. If the interval is non-empty, we sample the (expected constant number of) points in the interval and pick the closest one. Otherwise we look at the adjacent intervals, which also succeed with constant probability, giving us constant expected time by a geometric sum.
