5.15. Законы больших чисел в теории образов

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

случайных переменных

здесь в каждой строке все переменные стохастически независимы и принимают вещественные значения. Частичные суммы

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

при любом .

Подробное обсуждение по поводу этих предельных теорем читатель может найти в фундаментальной работе Гнеденко и Колмогорова (1954).

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

Если значения не являются вещественными числами, а образуют какие-то другие алгебраические структуры, то некоторые предельные теоремы остаются в силе. В качестве примера возьмем закон больших чисел

когда независимы, имеют одинаковое распределение и принимают значения в сепарабельном банаховом пространстве со средним которое интерпретируется как интеграл Петтиса. Расширения на другие алгебраические структуры можно найти в книге (Grenander 1963).

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

Допустим, что у нас есть массив случайных изображений из алгебры изображений

и соединители находящиеся в соответствии с типом соединения 2, принятым в При каких условиях можно доказать сходимость распределения случайных изображений

к некоторому предельному распределению на

Рассуждая по аналогии с классическим случаем мы должны предположить, что малы в некотором вероятностном смысле. В алгебре изображений обычно будет много (частичных) единичных элементов (см. гл. 3) и возникает желание потребовать, чтобы сосредотачивало большую часть всей вероятности вблизи некоторого единичного элемента, если достаточно велико.

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

Первый из них — очень простой. Рассмотрим алгебру свободных изображений в роли образующих выступают полуплоскости в и правило идентификации идентифицирует пересечения полуплоскостей. Другими словами (идеальные) изображения представляют собой выпуклые многоугольники. В этом случае, так же как и следующем, вопросы, связанные с измеримостью, не вызывают затруднений. Главные трудности заключаются в аналитическом рассмотрении предельных проблем.

Допустим, что с вероятностью единица все «реализации» случайного множества Г содержатся в фиксированном квадрате конечной площади А. Это предположение не имеет важного значения и введено лишь для удобства анализа.

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

Теорема 5.15.1. При сделанных выше предположениях

где состоит из всех точек таких что

Доказательство. Рассмотрим независимую последовательность одинаково распределенных случайных изображений с ассоциированными индикаторными функциями где Вспомним, что поскольку — алгебра свободных изображений, то у нас имеется только один тип соединителя. Следует также отметить, что рассматриваемая в данном случае регулярность не индуцирует стохастической зависимости для Последнее, конечно, в значительной мере упрощает анализ. Поскольку правило идентифицир) множества по пересечению, мы имеем просто

или, если выразить это через индикаторные функции,

Очевидно, . В таком случае, мера симметрической разности равна и для ее ожидаемого значения мы получаем:

Однако

Так как имеет конечную меру Лебега, можно воспользоваться теоремой об ограниченной сходимости. Подынтегральное выражение в (5.15.11), выраженное через (5.15.12), стремится к нулю тогда и только тогда, когда что и доказывает наше утверждение.

Замечание 1. В этом почти тривиальном случае мы не требовали, чтобы индивидуальные «члены» были вероятностно близки к единичному элементу, здесь — это Если потребовать

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

Замечание 2. Предельный элемент представляет собой выпуклое множество, но не обязательно многоугольник. Это означает, что он не обязательно принадлежит а принадлежит лишь замыканию этого пространства, см. конец гл. 4.

Обратимся теперь к более сложному случаю, все еще весьма частному, но представляющему большой интерес.

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

и выходной связью

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

В роли соединителей выступает конкатенация направо или налево; выберем, например, первое.

При этих условиях один из возможных вариантов для закона больших чисел может заключаться в следующем. Рассмотрим треугольный массив случайных изображений (5.15.5), причем для имеем

где . Вспомним — нам нужно, чтобы индивидуальные сжимались вплотную к единичному элементу. Мы будем теперь рассматривать как случайные переменные, скажем, на единичном квадрате, следуя процедуре, описанной в гл. 2 первого тома. Пусть все имеют -меру, заданную в виде плотности

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

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

При этих условиях мера Р на векторе будет задана плотностью

где нормировочная константа.

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

равномерно по и и

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

Теорема 5.15.2 При сделанных выше предположен раведливо

, а сходимость интерпретируется в смысле ожидаемой -нормы.

Доказательство. Введем функцию

Это плотность распределения в и потому определяет вероятностную меру Вероятностная мера для всех связей может быть выражена через ее плотность распределения как

причем

Мера описывает распределение для всех связей, если мы дали распределение с функцией плотности а все остальные сделали марковскими с плотностью перехода При произвольном положительном с для фиксированного

