We assume that a randomized algorithm does not flip
a coin unless the computation requires a random bit.
For simplicity, coins are assumed to be unbiased.
Randomized algorithms (to solve a problem)
are allowed to make errors and produce
incorrect outputs on some sequences of random bits.
They could also run forever
on some other random (infinite) sequences.
Let 
be a randomized algorithm. If on input
halts and
produces a correct output with 
being the random sequence
it generates, then 
is called a good input for . Clearly,
runs deterministically on .
If on input runs deterministically, then 
is
a good input, where 
denotes the empty string.
Let 
be a set of good inputs for and
.
Let 
be an input distribution.
If for all with 
, 
is
non-empty, we call a good-input domain of
(with respect to ).
Clearly, no string in
is a prefix of a different string in , for, otherwise,
the longer string cannot be in as the algorithm stops
before it can be generated. Let
, which is called
the rarity function of [BG93].
The smaller the value of the rarity function, the more good
random sequences there are for the algorithm.
If for all , 
,
the randomized algorithm produces a correct output with
probability 1. For our purpose, we only need to require that
the value of 
be ``reasonable'' in the sense that
is polynomial on average.
For decision problems, if the randomized algorithm also provides
a witness along with a yes/no answer, then
the correctness of the answer can be verified by evaluating
the witness (like search problems).
If a witness is not provided, then
one way to justify the
correctness of the output is to make sure that the input is good.
For example, we may need to require that
the good-input domain (with respect to )
be certifiable [BG93],
meaning that for every input , whether 
is deterministically decidable in ap-time with respect to distribution
.
By Definition 6.1,
an ap-time randomized algorithm on input produces
a correct output with probability 
, which could be small.
While this may not seem satisfactory,
Blass and Gurevich [BG93]
showed that by iterating such an algorithm in
an appropriate manner,
a correct solution will be produced with probability 1
in average polynomial time.
We assume that there is an efficient way to
check whether an output of an iteration is correct as discussed
above.
Since a randomized algorithm may run a much longer time on
inputs not in the good-input domain and it may not even halt
on some bad inputs, a new iteration should start early without waiting
for the previous one to stop.
One way to carry it out is to use the ``round-robin''
method. Denote by 
the iteration of .
At stage 
of , it independently
carries out one step in the first, second, ..., and the -th iterations
of respectively in that order.
stops as soon as one of the iteration
stops with a correct output. So
is a randomized algorithm whose sequence
of random bits on input is the combination of random bits of each
iteration in the round-robin fashion on the same input.
This is equivalent
to saying that flips a coin only when
an iteration asks for one and passes the random bit to that
iteration.
Several other iteration schemes have also been studied in
[BG93][WB93b].
A distributional decision problem 
is
solvable in randomized ap-time if
is decidable by a randomized algorithm
in time polynomial on -average with a
nonrare good-input, and the correctness of the output of the algorithm
can be efficiently verified. Denote by RAP the class of
all such problems.
The randomized reductions defined in Definition 6.2 are closed for randomized ap-time and they are transitive.
