§ 3. Определение функции роста
В этом параграфе будет введена
характеристика класса событий, достаточная для выяснения факта равномерной
сходимости.
Пусть 
– множество, 
– некоторая система
его подмножеств, 
–
последовательность элементов длины 
. Каждое множество 
определяет
подпоследовательность 
этой последовательности, состоящую из
тех и только тех элементов, которые принадлежат 
. Будем говорить, что индуцирует на последовательности 
. Обозначим через
число
различных подпоследовательностей , индуцированных множествами . Очевидно, что
.
Число будем называть индексом
системы относительно
выборки 
.
Определение
индекса системы можно сформулировать и иначе. Будем считать, что 
эквивалентно 
относительно выборки , если 
. Тогда индекс есть число классов
эквивалентности, на которые система разбивается этим отношением
эквивалентности.
Очевидно, что эти два определения
равносильны. Функцию
, (10.8)
где
максимум берется по всем последовательностям длины , назовем функцией роста системы . Здесь максимум
всегда достигается, так как индекс принимает лишь целые значения. Используя
функцию роста, сформулируем ниже достаточные условия равномерной сходимости
частот к вероятностям по классу событий и дадим соответствующие оценки.
В заключение этого параграфа
приведем несколько примеров функций роста для различных классов событий.
Пример 1. Пусть – прямая, a – множество всех лучей вида 
. Найдем функцию
роста.
Пусть дана последовательность
точек без
повторений. Изменив порядок последовательности, можно добиться того, что
.
Очевидно, что каждое множество вида
при
индуцирует
подпоследовательность
такую,
что 
.
При 
индуцируется пустая
подпоследовательность, а при 
– вся последовательность . Ясно, что число
различных последовательностей, индуцируемых множествами , равно 
. Таким образом,
.
Если в последовательности есть
повторения, то индекс разве лишь уменьшается. Поэтому
. (10.9)
Пример 2. Пусть – сегмент 
, а состоит из всех
множеств, каждое из которых представляет собой объединение конечного числа
непересекающихся сегментов с рациональными концами. Если – последовательность точек из
сегмента без
повторений, то для всякой подпоследовательности 
найдется множество из , включающее только те
точки 
,
которые входят в .
Для этого достаточно покрыть точки достаточно малыми сегментами
с рациональными концами и взять их объединение. Поэтому в данном случае
(отметим,
что система содержит
лишь счетное число элементов).
Пример 3. Пусть – 
-мерное 
евклидово пространство, – система всех подмножеств
вида
.
Тогда индекс определяет число различных
разбиений векторов
на два
класса с помощью гиперплоскостей, проходящих через начало координат. Как было показано
в главе V,
,
откуда
следует
. (10.10)
Можно
показать, что в действительности
.
Аналогично
показывается, что если – -мерное евклидово пространство, a – система подмножеств вида
,
где
–
произвольный вектор, а 
– произвольная скалярная величина, то
.
