Suppose I have an infinite number of time steps $X_0,\ldots,X_i,\ldots$, where each $X_i$ is an infinite dimensional random vector consisting of 0's and 1's.
I now specify $P(X_i|X_{(i-1)})$ and an initial condition $X_0$.
Suppose I want to know the state $X_i$. If the X_i's were finite, I could simulate $X_1, X_2, X_3, \ldots$ etc using $P(X_i|X_{(i-1)})$ and a pseudo-random number generator with some initial seed (so that each state is deterministic and can be recovered without saving to memory), and eventually get X_i.
- My intention is for each X_i to be deterministic from the pseudo-random number generator, but also be a sample from the Markov process.
Is there a way to do this in the infinite case without computing $X_1, X_2, \ldots, X_i$? In other words, someone would specify a range $[a,b]$ and $i$, and the elements with indices in the range of $[a,b]$ of $X_i$ would be returned. Moreover, giving the same query twice would return the same result, and if one were to measure the entire sequence $X_0,X_1\ldots$ it would be consistent with coming from a Markov process with the given probability transition function.
A possible solution I thought of was this: if $X_i$ has been measured, and $X_k$ is queried ($k>i$), one can find a formula for $P(X_k|X_i)$ and draw $X_k$ from that distribution. However things might get messy if I now query $X_w (i < w < k)$, whose probability distribution should depend on $X_i$ and $X_k$. Moreover, this approach gives results that depend on the order of measurement, and requires one to save each $X_i$ when measured.
This question was motivated by procedural generation techniques in games: I might make an infinite world where the height of each point in the map depends on the height of the points in the row to the left of it. When a player is spawned somewhere in this infinite world, the height at their particular location needs to be generated, and if they visit that position again it needs to have the same height.
Thanks for your help :) I find this a particularly interesting question, especially with the soon-to-be released "No Man's Sky".