At the next level of generality, we could consider classical
randomized strategies. Suppose we are given a randomized
strategy that succeeds in the test with probability \(1 - \varepsilon \) . Any
randomized strategy can be modeled by first sampling a random seed,
and then playing a deterministic strategy conditioned on the value of
the seed. A success probability of \(1 - \varepsilon \)  could have two
qualitatively different underlying causes: (1) on \(O(\varepsilon )\)  fraction
of the seeds, the strategy uses a function which is totally corrupted,
and (2) on a large fraction of the seeds, the strategy uses functions
which are only \(\varepsilon \) -corrupted. An analysis of randomized
strategies could naturally proceed in a “seed-by-seed” fashion, applying the
deterministic analysis of [1]} to the large fraction of “good” seeds (which
are each only \(\varepsilon \) -corrupted), while giving up entirely on the
“bad” seeds.
