生成器・生成分布・失敗率

生成器とは、乱数の列から入力の集合 $X$ の元を作る手続きをいう。生成器が作る入力は $X$ に値をとる確率変数で、その分布 $\mu$ を生成分布という。多くの生成器は大きさのパラメータ $s$（列の長さの上限、木の深さの上限、整数の絶対値の上限など）をもち、$s$ ごとに分布 $\mu_s$ が決まる。

性質 $\varphi$ の、生成分布 $\mu$ のもとでの失敗率を、反例の集合の確率

と定める。