CHARACTERIZATION OF PROBABILISTIC INFERENCE.

Inductive Inference Machines (IIMs) attempt to identify functions given only input-output pairs of the functions. Probabilistic IIMs are defined, as is the probability that a probabilistic IIM identifies a function with respect to two common identification critera: EX and BC. Let ID denote either of these criteria. Then ID//p //r //o //b (p) is the family of sets of functions U for which there is a probabilistic IIM identifying every f belonging to U with probability greater than equivalent to p. It is shown that for all positive integers n, ID//p //r //o //b (1/n) is properly contained in ID//p //r //o //b (1/(n plus 1)), and that this discrete hierarchy is the finest possible. This hierarchy is related to others in the literature.