Can the Nyquist sample rate be extended to stochastic sampling?
As long the mean sampling frequency fulfills the Nyquist criteria, you're good to go. So, for well behaved distributions with known mean, you won't need any extra math, aside from the required special handling of the non-uniform samples themselves.