# Does frequentism require exponentially many trials in some cases?

Frequentism is the philosophy that probabilities are statistical in the sense that they give the limiting frequency ratios of outcomes as the number of trials is large enough. For tiny probabilities like exponentially small probabilities, would this require exponentially many trials?

I know, I know, you are thinking if the probability of an outcome is exponentially small, then we won't expect it to happen in any trial if the number of trials is some reasonable practical number. This overlooks the situation where say the possible outcomes are some long strings of characters taken from some alphabet in the computer science sense, and the probability distribution is such that the probability for any particular string is exponentially small. In such a case, if someone were to specify some specific string in advance, and the number of trials is some realistic number, no one would expect to find that string in any trial outcome. On the other hand, if you were to look at the trial outcomes, they would all correspond to strings which if chosen a priori, would be considered practically improbable. In practice, what experimenters do in such a situation is conduct statistical randomness tests upon the strings obtained, but does this take us out of the realm of frequentism?

Can frequentism be saved in such a case?

-
I think a Bayesian vs. Frequentism debate fits better to math.stackexchange. The number of trials for a given probability can be calculated, but is this really the point here. Given a model and some data there are different ways to analyze the two together, both ways are valid but use a different interpretation of the outcome. –  Alexander Nov 18 '11 at 17:33
"exponentially". I do not think that word means what you think it means. When you say "exponentially small," do you just mean "very small?" –  Colin K Nov 18 '11 at 17:44
@ColinK - in the example given, the probability of finding a specific string of length N decreases exponentially with N. So it seems reasonable to refer to this as an exponentially small probability. –  user2963 Nov 18 '11 at 17:57
If a given string looks unlikely, it may just mean that we haven't understood the process that created it. The play "Hamlet" wasn't unlikely for whoever wrote it. A typical failing of statistical analysis is to assume statistical independence where there are in fact high-order correlations. The probability of writing "Hamlet" near the word "Claudius" is greater in Hamlet than they are in random text, but capturing all such structure in terms of a low-level concept like correlations is tricky. –  Peter Morgan Nov 18 '11 at 18:54