Главная страница

Тема Элементы комбинаторики Комбинаторика это наука о расположении элементов в определенном порядке и о подсчете числа способов такого расположения


Скачать 1.75 Mb.
НазваниеТема Элементы комбинаторики Комбинаторика это наука о расположении элементов в определенном порядке и о подсчете числа способов такого расположения
Дата23.11.2021
Размер1.75 Mb.
Формат файлаpdf
Имя файлаlekcii16.pdf
ТипКонспект
#280266
страница4 из 6
1   2   3   4   5   6
Тема 9. Случайные процессы. Цепи Маркова
Понятие случайного процесса является одним из важнейших не только в современной теории вероятностей, но и в естествознании, инженерном деле, экономике, теории связи и других областях. Оно позволяет описывать динамику развития изучаемого случайного явления во времени. Создание и развитие математической теории случайных процессов началось в XX веке и было связано с трудами А.Н.Колмогорова (1903-1987),
А.Я.Хинчина (1894-1959), Е.Е.Слуцкого (1880-1948), Н.Винера (1894-1965), Дж.Дуба
(1910-2004), П.Леви (1886-1971), В.Феллера (1906-1970) и многих других ученых.
Имелся ряд импульсов к возникновению нового раздела теории вероятностей.
Считается, что основной из них дала физика. Напомним, что в 1827 году шотландский ботаник Р.Броун (1773-1858) обнаружил под микроскопом хаотическое движение частиц цветочной пыльцы в воде.

