§ 3. Определение функции роста

В этом параграфе будет введена характеристика класса событий, достаточная для выяснения факта равномерной сходимости.

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

число различных подпоследовательностей , индуцированных множествами . Очевидно, что

.

Число  будем называть индексом системы  относительно выборки .

Определение индекса системы можно сформулировать и иначе. Будем считать, что  эквивалентно  относительно выборки , если . Тогда индекс  есть число классов эквивалентности, на которые система  разбивается этим отношением эквивалентности.

Очевидно, что эти два определения равносильны. Функцию

,                        (10.8)

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

В заключение этого параграфа приведем несколько примеров функций роста для различных классов событий.

Пример 1. Пусть  – прямая, a  – множество всех лучей вида . Найдем функцию роста.

Пусть дана последовательность точек  без повторений. Изменив порядок последовательности, можно добиться того, что

.

Очевидно, что каждое множество  вида

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

такую, что .

При  индуцируется пустая подпоследовательность, а при  – вся последовательность . Ясно, что число различных последовательностей, индуцируемых множествами , равно . Таким образом,

.

Если в последовательности есть повторения, то индекс  разве лишь уменьшается. Поэтому

.             (10.9)

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

(отметим, что система  содержит лишь счетное число элементов).

Пример 3. Пусть  – -мерное  евклидово пространство,  – система всех подмножеств вида

 .

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

,

откуда следует

.                 (10.10)

Можно показать, что в действительности

.

Аналогично показывается, что если  – -мерное евклидово пространство, a  – система подмножеств вида

,

где  – произвольный вектор, а  – произвольная скалярная величина, то

.