For stochastic algorithms you will probably use the same trick as with monadic I/O --- you can make the description of the algorithm purely functional, but not its execution.
Certainly possible, but how well this works depends on how, and to what extent, referential transparency is enforced by the language.
For instance, in Haskell, there really isn't a satisfying solution that I'm aware of. Threading a PRNG (as with the state monad) keeps the code "pure", but enforces a strict sequencing on use of the structure, wrecking laziness. On the other hand, any nondeterminism without threading a PRNG probably requires unsafePerformIO.