Number of times to run a lengthy experiment

Question

I have this long running experiment. Each time I run it I get a new goodness value, since the algorithm has random variables in it. So I need to report the mean and the std of some n runs. What should n be?

I need to be able to defend n based on some statistical ideas. Some kind of scientific reference (a book, a paper) would be wonderful, too.

I provide more details as you say, thanks for the answers:

In computer vision, an important challenge is to recognize objects from images. Different computer algorithms are developed for this purpose. To see how good a new algorithm is, one sometimes constructs a test and a training set of images, say 1000 images for each, train the algorithm with the training images, and produce a success rate using the test set. If out of the 1000 objects in the test images, 800 is recognized by the algorithm, the success rate is said to be 80 percent.

Now, my algorithm analyses, say, 1000 RANDOM points in the image, and using that analysis, tries to recognize the objects in the image. Each time I run the algorithm, I get a different success rate, since 1000 points are produced RANDOMLY. So I think its best to report some kind of summary statistics (e.g. the main and std deviation) of the success rate.

Also, one sometimes needs to say, "well in addition to my algorithm, I tried these, say, 10 algorithms on the same dataset, and this table shows that mine is the best in this and this way..." Some of these algorithms may need to run more than once, too. So one can really have a long experiment.

So, as I said before, at least how many times should I run the long running experiment?

Thx.

Answer 1

If we assume an underlying success probability $\theta$ for a specific training set and number of points used for image analysis, we can expect a binomial distribution for the number of successful object recognitions $k$ out of $n$ runs:

$P(k|\theta,n)=\left(n\atop k\right)\theta^k (1-\theta)^{n-k}$

What we're actually interested in, is the value and uncertainty of $\theta$ for given $n,k$. We get a probability distribution for $\theta$ by applying Bayes Theorem:

$p(\theta|k,n) \propto p(k|\theta,n)*p(\theta|n)$

The first term on the right side is the likelihood, for which we can use the formula from above. The second term is the prior distribution for $\theta$. If we want to be neutral about $\theta$ before any experiment is done we can choose the Jeffreys prior

$p(\theta|n) \propto \theta^{-1/2}(1-\theta)^{-1/2}.$

Putting our likelihood and prior distributions together and normalizing the resulting distribution we end up with

$p(\theta|k,n) = \frac{\Gamma(n+1)}{\Gamma(k+\frac{1}{2})\Gamma(n-k+\frac{1}{2})} \theta^{k-1/2}(1-\theta)^{n-k-1/2},$

which is the Beta distribution with parameters $k+\frac{1}{2}$ and $n-k+\frac{1}{2}$.

If we e.g. have $n=5$ runs and $k\in\{1,3\}$ successes, the distribution for probability of different underlying $\theta$ values looks like this:

From this probability distribution we can get all the information we need about $\theta$ in order to decide to do further runs or not, e.g. we can compute credible intervals for the true value of $\theta$. By computing expected values for $\theta$ and $\theta^2$ we can get formulas for the mean $\theta$ and the variance of $\theta$:

$E\left[\theta\right]=\int_{\theta=0}^1 \theta \; p(\theta|k,n) = \frac{2k+1}{2n+2}$

$E\left[\theta^2\right]=\int_{\theta=0}^1 \theta^2 p(\theta|k,n) = \frac{(2k+1)(2k+3)}{4(n+1)(n+2)}$

$V\left[\theta\right]=E\left[\theta^2\right] - E\left[\theta\right]^2=\frac{4k(n-k)+2n+1}{4(n+1)^2(n+2)}=\frac{(k+\frac{1}{2})(n-k+\frac{1}{2})}{(n+1)^2(n+2)}$

Now we could run experiments and compute the mean and variance of the expected $\theta$ and stop when the variance is smaller than a predefined value that reflects our desired certainty for $\theta$. For example, let's say we want the standard deviation of our $\theta$-distribution be smaller than $\sigma$, then we should do runs until the condition

$\frac{(k+\frac{1}{2})(n-k+\frac{1}{2})}{(n+1)^2(n+2)} < \sigma^2$

is satisfied, with a resulting estimate for ${\tilde \theta}=\frac{2k+1}{2n+2}$.

If e.g. $\sigma=0.05$ we have to do runs until we end up in the orange region in this plot:

We can see that we need a lot more runs to be as certain about $\theta$ in case of $\theta \approx 0.5$ (about a hundred in this example) than if we have a $\theta$ near zero or one (where perhaps 30 runs could be sufficient).

A nice introductory textbook which contains examples like this is Data Analysis: A Bayesian Tutorial. It also contains a small chapter on experiment design.