[kqfwttaf] Random access to Random

A pseudorandom number generator implemented using a block cipher in Counter mode has the feature that one can fast-forward to any random number in the stream without having to generate the previous ones.  And rewind. Can we leverage this feature to do interesting things not possible with a traditional RNG which operates by iterating a function on a state?

Suppose we are modeling a Markov process.  Can we fast forward this process the same way?

Probably not in general, but there may be interesting special cases.  An arbitrary Fibonacci number can be computed with the number of operations logarithmic in the index (not linear as the naive way of generating Fibonacci.)

The oblique inspiration was the Haskell RandomGen "split" operation which allows random computations to be parallelized, again not possible for a traditional iterative RNG.

Are there more interesting computational structures to generate randomness with interesting features?