§ 3. Оценка равномерного относительного уклонения частот в двух подвыборках
В этом параграфе мы докажем теорему о равномерном относительном уклонении частот в двух подвыборках. В задаче минимизации суммарного риска в классе характеристических функций эта теорема играет ту же роль, которую в задаче минимизации среднего риска играет теорема о равномерном относительном уклонении частот от вероятностей. Для того чтобы сформулировать теорему, введем функцию 
Пусть дано множество
состоящее из элементов двух типов: 
элементов типа а и 
элементов типа 
Выберем из этого множества наудачу 
элементов. Вероятность того, что среди выбранных элементов окажется 
элементов типа а, равна величине
Таким образом, с вероятностью (10.11) частота элементов типа а в отобранной группе составит 
и, следовательно, в оставшейся группе 
Вероятность того, что частота элементов а в первой группе уклонится от частоты элементов а во второй группе на величину, большую х, равна
где суммирование ведется по тем значениям 
для которых
Определим функцию
Функция 
легко может быть табулирована на ЦВМ.
Обозначим теперь через 
частоту ошибок классификации множества 
с помощью решающего правила 
Очевидно, что
Справедлива теерема о равномерном относительном уклонении частот в двух подвыборках.
Теорема 10.2. Пусть класс решающих правил 
имеет емкость 
Тогда вероятность того, что относительная величина уклонения хотя бы для одного правила из 
превзойдет к, оценивается величиной
Здесь принято: 
если 
Доказательство. Заметим, что число классов эквивалентности на полной выборке не превосходит 
Поэтому справедливо
При 
первый сомножитель правой части оценивается величиной 1,5 второй сомножитель оценивается функцией 
Действительно,
и, согласно определению,
Теорема доказана.
В дальнейшем нам понадобится равномерная по 
оценка частоты ошибок на рабочей выборке. Выведем ее, используя теорему 10.2. Ограничим правую часть (10.13) величиной 
Получим неравенство
наименьшее решение которого обозначим х.
Учитывая (10.12), из (10.13) заключаем, что с вероятностью 
для всех а справедливо неравенство
Этим неравенством мы и будем пользоваться при построении алгоритмов упорядоченной минимизации риска в классе характеристических функций.
