Сложность аппроксимации гауссовских случайных полей большой параметрической размерности тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

Хартов, Алексей Андреевич АВТОР
кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ
Санкт-Петербург МЕСТО ЗАЩИТЫ
2014 ГОД ЗАЩИТЫ
   
01.01.05 КОД ВАК РФ
Диссертация по математике на тему «Сложность аппроксимации гауссовских случайных полей большой параметрической размерности»
 
Автореферат диссертации на тему "Сложность аппроксимации гауссовских случайных полей большой параметрической размерности"

На правах рукописи

ХАРТОВ АЛЕКСЕЙ АНДРЕЕВИЧ

СЛОЖНОСТЬ АППРОКСИМАЦИИ ГАУССОВСКИХ СЛУЧАЙНЫХ ПОЛЕЙ БОЛЬШОЙ ПАРАМЕТРИЧЕСКОЙ

РАЗМЕРНОСТИ

01.01.05 — теория вероятностей и математическая статистика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

5 КОН 2014

005549759

Санкт-Петербург — 2014

005549759

Работа выполнена на кафедре теории вероятностей и математической

статистики математико-механического факультета

ФГБОУ ВПО «Санкт-Петербургский государственный университет»

Научный руководитель:

Лифшиц Михаил Анатольевич

доктор физико-математических наук, профессор,

профессор кафедры теории вероятностей и математической статистики

ФГБОУ ВПО «Санкт-Петербургский государственный университет»

Официальные оппоненты:

Велопольская Яна Исаевна

доктор физико-математических наук, профессор, профессор кафедры математики ФГБОУ ВПО «Санкт-Петербургский государственный архитектурно-строительный университет»

Чирина Анна Владимировна кандидат физико-математических наук, ассистент кафедры высшей математики № 2 ФГБОУ ВПО «Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В. И. Ульянова (Ленина)»

Ведущая организация:

ФГБОУ ВПО «Московский государственный университет им. М.В.Ломоносова»

Защита состоится «-»_2014 года в_часов на

заседании диссертационного совета Д 002.202.01 в ФГБУН Санкт-Петербургском отделении Математического института им. В. А. Стеклова Российской академии наук по адресу: 191023, Санкт-Петербург, наб. р. Фонтанки, д. 27, к. 311.

С диссертацией можно ознакомиться в библиотеке и на сайте ФГБУН

Санкт-Петербургского отделения Математического института

им. В. А. Стеклова Российской академии наук, http://www.pdmi.ras.ru/

Автореферат разослан «_»_2014 года.

Ученый секретарь

диссертационного совета Д 002.202.01 доктор физико-математических наук

А. Ю. Зайцев

Общая характеристика работы

Актуальность темы. Теория гауссовских случайных функций интенсивно развивается в последние годы (см. [1], [4]). Одним из ее современных направлений является исследование вопросов конечноранговой аппроксимации случайных полей (см. [3] и [7]). Здесь центральным является следующий вопрос: каким должен быть ранг аппроксимирующего поля, чтобы ошибка аппроксимации имела заданную малость? Задача может рассматриваться в двух постановках — в среднем и по вероятности. Наименьший подходящий ранг в этих постановках называется соответственно сложностью аппроксимации в среднем и сложностью аппроксимации по вероятности. Эти характеристики являются главными объектами изучения в теории информационной сложности, оформившейся в 80-х годах с выходом монографий [9]-[11].

В 90-х годах в рамках теории информационной сложности началось активное изучение многопараметрических задач аппроксимации. Основные положения и результаты этого молодого направления сформулированы в недавно изданном фундаментальном трехтомнике Э. Новака и X. Вожняковского «Tractability of Multivariate Problems» [12]-[14]. В многопараметрических задачах представляет интерес изучение случайных полей, зависящих от настолько большого числа параметров, что к самой параметрической размерности случайного поля можно подойти асимптотически. Иными словами, рассматривается не одно случайное поле, а целая последовательность случайных полей, как правило, структурно связанных между собой. Для каждого поля из этой последовательности можно определить характеристики сложности аппроксимации и изучать их при растущей параметрической размерности. Здесь есть два пути исследования. В одном из них сложность рассматривается как функция двух независимых переменных: уровня ошибки и параметрической размерности. В настоящее время центральную роль на этом пути играет понятие трактабильности, которое характеризует скорость изменения сложности аппроксимации по каждой из своих переменных. Здесь недавно получены важные результаты (см. [5] и [6]). Наряду с предыдущим подходом, можно рассматривать сложность аппроксимации в несколько иной постановке, а именно, при сколь угодно малом, но фиксированном уровне ошибки, и при стремящейся к бесконечности параметрической размерности. Фактически, речь идет о нахождении асимптотик сложности аппроксимации. Такая постановка представляет самостоятельный интерес, поскольку, как отмечается в [12], она характерна для некоторых моделей финансовых вычислений. Кроме того, в ней применяются идеи и методы, отличные от тех, что используются при рассмотрении трактабильности. Это направление до недавнего времени оставалось мало изученным.

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

Методы исследований. В диссертационной работе центральную роль в асимптотическом анализе сложности аппроксимации играет вероятностный подход, идея которого была впервые предложена в работе М. А. Лиф-шица и Е. В. Туляковой [7]. Этот подход значительно обобщается и дополняется автором, что позволяет достигать полученных результатов, используя аппарат классических предельных теорем и их уточнений. Кроме того в диссертации используются факты из теории безгранично делимых распределений и теории правильно меняющихся функций, применяются оценки теории больших уклонений.

Основные результаты.

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

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

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

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

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

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

Апробация работы. Результаты диссертации докладывались автором на 43-й всероссийской школе-конференции «Современные проблемы математики» (Екатеринбург, 29 января - 5 февраля 2012 г.), па международной конференции «Вероятность и анализ» (Польша, Бедлево, 10-16 июня 2012 г.), на международной конференции «Теория вероятностей и ее приложения» (Москва, 26-30 июня 2012 г.), на международной конференции «Современная стохастика: теория и приложения III» (Украина, Киев, 10-14 сентября 2012 г.), на 4-ом Северном Треугольном семинаре (Финляндия, Хельсинки, 6-8 марта 2013 г.). Кроме того, были сделаны доклады по теме диссертации в Санкт-Петербурге на городском семинаре по теории вероятностей и математической статистике под руководством академика И. А. Ибрагимова (март 2014 г.), на семинаре «Современная стохастика» (май 2011 г.) и на семинаре «Теория вероятностей» в Лаборатории им. П. Л. Чебышева (сентябрь 2013 г. и февраль 2014 г.).

