Цепи Маркова (1121219), страница 20

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 20)

(См.: Кац М . Вероятность и смежные вопросы в физике.М.: Мир, 1965.)9 Ср.с названием фильма «Murial’s Wedding».Эту величину можно вычислить как определитель от определителя, имеяв виду, что J2d−1 = Id−1 :Id−1 − Ad−1−Jd−1=dY−1j=0dY−1j=0( + 1 − d + 1 + 2j) m(d−1,j) =( − d + 2j) m(d−1,j) ( − d + 2(j + 1)) m(d−1,j) ==dY( − d + 2j) m(d−1,j) +m(d−1,j−1) ,j=0( − 1 − d + 1 + 2j) m(d−1,j)j=0гдеdY−1=(1 × 1)для d > 1.

Здесь Jd−1 — это бинарная (2d−1 × 2d−1)-матрица инцидентности, соответствующая двум копиям матрицы Ad−1 ; см. рис. 1.32. Мывидим, что Ad разбита на части (она содержит ненулевые элементы, блокииз которых коммутируют между собой).

Поэтому характеристический многочлен Dd ( ) = det( Id − Ad) имеет вид D0 ( ) = и для d > 1 выполняетсяравенствоDd ( ) = det( − d + 2j) m(d,j) =j=0(1.12.23)Ad−1 Jd−1Jd−1 Ad−1dYЧтобы доказать этот факт, рассмотрим матрицу смежности A d видаd × P. Матрица Ad состоит из элементов 0, 1 и является симметричной(2d × 2d)-матрицей, определяемой рекуррентными соотношениямиAd =( − d + 2j) m(d,j) ,откуда получаем, что собственные значения матрицы A d равны d − 2j, j == 0, . . . d, а собственные значения матрицы P = d−1 Ad задаются формулой(1.12.22). Чтобы подсчитать кратности m(d, j), вновь используем представленные выше рекуррентные соотношения:Cjd .dYj=0с геометрическими кратностямииDd ( ) =dA0 = (0)Итерация приводит к выражениюDd ( ) = det [( Id−1 − Ad−1) 2 − Id−1 ] == det[( − 1)Id−1 − Ad−1 ] [( + 1)Id−1 − Ad−1 ] == Dd−1 ( − 1)Dd−1 ( + 1).Классическая урновая модель Эренфеста может быть описана как случайное блуждание «по ближайшим соседям» на d-мерном двоичном кубес числом вершин 2d и числом ребер d2d−1 .

Вершины (состояния) индексированы двоичными «стороками» длины d: = ( 1 , . . . , d) ∈ {0, 1}d , где1 , . . . , d = 0, 1. Матрица перехода P = (pij) составлена из элементов1, если и 0 — ближайшие соседи, т. е. 0 может бытьdполучено из заменой лишь одной компоненты j(если j = 0, то 0j = 1, или если j = 1, то 0j = 0),p , 0=j = 1, . . . , d,0,впротивном случае, т. е.

когда и 0 отличаются другот друга более чем одной цифрой или совпадают.(1.12.21)= 1/2d и задаетИнвариантное распределение является равномерным:собственный вектор P, соответствующий собственному значению 0 = 1.Собственные значения можно вновь вычислить точно (хотя вычисленияболее сложные). Ответ таков: существуют d + 1 различных собственныхзначений2j(1.12.22)1 − , 0 6 j 6 d,§ 1.12. Геометрическая алгебра ц.м.д.в., I. Собственные значения и спектральные щели 125Глава 1.

Цепи Маркова с дискретным временем124−Jd−1Id−1 − Ad−1.Следовательно,m(d − 1, j) = 0, если j < 0 или j > d − 1.m(d, j) = m(d − 1, j) + m(d − 1, j − 1),откуда получаем m(d, j) = Cjd .Таким образом, алгебраическая и геометрическая кратности собственногозначения d − 2j матрицы Ad задаются формулой (1.12.23). (Это доказательство было представлено Дэвидом М. Р. Джексоном.)Цепь с вероятностями перехода (1.12.21) является неприводимой и периодической с периодом 2.

Это согласуется с тем фактом, что последнее§ 1.12. Геометрическая алгебра ц.м.д.в., I. Собственные значения и спектральные щели 127собственное значение 2d −1 равно −1. Чтобы получить апериодическуюцепь, удобно видоизменить модель, допуская, что блуждание может оставаться в прежнем состоянии с вероятностью 1/ (d + 1), а оставшаясявероятность d/ (d + 1) вновь распределяется равномерно между d ближайшими соседями. Такая модификация этого примера будет обсуждатьсяв следующем параграфе.Примеры 1.12.1 и 1.12.2 подготовили нас к обсуждению общих спектральных свойств матрицы вероятностей перехода. (Многие свойства,сформулированные ниже, справедливы и для произвольной матрицы Mс неотрицательными элементами.) Пусть P — это (l × l)-матрица вероятностей перехода.

