The idea is to use Markov chains to represent paths through the software under test. If the test data doesn't provide full path coverage, the Markov chains can be used to estimate either the cost of continuing to test with more data or the cost of stopping without testing further.
Markov chains have other uses in software testing; see, for example, A Markov Chain Model for Statistical Software Testing by James Whittaker and Michael Thomason; IEEE Transactions in Software Engineering; October 1994 (vol. 20, no. 10); pages 812-824.
This page last modified on 2 March 2005.