Accurate Monte Carlo Estimation of Very Small P-Values in Markov Chains
W. John Wilbur · SSRN Electronic Journal · 1998
There are many events in the real world that are far from random. If we could assign significance levels to them based on a rigorous random model, such p-values must be very small indeed. Why should we be interested in such small numbers? Basically because the number -log(pval) is an estimate of the expected amount of information in bits that must be added to the random model to determine the event in question. Such self information provides an estimate of the complexity of the event and may serve to rank events in order of interest prior to human examination. In some cases we can determine very small p-values from closed formulas. In other cases the appropriate random model is sufficiently complicated that we cannot do so. We present here an algorithm that allows one to calculate very small p-values for some complicated random models that can be realized as Markov processes. Three examples are given illustrating the performances of the algorithm.