Можно рассматривать ее правостороннее действиевида 7→ P, т. е. действия на l-мерную вектор-строку = ( 1 , . . . , l),и левостороннее действие x 7→ Px, когда матрица действует на l-мерный этом классе (и любое стационарное распределение является выпуклойлинейной комбинацией этих стационарных распределений для классов).Таким образом, значение 1 всегда является собственным значением; потрадиции ему приписывают индекс 0: 0 = 1.Аналогично спектр матрицы PT определяется как множество ее собственных значений. Мы знаем также, что матрица P T всегда имеет собственное значение 1: соответствующий собственный вектор — это 1T == (1, .

. . , 1). Действительно, 1T P = (P1) T = 1T , поскольку P1 = 1 (см.соотношение (1.1.3)). На самом деле характеристические уравнения для Pи PT имеют одни и те же корни, так как их характеристические многочленысовпадают: det( I − P) = det( I − P) T = det( I − PT). Следовательно,спектры матриц P и PT совпадают.ствительными или комплексными. Конечно, правостороннее действие Pсоответствует левостороннему действию транспонированной матрицы P Tи наоборот. (Однако PT не обязятельно является стохастической матрицей.) В дальнейшем, говоря о собственных значениях и собственныхвекторах, мы подразумеваем правостороннее действие рассматриваемойматрицы.

Таким образом, собственное значение матрицы P — это такоечисло , что yT P = yT для некоторого l-мерного вектора-строки yT .Аналогично, собственное значение матрицы P T — это такое число , чтоyT PT = y для некоторого вектора-строки yT ; очевидно, равенство yT PT == yT эквивалентно равенству Py = y. В обоих случаях и y могут бытькомплексными.Спектр матрицы P определяется как множество ее собственных значений.

Конечно, каждое собственное значение является корнем характеристического уравнения det( I − P) = 0; более того, каждый корень являетсясобственным значением. Определитель det( I − P) = (−1) l det(P − I)является многочленом спепени l (его называют характеристическим многочленом матрицы P), следовательно, он имеет l корней, причем некоторые изних могут быть комплексными (несмотря на то что коэффициенты многочлена действительны). Мы знаем, что каждое стационарное распределениеявляется собственным вектором, соответствующим собственному знав точности эточению 1, так как уравнение инвариантности P =и означает.

Далее, если матрица P неприводима, то она имеет единственноестационарное распределение; в общем случае для каждого сообщающегосякласса имеется единственное стационарное распределение, заданное наВ чем состоит различие между корнями характеристического уравнения (или, что эквивалентно, корнями характеристического многочлена)и собственными значениями? Краткий ответ: они отличаются кратностью.Предположим, что корнями характеристического полинома det( I − P) являются числа 0 , . . . , l−1 . Тогда можно представить определитель в видеlQ−1произведения det( I−P) =( − p). Однако корни могут быть кратными,Глава 1. Цепи Маркова с дискретным временем126Призрак бродит по Европе10x1p=0поэтомуудобно также записать это разложение в виде det( I − P) =Q= ( − p) p , где произведение берется по всем различным корням, или,pчто эквивалентно, по различным собственным значеиям.

Здесь следуетразличать алгебраическую кратность p корня p и геометрическуюкратность собственного значения p : в последнем случае кратность равна числу таких линейно независимых векторов y, что yP = p y (т. е.размерности собственного пространства E( p) ⊆ Cl , отвечающемусобственному значению p). Алгебраическая кратность всегда не меньшегеометрической: p > dim E( p). Но если p является корнем многочленаdet( I − P) (т. е. его кратность p > 1), то dim E( p) > 1, т. е. существуетсобственный вектор, соответствующий собственному значению p . Следовательно, матрица P может иметь меньше чем l линейно независимыхсобственных векторов, но их число всегда не меньше числа различныхкорней.Эти рассуждения, конечно, верны и для P T .

Более того, и алгебраичеК. Маркс (1818–1883), немецкий философxlвектор-столбец x =  ... ; в обоих случаях векторы могут быть дей-10 По-английскипризрак — это «spectre» (прим. перев.).§ 1.12. Геометрическая алгебра ц.м.д.в., I. Собственные значения и спектральные щели 129ская, и геометрическая кратности корней p одинаковы для обеих матрицP и PT .

Следовательно, число линейно независимых собственных векторову P и PT одинаково. Иными словами, спектры P и P T совпадают, дажеесли учитывается кратность. На самом деле последний факт имеет местодля любой действительной матрицы M.Если матрица P эрмитова (т. е. P = P T), то геометрические и алгебраические кратности совпадают. На самом деле в этом случае P имеетортонормированный базис из l собственных векторов. Кроме того, в этомслучае все собственные значения (или, что эквивалентно, все корни характеристического уравнения) действительны.

Иными словами, спектр Pявляется подмножеством действительной прямой R.в комплексном круге единичного радиуса с центром в начале координат.Точная формулировка содержится в следующей теореме.Теорема 1.12.3. Пусть P — это неприводимая стохастическая(l × l)-матрица. Тогда справедливы следующие утверждения.1. Число 0 = 1 всегда является собственным значением матрицP и PT , его алгебраическая и геометрическая кратности равны 1,и соответствующее собственное пространство матрицы P порождается стационарным распределением , а соответствующеесобственное пространство матрицы PT порождается вектором 1T .Норма ||P|| = ||PT || равна 1, и все собственные значения p 6= 0удовлетворяют неравенству | p | 6 1, т.

Характеристики

Список файлов лекций