Тогда для каждой конкретной реализации (9.4) может быть найдена функция вектор параметров и, таким образом, получена последовательность
Эта последовательность определяет последовательность чисел
задающих расстояния от параметров а до Как (9.5), так и (9.6) являются случайными последовательностями, которые порождаются алгоритмом А восстановления зависимости и реализацией (9.4). Исследование алгоритмов восстановления зависимостей сводится, таким образом, к исследованию сходимости последовательности (9.6).
Существуют различные понятия сходимости случайных последовательностей. В этой главе мы используем два понятия: сходимость по вероятности и сходимость с вероятностью единица (почти наверное).
Определение 1. Последовательность случайных величин сходится к величине по вероятности, если, каково бы ни было вероятность выполнения неравенства
при стремится к единице, т. е.
Факт сходимости по вероятности записывается так:
Определение 2. Последовательность случайных величин сходится к величине с вероятностью единица, если, каково бы ни было вероятность выполнения неравенства
стремится к единице при т. е.
Сходимость с вероятностью единица (почти наверное) принято обозначать так:
Приведенные определения отражают различные требования к понятию сходимости.
В первом случае событие выделяет множество последовательностей, для которых выполняется условие Для заданного фиксированного При этом каждая последовательность с ростом I может то удовлетворять этому условию, то не удовлетворять ему. Сходимость по вероятности есть в некотором смысле «слабая» сходимость — она не дает никаких гарантий того, что каждая конкретная реализация сходится в обычном смысле.
Напротив, сходимость с вероятностью единица есть понятие «сильной» сходимости. Оно означает, что почти все реализации сходятся в обычном смысле. Сходимость почти наверное может быть определена еще и так.
Определение 2а. Последовательность случайных величин сходится с вероятностью единица к если мера множества реализаций, для которых существует предел
равна единице, т. е.
Легко проверить, что из сходимости с вероятностью единица следует сходимость по вероятности. В самом деле, так как для любого I справедливо неравенство
то из условия
следует
Обратное утверждение, вообще говоря, неверно. Дополнительные условия, при которых из сходимости по вероятности вытекает сходимость с вероятностью единица, определяет следующая лемма.
Лемма (Борель — Кантелли). Если для случайной последовательности найдется такое что для любого окажется выполненным неравенство
то последовательность сходится к с вероятностью единица.
Доказательство. Обозначим через событие, состоящее в том, что выполняется неравенство
Рассмотрим событие состоящее в том, что выполнится хотя бы одно из событий
Оценим вероятность этого события
Так как в силу условий леммы ряд (9.7) сходится, то
Рассмотрим теперь событие
Из того, что событие влечет за собой любое из событий в силу (9.8) получаем
Наконец, положим Как нетрудно установить, это событие означает, что найдется такое что для каждого хотя бы при одном
будут выполняться неравенства
Так как
то в силу что и требовалось доказать.