Тест случайности получает на вход последовательность (p_1,b_1,...,p_n,b_n), в которой p_1,...,p_n --- числа из отрезка [0,1], а b_1,...b_n --- биты (нули или единицы). По этим данным тест говорит "верю" или "не верю". Мы подразумеваем, что тест верит или не верит в то, что биты b_1,...,b_n получены в этом порядке в результате случайных испытаний с вероятностями успеха p_1,...,p_n.

Говорят, что тест имеет доверительную вероятность \epsilon, если для любого распределения вероятностей на {0,1}^n вероятность того, что случайная (выбранная по этому распределению) последовательность вместе с условными вероятностями по нему же не пройдет тест, не больше \epsilon.

С другой стороны, если из черного ящика приходят биты, мы можем пытаться предсказывать вероятности следующих битов и хотеть пройти тест.

Основной результат: Это можно сделать (с помощью вероятностного алгоритма) так, чтобы для любой последовательности вероятность не пройти тест была бы лишь немного больше доверительной вероятности теста.