§ 3. Определение функции роста
В этом параграфе будет введена характеристика класса событий, достаточная для выяснения факта равномерной сходимости.
Пусть
– множество,
– некоторая система его подмножеств,
– последовательность элементов
длины
. Каждое множество
определяет подпоследовательность
этой последовательности, состоящую из тех и только тех элементов, которые принадлежат
. Будем говорить, что
индуцирует
на последовательности
. Обозначим через

число различных подпоследовательностей
, индуцированных множествами
. Очевидно, что
.
Число
будем называть индексом системы
относительно выборки
.
Определение индекса системы можно сформулировать и иначе. Будем считать, что
эквивалентно
относительно выборки
, если
. Тогда индекс
есть число классов эквивалентности, на которые система
разбивается этим отношением эквивалентности.
Очевидно, что эти два определения равносильны. Функцию
, (10.8)
где максимум берется по всем последовательностям длины
, назовем функцией роста системы
. Здесь максимум всегда достигается, так как индекс
принимает лишь целые значения. Используя функцию роста, сформулируем ниже достаточные условия равномерной сходимости частот к вероятностям по классу событий и дадим соответствующие оценки.
В заключение этого параграфа приведем несколько примеров функций роста для различных классов событий.
Пример 1. Пусть
– прямая, a
– множество всех лучей вида
. Найдем функцию роста.
Пусть дана последовательность точек
без повторений. Изменив порядок последовательности, можно добиться того, что
.
Очевидно, что каждое множество
вида

при
индуцирует подпоследовательность

такую, что
.
При
индуцируется пустая подпоследовательность, а при
– вся последовательность
. Ясно, что число различных последовательностей, индуцируемых множествами
, равно
. Таким образом,
.
Если в последовательности есть повторения, то индекс
разве лишь уменьшается. Поэтому
. (10.9)
Пример 2. Пусть
– сегмент
, а
состоит из всех множеств, каждое из которых представляет собой объединение конечного числа непересекающихся сегментов с рациональными концами. Если
– последовательность точек из сегмента
без повторений, то для всякой подпоследовательности
найдется множество из
, включающее только те точки
, которые входят в
. Для этого достаточно покрыть точки
достаточно малыми сегментами с рациональными концами и взять их объединение. Поэтому в данном случае

(отметим, что система
содержит лишь счетное число элементов).
Пример 3. Пусть
–
-мерное
евклидово пространство,
– система всех подмножеств вида
.
Тогда индекс
определяет число различных разбиений
векторов
на два класса с помощью гиперплоскостей, проходящих через начало координат. Как было показано в главе V,
,
откуда следует
. (10.10)
Можно показать, что в действительности
.
Аналогично показывается, что если
–
-мерное евклидово пространство, a
– система подмножеств вида
,
где
– произвольный вектор, а
– произвольная скалярная величина, то
.