What are the best ways to unit test code that outputs random sequences satisfying specific conditions, such as Markov chains?
Let's be specific. There are two natural things to test:
That the initial state returned in each chain follows the user-specified probabilities, such that
chain == iwith probability
That the transitions between states are correct, that is, if
chain[k] == i, then the probability of
chain[k+1] == jis given by
Now, I can think of two ways to do this.
- Test that the code does what I want it to do. Generate a large number of sequences (say, 10000) and test that the frequencies for the initial state approximate
p_initial. Next test that the frequencies of transitions to state
The difficulty with this approach is that any finite sample will exhibit fluctuations from the prescribed probabilities. I thus have to set an acceptable level for these fluctuations. But this means that a) the test might miss actual errors in the code if they only change the frequencies a little bit, and b) after a refactoring I might get false failures due to a particular chain falling outside the accepted fluctuation level by pure chance. (I'm assuming I'm using a fixed seed for the random number generator so that at least without refactoring the tests should be reproducible.) Worse, the more I relax my acceptance criteria to mitigate problem b), the more I risk falling for a).
Moreover, I'm only testing a small subset of the requirements for the model (I also want the transitions to be independent, for instance). And compared to how simple the implementation for this code is (given a random number generator; see below), it doesn't seem worth it to add more bloat in the testing code.
- The alternative is to assume that the random number generator was tested by its creators and works fine, and just test that my code calls it in the right way. So I can mock the RNG and check that my code calls it with the right arguments.
The problem with this approach is that it makes the test depend strongly on the implementation. For instance, I could choose the initial state by using something like
numpy.random.choice in Python, or I could simply generate a random number between 0 and 1 (
numpy.random.random) and implement my own logic for choosing the initial state based on that. Even within each of these choices, I could choose to order the states in any way. The tests must know what the code is doing, and that makes the tests fragile to refactoring.
So that's my problem: it seems wrong to couple the test to the implementation so strongly. But it also seems wrong to perform a lot of tests of my function that are in effect tests of the RNG (and not particularly stringent tests either).
Is there a different, better way to do this that allows me to test the code that I wrote while relying on the RNG writers to have checked their own code?
For definiteness, here is some (Python) code implementing a simple Markov chain generator
import numpy as np class PlainMarkov(object): def __init__(self, p_initial, p_transition, rng=None): """ p_initial = sequence of initial-state probabilities p_transition = sequence of sequences for transition probabilities rng = random number generator """ self.p_initial = np.asarray(p_initial) self.p_transition = np.asarray(p_transition) self.rng = rng is rng is not None else np.random.random.__self__ def run(self): """ Draw one chain from the Markov distribution. """ n_states = len(self.p_initial) state = self.rng.choice(n_states, p=self.p_initial) chain =  while state_numeric != 0: chain.append(state) state = self.rng.choice(n_states, p=self.p_transition[state]) return chain