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.