Let be the probability that a given algorithm gives the correct answer for input . We are also interested in , which is the average of over all squares , and , the average over all pseudo-squares, and , the average of over all .
If we are given an algorithm, we can easily determine by running it with input on a sample of randomly chosen and counting the number of times the algorithm answers ``this is a square.''
The procedure for determining is more elaborate. Suppose we have an algorithm for which . Using Lemma 26, generate a sample of 100 members of , and run the algorithm on each of them. Suppose we get the answer ``this is a square'' 65 times. There are squares in the sample, on which there have been .6(50) correct responses and 20 incorrect. Pseudo-squares have been identified as squares times, which suggests . Finally .
Lemma 24 or 25 can be used to determine the probability that these estimates come within a specified amount.