Imagine that you want to assess the compressibility of a large document very fast. You could randomly pick a subsequence, try to compress it. This can serve as a prediction for the overall compressibility of the document. But how big should your sample be?
We have come up with the following strategy:
- Pick an arbitrary (small) sample size. Measure the compressibility.
- Next, double the sample size and measure the compressibility again. If there is little change (say less than 10%), then conclude that you have reliably determined the compressibility of the document. If not, double the sample size again, and so on.
We are quite certain that this is not a new strategy, and we are wondering whether it is related to some well-known strategy used by statisticians.
("Compression" here is just an example. Basically, we are interested in a metric that has no known nice mathematical properties, so that it is not possible to determine analytically what could be a good sample size. We have no choice but to fall back on such heuristics.)
