We study the round complexity of two-party protocols for
generating a random $n$-bit string such that the output is
guaranteed to have bounded bias (according to some measure) even
if one of the two parties deviates from the protocol (even using
unlimited computational resources). Specifically, we require that
the output's statistical difference from the uniform distribution
on {0,1}^n is bounded by a constant less than 1.

We present a protocol for the above problem that has 2log*n+O(1)
rounds, improving a previous 2n-round protocol of Goldreich,
Goldwasser, and Linial (FOCS `91). Like the GGL protocol, our
protocol actually provides a stronger guarantee, ensuring that the
output lands in any subset T of {0,1}^n of density mu with
probability at most O(sqrt(mu+delta)), where delta is an
arbitarily small constant.

We then prove a matching lower bound, showing that any protocol
guaranteeing bounded statistical difference requires at least
log*n-log*log*n-O(1) rounds. As far as we know, this is
the first nontrivial lower bound on the round complexity of random
selection protocols (of any type) that does not impose additional
constraints (e.g. on communication or ``simulatability'').

We also prove several results for the case when the output's bias is
measured by the maximum multiplicative factor by which a party
can increase the probability of a subset T in {0,1}^n.