Random testing works very well in practice, but often we do not know why. In this talk, I shall explore techniques from randomized algorithms and combinatorics that enable us to provide theoretical results about the performance of random testing procedures in different situations. For the special case of testing distributed systems with random network partitions, we show a combinatorial result that shows that a "small" number of tests will provide coverage with respect to splitting nodes of the system into different partitions with high probability (Joint work with Filip Niksic, POPL 2017). On the one hand, these techniques provide insight into the workings and effectiveness of the testing procedures. On the other, they help us build new algorithms for random testing.