имеем

для события

Согласно (5.15.18) правая часть неравенства (5.15.23) стремится к нулю так, что

Если при записать

то становится очевидным, что При такой функции нормировочная константа в (5.15.22) может быть выражена через соотношение

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

следовательно, когда с достаточно мало, отношение

отличается от единицы на произвольно малую величину. Поэтому при

Однако маргинальная мера для задана плотностью

(кликните для просмотра скана)

Теперь изменим предположения и будем считать, что максимум не является единственным и что достигает в точках причем для . В этом случае, пользуясь методом, который мы только что применили выше, можно убедиться, что (5.15.25) по-прежнему выполняется, однако уже невозможно показать, что будет близок к какому-то определенному значению с большой вероятностью. Вместо (5.15.32) мы теперь получим

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

и, таким образом, после несложных рассуждений мы приходим к следующему утверждению.

Теорема 5.15.3. При тех же условиях, что и в теореме 5.15.2, за исключением того, что достигает своего максимума в для произвольного, но фиксированного справедливо

где задана выражением (5.15.42).

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

Замечание 3. Если достигает на отрезке [0, 1], то нам кажется, что предельное распределение будет равномерным на этом отрезке. Пока это еще не доказано.

Что происходит, когда условие (5.15.18) не выполняется? По этому поводу мы сделаем лишь некоторые эвристические замечания. Другими словами, рассмотрим тот случай, когда и, обусловленное и, не близко к и. Одна из возможностей, представляющая некоторый интерес, заключается в том, что очень близко не

где g - заданная функция, так что в (5.15.18) заменяется на Предположим, что функция непрерывна и положительна при и

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

будет меньше, чем Поэтому следует ожидать, что

Введем функцию

которая монотонно возрастает от 0 до по мере того, какл:

проходит значения от 0 до 1. Поэтому функция определена и можно ожидать, что

Отметим, что обратная функция переводит обратно на отрезок [0, 1]. как требуется в описании алгебры изображений. Вот почему мы ввели свойство (5.15.44).

Здесь будет рать роль и мы можем высказать догадку о его предельном распределении. В данном случае можно воспользоваться методом Лапласа, который мы применили для вывода (5.15.32), но при некоторой модификации. В самом деле, мы ожидаем получить одноточечное (или многоточечное, если максимум достигается в нескольких точках) распределение при значении для которого

является максимумом. Следовательно, асимптотически при мы будем искать такое которое максимизирует

где корень уравнения

Можно ли провести по этому поводу строгое доказательство — это другой вопрос, которым мы здесь заниматься не будем.

Вместо этого мы изучим несколько видоизмененную задачу. Аналитический метод, который мы к ней применим, по-видимому, будет иметь значительно более широкую сферу применения, чем тот частный случай, на примере которого он будет рассмотрен. Допустим, что образующие представляют собой линейные функции Чтобы носитель стремился к нулю, потребуем, чтобы функция сжималась, скажем, к . В табл. 5.15.1 проведено сравнение между рассматриваемым случаем и классическими предельными теоремами.

Таблица 5.15.1 (см. скан)

Пусть все образующие имеют в качестве носителей интервалы длины 1. Пусть далее, показатели связей образующей имеют совместное распределение на Если В конечно, то можно представить в виде квадратной матрицы

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

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

Отметим, что матрица не является случайной, однако сумма всех ее элементов равна единице. Если В — конечное множество, то без существенной потери общности можно считать, что показатели связей представляют собой натуральные числа:

с функцией разбиения

Результирующее изображение представляет линейную сплайн-функцию на и после нормирования мы получаем изображение определенное на [0, 1]. Здесь мы не можем воспользоваться теорией марковских цепей, чтобы получить предельную теорему - Q не является матрицей вероятностей переходов.

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

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

по вероятности. Случайное изображение будет определено ниже.

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

Случай 1. Если связи какой-либо образующей в точности одинаковы с вероятностью единица, то когда мы получаем только постоянные изображения на [0, 1], так что

Следовательно,

что убывает экспоненциально при таким образом, что мы можем ожидать

где

В таком случае

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

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

так что

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

При маргинальные вероятности остаются равными . В этом случае

здесь матрица вырожденная и имеет единственное ненулевое собственное значение Поскольку ординаты независимы

и одинаково распределены при естественно ожидать, что примет значение

о вероятностью единица — вспомним смысл сходимости в (5.15.55).

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

