Here's a nice essay about some folks that used Markov chains to write a nifty test data generator.
The article does a good job of explaining the underlying theory behind Markov chains, and also explains some of the implementation details they had to overcome, such as how they used a reference implementation as an oracle, to decide whether their code had passed a particular test or not, and how they had to train their test data generator by feeding it samples of test cases that they already had in place.
I also like the fact that they didn't turn to this technique until they had already developed a large testbed of test cases via other mechanisms:
- internally-developed test cases
- test cases contributed by customers
- test cases constructed by harvesting data off the internet
You're never done testing. When you think you are, consider a new technique.