Relative to a Random OracleA, PA NPA co- NPA with Probability 1

Let A be a language chosen randomly by tossing a fair coin for each string x to determine whether x belongs to A. With probability 1, each of the relativized classes LOGSPACEA, PA, NPA, PPA, and PSPACEA is properly contained in the next. Also, NPA co- NPA with probability 1. By contrast, with probability 1 the class PA coincides with the class BPPA of languages recognized by probabilistic oracle machines with error probability uniformly bounded below 12. NPA is shown, with probability 1, to contain a PA -immune set, i. e. , a set having no infinite subset in PA. The relationship of PA -immunity to p-sparseness and NPA -completeness is briefly discussed: PA -immune sets in NPA can be sparse or moderately dense, but not co-sparse. Relativization with respect to a random length-preserving permutation, instead of a random oracle A, yields analogous results and in addition the proper containment, with probability 1, of P^ in NP^ co- NP^, which we have been unable to decide for a simple random oracle. Most of these results are shown by straightforward counting arguments, applied to oracle-dependent languages designed not to be recognizable without a large number of oracle calls. It is conjectured that all pA -invariant statements that are true with probability 1 of subrecursive language classes uniformly relativized to a random oracle are also true in the unrelativized case.