§ П.2. Функция роста

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

Обозначим через

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

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

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

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

где максимум берется по всем последовательностям длины I, назовем функцией роста системы S. Здесь максимум всегда достигается, так как индекс принимает конечное число значений.

Функция роста класса событий S обладает следующим замечательным свойством.

Теорема Функция роста либо тождественно равна , либо, если это не так, мажорируется функцией где минимальное значение I, при котором

Иначе говоря,

Для доказательства этого утверждения нам понадобится следующая

Лемма Если для некоторой последовательности и некоторого

то существует подпоследовательность длины такая, что

Доказательство. Обозначим

(здесь и дальше считаем, что при Для этой функции, как легко убедиться, выполняются соотношения

Эти соотношения в свою очередь однозначно определяют функцию при

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

следует, что существует элемент последовательности такой, что для некоторого выполнится а для некоторого другого окажется и, следовательно,

Для утверждение леммы верно ввиду ложности посылки. Действительно, в этом случае посылка есть

что невозможно, так как

Наконец, допустим, что лемма верна для при всех Рассмотрим теперь случай Покажем, что лемма верна и в этом случае для всех

Зафиксируем и проведем индукцию по Для как указывалось, лемма верна. Предположим, что она верна для и покажем, что она справедлива для Действительно, пусть для некоторой последовательности справедливо условие леммы

Лемма будет доказана, если мы найдем подпоследовательность длины такую, что

Рассмотрим подпоследовательность Возможны два случая:

В случае а), в силу предположения индукции, существует подпоследовательность длины такая, что что и требуется.

Для случая б) разделим подпоследовательности последовательности индуцируемые множествами из на два типа. К первому типу отнесем такие подпоследовательности что на полной последовательности событиями из S индуцируется как так и Ко второму — такие что на последовательности ! индуцируется либо либо Обозначим число подпоследовательностей первого типа а второго типа Легко видеть, что

и, следовательно,

Обозначим через S систему всех подмножеств таких, что на последовательности они индуцируют подпоследовательности первого типа. Тогда, если

то в силу предположения индукции существует подпоследовательность такая, что

Но тогда для последовательности имеем

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

Если же

то получим в силу (П.4) и б)

откуда в силу свойств функции

что противоречит условию леммы (т. е. невозможно). Лемма доказана.

Теперь докажем теорему. Как уже отмечалось, Пусть не равно тождественно , и пусть первое значение при котором

Тогда для любой выборки длины большей справедливо

Действительно, в противном случае на основании утверждения леммы нашлась бы такая подвыборка что

Равенство же невозможно, так как по допущению

Таким образом, функция либо тождественно равна либо мажорируется .

Теорема доказана.

Замечание. Функция может быть оценена сверху при и следующим образом:

Поскольку для функции выполняются соотношения для доказательства достаточно убедиться, что при справедливо неравенство

и проверить на границе, т. е. при Неравенство очевидно, равносильно неравенству

справедливость которого следует из формулы бинома Ньютона.

Остается проверить соотношение на границе. При я —1 оно проверяется непосредственно. Далее проверим оценку при малых

Теперь, чтобы проверить при воспользуемся формулой Стирлинга для оценки сверху

откуда при

и далее при

С другой стороны, всегда . Поэтому достаточно проверить, что при

С ростом I (при это неравенство усиливается, и поэтому достаточно его проверить при в чем и убеждаемся непосредственно.

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

Таким образом, для того чтобы оценить поведение функции роста, достаточно выяснить, каково минимальное число такое, что ни на одной последовательности длины I система S не индуцирует все возможные подпоследовательн ости.