Теорема 5.15.4. Пусть наибольшее собственное число А, матрицы соответствует оператору проектирования Р, и предположим, что все остальные собственные числа меньше по абсолютной величине. Тогда сходится по вероятности к в соответствии со слабым распределением.

где -собственный вектор матрицы соответствующий собственному числу

Доказательство. Сначала очертим план доказательства, которое будет долгими полным технических деталей. Начнем с предположения, что простое. Согласно классической теории Фробениуса должно быть положительным, так же как и один из собственных векторов, нормированный соответствующим образом.

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

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

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

при помощи ортогональной -матрицы О и диагональной матрицы , предположим, что собственные числа были пронумерованы так, чтобы была невозрастающей

последовательностью. Вспомним, что является собственным вектором матрицы

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

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

и ее характеристическую функцию

Если воспользоваться (5.15.53), то можно записать

Последнее выражение перепишем в виде

причем

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

Чтобы вычислить сумму в (5.15.73), выразим ее в виде матричного произведения.

или

Вспомнив, что мы ввели вектор все элементы которого равны нулю, кроме элемента, (5.15.77) можно выразить как

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

Здесь главным членом является

С выражением для дело обстоит сложнее. Мы имеем

Отсюда следует, что для больших значений

так что, если ввести новую матрицу А, то

Аналогичным образом, справедливо следующее:

Эти соотношения приводят нас естественным образом к применению классического метода возмущений. Пусть наибольшим собственным значением будет а соответствующим ему нормированным собственным вектором будет Аналогичные обозначения примем для меньших собственных значений и соответствующих

им собственных векторов. Теперь воспользуемся хорошо известной формулой для вычислений по методу возмущений

где второе соотношение можно легко уточнить, однако здесь это не требуется. Следовательно,

причем

и

Тогда имеем

и, воспользовавшись соотношениями (5.15.85), получаем

Если теперь устремить к бесконечности, то

Однако так что полученное выше выражение сводится к

Объединяя что с (5.15.77) и (5.15.80), мы приходим к

Согласно теореме Парсеваля сумма в полученном выше выражении дает

Вернемся теперь к асимптотическому выражению для заданному в (5.15.69), и непосредственно из (5.15.73), (5.15.93), (5.15.77) и (5.15.70) получим

что есть преобразование Фурье от меры, сосредоточенной в точке Пользуясь опять тем фактом, что собственный вектор матрицы , а также соотношением (5.15.83), определяющим матрицу А, мы получаем постоянную

где Таким образом, мы показали, что

по вероятности при

Рассмотрим теперь произвольную вещественнозначную непрерывную функцию на [0, 1] и построим интег соответствующий слабой топологии в , как было описано выше:

Оцепим сверху через и снизу через

где — конечные функции (постоянные на интервалах). Тогда можно записать

пользуясь индикаторной функцией для множества Однако нам известно, что выполняется (5.15.96), откуда следует

и поэтому

и для изображения имеем

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

В данном случае значение — простое и соответствующий проектор так что матрица

вырожденная и имеет единственное ненулевое собственное значение

с соответствующим собственным вектором Тогда вероятность (5.15.66) сводится к

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

Чтобы перейти к случаю кратного мы сначала заметим, что (5.15.69) немедленно обобщается к по существу при помощи тех же рассуждений.

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

Нам нужны высокие степени чтобы вычислить в (5.15.86). Однако мы приходим к выражениям вида

Ясно также, что «большинство» членов в имеют вид при больших и так что

Продолжая рассуждения в том же духе, получаем

Можно также мажорировать нормы членов (5.15.107), пользуясь неравенствами

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

В нашем случае так что

Для мы получаем, как и прежде,

так что, снова пользуясь теоремой Парсеваля, соотношениями (5.15.73), (5.15.69) и тем фактом, что матрица Р

самосопряженная, мы получаем

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

так что

При

мы имеем

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

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

и из (5.15.118) мы получаем Если то любой собственный вектор должен лежать в области значений Р.

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

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

Однако это сделать нелегко. Рассмотрим матрицу вероятностей переходов для при заданном Она будет зависеть от Можно показать (см. Grenander 1978b), что эта матрица сходится при Возможно, этим можно воспользоваться как исходной точкой для более простого доказательства.

Замечание 5. Нам неизвестно, справедлива ли теорема также в случае слабой топологии.

Замечание 6. Законы больших чисел для других регулярных структур еще не изучались. Наиболее удобным объектом для таких исследований, по-видимому, является случай «квадратная решетка».