Рис. 1. Броуновское движение.
Однако природа этого движения, получившего название броуновского, долго оставалась невыясненной. Только в конце XIX –– начале XX века было осознано, что оно представляет собой одно из проявлений теплового движения атомов и молекул вещества.
Оказалось, что для описания процессов такого рода требуются вероятностно- статистические подходы. Математические и физические модели броуновского движения и более общих процессов диффузии были построены А.Эйнштейном (1879-1955),
М.Смолуховским (1872-1917), М.Планком (1858-1847), А.Фоккером (1887-1972),
П.Ланжевеном (1872-1946), Н.Винером (1894-1964) и другими учеными. Интересно отметить, что в диссертации Л.Башелье (1870-1946), написанной в 1900 году под руководством А.Пуанкаре (1854-1912), впервые, на 5 лет раньше физиков, предложена модель для описания флуктуаций на бирже курсов ценных бумаг, которая содержала математическую теорию броуновского движения. Эта работа долго оставалась без должного внимания.
Среди важных предпосылок создания теории случайных процессов следует назвать "цепную зависимость", введенную А.А.Марковым (1856-1922) в 1906 году. Удивительно, что построенная модель случайных величин, получившая название цепи Маркова, возникла при изучении им расположения комбинаций гласных и согласных букв в тексте романа "Евгений Онегин" и лишь позднее была использована и обобщена в ряде физических исследований. На сегодняшний день создана мощная теория марковских процессов, имеющая разнообразные применения, в частности, в биологии. Интерес представляет и теория марковских случайных полей, возникшая на основе теории марковских процессов. Марковские цепи и поля находят приложения и при распознавании образов. Упомянем также широко известный метод Монте-Карло марковских цепей
(английская аббревиатура MCMC). Укажем на книги Е.Б.Дынкина, Ю.А.Розанова,
Р.Киндермана, Н.Бремо, Г.Винклера.
Кроме того, Ф.Лундбергом (1876-1965) в его диссертации (1903) была введена модель, описывающая деятельность страховой компании. В этой работе впервые возник так называемый пуаcсоновский процесс, который позднее стал использоваться при
изучении радиоактивного распада. В теории страхования ныне широко известны модели
Крамера – Лундберга и Спарре Андерсена. Процессы с "дискретным вмешательством случая" и идеи, восходящие к классическим задачам "геометрических вероятностей"
(например, о "случайном бросании" на плоскость точки или иглы) привели позднее к созданию теории точечных случайных процессов (см., например, монографию Д.Штояна и Г.Штояна). Отметим также модель Гальтона – Ватсона, относящуюся к анализу вымирания аристократических фамилий в Великобритании. Эта модель сформировалась в
1873 году в ходе переписки Ф.Гальтона (1822-1911) и Г.Ватсона (1827-1903), приведшей к "теореме вырождения". Она послужила основой для развития во второй половине XX века теории ветвящихся процессов, изучающей эволюцию семейств рождающихся и гибнущих частиц, а также взаимодействия частиц различных типов. Укажем на труды
А.Н.Колмогорова, Н.А.Дмитриева (1924-2000), Б.А.Севастьянова, Р.Беллмана (1920-1984),
Т.Харриса (1919-2005), П.Ягерса и их последователей.
Выдающуюся роль в создании общей теории случайных процессов сыграли статьи
А.Н.Колмогорова "Об аналитических методах в теории вероятностей" (1931) и
А.Я.Хинчина "Теория корреляции стационарных стохастических процессов" (1934).
Однако прочный фундамент для теории случайных процессов (и всей теории вероятностей) был заложен лишь в 1933 году благодаря аксиоматике Колмогорова.
Случайный процесс – это семейство случайных величин
{
}
T
t
t
X

),
(
, заданных на некотором вероятностном пространстве
)
,
,
(
P


и некотором промежутке


T
Параметр t интерпретируется как время. Таким образом, X(t) представляет собой состояние (исследуемой) "системы" в момент t. Точнее говоря, случайный процесс – это функция X=X(

,t) переменных



и
T
t
такая, что X(

,t) является случайной величиной при каждом
T
t
. При фиксированном ω функция X(ω,

) называется траекторией (или реализацией) процесса. Обычно аргумент ω опускают и пишут X(t).
Разумеется, можно рассматривать случайный процесс, заданный на каком-либо вероятностном пространстве
)
,
,
(
P


и произвольном параметрическом множестве T.
Если
d
T


и d>1, то говорят о случайном поле. Возможны и дальнейшие обобщения, например, исследуются процессы, у которых величины X(t) принимают значения в абстрактном пространстве S, снабженном

-алгеброй

(при каждом
T
t
величина X(t) является

 |
-измеримой). Наряду с термином случайный процесс (определенный на некотором множестве T) как синоним используется термин случайная функция.
Классическая теорема Колмогорова дает условия, при которых на некотором пространстве
)
,
,
(
P


существует случайный процесс
{
}
T
t
t
X

),
(
c заданными конечномерными распределениями, т.е. мерами, представляющими собой законы распределения векторов
))
(
),...,
(
(
1
n
t
X
t
X
, где
T
t
t
n

,...,
1
и


n
Случайный процесс
{
}
T
t
t
X

),
(
, где
,


T
называется цепью Маркова, если величины
)
(t
X
при всех
T
t
принимают значения в конечном или счетном множестве S

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

,
,...,
1
S
j
i
i
i
n
,
<
<
<
<
1
t
s
s
s
n
T
t
s
s
s
n

,
,
,...,
1
и


n
),
=
)
(
|
=
)
(
(
=
)
=
)
(
,
=
)
(
,...,
=
)
(
|
=
)
(
(
1 1
i
s
X
j
t
X
P
i
s
X
i
s
X
i
s
X
j
t
X
P
n
n
когда
0

)
=
)
(
,
=
)
(
,...,
=
)
(
(
1 1
i
s
X
i
s
X
i
s
X
P
n
n
Смысл данного определения состоит в том, что поведение «системы» в момент времени
T
t
при заданных состояниях в предшествующие моменты времени
T
s
s
s
n

,
,...,
1
зависит только от ее состояния в последний момент s, предшествующий t.
Обычно рассматриваются цепи Маркова с дискретным или непрерывным временем, т.е. когда соответственно
+
=


T
или
).

,
0
[
=
T
Конечномерные распределения марковской цепи задаются двумя объектами – переходными вероятностями
),
=
)
(
|
=
)
(
(
=
)
,
(
,
i
s
X
j
t
X
P
t
s
p
j
i
где
)

,
(

T
t
s
t
s
, и начальным распределением
)
=
)
0
(
(
i
X
P
,

,
S
j
i
Заметим, что динамика случайных явлений фактически присутствовала и в ряде классических задач, вовлекавших рассмотрение последовательности случайных величин
,...
,
2 1
X
X
. Достаточно упомянуть первую предельную теорему теории вероятностей – закон больших чисел, установленный Бернулли в 1713 году. Эта теорема в современном изложении утверждает, что

1
=

1
n
k
k
p
X
n
по вероятности при


n
для последовательности независимых случайных величин, принимающих значения 1 и 0 соответственно с вероятностями p и 1-p (0 0 выполнено соотношение

1


,
0

)
>
|
-
1
(|
n
k
n
p
X
n
P

Тем самым "частота" появления "успехов" (т.е. единиц) сходится в указанном смысле с ростом n к вероятности "успеха" в отдельном испытании.
Развитие этого направления привело в теории случайных процессов к рождению эргодической теории. В этой связи достаточно упомянуть эргодическую теорему Биркгофа – Хинчина и субэргодическую теорему Кингмана – Лиггетта.
Например, с помощью последней теоремы устанавливается теорема Фюрстенберга –
Кестена, утверждающая следующее. Пусть
,...
,
2 1
X
X
– стационарная последовательность
d
d ×
-матриц с положительными элементами, логарифм которых интегрируем по мере P.
Тогда найдется случайная величина Y такая, что для матричных элементов
n
X
X
1
при всех
}
,...,
1
{

,
d
r
k
имеем


),
,
,
(
в и
п.н.

)
log(
1 1
,
1
n
P
L
Y
X
X
n
r
k
n


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

Выдающийся вклад в эргодическую теорию внесен Я.Г.Синаем и его школой.

Здесь же упомянем интенсивно развивающуюся область изучения случайных операторов и их спектров. Более того, оказалось, что изучение спектров бесконечных случайных матриц имеет непосредственное отношение к знаменитой гипотезе Римана о нулях ζ-функции.
Теория случайных процессов бурно развивалась в XX-м веке. Возникли обширные новые направления этой теории. Например, исследования А.К.Эрланга (1878-1929), связанные с изучением загрузки телефонных сетей, привели к формированию теории массового обслуживания ("теории очередей"). В этой области выделяются работы
Б.В.Гнеденко (1912-1995), И.Н.Коваленко, Ю.К.Беляева и А.Д.Соловьева (1927-2001).
Ныне эта теория охватывает новые области исследований, например, транспортные сети.
Введение К.Ито (1915-2008) стохастического интеграла, называемого ныне интегралом Ито, привело к созданию стохастического исчисления и мощной теории стохастических дифференциальных уравнений. Например, уравнение Ланжевена для скорости V=V(t) движения частицы в жидкости может быть записано в виде dV(t)= a V(t)dt + b dW(t) , t≥ 0, где a и b – числовые коэффициенты, характеризующие массу частицы и вязкость среды, а W=W(t) – винеровский процесс (броуновское движение). Поразительный факт заключается в том, что почти все (по мере P) траектории винеровского процесса не дифференцируемы ни в одной точке
)

,
0
[

t
! Поэтому приведенное уравнение следует понимать как формальную запись некоторого интегрального соотношения, вовлекающего интеграл Ито. Для привлечения внимания читателей к этой области исследований отметим, что методы стохастического анализа позволили решить сложные и важные задачи выделения сигнала на фоне шума. Более того, отметим, что ныне на передний край выходят исследования стохастических дифференциальных уравнений в частных производных.
Отдельного упоминания заслуживают разнообразные задачи оптимального управления случайными процессами. Например, задачи нахождения (в определенном смысле) оптимальных режимов функционирования сложных систем.
Теория гиббсовских случайных полей, заложенная в 60-е годы прошлого века в работах Р.Л.Добрушина (1929-1995), О.Лэнфорда и Д.Рюэля, позволила, например, интерпретировать фазовые переходы состояний вещества. Теория автомодельных процессов, инициированная А.Н.Колмогоровым в 40-е годы XX-го столетия, обеспечила прогресс в изучении турбулентности. Оказалось, что автомодельность свойственна многим физическим процессам. Дальнейшее развитие этой теории "фрактальности" связано с работами Б.Мандельброта и его последователей.
Отдельно отметим, что возникли новые разделы математической статистики, относящиеся к изучению случайных процессов (в частности, прогноз и интерполяция). В этой связи укажем на исследования У.Гренандера, И.А.Ибрагимова и Р.З.Хасьминского.

Важную роль в современных условиях играет и моделирование (на компьютере) случайных процессов и полей.
Можно сказать, что сейчас существует целый ряд самостоятельных направлений исследований в теории случайных процессов, некоторые из них были упомянуты выше.
Как правило, выделяются достаточно широкие классы случайных процессов и для их изучения используется соответствующий набор методов.
По семействам независимых случайных величин (более общим образом, случайных элементов), которые существуют в силу теоремы Ломницкого - Улама, возможно строить новые случайные функции. Так, например, определяются процессы восстановления.
Напомним, что если
,...
,
2 1
X
X
– независимые одинаково распределенные положительные величины, то простейший процесс восстановления задается формулой

n
1
=
k k
},

X
:

max{
=
)
(
t
n
t
Y

где
)

,
0
[

t
и сумма по пустому множеству индексов (т.е. когда
t
X >
1
) считается равной нулю. Если "поломки" некоторого устройства происходят в случайные моменты
,
+
+
,
+
,
3 2
1 2
1 1
X
X
X
X
X
X
, и мгновенно производится устранение этих поломок, то Y(t) дает общее число восстановлений за время от 0 до t. Заметим, что анализ траекторий сумм независимых случайных величин (иначе говоря, случайных блужданий) нашел применения в теории полимеров. Большой интерес представляют также случайные блуждания в случайной среде.
Важный класс образуют процессы с независимыми приращениями. В этот класс входят броуновское движение (называемое также винеровским процессом) и пуассоновский процесс. В связи с задачами стохастической финансовой математики большое значение приобрели также процессы Леви.
Обширный и хорошо изученный класс составляют гауссовские процессы.
Действительный гауссовский процесс
{
}
T
t
t
X

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


n
и произвольных
T
t
t
n

,...,
1
вектор
))
(
),...,
(
(
1
n
t
X
t
X
является гауссовским.
Другими словами, характеристическая функция этого вектора имеет вид
)},
,
(
2 1
-
)
,
(
exp{
=
))}
(
+
+
)
(
(
exp{
1 1





C
a
i
t
X
t
X
i
E
n
n
где (

,

) – скалярное произведение в
n

,
=
2
i
–1,
,

)
,...
(
=
1
n
n




вектор
n
n
a
a
a


)
,...,
(
=
1
и
n
n ×
-матрица
)
(
=
,r
k
c
C
симметрична и обладает свойством неотрицательной определенности (
)
(
=
k
k
t
EX
a
и
))).
(
),
(
cov(
=
,
r
k
r
k
t
X
t
X
c
Заметим, что компоненты гауссовского вектора
))
(
),...,
(
(
1
n
t
X
t
X
независимы в том и только том случае, когда
0
=
))
(
),
(
cov(
r
k
t
X
t
X
при всех
}).
,...,
1
{

,
(

n
r
k
r
k
Броуновское движение является гауссовским процессом.

Множество глубоких результатов относится к изучению траекторий гауссовских процессов (и полей). Например, найдены необходимые и достаточные условия непрерывности траекторий. Исследованы такие важные задачи, как нахождение асимптотики вероятности выброса процесса за высокий уровень u (когда


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

-алгебр


, где


T
t
, обладающих свойством "возрастания":







при всех
T
t
s

,
, для которых
t
s
Действительный случайный процесс
{
}
T
t
t
X

),
(
называется мартингалом относительно фильтрации
T
t
)
(


, если величина X(t) является
)
(
|




-измеримой при любом
T
t
и
)
(
=
)
|
)
(
(
s
X
t
X
E


для всех
T
t
s

,
таких, что
t
s
. Здесь
)
|

(


E
обозначает условное математическое ожидание относительно

-алгебры


. Оказалось, что класс мартингалов
(и более общий класс семимартингалов) играет важнейшую роль в теории стохастических дифференциальных уравнений.
Во второй половине XX-го века стали исследоваться процессы и поля с перемешиванием, а начиная с 70-х годов - процессы и поля, обладающие различными формами положительной или отрицательной зависимости. Часто положительную зависимость называют ассоциированностью. В физической литературе используются близкие условия, носящие название ФКЖ-неравенств. Такие неравенства и их аналоги оказались полезными в задачах теории перколяции (или просачивания). Простейший вариант такой задачи был сформулирован в 1957 году С.Бродбентом и Дж.Хаммерсли
(1920-2004). Поместим пористый камень в емкость с водой. С какой вероятностью вода
попадет в заданную точку этого камня? Формализуется задача следующим образом.
Представим себе камень как множество "широких" и "узких" каналов. Удобно рассматривать камень как решетку
d

(при d=3) и считать каналами ребра, соединяющие соседние вершины (для которых |x-y|=1, где
d
y
x


,
и

1
=
|,
|
=
|
|
d
k
k
u
u
d
d
u
u
u


)
,
,
(
=
1

).
Пусть каждое ребро
d

является открытым ("широким") с вероятностью p и закрытым
("узким") с вероятностью 1-p, причем все ребра открываются или закрываются независимо друг от друга (0
d

возникает бесконечный путь из открытых каналов (имеются и другие формулировки). Доказывается, что ответ на поставленный вопрос зависит от того, больше или меньше p некоторой критической вероятности
)
(d
p
c
. Дальнейшему развитию этой проблематики посвящены, например, книги Г.Кестена и Дж.Гримметта.
Во второй половине прошлого века были установлены глубокие взаимосвязи между изучением процессов (полей), заданных на дискретных и непрерывных параметрических множествах, а также исследованы распределения процессов в различных функциональных пространствах. Огромный вклад в эту область функциональных предельных теорем внесли А.Н.Колмогоров, Ю.В.Прохоров, А.В.Скороход, В.Штрассен, А.А.Боровков,
А.Н.Ширяев, Ж.Жакод и другие ученые.
Новые проблемы, требующие развития теории случайных процессов и полей, возникают в биологии и медицине. Усилия многих математиков направлены также на развитие актуарной и стохастической финансовой математики.
Интересно, что вероятностные идеи используются в различных математических областях. Например, в комплексном анализе хорошо известно уравнение Левнера. А именно, рассмотрим односвязную область
2


D
и простую непрерывную кривую γ в
D, начинающуюся на

D. По теореме Римана
])
,
0
([
\
=
:
t
D
D
t

конформно изоморфно D.
Пусть D – единичный диск,
t
t
D
D
f

:
– должным образом нормированный изоморфизм.
Для
D
z
уравнение Левнера имеет вид
,
=
)
(
,
-
)
(
+
)
(
)
(
-
=

)
(

0
'
z
z
f
z
t
z
t
z
f
t
z
f
t
t


где ζ(t) – некоторая функция. Эволюция Шрамма -- Левнера означает выбор
).
(
=
)
(
t
W
t


Здесь W – винеровский процесс и

– некоторая константа. Удобно вместо
t
f
использовать обратное отображение
t
g
, а также переход от диска к верхней полуплоскости, тогда возникает уравнение
=
)
(
g
,
)
(
-
)
(
2
=

)
(

0
z
z
t
z
g
t
z
g
t
t

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

Известно, что крупные достижения в науке возникают на стыке нескольких областей. Отметим, что в 2006 году А.Ю.Окунькову была присуждена премия Филдса "за достижения, соединяющие теорию вероятностей, теорию представлений и алгебраическую геометрию". В 2010 году С.К.Смирнов был удостоен премии Филдса за работы по теории перколяции и исследование скейлинговых пределов в моделях статистической физики.
1   2   3   4   5   6


написать администратору сайта