Публикации. Основные результаты диссертации опубликованы в статьях [П1]-[ПЗ] журналов, рекомендованных ВАК, а также в тезисах [П4]-[П6] докладов автора на конференциях.

Структура и объем диссертации. Диссертация состоит из введения, пяти глав и списка литературы, содержащего 101 наименование. Общий объем работы составляет 137 страниц.

Содержание работы

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

Рассмотрим случайное поле X(£), Ь € Т, с траекториями в некоторого нормированном пространстве (<2, || • ||<э) функций, определенных на Т. Будем аппроксимировать поля X с помощью полей конечного ранга'.

п

Х{1) = X) * 6 т> (!)

т=1

гДе - случайные величины, фт{-) ~ детерминированные функции, принадлежащие пространству <3. Обозначим Лп класс полей вида (1). Задача заключается в поиске такого п, чтобы ошибка аппроксимации имела заданную малость. Здесь возможны две постановки — в среднем и по вероятности. Сложностью аппроксимации в среднем называется величина

паУЕ(е) := шш(п € N : ш£ Е \\Х - Х\\% < е2Е ||Л||?Л.

хелгп >

Сложностью аппроксимации по вероятности называется величина пргоЬМ):=тт{п€М: Ы р(||Х - Х\\% > е2Е <

Здесь е € (0,1) — порог ошибки, а 6 е (0,1) — уровень значимости.

В рамках теории многопараметрических задач (см. [12]—[14]) представляет интерес изучение величин пауЕ (е) и пргоЬ(е, 6) для случайных полей возрастающей параметрической размерности. То есть рассматривается не одно поле X, а последовательность случайных полей £ € Т^ С

в, € М, с траекториями в нормированных пространствах || ■ Для

каждой пары ((¿л, Ха), ё € определяются характеристики и

п2гоЬ(е,5), и далее они изучаются при <2 —> оо.

Описанная задача в той степени общности, в которой она сформулирована, пока изучена слабо. Мы рассматриваем только гильбертов случай (¿л := £г([0,1]^), й € N. Здесь непрерывное в среднеквадратическом случайное поле Ха^), £ 6 [0,1]сг, как элемент пространства ^([0,с нормой |[ • Цг.й с вероятностью 1 может быть представлено разложением Кархунена-Лоэва:

Ы*) = £ Фа,Ж * е [0,1]«, (2)

пгбК

где (А^.т)тбк — невозрастающая последовательность собственных чисел, (Фс1,т)тп£П — соответствующая последовательность собственных функций корреляционного оператора поля Х^, (£<*,т)тек — независимые стандартные гауссовские случайные величины. Как известно (см. [8], с. 51), разложение (2) является в -£<2([0,1]^) оптимальным с точки зрения конечноран-говой аппроксимации. Здесь справедливы следующие представления для

сложности в среднем:

п™е(е) := шш{п е N : Е \\Хй - < е2 Е

и сложности по вероятности:

пГЬ(е, <5) := тш{п 6 N : - Ха,п\\\А > е2 Е ^ б).

где Xtг,n(t) := £т=1 и,т t 6 [0,1]«.

Основное внимание в работе уделяется случайным полям Xй € М, с корреляционными функциями следующего вида:

а

0,1]", (3)

¿=1

где /сЬ) — корреляционные функции некоторых однопараметрических процессов t € [0,1], 1 6 N. Случайные поля с такой корреляционной структурой называют тензорными (см. [4]); в частности, говорят, что поле Хл^), £ £ [0,1]^ есть тензорное произведение процессов ..., Если в формуле (3) все одинаковы и равны корреляционной функции 1С некоторого процесса X, то Хд называют тензорной степенью процесса X. Класс случайных полей тензорного типа достаточно широк. Типичными его представителями служат броуновский лист — тензорная степень винеровского процесса, броуновская «подушка» — тензорная степень броуновского моста, тензорные произведения интегрированных гауссовских процессов с определенными степенями гладкости и т.д. (см. [2]).

Для тензорного произведения процессов ..., Х^ с корреляцион-

ной функцией вида (3) собственные пары в разложении Кархунена-Лоэва (2) формируются следующим образом: (А^т)т6м есть занумерованная в порядке невозрастания последовательность чисел > а (Ф<1,т)т,еп

соответствующим образом индексированная последовательность собственных функций вида У'к- 1 ~ • • • е [0,6 М, где для каждого £ N невозрастающая последовательность обозначает

собственные числа, а (^Р'^ек — соответствующие собственные функции корреляционного оператора процесса при этом обозначим А« :=

Егек^?'- Если £0) = 1С, то мы будем упрощать обозначения: А» := г 6 N. А := А^, ] € N.

Таким образом, для ¿г-нормы задача изучения сложности аппроксимации при 6, —> оо во многом сводится к асимптотическому анализу упорядо-ченнного по невозрастанию массива произведений ^ с растущим к бесконечности числом сомножителей.

В главе 1 настоящей работы делается обзор теории информационной сложности и теории многопараметрических задач, описывается понятие трактабильности, приводятся связанные с ней результаты. В этой главе мы рассматриваем задачу ^г-аппроксимации в рамках данных теорий с более абстрактной точки зрения, где Ха является случайным элементом тензорного произведения' сепарабельных гильбертовых пространств. Кроме того, в главе 1 подробно рассматривается семейство тензорных случайных полей и его известные представители.

Детальному изучению сложности в среднем и сложности по ве-

роятности га^гоЪ(£, при фиксированном пороге ошибки е £ (0,1), параметрической размерности <1 —> ос, и уровне значимости 5 = возможно зависящем от е и й, посвящены главы 2-5 диссертации.

В главе 2 мы рассматриваем последовательность случайных полей Хд, (/ € К, без предположения тензорной корреляционной структуры. Все полученные результаты о поведении п^У5(е) и п^тоЪ(е,6) при й -> оо формулируются в терминах серий (Ай1ТП)тем, й е N. Отметим, что теоремы и утверждения главы 2 широко используются в последующих главах.

Глава 3 диссертации посвящена асимптотическому анализу сложности аппроксимации в среднем. В параграфе 1 рассматривается вопрос о критериях ограниченности сложности. Приведем полученные утверждения в сокращенной форме.

Утверждение 1. Следующие соотношения эквивалентны:

оо _ дШ

(г'г) Ve е (0,1) п™е(е:) -> оо, d -»• оо. Утверждение 2. Следующие соотношения эквивалентны:

(ii) Ve е (0,1) sup пйр{е) < оо. deN

В параграфе 2 мы развиваем вероятностный подход, предложенный М. А. Лифшицем и Е. В. Туляковой в статье [7]. В параграфе 3 приводятся необходимые факты из теории правильно меняющихся функций, теории безгранично делимых законов распределения и классической теории предельных теорем теории вероятностей

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

Теорема 1. Пусть А = (Ad)deN — последовательность из R, а В — (B¿)¿efi — такая последовательность, что Bd —> оо при d —^ оо. Пусть невозрастающая функция q: (0,1) R и функция распределения С: R —> [0,1], для любого е £ (0,1) удовлетворяют равенству q(e) = £-1(1 — е2). Пусть для последовательности (A¿)¿gN выполнено:

Ve еС(q) ]nnYs(e) = Ad + q{£)Bd + o{Bd), d оо.

Тогда функция распределения £ принадлежит классу устойчивых распределений.

Прежде чем сформулировать дальнейшие результаты, мы рассмотрим условия на (A¿)teNi которые в них фигурируют.

Наиболее важный случай соответствует предположению о сходимости следующего ряда:

>е N

Если это выполнено, то конечны следующие величины:

¿6N ¿6N

Рассматриваются также (A¿)¿g;;, не удовлетворяющие (4), по имеющие правильное изменение:

Й1^6")51"^1' [0-2], (5)

»6N ^ '

где iр — медленно меняющаяся функция (м. м. ф.) при х —» оо.

Доказаны следующие теоремы, обобщающие результат М. А. Лифшица и Е. В. Туляковой об асимптотике сложности в среднем из статьи [7].

Теорема 2. Пусть А = (.A^deN ~~ последовательность из R, а В = (Bd)den — такая последовательность, что Bd оо при d оо. Чтобы для (A¿)¡eN была справедлива асимптотика:

Ve 6(0,1) lnn%s{e)=Ad + <í>-\l-e2)Bd + o(Bd), d ^ оо,

необходимо и достаточно выполнение условия (4), где а2 > 0, или условия (5) при а —2, а также выполнение условий

Bd~B'd, Ad = dE + o{B'd), d-> оо.

Здесь Ф — функция распределения стандартного нормального закона, числа B'd := d1/2(pi(d), где м. м. ф. <fi(d) := ((2^)~1^2)*(d1/2), ф — функция де Хаана для tp, (•)* — сопряжение де Вруина. При выполнении (4) можно полагать B'd := crd1!2.

Теорема 3. Пусть А = (А^лек ~~ последовательность из а В = (Б^аеК — такая последовательность, что В а оо при <1 оо. Чтобы для при заданном а € (0,2) была справедлива асимптотика:

У£€(0,1) \пп^(е) = Ас1 + 5-^,0(1 - + о(Ва), й оо,

необходимо и достаточно выполнение условия (5) при заданном а, а также выполнение условий

ВЛ ~ В'л, АЛ = А'а + о(В'Л), оо.

Здесь 50,1,1,0 — функция распределения а-устойчивого закона с крайней правой асимметрией, числа В'а := , где м. м. ф. ^г(^) := гф^{д}/а),

(•)* — сопряжение де Бруина, гра(х) := {са/(р{х))1/а,

С<* := ^ Г(2-Осо»(*4/2)-

Константы А'а = 0 при а е (0,1), = ¿Е при а е (1,2), а при а = 1

:=<1<р(В'а)-с--В'<11

где — функция де Хаана для <р, с — константа Эйлера.

Для случая медленного изменения хвостов спектра доказан следующий результат.

Теорема 4. Пусть удовлетворяет условию (5) при а = 0. Тогда

для любого е € (0,1) имеем

1ип ¿¥?(1пп™е(е)) = -1п(1 -е2).

Показывается, что при любом е € (0,1) величина 1пп^У8(е) является быстро меняющейся функцией на оо по параметру й £ N.

В параграфе 5 главы 3 при небольшом усилении условия (4):

5>хГх<»' т

ieN

найдено точное асимптотические представление для (е) при й -> оо для тензорных степеней процессов. Вид этой асимптотики зависит от арифметической структуры собственных чисел (А£)^к. Последовательность (А;)^ назовем экспоненциальной, если найдутся такие числа а и Ъ > 0, что выполнено

Параметры о и 6 будем называть соответственно сдвигом и шагом экспоненциальной последовательности (Аг-),еИ. Всегда будем полагать, что а и Ъ выбраны так, что шаг Ь максимально возможный.

Теорема 5. Пусть (А^е^ удовлетворяет условию (6), причем а2 > О, не является экспоненциальной. Тогда для любого е £ (0,1) имеем

где

~ Г ■ ехР {Ей + + 9«.2°) > оо.

Ьд := Ф-(1 - е2), Е(|1пх1 - Т (7)

Теорема 6. Пусть (Аг),-6к удовлетворяет условию (6), причем о2 > 0, и является экспоненциальной с некоторым максимальным шагом Ъ > 0 и сдвигом а € К. Тогда для любого £ € (0,1) будем иметь при д —> оо

■ ехр ^Ей -1- дЕд<7с21/2 + ^¿о + ЬАй.е} ,

величины и дЕ)г выбираются из (7), а удовлетворяет соотношениям

-1/2 < Иш ^ Пт < 1/2.

¿-л оо

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

дО)

Нт -7^ = 1. (8)

Отметим, что асимптотический анализ проводится лишь при расходимости ряда (см. утверждение 1):

3=1 Л1

Здесь ключевую роль играют саморазложимые распределения (класс Ь безгранично делимых законов распределения).

Теорема 7. Пусть А = последовательность из Ш, а В =

— такая последовательность, что Вд сс при (1 —> оо. Пусть

невозрастпающая функция д: (0,1) —» М и функция распределения К —> [0,1], для любого е е (0,1) удовлетворяют равенству = £-1( 1 — г2). Пусть для 3 б выполнены условия (8) и (9). Если имеет

место асимптотика

Уе € С(9) ' 1п= А<1 + ч(е)ВЛ + о(Ва), й -> оо, (10)

то функция распределения С, принадлежит классу Ь с нулевой спектральной функция Леей на отрицательной полуоси.

В параграфе б сформулированы необходимые и достаточные условия для того, чтобы п^в(е) имела асимптотику вида (10). Приведем здесь этот результат в наиболее простой форме, когда дополнительно выполнено условие сильного доминирования первых двух собственных чисел в последовательностях (А^)гси, 3 6 М:

^ V- ^

Е £ 717)<°°- (11)

] = 1 »£№¿>2 Л1

Теорема 8. Пусть А — — последовательность из К, а В =

(.В^ек — такая последовательность, что Вд —V оо при (1 —> оо. Пусть функция распределения £: Е —» [0,1] принадлежит классу £ с триплетом (ц.82,Ь), где Ь{х) = 0 при х в (—оо,0). Пусть невозрастающая функция д: (0,1) —> К и функция распределения, С для любого е € (0,1) удовлетворяют равенству ^(гг) = £-1( 1 — е2). Чтобы для (А^)гем> 3 £ удовлетворяющих (8), (9) и (11), была справедлива асимптотика:

Ve € (0,1) lnn*vs(£) = Ad + q{e)Bd + o(Bd), dоо,

необходимо и достаточно выполнение следующих условий: Л А(л /А« \

(A)

(B) Шп ± (Âd - ¿lin = -, - / ;

1 (О,оо)

(C) = Я&^оЩ t^Bd) = s2,

где

Ad := Ad-2^ln~Tj)' d€N' j=i

jln^l ^i^e—), ieN, d e N.

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

Теорема 9. Пусть А = (А^)йем — последовательность из М, а В = (Bd)d£H ' такая последовательность, что B¿ —> oo при d —> ос. Пусть невозрастающая функция q: (0,1) —► R и функция распределения £: R —¥ [0,1] для любого е € (0,1) удовлетворяют равенству q(¿) — C~l{\ — е2). Пусть для (A¿)¿6n выполнено Х\ < Л и при некотором фиксированном 5 £ (0,1) имеет место асимптотика:

VeeC(q) lnn%°b(e,6)=Ad + q(e)Bd+o(Bd), d -> oo.

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

Следующие теоремы обобщают и дополняют результат М. А. Лифшица и Е. В. Туляковой из статьи [7] об асимптотике сложности по вероятности.

Теорема 10. Пусть для (A¡)¿6n выполнено условие (4), с сг2 > 0, или условие (5) при а = 2. Пусть константы Bd, d 6 N, удовлетворяют условиям теоремы 2. Тогда для любого е S (0,1) и для произвольной последовательности (6d,s)deN W3 (0,1), удовлетворяющей условиям:

lim —^-=г->-< lim -¿-< g(e),

d—»oo d—>oo iíd

1пп^гоЬ(е,(5й)Е) = Ed. + Ф-1(1 — e2)Bd 4- o(Bd), d oo. (12)

Теорема 11. Пусть для (Ai)igN выполнено условие (5) при а € (0,2). Пусть константы Ad и Bd, d е N, удовлетворяют условиям теоремы 3. Тогда для любого е € (0,1) и произвольной последовательности (5d,e)de'A из (0,1), удовлетворяющей условиям:

hm --—-< q(e), lim -J-< q(e),

d—>ca JDd d—*oо

имеем

lnnfb(£, SdtC) =Ad + 5-^,0(1 - e2)Bd + o(Bd), d -»■ 00, (13)

Кроме того, в параграфе 1 главы 4 доказана необходимость условий (4) и (5) при а € (0,2] для асимптотик (12) и (13). В этом же параграфе рассмотрен случай, когда собственные числа удовлетворяют условию (5) при а = 0.

Теорема 12. Пусть для (Aj)¿eN выполнено условие (5) при а = 0. Тогда для любого е £ (0,1) и для произвольной последовательности (<$d,e)<ieN из (0,1), удовлетворяющей условиям:

dp(ln|ln(l-<Ы1) , dv(ln\\n6dtE\)

Ьт -тгт:-ом-> У® и п-2Т1 ^

d^ 11п(1 — е2)| 11п(1 — е2)|

имеем

lim ¿Mlnn^M^)) = -ln(l -е2).

d—ь оо

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

Теорема 13. Пусть для (A¿)í6n выполнено условие (6), причем а > 0. Тогда для любого е £ (0,1) и произвольной последовательности из (0,1), такой что

У |bi(min{<Sd|g,l-<yd>e})[ Л™ d~Va exp{Ed + q€tldV2} ~ '

UAieeAt

Помимо однородных тензорных произведений процессов в главе 4 рассмотрены неоднородные тензорные произведения. При условиях (8) и (9) на их последовательности собственных чисел j £ N, получены

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

Inn§™b(e> 6d,t) = Ad + q(e)Bd + o(Bd), d 00.

При этом доказывается, что они для n¿vs(e) и n¿rob(£, S) идентичны в достаточно широкой области варьирования ö — öd,e. Также показано, что

компонента д функционально связана с квантилями саморазложимых законов распределения. Эти результаты аналогичны теоремам 10 и 11.

В главе 5 диссертации мы применяем критерии, полученные в главах 3 и 4, для конкретных примеров тензорных случайных полей. В параграфе 1 мы находим логарифмические асимптотики сложности в среднем и по вероятности для тензорных степеней процессов, у которых последовательность собственных чисел правильно изменяется в соответствии с асимптотикой:

Аг _Р_

Л ~ г1+Ро(1пг)1+Р1(1п1пг)1+^ ' ■ 1

где ¡3 > 0, ро > 0, а числа р1 £ Р. и р2 £ К подбираются так, чтобы < со. В параграфе 2 мы получаем точные асимптотики сложности аппроксимации в среднем и по вероятности для броуновского листа и броуновской «подушки».

Параграф 3 главы 5 посвящен изучению логарифмических асимптотик сложности в среднем и по вероятности для тензорных произведений эйлеровских интегрированных процессов с возрастающей степенью гладкости. Рассмотрен случай, когда отношение первых двух собственных чисел процессов ведет себя регулярно по ^ € N в соответствии со следующей асимптотикой:

\(Л о

= з-2(г,+1) „ 5 (14)

Аы з№з)р к ;

где Р > 0 и р 6 Е.

Показано, что при р > 1 справедливо зир^^п^^е) < оо для любого е 6 (0,1). Для случая р = 1 получен следующий результат.

Утверждение 3. Пусть выполнено условие (14) при р = 1 и /3 > 0. Тогда

Уе 6(0,1) 1пп^(е) = £_1(1-е2)1псг+о(1псг), й -> оо,

где С. — саморазложимый закон распределения с триплетом (/л,в2,!,), в котором /х = /?7г/4, в2 = 0 и Ь(х) = /31пж1(х 6 (0,1)).

В случае р < 1 при дополнительном усилении условия (14):

я

2_ _ 3-2(г^ + 1) _ _Р_

(15)

вычислена следующая асимптотика.

Утверждение 4. Пусть выполнено условие (15) прир <1 и /3 > 0. Тогда имеем асимптотику

Уе б (0,1) 1пп^(£)=^ + Ф-1(1-£2)В^ + о(^), <1ос,

где

А', := (1п+ с^(1п 1пй)(1п+ с{р%(1п В', := с^Опй)^. Здесь коэффициенты определяются по формулам: с(!) — с(2) с(3) ._ 0(1-2р) _ г(4) ._ (_£.\1/2

ср,/9 — 2-р> — ср,0 (1_р)2 1-р > СР,/3 — \,3-рУ •

Также показано, что логарифмические асимптотики п^гоЬ(е, 5) и п™&(е) совпадают в достаточно широкой области варьирования 5 = ^.е-

Приведенные утверждения параграфа 3 в некотором смысле уточняют и дополняют результаты о трактабильности, полученные в статье [6].

Список литературы

[1] R. J. Adler, J. Taylor, Random Fields and Geometry, Springer, New York, 2007.

[2] A. Karol, A. Nazarov, Ya. Nikitin, Small ball probabilities for Gaussian random fields and tensor products of compact operators, Trans. Amer. Math. Soc., 360 (2008), no. 3, 1443-1474.

[3] T. Kühn, W. Linde, Optimal series representations of fractional Brownian sheets, Bernoulli, 8 (2002), no. 5, 669-696.

[4] M. A. Lifshits, Lectures on Gaussian Processes, Springer, New York, 2012.

[5] M. A. Lifshits, A. Papageorgiou, H. Wozniakowski, Average case tractability of non-homogeneous tensor product problems, J. Complexity, 28 (2012), no. 5-6, 539-561.

[6] M. A. Lifshits, A. Papageorgiou, H. Wozniakowski, Tractability of multi-parametric Euler and Wiener integrated processes, Probab. Math. Stat., 32 (2012), no. 1, 131-165.

[7] M. A. Lifshits, E. V. Tulyakova, Curse of dimensionality in approximation of random fields, Probab. Math. Stat., 26 (2006), no. 1, 97-112.

[8] K. Ritter, Average-case Analysis of Numerical Problems, Lecture Notes in Math. No 1733, Springer, Berlin, 2000.

[9] J. F. Traub, G. W. Wasilkowski, H. Wözniakowski, Information, Uncertainty, Complexity, Addison-Wasley, Reading MA, 1983.

[10] J. F. Traub, G. W. Wasilkowski, H. Wozniakowski, Information-Based Complexity, Academic Press, New York, 1988.

[11] J. F. Traub, H. Wozniakowski, A general theory of optimal algorithms, Academic Press, NewYork, 1980.

[12] E. Novak, H. Wozniakowski, Tractability of Multivariate Problems. Volume I: Linear Information, EMS Tracts Math. 6, EMS, Zürich, 2008.

[13] E. Novak, H. Wozniakowski, Tractability of Multivariate Problems. Volume II: Standard Information for Functionals, EMS Tracts Math. 12, EMS, Zürich, 2010.

[14] E. Novak, H. Wozniakowski, Tractability of Multivariate Problems. Volume III: Standard Information for Operators, EMS Tracts Math. 18, EMS, Zürich, 2012.

Публикации автора по теме диссертации

Статьи в журналах, рекомендованных ВАК:

[Ш] А. А. Хартов, Аппроксимация в среднем тензорных случайных полей возрастающей размерности, Зап. науч. сем. ПОМИ, 396 (2011), 233256.

[П2] А. А. Хартов, Аппроксимация по вероятности тензорных случайных полей возрастающей параметрической размерности, Зап. научн. сем. ПОМИ, 412 (2013), 252-273.

[ПЗ] А. А. Хартов, Сложность аппроксимации случайных полей тензорного типа с тяжелым спектром, Вестник СПбГУ, Сер. 1 Матем., Мех., Астр., (2013), №2, 64-67.

Другие публикации:

[П4] А. А. Хартов, Аппроксимация в среднем тензорных случайных полей возрастающей размерности, Тезисы Международной (43-й Всероссийской) молодежной школы-конференции «Современные проблемы математики», УроРАН, Институт математики и механики, Екатеринбург, (2012), 296-298.

[П5] A. A. Khartov, Approximation in probability of tensor product-type random fields of increasing parametric dimension, Abstracts of International Conference «Probability Theory and Its Applications», Moscow, 2012, 108-109.

A. A. Khartov, Approximation complexity of tensor product-type random fields with heavy spectrum, Abstracts of International conference «Modern Stochastics: Theory and Applications III», Kyiv, 2012, 21-22.

Подписано в печать 29.04.2014. Формат 60x84/16 Отпечатано с готового оригинал-макета в типографии ЗАО «КопиСервис». Печать ризографическая. Заказ № 1/0429. П. л. 1.00. Уч.-изд. л. 1.00. Тираж 100 экз.

ЗАО «КопиСервис» Адрес: 197376, Санкт-Петербург, ул. Проф. Попова, д. 3. тел.: (812) 327 5098

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

ФГБОУ ВПО «Санкт-Петербургский государственный университет»

Сложность аппроксимации гауссовских случайных полей большой параметрической размерности

Специальность 01.01.05 — Теория вероятностей и математическая статистика

На правах рукописи

Хартов Алексей Андреевич

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата физико-математических наук

Научный руководитель: д. ф.-м. н., проф. М. А. Лифшиц

Санкт-Петербург — 2014

Оглавление

Введение 3

1. Основы теории многопараметрических задач аппроксимации 11

1.1. Теория информационной сложности..................................................11

1.1.1. Основные понятия и мотивация..............................................11

1.1.2. Типы информации..............................................................13

1.1.3. Сложность в среднем и по вероятности......................................14

1.1.4. Линейные задачи ..............................................................16

1.1.5. Стохастическая интерпретация линейных задач............................18

1.2. Многопараметрические задачи аппроксимации ....................................19

1.2.1. Линейные задачи ..............................................................20

1.2.2. Линейные тензорные задачи..................................................24

1.2.3. Случайные поля тензорного типа............................................28

1.2.4. Примеры тензорных случайных полей......................................30

2. Линейные задачи 33

2.1. Сложность в среднем..................................................................33

2.1.1. Аппроксимационный порог и общие оценки сложности....................33

2.1.2. Ограниченность по параметрической размерности ........................36

2.1.3. Скалярные спектральные меры..............................................40

2.1.4. Логарифмические асимптотики..............................................41

2.2. Сложность по вероятности............................................................45

2.2.1. Вспомогательные утверждения ..............................................46

2.2.2. Логарифмические асимптотики..............................................50

3. Линейные тензорные задачи в постановке в среднем 54

3.1. Ограниченность сложности но параметрической размерности....................54

3.2. Скалярные спектральные меры......................................................56

3.3. Вспомогательные факты..............................................................58

3.3.1. Правильно меняющиеся функции............................................58

3.3.2. Классические предельные теоремы для сумм независимых случайных величин..........................................................................61

3.4. Логарифмические асимптотики сложности в однородных задачах . . . .... 69

3.5. Точные асимптотические представления сложности в однородных задачах . . 78

3.5.1. Неэкспоненциальный случай..................................................79

3.5.2. Экспоненциальный случай....................................................85

3.6. Логарифмические асимптотики сложности в неоднородных задачах............92

3.6.1. Общий критерий................................................................94

3.6.2. Критерий с сильным доминированием......................................97

4. Линейные тензорные задачи в постановке по вероятности 102

4.1. Логарифмические асимптотики сложности в однородных задачах..............102

4.2. Точные асимптотические представления сложности в однородных задачах . . 107

4.3. Логарифмические асимптотики сложности в неоднородных задачах............113

5. Приложения к тензорным случайным полям 115

5.1. Однородные случайные поля с регулярным спектром..............................115

5.2. Броуновский лист и миогопараметрический броуновский мост..................119

5.3. Многопараметрический эйлеровский интегрированный процесс..................120

Заключение 130

Литература 131

Введение

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

Рассмотрим случайное поле £ 6 Т, чьи траектории можно рассматривать как эле-

менты (ф, || • ||д) - некоторого нормированного пространства функций, определенных на Т. Теоретический и практический интерес (в частности для компьютерного моделирования) представляет аппроксимация поля X полями конечного ранга:

71

Х{1) = ^гпфш{1), ьет, (1)

т=1

где £т - случайные величины, ф,п(-) - детерминированные функции, принадлежащие пространству С^. Обозначим Т1п класс полей вида (1).

Возникает естественный вопрос: каким должно быть п, чтобы ошибка аппроксимации имела заданную малость? Здесь возможны две постановки - в среднем и по вероятности. Введем минимальную среднеквадратическую ошибку аппроксимации X полями ранга п:

1/2

(Е||А-А|^]

Х£Кп

Сложностью аппроксимации в среднем называется величина

/ ~ \1 en(X):= jnf ЕЦА-АЦМ

Y (=7? _ V /

п

avg

(е) := min {ne N : еп(Х)2 sC е2Е ||Х||^} . (2)

Подчеркнем, что здесь речь идет об относительной точности, учитывающей «размер» случайного поля X.

Сложностью аппроксимации по вероятности называется величина

тгргоЬ

(е, := minin G N : _inf pf||АГ - Х\Ц > е2Е \\Х\&) < Л. (3)

хагп \ ' J

Здесь е £ (0,1) называется порогом ошибки, a Ö € (0,1) - уровнем значимости. Характеристики navg(e) и nprob(e, Ö) являются главными объектами изучения в теории информационной сложности (Information-Вased Complexity), оформившейся с выходом монографий [83]—[85].

Задачу исследования величин navg(e) и пргоЬ(е,5) мы будем решать в духе молодого направления теории информационной сложности —теории многопараметрических задач, основные положения и результаты которой сформулированы в недавно изданном фундаментальном трехтомнике Э. Новака и X. Вожняковского «Tractability of Multivariate Problems»

[71]—[73]. Согласно этой теории, представляет интерес изучение случайных полей, зависящих от настолько большого числа параметров, что к самой размерности параметрического множества можно подойти асимптотически. Иными словами, мы будем рассматривать не одно иоле X, а целую последовательность случайных полей X,i(t), t Е T(i С d E N, с траекториями в нормированных пространствах (Qj, || ■ HqJ. Как правило, пары (Qd,Xd), d Е N, структурно связаны между собой, но, независимо от этого, для каждой из них можно рассматривать введенные выше характеристики сложности аппроксимации, обозначая их теперь n^vs(e) и nJjrob(e, <5), и изучать их при растущей параметрической размерности d.

Сосредоточимся пока что на рассмотрении сложности аппроксимации в среднем. Сформулированная задача может решаться в следующем направлении. Мы изучаем п™ё(е), d Е N, е Е (0,1) как функцию двух независимых переменных d и е, где параметрическая размерность d может быть сколь угодно большой, а порог ошибки е — сколь угодно малым. Здесь в настоящее время центральную роль играет понятие трактабильности (см. глава 1). Говорят, что задача аппроксимации для последовательности (X^deN является W-трактабильной (англ. weak tractable) в среднем, если рост п™к(е) при d —> оо или е —> 0 медленнее экспоненциального одновременно как по d, так и по е-1. W-трактабильные задачи представляют па практике особый интерес, т.к. их реализация не требует больших вычислительных ресурсов. В этом семействе принято выделять следующие вложенные подклассы. Рассматриваемую задачу аппроксимации называют

• QP-трактабильной (англ. quasi-polynomially tractable) в среднем, если существуют константы с > 0 и I ^ 0 такие, что

Ve Е (0,1) Wen n^vg(e) ^cexp{i(l + liid)(l + lne-1)};

• Р-трактабилъной(етгл. polynomially tractable) в среднем, если существуют константы с > 0, г ^ 0 и s ^ 0 такие, что

Ve е (о, 1) Vd G N 7i*vg(e) < cdr

• SP-трактабилъной (англ. strong polynomially tractable) в среднем, если существуют константы с > 0 и s ^ 0 такие, что

Ve Е (0,1) Vc? G N n*vg(e) ^ се-5.

Аналогично вводятся типы трактабильности для задач аппроксимации с вероятностной постановкой (см. [72] с. 298-300).

Наряду с указанным выше подходом, можно рассматривать сложность аппроксимации в несколько иной постановке, а именно, при сколь угодно малом, но фиксированном е Е (0,1), и большом d Е N. Фактически, здесь речь идет о нахождении асимптотик величии rijVg(s) и /¿¿гоЬ(е, б) при d —> оо, что в некоторых важных случаях требует применения идеи и методов решения, отличных от тех, что используются при рассмотрении трактабильности.

Задача изучения и п|]го (е, 5) при больших с1 Е N в той степени общности, в которой

она сформулирована, пока изучена слабо. Однако для гильбертова случая С^а = /^([0,1]^), в, Е М, к настоящему времени уже получены некоторые результаты. Далее мы сосредоточимся только на нем. Здесь случайное поле Х^Ь), I Е [0,I]4*, как элемент пространства 1]^) с нормой || ■ ^^ с вероятностью 1 может быть представлено разложениелг Кархунена-Лоэва:

Ха{1) = ^ А^ фа>т(1), Ь Е [0,1]*, (4)

тем

где (\а,т)т€№ — певозрастающая последовательность собственных чисел, ("¡/>^,т)тем — соответствующая последовательность собственных функций корреляционного оператора поля Ха, (£сг,т)шем — независимые стандартные гауссовские случайные величины. Как известно (см. [76], с. 51), разложение (4) является в Ь2{[0,1]сг) оптимальным, то есть

где Х^п{1) := К/,пЛ(1,т I 6 [0,1]с/. Здесь справедливы новые представления для

сложности в среднем:

:= ш{п € N : Е \\Ха - Х^Щ, ^ в2 Е \\Ха\\224}, и сложности по вероятности:

пГЪ(б, 6) := шш{п € N : Р(||Л^ - ^.„Ц^ > е2 Е ЦХ.Ц2,,) < 6}.

В контексте задач с большой параметрической размерностью особенно интересен случай, когда корреляционные функции /С^ полей Х^, с1 £ 14, заданы следующим образом:

в.

КА{1,з):= (5)

где £ — (¿1,..., Ьа) и й = (5Ь ..., з^), КР^ — корреляционные функции некоторых одпопара-метрических процессов £ £ [0,1], j Е N. Случайные поля с такой корреляционной

структурой называют тензорными (см. [61]); в частности, говорят, что поле Ха(Ь), £ € [0,1]^ есть тензорное произведение процессов

. Если в формуле (5) все /С^ одинаковы и равны корреляционной функции /С некоторого процесса X, то Xа называют тензорной степенью процесса X. Класс случайных полей тензорного типа достаточно широк. Типичными его представителями служат броуновский лист — тензорная степень виперовского процесса, броуновская «подушка» — тензорная степень броуновского моста, тензорные произведения интегрированных гауссовских процессов с определенными степенями гладкости и т.д. (см. [57]).

Для тензорного произведения процессов ..., Х^ с корреляционной функцией вида (5) собственные пары в разложении Кархунена-Лоэва (4) формируются следующим образом: (^сг.т)тем есть занумерованная в порядке невозрастания последовательность чисел А^, & N — соответствующим образом индексированная последовательность собственных

функции вида Фк-(Ь)' £ = (¿1,■ ■ • € [0,1]'', € М, где для каждого ] в N последовательность обозначает собственные числа, а (^Р^)геп — соответствующие собственные функции корреляционного оператора процесса Таким образом, для ¿2-11ормы задача оценки сложности аппроксимации во многом сводится к асимптотическому анализу упоря-дочепнного по невозрастанию массива произведений ^ с растущим к бесконечности числом сомножителей.

К настоящему моменту известны необходимые и достаточные условия ранее перечисленных типов трактабильпости в среднем в терминах серий (А<1,т)т^, (I £ (см. [50], [51], [62] и [71]) для последовательности общих случайных полей (Х^^еы без предположения тензорной структуры. Кроме того, для тензорных полей Х^, с1 6 К, с заданной последовательностью маргинальных корреляционных функций ; £ К, в недавней статье [62] найдены критерии всех типов трактабильпости в среднем в терминах последовательностей (Ар^ен собственных чисел, отвечающих у £ N (см. главу 1). Эти критерии применялись в статье [63] для тензорных произведений эйлеровских и винеровских интегрированных процессов с возрастающими степенями гладкости. Условия трактабильпости по вероятности остаются пока неизученными.

Понятие трактабильпости и перечисленные результаты, связанные с ней, приводятся в главе 1 настоящей работы. При этом предварительно в параграфе 1 делается обзор теории информационной сложности, а в параграфе 2 — теории многопараметрических задач. Кроме того, мы рассматриваем задачу Ьг-аиироксимации в рамках этих теорий с более абстрактной точки зрения, где Хл является случайным элементом тензорного произведения сепарабель-пых гильбертовых пространств. Тензорные случайные поля подробно рассматриваются в пункте 1.2.3, а их примеры — в пункте 1.2.4.

Детальному изучению п™&{е) и 7г[]гоЪ(£, 5) при фиксированном е £ (0,1), (I оо, и 5 = возможно зависящем от е и с/, посвящены главы 2-5 диссертации. В главе 2 мы рассматриваем последовательность случайных полей Ха, (I <Е М, без предположения тензорной корреляционной структуры. Все полученные результаты формулируются в терминах серий (А(;1т)те^, й £ N. Перечислим их. В параграфе 1 найдены необходимые и достаточные условия ограниченности и также неограниченности сложности при любом фиксированном е £ (0,1) по параметрической размерности й (утверждения 2.1.3 и 2.1.4). Кроме того, представлен критерии стремления —> оо, с1 —¥ оо, при произвольно фиксированном е £ (0,1) (утверждение 2.1.2). В другом пункте этого же параграфа получен критерий для выполнения следующей асимптотики:

УееС(д) 1пп^(е) = Аа +Ч{е)Вл +о{Вл), <1^ оо, (6)

при заданной последовательности из М, последовательности (/^¿)(/егь стремящейся

к оо, и при фиксированной невозрастающей функции <7: (0,1) К с множеством точек непрерывности С(о) (теоремы 2.1.2-2.1.4). Основной смысл этого критерия таков: наличие у п^5(е) асимптотики (6) равносильно слабой сходимости к некоторому вероятностному распределению определенным образом построенных скалярных спектральных мер на (А<*)т),„ем>

(I Е М, причем компонента д связана с кваитилыо этого предельного распределения. Далее в параграфе 2 показано (теоремы 2.2.1 и 2.2.2), что при любом фиксированном £ Е С(д) сложность но вероятности п^гоЬ(е, 5) имеет ту же логарифмическую асимптотику вида (6), что и п™е(£), при (I —>■ оо в достаточно широкой области варьирования 6 — Е (0,1). При получении этих результатов доказан ряд вспомогательных оценок (леммы 2.2.1-2.2.3), которые по мнению автора могут быть полезными для малоизученных задач аппроксимации с вероятностной постановкой. Отметим, что теоремы и утверждения главы 2 широко используются в последующих главах.

Рассмотрим поведение сложности аппроксимации в среднем и по вероятности при фиксированном £ Е (0,1) и (1 —> оо для тензорных случайных полей. Отметим, что первые результаты в данном направлении получены М. А. Лифшицем и Е. В. Туляковой в статье [64]. В ней авторами с помощью специального вероятностного подхода для тензорных степеней процессов найдены логарифмические асимптотики п^®(е) и 7г^гоЪ(е, <5) в случае, когда маргинальные собственные числа Л£, г Е М, имеют единичную кратность и удовлетворяют следующему условию:

геи

Несколько позже в статье [24] была сделана попытка уточнения логарифмической асимптотики п^у®(е) из [64], но результаты [24], к сожалению, содержат значительные неточности. Других работ по асимптотическому анализу при <1 —> оо сложности аппроксимации в среднем тензорных полей автору не известно. Этому направлению посвящены главы 3 и 4 диссертации. Сделаем краткий обзор полученных результатов. В параграфе 1 главы 3, опираясь на утверждения из второй главы, мы приходим к любопытному факту: в зависимости от поведения

величина может либо для любого £ Е (0,1) стремится к оо при

(I оо либо для любого £ Е (0,1) быть ограниченной по с1. Там же приведены критерии для каждой из альтернативных ситуаций. В параграфе 2 главы 3 мы развиваем вероятностный подход, предложенный М. А. Лифшицем и Е. В. Туляковой. Это позволяет обобщить их результаты для тензорных степеней процессов па случай, когда маргинальные собственные числа А,, г 6 М, имеют произвольную кратность (теоремы 3.4.3 и 4.1.2). Кроме того, получены логарифмические асимптотики п^(£) и п^гоЬ(£,<5) вида (6), в случае невыполнения (7) и при условии следующего регулярного убывания:

ген ^ '

где у? — медленно меняющаяся функция на оо (теоремы 3.4.4 и 4.1.4). Показана в некотором смысле необходимость условий (7) и (8) для асимптотик и п^гоЪ(е,5) вида (6) (теоре-

мы 3.4.1, 3.4.4 и 4.1.3, 4.1.5). Отметим, что в этих случаях рост сложности в среднем и по вероятности является экспоненциальным и надэкспопенциальпым при (I —> оо. Также изучен случай медленного изменения хвостов Х^ем'л'-^'л < е~Х) (см- теоРемы 3.4.5 и 4.1.6). Здесь рост сложностей имеет тип «экспонента в экспоненте».

Также в параграфе 5 главы 3 при небольшом усилении условия (7):

Е| А^ ^ А^ Г Л Л<00'

найдено точное асимптотические представление для п^УЙ(е) при (I —У оо для тензорных степеней процессов (теоремы 3.5.2 и 3.5.4). Вид этой асимптотики зависит от арифметической структуры собственных чисел (А;)*^ (см. параграф 3.5). В параграфе 2 главы 4 доказано, что вне зависимости от структуры (А*)^ при любом фиксированном е € (0,1) в широкой области варьирования 6 = справедлива эквивалентность п^гоЬ(е, 5^) ~ п^(е) при (I —> оо (теорема 4.2.1). Это подчеркивает близость результатов для постановок в среднем и по вероятности.

Помимо тензорных степеней процессов в главах 3 и 4 рассмотрены неоднородные тензорные произведения процессов. При естественных слабых предположениях на их последовательности собственных чисел (Аг-^),ер), j е М, получены необходимые и достаточные условия для того, чтобы сложность в среднем и по вероятности имели логарифмические асимптотики вида (6) (теоремы 3.6.2 и теорема 4.3.2). При этом доказывается (следствие 4.3.1), что они для п^У®(е) и пГъ(е, идентичны в достаточно широкой области варьирования 6 = <5^£. Также показано, что компонента д из (6) функционально связана с квантилями саморазложимых законов распределения (класс Ь безгранично делимых законов, см. теорему 3.6.1). Проведена редук