НЕТ
Общая характеристика работы
Актуальность темы. Теория массового обслуживания — богатая и интенсивно развивающаяся область математического знания. Начиная с работ А.К. Эрланга1, ей была присуща очевидная практическая направленность, что приводило к появлению множества естественных и интересных вероятностных задач.
Усложнение применяемых на практике технологических систем, и, прежде всего, широкое распространение систем обработки и передачи данных, способствовало формированию новой области теории массового обслуживания — теории сетей обслуживания. Из разнообразных сетей обслуживания в отдельную группу выделяют системы поллинга, которые состоят из конечного числа станций, посещаемых одним или несколькими обслуживающими приборами. В настоящее время теория поллин-говых систем активно развивается, о чём свидетельствует обширная отечественная и зарубежная литература.
К типу поллинговых можно отнести системы, в которых обслуживание состоит в перевозке требований, а перемещение приборов возможно только при наличии требования. Такие модели естественно возникают при описании транспортных сетей.
Вплоть до недавнего времени арсенал методов теории массового обслуживания не позволял эффективно подходить к изучению подобных моделей. Обычно можно легко задать цепь Маркова, которая описывает изучаемую систему. Однако, пространство состояний марковской цепи оказывается существенно многомерным и выписать стационарное распределение за редкими исключениями не удаётся. Например, Р.Л. Добрушин придерживался той точки зрения, что явные формулы для стационарных распределений в «общем случае» получить нельзя. С точки зрения вычисления операционных характеристик системы необходимо знать именно явную формулу для стационарного распределения, из которой хорошо видно, как параметры системы влияют на целевую функцию. В связи с этим возникает вопрос о нахождении асимптотических формул для стационарного распределения в многочисленных предельных случаях: для большой или малой загрузки, нулевых времён перемещения (в частности, классические формулы Б.В. Гнеденко в задаче о станках могут рассматриваться как предельный случай ситуации, когда время перемещения работников между станками равно нулю) и пр.
В настоящей диссертации асимптотические формулы изучаются в предельном случае, отвечающем большой размерности системы массового обслуживания (большая размерность чаще всего связана с большим числом приборов или очередей к этим приборам, каждую из которых надо описывать отдельной координатой). Такую задачу можно решать с помощью так называемого метода среднего поля, в котором
lE. Brockmeyer, H.L. Halstr0m, A. Jensen. The life and works of A. K. Erlang. // Trans. Danish Acad. Tech. Sci., vol. 1948, №2, pp.277, 1948.
1
пространство состояний сети выбирается таким образом, чтобы при увеличении числа компонент сети поведение системы становилось все более и более детерминированным, а в пределе её состояние описывалось бы системой обыкновенных дифференциальных уравнений (которые могут быть и нелинейными).
Другой, вероятностный, взгляд на проблему состоит в том, что при наличии достаточно сильной симметрии у системы, когда число компонент увеличивается, зависимость их друг от друга ослабевает и, в конце концов, все компоненты начинают эволюционировать независимо друг от друга. Эта эволюция описывается опять-таки нелинейными дифференциальными уравнениями, неподвижная точка которых и представляет собой желаемое стационарное состояние каждой из компонент.
Согласно обзору2, этот метод в «интуитивной» форме известен математикам и инженерам довольно давно — с 60-х годов XX века, однако, вопрос о строгом обосновании всех описанных шагов сталкивается с большими трудностями. Авторы обзора2 называют гипотезой Р.Л. Добрушина утверждение о том, что указанный метод действительно можно строго обосновать математически в большинстве систем. К этой гипотезе близка несколько более частная гипотеза А.А. Боровкова о предельном поведении замкнутой полностью симметричной сети Джексона с общим временем обслуживания заявок.
Одним из самых сложных вопросов является вопрос о сходимости решений нелинейной системы дифференциальных уравнений к неподвижной точке, необходимый для обоснования сходимости стационарных распределений к распределению, сосредоточенному в неподвижной точке. В частности, после работы3 Ф.И. Карпелевича и А.Н. Рыбко именно доказательство сходимости решений к неподвижной точке нелинейной системы уравнений осталось последним препятствием в доказательстве гипотезы А.А. Боровкова.
Такого рода задача называется задачей о глобальной асимптотической устойчивости. Заметим, что хорошо развита лишь теория локальной устойчивости, то есть, устойчивости в окрестности неподвижной точки, в то время как в случае глобальной асимптотической устойчивости исследователь может надеяться лишь на собственную интуицию, которая поможет ему построить функцию Ляпунова (называемую иногда пробной функцией). Одним из немногих свойств нелинейной системы дифференциальных уравнений, которые позволяют исследовать её сходимость к неподвижной точке, является покоординатная монотонность решений по начальному условию. Такое свойство действительно имеется для целого класса систем возникающих в данном контексте, хотя и требует определённого искусства в выборе системы координат.
2F.I. Karpelevich, E.A. Pechersky, Yu.M. Suhov. Dobrushin's approach to queueing network theory. // J. Appl. Math. Stochastic Anal., vol. 9, №4, pp.373-397, 1996.
Ф.И. Карпелевич, А.Н. Рыбко. Асимптотическое поведение симметричной замкнутой сети массового обслуживания в термодинамическом пределе. // Пробл. передачи информации, т. 36, №2, с.69-95, 2000.
Тем не менее, существует значительное число практически и теоретически важных моделей, для которых свойство монотонности не выполняется и вопрос о глобальной устойчивости не может быть решён в рамках существующих методов. К ним относятся системы с законом сохранения типа суммы координат, естественным образом возникающие в приложениях (например, в теории транспортных сетей). Это делает проблемы разработки новых подходов для исследования глобальной устойчивости предельных систем уравнений весьма актуальной.
Цель работы. — Доказательство предельных теорем типа закона больших чисел для поллинговых моделей, описывающих транспортные сети;
— разработка методов исследования глобальной асимптотической устойчивости для предельных систем дифференциальных уравнений, не обладающих свойством монотонности;
— доказательство на этой основе сходимости стационарных распределений к неподвижной точке нелинейной системы и отыскание этой точки;
— применение разработанных методов к исследованию эргодичности цепей Маркова;
— анализ системы с бесконечным числом узлов как случайного процесса с локальным взаимодействием.
Методы исследования. В работе используются методы теории марковских процессов, методы функционального анализа, теория неотрицательных матриц и аппарат теории обычных дифференциальных уравнений.
Научная новизна. Все результаты диссертации являются новыми.
— Для стохастических случайных процессов, описывающих транспортную сеть, установлена сходимость по вероятности к предельной системе, которая описывается нелинейными дифференциальными уравнениями.
— Доказана теорема о глобальной устойчивости нелинейной системы дифференциальных уравнений (в конечном и счётномерном случаях) в предположении, что элементы матрицы Якоби неотрицательны. С помощью этой теоремы получена сходимость стационарных распределений к неподвижной точке системы уравнений для новых моделей и целого ряда моделей, рассматривавшихся ранее другими авторами.
— Найдены инвариантные меры для процесса с локальным взаимодействием, возникающего при рассмотрении системы с бесконечным числом узлов, а также доказана единственность феллеровского процесса с заданным инфинитезимальным оператором.
— Предложен новый достаточный признак эргодичности цепи Маркова, основанный на существовании инвариантного компактного множества.
Теоретическая и практическая значимость. Работа носит теоретический характер. Её результаты могут быть использованы специалистами в области теории вероятности, теории массового обслуживания, теории динамических систем и теории операций.
Апробация диссертации. Результаты диссертации докладывались и обсуждались на Большом научно-исследовательском семинаре кафедры теории вероятностей (руководитель — член-корреспондент РАН А.Н.Ширяев) (2000), на Первых Колмого-ровских чтениях в МГУ (1999), Ломоносовских чтениях в МГУ (1999), а также на семинарах по теории вероятностей и статистической физике (руководители — проф. Б.М. Гуревич и проф. В.И. Оселедец), по динамическим системам (руководитель — проф. Я.Г. Синай), на семинаре под руководством В.В. Веденяпина в ИПМ РАН.
Публикации. Результаты диссертации опубликованы в восьми работах, список которых приведён в конце автореферата.
Структура и объём диссертации. Диссертация состоит из введения и трёх глав. Текст диссертации изложен на 137 страницах. Работа содержит 8 рисунков и 76 наименований библиографии.
Содержание работы
Введение. Во введении приводится краткий обзор истории исследований в теории массового обслуживания и формулируются основные результаты, полученные в диссертации.
Глава 1. Первая глава диссертации посвящена исследованию конечномерных моделей.
Обозначим гг-мерное вещественное пространство через R™. Для всякого вектора х = (xi,... ,хп)т € Шп определим норму ||-|| по правилу ||ж|| = \х\\ + ... + \хп\, где • | означает абсолютную величину числа. Под R™ понимается множество покоординатно неотрицательных векторов iGK". Под / : R™ —> W1 подразумевается тождественное отображение: 1х — х для всех х ? К". Введём линейное подпространство L = {х ? К" : х\ + ... + хп = 0}. Линейное отображение A: Rn —>• W1 назовём марковским, если транспонированная матрица этого отображения является стохастической или /Ш™ С R™ , (1, ..., Х)А = (1, ..., 1). Пусть А — аВ — отображение, пропорциональное марковскому отображению В с коэффициентом пропорциональности а > 0. Для такого отображения А определим коэффициент эргодичности к(А) по правилу к(А) - ||Л|| - \\A\\L. Здесь
||Л|| = sup \\Ax\\ = max\\Aei\\,
P||L= sup \\Ax\\ =max||A(ei-ej)||/2,
|||| lJ
где ||ж|| = \х\\ + ... + \хп\, а {е^} — стандартный базис в Rn. Отметим, что ||Б|| = 1, к(В) = 1 — ||-В||ь и к (А) = ак(В). Для стохастических матриц Вт коэффициент эргодичности ввёл Р.Л. Добрушин4' 5 и его определение совпадает с данным.
В разделе 1 исследуется автономная конечномерная система дифференциальных уравнений
х = /(х),хе№, (*)
обладающая следующими свойствами
1) векторное поле f{x) дифференцируемо по ж и матрица Якоби
J{x) = df/дх = (dfi/dXj)
непрерывно зависит от х. Эти условия обеспечивают при t ^ О существование и единственность решения x(t, д) системы (*) с начальным условием х(0, д) = д. Кроме того, x(t,g) непрерывно дифференцируемо по д.
2) Существует множество X, инвариантное относительно динамической системы (*), и, кроме того, X — компактное выпуклое подмножество аффинного многообразия L + с при некотором с Е К".
3) Система (*) обладает первым интегралом 5^Г=1жг> т-е- Y^i=ifi{x) = 0- Отсюда следует, что J(x)L С L или, что то же самое, сумма строк матрицы J(x) равна нулю. Кроме того, недиагональные элементы матрицы J(x) неотрицательны при всех
х el.
Заметим, что третье условие носит вероятностный характер и означает, что матрица J(x) является матрицей интенсивностей переходов некоторого марковского процесса6' 7.
Теорема 1. Если выполнены условия 1)-3), то для любых начальных условий д°, gl G X при всяком t ^ 0 выполнено неравенство
т.е. функция x(t,-) : X —> X не увеличивает расстояние между любыми двумя точками.
Теперь предположим, что существует линейное отображение В ;> 0, удовлетворяющее при некотором С ^ 0 следующим условиям
(а) при всех х G X верно неравенство J(x) + C,I ^ В, где / является единичной
матрицей;
Р.Л. Добрушин. Центральная предельная теорема для неоднородных цепей Маркова. I. // Теория вероятностей и её приложения, т. 1, №1, с.72-89, 1956.
5Р.Л. Добрушин. Центральная предельная теорема для неоднородных цепей Маркова. II. // Теория вероятностей и её приложения, т. 1, №4, с.365-425, 1956.
И.И. Гихман, А.В. Скороход. Теория случайных процессов. Наука, Москва, 1971. 7 J.R. Norris. Markov chains. Cambridge University Press, Cambridge, 1998.
(б) В — пропорционально марковскому отображению и при некотором щ G N выполнено к((1 + В)п°) > 0.
Требование (б) является существенным и предохраняет от различных вырождений.
Теорема 2. В условиях 1)-3) и (а)-(б) при всяком t > 0 существует такое q = q(t) < 1, что для любых начальных условий g°, д1 e X выполнено неравенство
т.е. отображение x(t, •): X —> X является сжимающим с коэффициентом сжатия
Дальнейшие обобщения этих теорем приведены в разделе 1 главы 1.
Рассмотренные нелинейные дифференциальные уравнения естественно появляются при применении метода среднего поля к некоторым сложным моделям теории массового обслуживания.
В разделе 2 главы 1 изучается сеть из N узлов и rN обслуживающих приборов (автомобилей). В каждый узел в сооответствии с пуассоновским потоком интенсивности A(i) поступают заявки (пассажиры). Пуассоновские потоки заявок в разные узлы независимы. Заявка, попавшая в пустой узел, покидает систему. Если заявка попадает в узел с приборами, то случайно и равновероятно выбирается один из приборов, который забирает заявку и перемещается экспоненциально распределенное время. Движение прибора моделируется с помощью введения дополнительного виртуального узла: когда прибор начинает перемещаться, он попадает в виртуальный узел, где находится экспоненциально распределенное время со средним значением 1, а затем перемещается в узел, равновероятно выбираемый из всех N узлов. Если число приборов в выбранном узле равно т, прибор ждет следующей попытки в виртуальном узле экспоненциально распределенное время со средним 1 и т.д. Таким образом, в каждом узле (кроме виртуального) может находиться от 0 до т приборов.
Пусть щ — число узлов, количество приборов в которых равно k, fk = nk/N — доля этих узлов, W — количество приборов, находящихся в виртуальном узле, а V = W/N. В технических целях удобно перейти от Д к накопленным долям Uk — X^/t fi ¦
Все случайные интервалы времени и пуассоновские потоки предполагаются независимыми в совокупности.
Из наших предположений следует, что эволюция системы описывается некоторым марковским процессом Uff(t), для которого можно выбрать пространство состояний XN содержащее все такие вектора и = (щ, ..., ит, V)T из (l/iV)Z™+1, что выполнены неравенства
1 = щ ^ щ ^ ... ^ ит ^ 0, V ^ 0 и V + щ + ... + ит = г. (о)
Кроме того, из наших предположений следует, что производящий оператор AN(t) процесса UN(t), который действует на функции над XN, задается следующим образом
771—1
A?f(u) = N\(t) J2(uk ~ uk+1)[f(u - ek/N + em+1/N) - f(
+ NX{t)um[f{u - em/N + em+l/N) - f(u)] +
+ ek/N-em+1/N)-f(u)]1
k=l
где е, — вектор, г-тая координата которого равна 1, а остальные координаты равны 0. В силу конечности XN оператор AN(t) определяет единственный марковский процесс UN(t).
Метод среднего поля подсказывает, что в пределе при N —> оо эволюция и становится детерминированной. Более точно: пусть X означает множество всех векторов Mm+1, удовлетворяющих условиям (о). Тогда, если распределение начального состояния С/дг(О) сходится к вырожденной мере, сконцентрированной в точке д G X, то распределение U^(t) сосредотачивается при больших N на траектории u{t) G X, удовлетворяющей системе дифференциальных уравнений
u = f(u,\), (оо)
где
fi(u7 X) = X(ui+1 - щ) + F(uj_i - щ), г = 1, ..., т - 1, щ = 1, /то(и, А) = — Хит + V(um-i — ит), fm+i(u, А) = Хщ - V(l - ит).
Система (оо) является нелинейной с квадратичной правой частью. Чтобы строго сформулировать утверждение о сходимости процесса U^(t) к решению u(t,g) системы (оо) с начальным условием д, определим семейство производящих операторов Tn = TN(t) по правилу
TN(t)f(g) = B(f(UN(t)) | UN(0) =g),g€ XN.
Теорема 3. Для всех f G C(X), равномерно no t на произвольном отрезке из R+ = {t 2 0}7
lim sup sup \TN(s)f(g) -f(u(s,g))\ = 0.
iV-s-oo i
Доказательство этой теоремы опирается на классические результаты о сходимости
рковских процессов, если сходятся их производящие операторы8.
Обозначим через ед дискретную вероятностную меру, сосредоточенную в точке
9
8S.N. Ethier, T.G. Kurtz. Markov processes (Characterization and convergence). John Wiley & Sons Inc., New York, 1986.
7
Теорема 4. Если UN(0) по вероятности сходится к ев, то
sup ||?/дг(§) — u(s,r,g)\\ —>• 0 по вероятности при всех t ^ 0.
Обозначим через д* точку д* — (и\,... -,и*т1 V*), которая является стационарным решением системы (оо) т.е., f(g*, A) = 0. Тогда
Pk-Pm+1
_ пт+1
Р
т + 1
при А; = 1, ..., т, V* — V{p) = Ар, где р единственным образом определяется из условия на первый интеграл:
При обозначении L(p) — щ(р) + ... + ит(р) с учётом V(p) = Xp последнее условие принимает вид
L(p) + Xp = r.
Если X(t) — постоянна, то процессы U^(t), образуют семейство однородных цепей Маркова с непрерывным временем и конечным числом состояний, каждая из которых в силу неприводимости обладает единственной инвариантной мерой (j,N.
Реализация изложенной в начале введения программы по поиску асимптотических характеристик систем позволяет доказать следующую теорему, существенно использующую теорему 2.
Теорема 5. Инвариантные меры ц^ процессов ?/дг слабо сходятся к дискретной мере, сосредоточенной в д*.
Кроме того, в разделе 2 исследуется случай непостоянного X(t).
В разделе 3 показано, как теорему 2 можно применять для доказательства сходимости в модели Н.Д. Введенской, Р.Л. Добрушина и Ф.И. Карпелевича9 с дополнительным ограничением на длину очереди.
Раздел 4 посвящен техническому результату, который позволяет изучать поведение предельной динамической системы строго «внутри» фазового пространства. Дело в том, что на границе фазового пространства свойства динамической системы могут нарушаться: например, может пропадать равномерное сжатие фазового потока.
В разделе 5 рассматривается задача, которая не поддаётся непосредственному применению теоремы 2, но после замены координат удаётся в некоторых частных случаях показать сходимость. У матрицы Якоби, приведённой в разделе 5, имеется ровно
. Введенская, Р.Л. Добрушин, Ф.И. Карпелевич. Система обслуживания с выбором наименьшей из двух очередей — асимптотический подход. // Пробл. передачи информации, т. 32, №1, с.20-34, 1996.
один элемент, который может принимать отрицательные значения. Во многих современных задачах асимптотического анализа возникают системы дифференциальных уравнений с матрицами Якоби ещё более сложной структуры. Возможно, дальнейшее изучение системы раздела 5 позволит найти более общий подход к системам, в которых отсутствует монотонность.
Раздел 6 посвящен обобщению модели раздела 2 в сторону асимметричности. А именно, узлы разбиваются на несколько районов, в каждом из которых маршрутизация равновероятна. Оказывается, что и в этом случае можно найти неподвижную точку, к которой в силу аналога теоремы 5 и сходятся инвариантные меры конечных систем.
Заметим, что все модели, рассмотренные в разделах 2-6, а также освещенные в работах9' 10' И' 12 предполагают экспоненциальность распределения времён обслуживания.
В разделе 7 рассмотрена простейшая модель транспортной сети, аналогичная модели раздела 2 с тем усложнением, что время перемещения прибора от одного узла к другому распределено не показательно, а по т.н. гиперэрланговскому закону. Ги-перэрланговским законом называют конечную смесь эрланговских распределений, а эрланговское распределение, в свою очередь, имеет плотность 0 при х < 0 и vlх1 e~vxI{I — 1)! при х > 0, где параметры удовлетворяют условиям v > 0 и I G N.
Как известно13' 14, конечная смесь эрланговских распределений сколь угодно точно в метрике пространства L1 приближает любое заданное наперёд распределение с конечным средним.
Основной результат раздела 7 состоит в том, что при большом количестве компонент системы распределение приборов по узлам сети зависит лишь от математического ожидания гиперэрланговского распределения, а вид этого распределения такой же, как для экспоненциального случая. То есть распределение числа приборов по узлам описывается теми же формулами, что и в разделе 2.
Глава 2. Вторая глава диссертации посвящена исследованию существенно счётно-мерных систем. В разделе 1 изучается устойчивость некоторого специального класса
10L.G. Afanassieva, G. Fayolle, S.Yu. Popov. Models for transportation networks. // J. Math. Sci. (New York), vol. 84, №3, pp.1091-1103, 1997.
11 J.B. Martin, Yu.M. Suhov. Fast Jackson networks. // Ann. Appl. Probab., vol. 9, №3, pp.854-870, 1999.
12 V. V. Scherbakov. Long time dynamics in large closed Jackson networks. // Markov Process. Related Fields, vol. 6, №1, pp.107-119, 2000.
lsH.II. Бусленко, В.В. Калашников, И.Н. Коваленко. Лекции по теории сложных систем. Советское радио, Москва, 1973.
145. Asmussen. Applied probability and queues. John Wiley & Sons Ltd., Chichester, 1987.
счётных систем дифференциальных уравнений на основе усовершенствования подхода, изложенного в разделе 1 первой главы. Различие между конечномерным и счётно-мерным случаем у систем из рассматриваемого класса аналогично различию между конечными и счётными цепями Маркова. Условие на положительность коэффициента эргодичности некоторой степени матрицы Якоби соответствует условию Дёблина эргодичности цепи Маркова. Хорошо известно, что условие Дёблина весьма ограничительно, и, например, обычный процесс рождения и гибели с существенно счётным пространством состояний ему уже не удовлетворяет. Можно показать, что у всех бесконечных систем дифференциальных уравнений из работ9' 11; 15' 16 коэффициент эргодичности матрицы Якоби равен 0. Поэтому вводится обобщение коэффициента эргодичности, которое называется коэффициентом эргодичности по направлению.
С использованием коэффициента эргодичности по направлению можно доказывать строгое уменьшение расстояния между образами любых двух начальных условий. Отметим, что в этом случае нельзя пользоваться принципом сжимающих отображений, поскольку коэффициент сжатия зависит от точки и может быть сколь угодно близок к 1. Поэтому мы используем специальные теоремы о неравномерном сжатии.
Следуя общепринятым обозначениям17 обозначим через 1\ пространство последовательностей х = (xq, х\, .. .)т с нормой ||ж|| = |жо| + \х\\ + ... Мы полагаем х бесконечным столбцом, чтобы подчеркнуть аналогию с конечномерным случаем. Норма ||-|| индуцирует норму, а следовательно, и топологию на ограниченных линейных операторах A: li —»• li, ||Л|| = sup||Ax||/||x||. Окрестность точки д ? 1± обозначим через
U?(g) = {х € h \\g — х\\ < е}. Все векторные и матричные неравенства следует понимать как покомпонентные. Под / понимается тождественное преобразование: 1х = х для всех х G 1\.
Линейное отображение А: 1\ —>• ^ назовём марковским, если Ah ^ 0 при любом h ^ 0 и (1, ..., 1, .. )А — (1, ..., 1, ...). Заметим, что отображение А — марковское, если его транспонированная бесконечная матрица является стохастической.
Введём линейное подпространство L = {д G h \ до + ¦ ¦ ¦ = 0}. Рассмотрим отображение А — аВ, где а > 0 и В — марковское отображение, В : ^ —> 1г. Определим коэффициент эргодичности k(A, g) отображения А: 1± —> 1\ по направлению д G /i\{0} по правилу к(А,д) = \\A\\\\g\\ - \\Ag\\. Здесь
= sup ||Лж||
N.D. Vvedenskaya, Yu.M. Suhov. Dobrushin's mean-field approximation for a queue with dynamic routing. // Markov Process. Related Fields, vol. 3, №4, pp.493-526, 1997. Statistical mechanics of large networks (Rocquencourt, 1996).
16F.I. Karpelevich, A.N. Rybko. Thermodynamic limit for the mean field model of simple symmetrical closed queueing network. // Markov Process. Related Fields, vol. 6, №1, pp.89-105, 2000.
A.H. Колмогоров, С.В. Фомин. Элементы теории функций и функционального анализа. «Наука», Физматгиз, Москва, 1976.
10
где ejt — вектор, каждая координата которого, кроме к-й равной 1, равна 0. Очевидно, к(А,д) = ак{В,д).
Можно также определить коэффициент эргодичности отображения А по правилу к(А) = \\A\\ - \\A\\L. Очевидно, что
к(А) = inf М^ = |И|| - sup яеь\о |Ы1 geL\0
и если к (А) > 0, то k(A,g) > 0 для всех g G L \ 0. Обратное утверждение верно в конечномерном случае, но, вообще говоря, неверно в бесконечномерном случае. Действительно, в конечномерном случае (или в случае компактного оператора А)
1П(= ЧА *(А
||=i деь,\\д\Ы
где V = {д' | д' = Ад при некотором g G L, ||g|| = 1}. Множество V компактно в силу компактности оператора А. Заметим \\A\\ — ||-|| — непрерывная функция на V и она принимает те же значения, что и к(А: д) при д G 1Д0, \\g\\ = 1, а потому \\A\\ — \\д'\\ > 0 для всякого д' G V. Поэтому функция ||Л|| — ||-|| достигает на V минимума, и этот минимум, равный к (А), строго больше нуля.
Рассмотрим теперь бесконечномерный случай. Назовём размахом ленточной матрицы ограниченного оператора А такое число d, что ац = 0, как только \г — j\ > d.
Лемма 6. Пусть В — марковский оператор с размахом d и А = аВ. Тогда при всех t ^ 0 имеем k(exp(tA)) = 0. Однако, существуют марковские операторы с размахом 1, для которых при всех t > 0 и при всех g G L \ 0 выполнено A;(exp(iA), g) > 0.
Таким образом, можно надеяться лишь на строгое уменьшение расстояний между векторами, а так называемая «спектральная щель» в изучаемых системах, вообще говоря, отсутствует (по меньшей мере в той «естественной» системе координат, в которой они заданы).
Будем говорить, что семейство {Fa} всюду плотно в множестве U С X, если для любого х G U и для любого ? > 0 существует такое а и х G Fa, что р(х,х) < е. Автору не удалось найти никаких ссылок на следующую простую теорему, которая полезна в контексте исследуемых далее задач.
Теорема 7. Пусть отображение f строго уменьшает расстояния, т.е. для любых х, у G X выполнено p(fx,fy) < p(x,y). Предположим, что существует семейство {Fa} компактных подмножеств X, удовлетворяющее условиям
а) {Fa} всюду плотно в X,
б) fFa С Fa для любого Fa G {Fa}.
Тогда существует единственная неподвижная точка х* G X, удовлетворяющая уравнению fx* — х*, и для любого х G X выполнено fnx —> х*.
Иногда неподвижная точка известна и удобно пользоваться следующим признаком сходимости.
11
Теорема 8. Предположим, что X — банахово пространство, ах*— неподвижная точка отображения /. Пусть отображение f строго уменьшает расстояния, т.е. для любых х, у G X выполнено p(fx,fy) < p(x,y). Также предположим, что при некотором ? > 0 для множества U?(x*) = {х G X | \\х — х*\\ ^ е} существует семейство {Fa} компактных подмножеств U?(x*), удовлетворяющее условиям
а) семейство {Fa} всюду плотно в U?(x*),
б) fFQ С Fa при всех Fa G {Fa}.
Тогда неподвижная точка х* единственна и для любого х G X при п —> оо выполнено p(fnx:x*) —>• 0.
В счётномерном пространстве, вообще говоря, вопрос о существовании решений системы дифференциальных уравнений надо изучать специально. Пусть x(t, g) — единственное решение системы уравнений
х = /(ж), xeh, / : k -»• k (**)
с начальным условием x(t0, g) = g G k- Более того, пусть x(t,g) непрерывно дифференцируемо зависит от начального условия, а производная Ф(?, g) — dx(t1g)/dg решения по начальному условию непрерывна по д и удовлетворяет системе уравнений в вариациях:
х = /(ж), Ф - J(x№, x(t0, g)=g€h, Ф(*о, в) = I -k -»• к, (* * *)
где J(x) = (dfi/dxj)f°j^1 — матрица оператора Якоби, а / — тождественный оператор.
Теорема 9. Пусть функция f(x) и ее производная J(x) при х G Uv(g) непрерывны и удовлетворяют условиям ||/(ж)|| < Mq, \\J(x)\\ < M\. Тогда существует такое число 5 > 0, S = тт(г]/Мо, \/М\), что для всякого t в интервале (to — S,to + S) дифференциальное уравнение (**) имеет одно и только одно решение, удовлетворяющее условиям x(to,g) = g и x(t,g) G Uv(g). При этом x(t,g) непрерывно дифференцируемо по начальному условию и его производная удовлетворяет уравнению (***).
Обозначим L = {g G k \ до + ¦ • ¦ = 0}. Во всех последующих результатах предполагается, что существует такое выпуклое множество X С с + L, с G к, что x(t,g) G X при всех д G X при любом t ^ 0 и exp(iJ(g)) — марковское отображение.
Теорема 10. Для любых д°, д1 G X при всех t ^ 0: \\x(t,д1) — x(t,д°)\\ ^ Ц^1 — д°\\
Чтобы доказать сходимость любого решения к стационарному, необходимо проверять дополнительные условия.
Теперь предположим, что существует линейное отображение В ^ 0, удовлетворяющее при некотором С ^ 0 следующим условиям
(а) при всех х G X верно неравенство J(x) + QI ^ В, где / является единичной матрицей;
12
(б) В — пропорционально марковскому отображению и для t > 0 коэффициент эргодичности ехр(Ш) по любому фиксированному направлению д G Ь\ {0} строго больше нуля: k(exp(tB), д) > 0.
Теорема 11. Если X выпукло, X С с + L, где с G 1\, и выполнены, условия (а) и (б), то для любого т > 0 и для любых д°, д1 G X, д1 — д° ф 0: \\х(т,д1) — х(т,д°)\\ <
Ы-дЧ-
Теорема 12. Пусть выполнены условия теоремы 11 и существует семейство компактных множеств {Fa}, удовлетворяющее условиям
(а) семейство множеств {Fa} всюду плотно в X,
(б) для любого Fa G {Fa} выполнено x(t, Fa) С Fa при любом t ^ 0.
Тогда существует единственная неподвижная точка д* и для любого g G X выполнено x(t, g) —>• g* при t —> со.
В разделах 2 и 3 приводятся примеры явного построения семейства Fa. Иногда
можно выбрать Fa = Fg = {x(t,g) t ^ 0} и доказать, что для всякого g траектория {x(t,g) | t ^ 0} предкомпактна.
Следующая теорема даёт достаточный признак предкомпактности траектории.
Теорема 13. Если
(i) существует такая однородная эргодичная положительно возвратная цепь Маркова со счётным числом состояний N U {0} и непрерывным временем, с матрицей интенсивностей переходов Q = (qij), что ^2 Jij{x(t, g)) ^ ^2imi при любых
j < т, k G {0,..., j} U {m + 1,...}, t> 0, g e X;
(ii) существует неподвижная точка g* — x(t,g*) G X,
то для любого g G X траектория решения {x(t,g) | t ^ 0} предкомпактна.
Связь требования на неотрицательность недиагональных элементов матрицы J{g)
с поведением x(t,g) раскрывается в следующей теореме.
Теорема 14. Пусть x(t,g) G h при любом t ^ 0 и g G l\. Следующие утверждения равносильны:
(i) для всех g недиагональные элементы J{g) неотрицательны; (И) для всех g для любого h G h, h ^ 0 x(t, g + h) ^ x(t,g).
Эту теорему можно сформулировать для решений x(t,-), остающихся в некотором «толстом» множестве X С 1\. Однако технические условия, которые в этом случае надо наложить на X, затемнили бы существо дела, в то время как максимальной общности так и не удалось бы достичь. Доказательства всех описанных теорем проведены в разделе 1.
В разделе 2 получено новое доказательство сходимости системы, которую изучали Н.Д. Введенская, Р.Л. Добрушин и Ф.И. Карпелевич9. Они показали покоординатную сходимость, в то время как применение теорем 10-14 позволяет доказать сходимость по норме в пространстве 1\.
13
В разделе 3 изучается система дифференциальных уравнений для замкнутой системы с законом сохранения типа суммы компонент.
Пусть г > О, А > 0. Рассмотрим уравнения среднего поля для симметричной транспортной сети, которая получается при т —> оо из системы, рассмотренной в [2] и разделе 2 первой главы:
V = \иг- V,
щ = Л(и2 - щ) + V(l — щ), й2 = А(м3 - и2) + У(щ - и2), й3 = А(м4 - щ) + V(u2 - щ),
- ик) - У(ик_г - ик).
Обозначим через u(t, g) единственное решение последней системы с начальным условием и(0, д) — д Е 1\. Уравнение сокращённо будем обозначать й — f(u). Для обоснования существования и единственности локального решения u(t, g) воспользуемся теоремой 9. Действительно, в ограниченном шаре ||и|| ^ С, \\f(u)\\ ^ 3(А + С)(1 + ||и||) ^ 3(А + С)(1 + С). Матрица Якоби имеет следующий вид:
/ -1 А О О О ..Л
1 - щ -/3 А 0 0 ...
J(u) =
где /3 = А + V. Из вида J(u) следует, что ||«7(и)|| ^ тах(2(А + ||и||),2(1 + ||и||)) при ||и|| < С. Условия теоремы 9 выполнены, и для д G 1\ в некоторой окрестности to = 0 существует решение u(t,g).
Лемма 15. Множество
щ -и2 V —Р А 0
и2 -щ 0 V А
щ — щ 0 0 V —,
щ 0 0 0 V
к=1
является инвариантным множеством системы й — f{u) при г > 0.
При А > 0 легко найти стационарное решение u(t,g*) = д* при t ^ 0 и доказать его единственность в U. Действительно, приравнивая правые части й — f(u) к нулю, получаем f(g*) = 0, откуда и\ = V/X = р, ик = рк'¦ Принимая во внимание, что V + щ + ... = г, получаем уравнение на р:
Р
1-р
= г-\р,
14
которое имеет единственное решение р* при р > 0. Таким образом, д^ = Хр*, д% =
(Р*)к-
Оказывается, можно построить такое семейство компактных инвариантных подмножеств, плотное в некотором шаре, что будут выполнены условия теоремы 8, откуда вытекает следующее утверждение. Теорема 16. При А > 0 для любого g e U: \\u(t,g) — g*\\ —> 0 при t —>• сю.
Раздел 4 посвящен краткому перечислению других счётномерных систем дифференциальных уравнений, к которым применим описанный метод.
В разделе 5 изучается неприводимая апериодическая цепь Маркова со счётным пространством состояний, непрерывным временем и ограниченными в совокупности интенсивностями переходов. В этом разделе устанавливается достаточный признак эргодичности цепи Маркова в терминах существования инвариантных подмножеств у описывающей её системы дифференциальных уравнений. Отметим, что задача об эргодичности таких цепей Маркова в терминах существования инвариантного распределения решена полностью, т.е. неприводимая апериодическая марковская цепь с ограниченными интенсивностями переходов эргодична тогда и только тогда, когда имеется единственное инвариантное распределение.
Очень часто найти само стационарное распределение в явном виде не представляется возможным и интересен сам вопрос об эргодичности цепи Маркова. Существует множество подходов для доказательства эргодичности цепей Маркова, среди которых следует выделить метод обновлений С. Асмусена14, метод склеивания (coupling'a), предложенный Т. Линдвалом18 и метод пробных функций (метод Фостера-Ляпунова), изложенный с современной точки зрения в книге В.А. Малышева, М.В. Меньшикова и Г. Файоля19. Эти подходы не апеллируют (по меньшей мере, явно) к дифференциальным уравнениям, которыми описываются цепи Маркова. В разделе 5 устанавливается некоторая новая теорема о сходимости в терминах прямой системы дифференциальных уравнений Колмогорова, описывающей цепь Маркова.
Без ограничения общности будем считать, что пространство состояний эргодичной апериодической цепи Маркова состоит из целых неотрицательных чисел {0,1,2,...}. Вероятности нахождения в момент t в состоянии pi удовлетворяют прямой системе дифференциальных уравнений Колмогорова
X = QTX: xehx= (po,Pl, - - -Г;
где pi ^ 0, ^2i>0Pi = 1, а матрица Q задаёт интенсивности переходов.
Далее предполагается, что матрица QT задаёт ограниченный оператор в 1г, что эквивалентно условию q = supjj,0(—qa) < сю. Обозначим через x(t,p) решение системы
18 Г. Lindvall. Lectures on the coupling method. John Wiley & Sons Inc., New York, 1992. A Wiley-Interscience Publication.
19G. Fayolle, V. A. Malyshev, M. V. Men'shikov. Topics in the constructive theory of countable Markov chains. Cambridge University Press, Cambridge, 1995.
15
дифференциальных уравнений х = QTx. Через X обозначим множество
Лемма 17. Пусть существует такое семейство компактных инвариантных подмножеств {Fa}, что для всякого а выполнено x(t, Fa) С Fa при всех t ^ 0. Кроме того, предположим, что при некотором ? ^ q для всякого g G L \ 0 выполнено /с(ехр (Q + (I),g) > 0. Тогда существует единственная неподвижная точка р* G X, причём для всякого pel имеется сходимость x(t,p) —> р* при t —> оо.
Таким образом, если есть хотя бы одно компактное инвариантное множество, то существует единственное инвариантное распределение р*. Некоторое обратное утверждение изложено в следующей лемме.
Лемма 18. Предположим, что существует инвариантное распределение р*. Тогда всякая траектория предкомпактна.
В разделе б показано, каким образом можно применять лемму 17 к изучению эргодичности некоторой специальной транспортной сети, состоящей всего из двух узлов, но имеющей бесконечную очередь пассажиров.
Глава 3. Третья глава посвящена изучению транспортной сети с изначально счётным числом узлов. Оказывается, такая сеть является обобщением хорошо известного процесса с нулевой областью зависимости, введённого Ф. Спицером20.
Здесь используется терминология, принятая для процессов с нулевой областью зависимости: под частицами подразумеваются приборы, а под ячейками — узлы. Так что, имеется конечное или счётное число частиц, которые находятся в счётном множестве узлов J. Переходы частиц, находящихся в узле г G J, происходят после истечения случайного показательно распределённого времени Tj с параметром 7г- Если по прошествии этого времени узел г непуст, то одна и только одна из частиц, находящихся в ячейке, мгновенно перемещается в некоторый узел j, который выбирается с вероятностью рц. Все имеющиеся интервалы времени и переходы считаются независимыми в совокупности. Вероятности перехода из г в j составляют матрицу Р — (pij)i e j, V? G J ^2 Pij = 1- Этот процесс можно описать с помощью
бесконечного вектора r](t) — {4i{t)}ieJ , t > 0, где rji(t) — это число частиц в узле i в момент t. Существование феллеровского процесса rj(t) выводится из существования описывающей его марковской полугруппы S(t) ((S(t)f)(r)) = E(/(r;(t)) | т/(0) = г})) с помощью известных теорем теории марковских процессов6. Построение же марковской полугруппы S(t) можно провести с помощью техники, описанной в книге Т.М. Лиггетта21.
20F. Spitzer. Interaction of Markov processes. // Advances in Math., vol. 5, pp.246-290 (1970), 1970. Т.М. Лиггетт. Марковские процессы с локальным взаимодействием. Изд-во «Мир», Москва, 1989.
16
Пусть Z+ = N U {0}, Z+ = Z_|_U{oo}. Тогда в пространстве состояний системы W =Z+ можно ввести специальную метрику, в которой само пространство будет компактным. Пусть В — сг-алгебра, порождаемая цилиндрическими множествами, a C(W) — банахово пространство всех действительно-значных функций на W с равномерной нормой.
Для всякой / G C(W) V г G J определим «меру зависимости от координаты г» по правилу
Af(i) = sup {| f(V) - /(С) \:v,CeW,Vj = О V j ф г} .
Введём плотное в C(W) множество D(W) — < / G C(W) : \\\ f \\\ = Yl A/(*) < °° f •
I ieJ )
Определим следующий оператор на D(W):
ieJ jeJ Теорема 19. Если
У] <сю, (х)
mo
(1) Замыкание А оператора А является инфинитезимальным оператором марковской полугруппы S(t) и подпространство D(W) является существенным подпространством для А.
(2) Существует единственный феллеровский процесс rj{t) : (f^, S, P) —? (W,B) с заданным инфинитезимальным оператором А; (Л, S, Р) — некоторое вероятностное пространство.
Следствие 20. Если выполнено одно из утверждений:
• sup 7i < оо, sup J2 Pji < °° ieJ ieJ jeJ
• J2 Ъ < °°; ieJ
утверждения (1)-(2) теоремы 19 верны.
Далее всюду предполагается, что условие (х) выполнено.
Предположим, что однородная марковская цепь с пространством состояний J и переходной матрицей Р является апериодичной и неприводимой. Введём
Предположение А: Существует положительная инвариантная мера тг = (ttj) для Р (необязательно конечная).
Предположение Б: Существует единственная инвариантная вероятностная мера тг = {^i) для Р (которая называется стационарной).
Предположение В: Счётная цепь Маркова с переходной матрицей Р является транзиентной.
17
Обозначим
def Щ
a = sup — < oo. (x x)
i?J li
Пусть /5max = I/a. Для любого p G [0; ртах] и p — oo введём меру-произведение Ьр(-) на (W,B) с координатными множителями /*(•), г G J, определяемыми по-разному в следующих двух случаях:
если р G [0; /?тах] и р(тГг/ъ) < 1, то
(Х ~ Pfahi)) (p{Kihi)t , A; G Z+,
0, /Ь = оо если же р — ртах, p{^iMi) — 1 либо просто р = оо, то
L, К = OO.
Введём L = {Lp(-) : p G [0;pmax], p = oo}. Обозначим через L выпуклую оболочку L:
(1 ^'
К—замкнутое выпуклое множество, /("DL
Пусть М. — класс всех инвариантных мер марковского процесса {f]{t)}t>o ¦ Теорема 21. Предположим, что выполнены предположение А и условие (хх). Тогда замкнутая выпуклая оболочка L множества мер
{Lp(-) : р G [0; ртах], р = оо}
включена в класс Л4 всех инвариантных мер марковского процесса {i](t)}t>0-Пусть
ТГг / n
— < ОО. (X X XJ
Утверждение 22. Предположим, что выполнены предположение А и условие (х х х). ТогдаЧ р? [0; pmax]
т („ . Х^„ < ^Л _ 1
lp I v ¦ 2^^г I ~
Теорема 23. Пусть выполнены предположение А и условие (х х х). Предположим, что для узла j0 G J выполнено условие тг^0/^0 = тахт^/т*. Тогда V k G Z+
Теорема 24. Предположим, что выполнено одно из следующих условий:
(1) 7 < °° и предположение В;
(2) 7 < оо и Vj G J J2Pij < I/
18
ICQ: 638099552 (в сети)
Тел.: +7 (928) 260-05-38 (на связи)
Почта.: 
Интересные работы (за сутки)
Новые поступления
