§ 8. Свойства функции роста
Функция роста имеет простой смысл: она вычисляет максимальное число способов разделения I точек на два класса с помощью решающих правил 
Для функции роста справедлива замечательная теорема, которая позволяет легко ее оценить.
Теорема 6.6. Функция роста либо тождественно равна 
, либо при 
мажорируется функцией
где 
минимальный объем выборки, при котором нарушается условие 
Иначе говоря,
Доказательство теоремы 6.6 приведено в приложении к главе.
Для того чтобы оценить функцию роста, надо показать, что либо для любого 
найдутся точки 
такие, что с помощью решающих правил 
их можно разбить на два класса всеми 
возможными способами, либо существует число 
такое, что 
точек можно, но никакие 
точек нельзя разбить на два класса всеми возможными способами. В первом случае функция роста — показательная, во втором случае — степенная. Число 
может служить мерой разнообразия класса решающих правил.
Определение. Будем говорить, что класс характеристических функций имеет емкость 
если справедливо неравенство
В случае выполнения равенства
будем говорить, что емкость класса характеристических функций 
бесконечна.
Нетрудно убедиться, что если емкость класса характеристических функций конечна, то всегда имеет место равномерная сходимость частот к вероятностям. В самом деле, в этом случае справедливо
и достаточное условие выполнено.
Важную роль в дальнейшей теории играет класс линейных по параметру решающих правил:
Нетрудно найти функцию роста для класса событий, заданных линейными решающими правилами (6.40). Для этого достаточно определить максимальное число точек 
в пространстве размерности 
которые можно с помощью гиперплоскости разбить на два класса всеми 
способами. Известно, что это число равно 
Поэтому, согласно теореме 6.6, для класса линейных решающих правил (6.40) функция роста оценивается
И, следовательно, для класса линейных решающих правил выполнены достаточные условия равномерной сходимости.
В главе II было показано, что факт равномерной сходимости частот появления событий к их вероятностям по классу событий, заданному одномерными линейными решающими правилами 
составляет содержание теоремы Гливенко — Кантелли, утверждающей равномерную сходимость эмпирической функции распределения к истинной.
