§ 4. Свойства функции роста

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

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

.

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

.

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

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

,

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

.

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

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

,

 при ,

 при .                       (10.11)

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

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

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

.

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

,

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

.

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

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

справедливо условие леммы:

.

Найдем подпоследовательность длины :

такую, что

.

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

а) .

б) .

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

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

; ,

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

.                     (10.12)

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

б') ,

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

 и .

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

,

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

Если же

б") ,

то получим в силу (10.12) и б)

,

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

в противоречии с предположением, т. е. б") невозможно.

Лемма доказана.

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

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

.

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

.

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

.

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

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

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

.                       (10.13)

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

,                      (10.14)

и проверить (10.13) на границе, т. е. при , .

Неравенство (10.14), очевидно, равносильно неравенству

,

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

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

	1	2	3	4	5
	1	4	11	26	57
	1,5	4	12		81

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

,

откуда при

и, далее, при

.

С другой стороны, всегда

.

Поэтому достаточно проверить, что при

.

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

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

.                 (10.15)

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

Рис. 21.

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

Замечание 2. Существуют примеры класса событий , для которых

,

где  – первое число, при котором

.

Пусть  – произвольное бесконечное множество, a  состоит из всех его конечных подмножеств с числом элементов, меньшим . Очевидно, что

 при ,

 при .

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