Page 206

		The proof of this lemma involves more technical probability theory than we want to discuss here. We refer the reader to Pitt [150] for its proof. The lemma frees us from specifying the number of sides of the coin, thereby allowing us to talk about probability function without specifying t. For this reason, we will refer to as simply pr in the sequel. Also, we are at liberty to use whatever number of sides of a coin that is convenient for the presentation at hand.

		9.15 Definition (Pitt [149, 150]) Let .

		(a) We say that P ProbpEx-identifies f (written: ) just in case

		(b)

		The next proposition establishes a link between team and probabilistic inference. It says that any class of functions team-identifiable by a team of scientists of size n can also be identified by a single probabilistic scientist with probability 1/n.

		9.16 Proposition (Pitt [149, 150]) Let, Then .

		Proof: Let , as witnessed by the team of scientists M1, M2, . . ., Mn. Let P be a probabilistic scientist, equipped with an n-sided coin, that behaves as follows. P on first flips its coin once and obtains a number and henceforth simulates scientist Mi+1 on f. Clearly, for each , .

		Pitt [149, 150] also established the converse of the above result: for each , and thus showed that probabilistic identification and team identification are successful on essentially the same collections on functions. This result will be an immediate corollary of Proposition 9.24 below. In order to prove this result, Pitt used a technique of calculating probabilities on "infinite computation trees" described in the next subsection. To facilitate the description, it is helpful to standardize the way probabilistic machines make use of their coin flips—see the next definition. The lemma following this definition shows that we may, without loss of generality, assume all probabilistic scientists are so standardized.

		9.17 Definition (Pitt [149, 150]) Suppose P is a probabilistic scientist. P is nice just in case P is equipped with a two-sided coin and the behavior of P on a function f is an infinite sequence of rounds each of which consists of the following three phases carried out in the order indicated.