ГАУССОВЫ МАРКОВСКИЕ ПОСЛЕДОВАТЕЛЬНОСТИ
Гауссовы марковские последовательности
23
УДК 519.2
С. Н. ВОРОБЬЕВ, Н. В. ГИРИНА, Л. А. ОСИПОВ
ГАУССОВЫ МАРКОВСКИЕ ПОСЛЕДОВАТЕЛЬНОСТИ
Устанавливается свойство ( 2k +1)-диагональности матрицы точности гауссовой
марковской последовательности k-го порядка. Немарковские процессы аппроксимируются марковскими последовательностями путем сохранения главных диагоналей матрицы точности.
Ключевые слова: гауссова марковская последовательность, свойство ( 2k +1)-
диагональности матрицы, матрица точности, последовательности k-го порядка.
Введение. В соответствии с классификацией марковских процессов [1] стационарная гауссова марковская последовательность может быть задана множеством отсчетов
XT = [x1, x2 ,..., xn ] стационарного процесса x (t ) ∈ N (m, R (τ)) , взятых с интервалом дискре-
тизации ∆ ; здесь m — математическое ожидание, R (τ) — функция корреляции. Такая мо-
дель описывает, например, дискретизированный во времени шум на входе радиоэлектронной
системы. Марковские последовательности в общем случае характеризуются условными
функциями распределения и плотностями распределения переходов [1]. Для нормального
распределения значений отсчетов можно получить другое описание марковских последова-
тельностей, позволяющее рассчитывать условные корреляционные матрицы и генерировать
марковские последовательности на компьютере.
Марковская последовательность k-го порядка (сложная последовательность [1]) опреде-
ляется условной плотностью распределения
( ) ( )f xp+1,..., xn | x1,..., xp = f xp+1,..., xn | xp−k+1,..., xp ,
(1)
т.е. зависимостью от k предыдущих значений.
Общими для гауссовых последовательностей, в том числе марковских, являются соот-
ношения для n-мерного нормального распределения [2]: разделению n ×1 -вектора отсчетов
X ∈ N (M, B) на X1T = [ x1...xk ] и XT2 = [xk+1...xn ] соответствует разбиение корреляционной
матрицы B на блоки:
B
=
⎡ B11 ⎢⎣B21
B12 B22
⎤ ⎥ ⎦
,
(2)
где B11, B22 — корреляционные матрицы первых k и последних n − k отсчетов.
Вектор математических ожиданий M | X1 и корреляционная матрица BC = B | X1 услов-
ной плотности распределения f ( X2 | X1 ) определяются как
M | X1 = M2 + C( X1 − M1 ) ;
(3)
BC = B | X1 = B22 − CB12 ;
C = B21B1−11,
а математические ожидания MT = ⎣⎡M1T ; MT2 ⎤⎦ = [m1,..., mk ; mk+1,..., mn ] .
(4)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 1
24 С. Н. Воробьев, Н. В. Гирина, Л. А. Осипов
Гауссовы марковские последовательности первого порядка. Корреляционная матрица B последовательности X , полученной дискретизацией стационарного марковского процесса первого порядка, имеет вид [3]
⎡ 1 b b2 ... bn−1 ⎤
⎢ ⎢b
1
b
...
bn−2
⎥ ⎥
B
=
σ2
⎢ ⎢
b2
b
1
...
b
n−3
⎥ ⎥
,
⎢ ⎢
...
... ... ...
...
⎥ ⎥
⎢⎣bn−1 ... b2 b 1 ⎥⎦
(5)
где b = k (∆) — коэффициент корреляции между соседними значениями матрицы, σ2 —
дисперсия. Действительно, если матрицу (5) подвергнуть согласно уравнению (1) такому разбие-
нию, что B22 = b22 = σ2 (с выделением последних строки и столбца), то нетрудно увидеть, что матрица, обратная блоку B11, трехдиагональна:
⎡ 1 −b 0
0 ... 0 ⎤
⎢⎢−b 1 + b2 −b
0
...
0
⎥ ⎥
B1−11
=
σ−2 1− b2
⎢ ⎢ ⎢ ⎢
0 0
−b 1 + b2
−b
...
0
⎥ ⎥
;
0
−b
1+ b2
−b
0
⎥ ⎥
⎢ ... ... ... ... ... ...⎥
⎢ ⎣
0
0
...
0
−b
1
⎥ ⎦
(6)
блок B21 = σ2[bn−1 bn−2 ... b], так что вектор (4), определяющий условное математическое ожидание (3),
C = B21 B1−11 = [0 0 ... 0 b]
имеет один последний ненулевой элемент, равный b , а предыдущие n − 2 элемента равны нулю.
Зависимость условного математического ожидания от одного последнего предыдущего
значения характеризует одну из особенностей марковского процесса первого порядка [1].
Рассмотрим частный случай: b = e−α ∆ — марковский гауссов процесс с экспоненциальной функцией корреляции (первая теорема Дж. Дуба [1]).
Для двух последних значений xn−1 , xn при фиксированных x1,..., xn−2 блоки
матрица (4)
B21
=
σ2
⎡bn−2
⎢ ⎣⎢
bn−1
bn−3 bn−2
... ...
b b2
⎤ ⎥ ⎥⎦
,
B12
=
BT21 ,
B22
=
⎡σ2 ⎢ ⎣⎢ b
b σ2
⎤ ⎥ ⎥⎦
,
C
=
⎡0 ⎣⎢0
0 0
... ...
0 0
b⎤
b2
⎥ ⎦
также определяет зависимость вектора условных математических ожиданий (3) от одного по-
следнего фиксированного xn−2 . При фиксированных первых k значениях последовательно-
сти (n − k ) × k -матрица C для последующих n − k значений равна
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 1
Гауссовы марковские последовательности
25
⎡ 0 0 ... 0 b ⎤
C
=
⎢ ⎢
0
⎢...
0 ...
... ...
0 ...
b2 ...
⎥
⎥ ⎥
.
⎢⎥
⎢⎣ 0 0 ... 0 bn−k ⎥⎦
(7)
Матрица (7) по сути является матрицей связи наблюдаемых значений с предыдущими.
Фундаментальное свойство марковских последовательностей заключается в том, что
любая подпоследовательность является марковской [1]. Следовательно, блок B11, так же как
матрица B , есть корреляционная матрица марковской последовательности первого порядка
(укороченной по сравнению с исходной). Таким образом, марковская последовательность
может описываться обратной матрицей D = B−1 (матрицей точности [2]) вида (6), как и кор-
реляционной матрицей. Однако матрица точности марковской последовательности первого
порядка имеет характерную форму — она трехдиагональна. Переход от описания последова-
тельности корреляционной матрицей к описанию матрицей точности позволяет сформулиро-
вать необходимый признак принадлежности стационарной гауссовой последовательности
классу марковских первого порядка [3]: трехдиагональность матрицы точности D .
Если матрицы B и D разбиты на блоки
B
=
⎡ B11 ⎢⎢⎣B21
B12 ⎤
σ2n
⎥ ⎥⎦
,
D
=
⎡ D11 ⎣⎢D21
D12 d22
⎤ ⎥ ⎦
,
соответствующие условной плотности f ( xn | x1,..., xn−1 ) , их произведение (единичная мат-
рица) равно
BD
=
I
=
⎡B11D11 + B12D21
⎢ ⎢⎣
B21D11
+
σn2
D21
B11D12 + B12d22 B21D12 + σn2 d22
⎤ ⎥ ⎦⎥
=
⎡ I11 ⎣⎢I21
I12 1
⎤ ⎥ ⎦
,
(8)
где I21, I12 — строка и столбец нулей, I11 — единичная (n −1) -матрица, d22 — последний
элемент матрицы точности. Матрица связи C = B21B1−11, так что B21 = CB11 ; условная дисперсия σ2nC = σn2 | x1,..., xn−1 = σ2n − CB12 ,
так что CB12 = σn2 − σ2nC . В матричном уравнении (8) одно из соотношений B11D11 + B12D21 = I определяет равенство B11D11 = I − B12D21. Другое соотношение, таким образом, записывается как
B21D11 + σn2D21 = CB11D11 + σn2D21 = C (I − B12D21 ) + σn2D =
( )= C − σ2n − σ2nC D21 + σ2nD21 = C + σ2nCD21 = 0 ,
т.е. матрица
C = −σn2CD21 = [0 ... 0 a]
характеризует отличие от нуля одного последнего элемента в векторе связи, определяющее первый порядок последовательности. Так как вектор D21 подобен вектору C при трехдиагональной матрице точности, свойство ее трехдиагональности является также достаточным признаком первого порядка марковской последовательности.
Свойство трехдиагональности распространяется на нестационарные последовательности, корреляционная матрица которых имеет вид
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 1
26 С. Н. Воробьев, Н. В. Гирина, Л. А. Осипов
⎡ ⎢
σ12
⎢ bσ2σ1
B
=
⎢ ⎢
b2 σ3 σ1
⎢ ⎢
...
⎣⎢bn −1σn σ1
bσ1σ2 σ22
bσ3σ2 ...
...
b2σ1σ3 bσ2 σ3
σ32 ...
...
... ... ... ... bσn σn −1
bn−1σ1σn bn−2σ2σn
⎤ ⎥ ⎥
bn−3σ3σn
⎥ ⎥
,
σi
≠
σj,
...
⎥ ⎥
σ2n ⎥⎦
а матрица точности, подобно матрице (6), трехдиагональна с элементами главной диагонали
{ ( ) ( ) } ( )σ1−2 1 + b2 σ−22 ... 1+ b2 σ−n−21 σ−n2 1 − b2 и элементами следующих диагоналей
( )dij = −bσi−1σ−j1 1 − b2 , где i, j — номера строк и столбцов.
Например, пусть корреляционная матрица B стационарной последовательности трансформируется в матрицу Bm последовательности с переменной дисперсией:
⎡ 1 b b2 b3 ⎤
⎡ 1 2b 3b2 4b3 ⎤
⎢
B
=
⎢b ⎢⎢b2
1 b
b 1
b2
⎥ ⎥
b
⎥ ⎥
;
Bm
=
⎢ ⎢ 2b ⎢⎢3b2
4 6b
6b 9
8b2 12b
⎥ ⎥ ⎥ ⎥
,
⎣⎢b3 b2
b
1
⎥ ⎦
⎢⎣4b3
8b2
12b
16
⎥ ⎦
тогда матрица точности трехдиагональна:
⎡1
D
=
1 1− b2
⎢⎢−b / ⎢ ⎢0
2
⎢
⎢⎣ 0
−b / 2
( )1+ b2 / 4
−b / 6
0
0 −b / 6
( )1+ b2 / 9
−b /12
0⎤
0
⎥ ⎥
⎥.
−b /12⎥
⎥
1/16 ⎦⎥
Использование соотношения (8) позволяет получить еще один результат. Из равенства
B21D12 + σn2d22 = 1 следует
σ2
=
1 − B21D12 d22
;
условная дисперсия значения xn равна
σ2nC
=
σ2
− B21B1−11B12
=
1 d22
− B21D12
+ d22B21B1−11B12 d22
.
(9)
Из равенства B11D12 + d22B12 = I12 = 0 следует
D12 = −d22B1−11B12 .
(10)
Подстановка уравнения (10) в формулу (9) дает соотношение для условной дисперсии
σn2C
=
1 d22
−
−d22B21B1−11B12 + d22
d 22 B 21B1−11B12
=
1 d22
,
которая обратна последнему элементу матрицы точности.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 1
Гауссовы марковские последовательности
27
Этот результат справедлив также для нестационарных марковских последовательностей. Так, в предыдущем примере для b = 1/ 2 матрица связи
C = [0 0 2 / 3] , d22 = 1/12 ,
условная дисперсия
σ24C = d2−21 = σ24 − CB12 = 16 − 4 = 12 .
Гауссовы марковские последовательности k-го порядка. Марковская последова-
тельность k-го порядка определяется как последовательность с условной плотностью распре-
деления (1), т.е. последние значения зависят от k предыдущих [1]. Такая зависимость задает
общий вид матрицы связи (4): в ней отличен от нуля хотя бы один элемент каждого из k по-
следних столбцов:
⎡ 0 ... 0
C
=
⎢ ⎢
0
⎢⎢...
... ...
0 ...
c1( p−k +1) c2( p−k +1)
...
... c1p ⎤
... ...
c2 p ...
⎥
⎥ ⎥
.
⎥
⎢ ⎣
0
...
0
c(n− p)( p−k+1)
...
c(n−k
)
p
⎥ ⎦
(11)
Например, при наблюдении семи значений процесса третьего порядка с нулевыми сред-
ними математическое ожидание (3) шестого и седьмого значений равно
Μ[x6 ,
x7
|
x1,...x5 ]
=
CX
=
⎡ c13 x3 ⎢⎣c23 x3
+ c14 x4 + c24 x4
+ +
c15 x5 ⎤
c25
x5
⎥ ⎦
,
так как матрица связи (11) имеет вид
C
=
⎡0 ⎢⎣0
0 0
c13 c23
c14 c24
c15 c25
⎤ ⎥ ⎦
.
При умножении (8) блочных матриц BD = I одна их четырех сумм
B21D12 + B22D22 = I ,
где I — (n − p) × (n − p) -единичная матрица ( p первых значений фиксированы). Отсюда
B22 = D2−21 (I − B21D12 ) ; D2−21 = B22 + D−221B21D12 ,
(12)
следовательно, для матрицы связи и условной корреляционной матрицы имеют место соот-
ношения
C = −D2−21D21 ;
(13)
BC = D2−21 ,
(14)
так как в этом случае условная корреляционная матрица BC = B22 − CB12 и матрица (12) рав-
ны. Таким образом, если элементы l первых столбцов матрицы D21 равны нулю, а элементы
матрицы D2−21 отличны от нуля, матрица (13) имеет вид матрицы D21 : l первых столбцов ну-
левые. Равенство (14) в общем случае справедливо для уравнения (9).
На основе этих результатов в работе [3] формулируется утверждение о том, что матрица
точности марковской последовательности k -го порядка имеет 2k + 1 главных (ненулевых)
диагоналей (остальные элементы матрицы точности равны нулю).
Необходимость ( 2k + 1)-диагональности матрицы точности следует из того, что ее блок
D21 при k < p имеет p − k первых нулевых и k ненулевых столбцов, следовательно, матри-
ца связи имеет вид (11). Например, условно изображенную матрицу точности (звездочками
обозначены ненулевые элементы) с семью диагоналями можно разбить на блоки следующим
образом:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 1
28 С. Н. Воробьев, Н. В. Гирина, Л. А. Осипов
⎡* * * * 0 0 0⎤
⎢⎢* * * * * 0 0⎥⎥
⎢* D = ⎢⎢*
⎢0
* * *
* * *
* * *
* * *
* * *
0⎥
*
⎥ ⎥
*⎥
,
D21
=
⎡0 ⎢⎣0
0 0
∗ 0
∗ ∗
∗⎤ ∗⎦⎥
.
⎢⎢0
0
*
*
*
*
*
⎥ ⎥
⎣⎢0 0 0 * * * *⎦⎥
Произведение (13) преобразуется к матрице связи двух значений с пятью предыдущими
марковской последовательности третьего порядка:
C
=
⎡0 ⎣⎢0
0 0
∗ ∗
∗ ∗
∗⎤ ∗⎥⎦
.
Матрица связи (13) C = −D2−21D21 = −BCD21 , условная корреляционная матрица BC — положительно-определенная: det BC > 0 . Пусть элементы первого столбца матрицы C равны нулю (фиксированы первые p из n значений последовательности k -го порядка, rij — эле-
менты матрицы −BC ):
r( r(
p+1)( p+1)d( p+1)1 p+2)( p+1)d( p+1)1
+ +
rr((pp++12)()(pp++22))dd((pp++22)1)1++......++r(r(pp++1)2n)nddn1n1==c1c121==0;0;⎪⎫⎪
.....................................................................................
⎬ ⎪
rn( p+1)d( p+1)1 + rn( p+2)d( p+2)1 + ... + rnndn1 = c(n−k )1 = 0.
⎪ ⎭
(15)
При заданных rij система (15) представляет собой систему однородных линейных урав-
нений относительно dl1, l = n − p . Определитель BC не равен нулю, следовательно, система (15) имеет нулевое решение. Система уравнений вида (15) существует для второго, третьего и последующих столбцов матрицы связи, если столбец равен нулю. Таким образом, столбец матрицы (11) равен нулю только в том случае, если равен нулю соответствующий столбец матрицы D21 , что определяет достаточность условия ( 2k + 1)-диагональности матрицы точности.
Понятие ( 2k + 1)-диагональности матрицы точности распространяется на случай, когда диагонали с первой по ( k −1)-ю нулевые: порядок гауссовой марковской последовательности определяется номером k последних ненулевых диагоналей (главная диагональ имеет номер k = 0 ).
Пример 1. Отсчеты процесса с функцией корреляции R (τ) = e− τ cos πτ , взятые с ин-
тервалом ∆ = 0,5 , образуют марковскую последовательность второго порядка. Действитель-
но, n = 6 осчетов описываются пятидиагональной матрицей точности
⎡1,1565
⎢ ⎢
0
D
=
⎢0, ⎢ ⎢
4255 0
⎢0
⎢ ⎣
0
0 1,1565
0 0, 4255
0 0
0, 4255 0
1, 3130 0
0, 4255 0
0 0, 4255
0 1, 3130
0 0, 4255
0 0 0, 4255 0 1,1565 0
0⎤
0
⎥ ⎥
0,
0⎥ 4255⎥⎥
;
0⎥
1,1565
⎥ ⎦
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 1
Гауссовы марковские последовательности
29
при фиксировании первых трех значений последовательности матрица связи и условная корреляционная матрица определяются как
⎡0 C = ⎢⎢0
⎣⎢0
−0, 3679 0
0,1353
0⎤
⎡ 0,8647
−0, 3679⎥⎥
,
BC
=
⎢ ⎢
0
0 ⎥⎦
⎣⎢ −0, 3181
0 0, 8647
0
0, 3181⎤
0
⎥ ⎥
.
0, 9817 ⎥⎦
Условные математические ожидания равны
m4c = m4 − 0,3679x2 , m5c = m5 − 0, 3679x3 , m6c = m6 + 0,1353x4 .
Этот результат обусловлен корреляционными свойствами последовательности. Анализ четырех составляющих блочного произведения BD = I приводит также к смешанным соотношениям для матрицы связи
C = −B22D21D1−11B1−11 = −B22D21 (I − )B12D21 −1
и вектору связи последнего значения xn при фиксированных предыдущих [3]:
C
=
−
D21 dnn
=
−
1 dnn
⎣⎡0
...
0
d p−k+1
...
d p ⎦⎤ , D22 = dnn .
Аппроксимация немарковского гауссова процесса марковской последовательностью. Марковское приближение отсчетов X немарковского гауссова процесса с корреляционной матрицей BX реализуется приведением его матрицы точности DX к многодиагональному виду D путем замены нулями всех элементов за исключением элементов 2k + 1 главных диагоналей. Матрица D при условии положительной определенности матрицы B = D−1 есть матрица точности марковской последовательности k -го порядка (в общем случае нестационарной). Если обнуляются элементы dij ≈ 0 , можно ожидать, что погрешность такого пред-
ставления невелика, т.е. B ≈ B X . На основе корреляционной матрицы B можно построить программу-генератор марковской последовательности X′ , близкой к последовательности X по корреляционным свойствам. Условные матрицы (13) и (14) позволяют генерировать траектории X′ точка за точкой, парами, триадами точек и т. д. [3].
Пример 2. Рассмотрим матрицы D1, D2 точности отсчетов X1 и X2 процессов с функ-
циями корреляции R1 (τ) = 0, 5e− τ + 0, 5e−2 τ ; R2 (τ) = 2e− τ − e−2 τ ; ∆ = 0,5 , n = 5 :
⎡ 1,3118 ⎢⎢−0, 6269 D1 = ⎢−0, 0186 ⎢⎢−0, 0093 ⎢⎣−0, 0060
−0, 6269 1, 6114 −0, 6181 −0, 0142 −0, 0093
−0, 0186 −0, 6181 1, 6116 −0, 6181 −0, 0186
−0, 0093 −0, 0142 −0, 6181 1, 6114 −0, 6269
−0, 0060⎤ −0, 0093⎥⎥ −0, 0186⎥ , −0, 6269⎥⎥ 1,3118 ⎥⎦
⎡ 4, 2057
⎢⎢ −5,1474
D2
=
⎢ 2, 2201 ⎢⎢−0, 5406
⎣⎢ 0,1034
−5,1474 10, 5031 −7, 8513 2, 8272 −0, 5406
2, 2201 −7, 8513 11, 6055 −7, 8513 2, 2201
−0, 5406 2, 8272 −7, 8513 10, 5031 −5,1474
0,1034 ⎤
−0, 5406⎥⎥
2, 2201 ⎥ .
−5,1474
⎥ ⎥
4, 2057 ⎦⎥
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 1
30 С. Н. Воробьев, Н. В. Гирина, Л. А. Осипов
Элементы d15 , d14 , d13 , d24 , d25 , d35 матрицы D1 по абсолютной величине значительно меньше предыдущих, следовательно, можно, обнуляя их и оставляя пять или три ненуле-
вые диагонали, аппроксимировать X1 марковской последовательностью второго или первого порядка. Результаты аппроксимации показаны в таблице и на рисунке, а, где кривая 1 соответствует функции корреляции исходной немарковской последовательности (в таблице — R ), кривые 2 и 3 — функции корреляции аппроксимирующих последовательностей второго и первого порядков (в таблице — R2 и R1 ).
R 1,0000 0,4872
R2 0,9962 0,4822 R1 0,9857 0,4674
0,2516 0,2438 0,2188
0,1365 0,1218 0,1031
0,0768 0,0616 0,0493
Нестационарность аппроксимирующей последовательности первого порядка проиллюстрирована ниже, где представлены диагональные элементы корреляционной матрицы.
а) R
diag(B1)
0,9857
0,9780
0,9717 б) R
0,9780 0,9857
11
0,8 0,8
0,6 0,6
0,4
3 0,2 1
2
0,4 0,2
2 3
1
0
0,5 1
1,5 t
0
1 2t
Применение процедуры обнуления элементов к матрице D2 приводит к неудовлетвори-
тельным результатам: аппроксимация X2 последовательностью третьего порядка сопровождается заметными погрешностями воспроизведения корреляционных свойств (рисунок, б, кривая 2). Если увеличить протяженность X2 до n = 7 , то удовлетворительной становится аппроксимация последовательностью четвертого порядка (см. рисунок, б, кривая 3).
СПИСОК ЛИТЕРАТУРЫ
1. Тихонов В. И., Миронов М. А. Марковские процессы. М.: Сов. радио, 1977. 488 с.
2. Королюк В. С. и др. Справочник по теории вероятностей и математической статистике. М.: Наука, 1985. 640 с.
3. Осипов Л. А., Воробьева Ю. Г. Генерирование гауссовых марковских последовательностей // Информационно-управляющие системы. 2006. № 4 (23). С. 4—9.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 1
Гауссовы марковские последовательности
31
Сведения об авторах
Станислав Николаевич Воробьев — канд. техн. наук, доцент; Санкт-Петербургский государственный уни-
верситет аэрокосмического приборостроения, кафедра информацион-
но-сетевых технологий
Наталья Владимировна Гирина — аспирант; Санкт-Петербургский государственный университет аэро-
космического приборостроения, кафедра информационно-сетевых
технологий; E-mail: natalia.girina@gmail.com
Леонид Андроникович Осипов
— д-р техн. наук, профессор; Санкт-Петербургский государственный
университет аэрокосмического приборостроения, кафедра информа-
ционно-сетевых технологий
Рекомендована кафедрой информационно-сетевых технологий
Поступила в редакцию 15.10.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 1
23
УДК 519.2
С. Н. ВОРОБЬЕВ, Н. В. ГИРИНА, Л. А. ОСИПОВ
ГАУССОВЫ МАРКОВСКИЕ ПОСЛЕДОВАТЕЛЬНОСТИ
Устанавливается свойство ( 2k +1)-диагональности матрицы точности гауссовой
марковской последовательности k-го порядка. Немарковские процессы аппроксимируются марковскими последовательностями путем сохранения главных диагоналей матрицы точности.
Ключевые слова: гауссова марковская последовательность, свойство ( 2k +1)-
диагональности матрицы, матрица точности, последовательности k-го порядка.
Введение. В соответствии с классификацией марковских процессов [1] стационарная гауссова марковская последовательность может быть задана множеством отсчетов
XT = [x1, x2 ,..., xn ] стационарного процесса x (t ) ∈ N (m, R (τ)) , взятых с интервалом дискре-
тизации ∆ ; здесь m — математическое ожидание, R (τ) — функция корреляции. Такая мо-
дель описывает, например, дискретизированный во времени шум на входе радиоэлектронной
системы. Марковские последовательности в общем случае характеризуются условными
функциями распределения и плотностями распределения переходов [1]. Для нормального
распределения значений отсчетов можно получить другое описание марковских последова-
тельностей, позволяющее рассчитывать условные корреляционные матрицы и генерировать
марковские последовательности на компьютере.
Марковская последовательность k-го порядка (сложная последовательность [1]) опреде-
ляется условной плотностью распределения
( ) ( )f xp+1,..., xn | x1,..., xp = f xp+1,..., xn | xp−k+1,..., xp ,
(1)
т.е. зависимостью от k предыдущих значений.
Общими для гауссовых последовательностей, в том числе марковских, являются соот-
ношения для n-мерного нормального распределения [2]: разделению n ×1 -вектора отсчетов
X ∈ N (M, B) на X1T = [ x1...xk ] и XT2 = [xk+1...xn ] соответствует разбиение корреляционной
матрицы B на блоки:
B
=
⎡ B11 ⎢⎣B21
B12 B22
⎤ ⎥ ⎦
,
(2)
где B11, B22 — корреляционные матрицы первых k и последних n − k отсчетов.
Вектор математических ожиданий M | X1 и корреляционная матрица BC = B | X1 услов-
ной плотности распределения f ( X2 | X1 ) определяются как
M | X1 = M2 + C( X1 − M1 ) ;
(3)
BC = B | X1 = B22 − CB12 ;
C = B21B1−11,
а математические ожидания MT = ⎣⎡M1T ; MT2 ⎤⎦ = [m1,..., mk ; mk+1,..., mn ] .
(4)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 1
24 С. Н. Воробьев, Н. В. Гирина, Л. А. Осипов
Гауссовы марковские последовательности первого порядка. Корреляционная матрица B последовательности X , полученной дискретизацией стационарного марковского процесса первого порядка, имеет вид [3]
⎡ 1 b b2 ... bn−1 ⎤
⎢ ⎢b
1
b
...
bn−2
⎥ ⎥
B
=
σ2
⎢ ⎢
b2
b
1
...
b
n−3
⎥ ⎥
,
⎢ ⎢
...
... ... ...
...
⎥ ⎥
⎢⎣bn−1 ... b2 b 1 ⎥⎦
(5)
где b = k (∆) — коэффициент корреляции между соседними значениями матрицы, σ2 —
дисперсия. Действительно, если матрицу (5) подвергнуть согласно уравнению (1) такому разбие-
нию, что B22 = b22 = σ2 (с выделением последних строки и столбца), то нетрудно увидеть, что матрица, обратная блоку B11, трехдиагональна:
⎡ 1 −b 0
0 ... 0 ⎤
⎢⎢−b 1 + b2 −b
0
...
0
⎥ ⎥
B1−11
=
σ−2 1− b2
⎢ ⎢ ⎢ ⎢
0 0
−b 1 + b2
−b
...
0
⎥ ⎥
;
0
−b
1+ b2
−b
0
⎥ ⎥
⎢ ... ... ... ... ... ...⎥
⎢ ⎣
0
0
...
0
−b
1
⎥ ⎦
(6)
блок B21 = σ2[bn−1 bn−2 ... b], так что вектор (4), определяющий условное математическое ожидание (3),
C = B21 B1−11 = [0 0 ... 0 b]
имеет один последний ненулевой элемент, равный b , а предыдущие n − 2 элемента равны нулю.
Зависимость условного математического ожидания от одного последнего предыдущего
значения характеризует одну из особенностей марковского процесса первого порядка [1].
Рассмотрим частный случай: b = e−α ∆ — марковский гауссов процесс с экспоненциальной функцией корреляции (первая теорема Дж. Дуба [1]).
Для двух последних значений xn−1 , xn при фиксированных x1,..., xn−2 блоки
матрица (4)
B21
=
σ2
⎡bn−2
⎢ ⎣⎢
bn−1
bn−3 bn−2
... ...
b b2
⎤ ⎥ ⎥⎦
,
B12
=
BT21 ,
B22
=
⎡σ2 ⎢ ⎣⎢ b
b σ2
⎤ ⎥ ⎥⎦
,
C
=
⎡0 ⎣⎢0
0 0
... ...
0 0
b⎤
b2
⎥ ⎦
также определяет зависимость вектора условных математических ожиданий (3) от одного по-
следнего фиксированного xn−2 . При фиксированных первых k значениях последовательно-
сти (n − k ) × k -матрица C для последующих n − k значений равна
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 1
Гауссовы марковские последовательности
25
⎡ 0 0 ... 0 b ⎤
C
=
⎢ ⎢
0
⎢...
0 ...
... ...
0 ...
b2 ...
⎥
⎥ ⎥
.
⎢⎥
⎢⎣ 0 0 ... 0 bn−k ⎥⎦
(7)
Матрица (7) по сути является матрицей связи наблюдаемых значений с предыдущими.
Фундаментальное свойство марковских последовательностей заключается в том, что
любая подпоследовательность является марковской [1]. Следовательно, блок B11, так же как
матрица B , есть корреляционная матрица марковской последовательности первого порядка
(укороченной по сравнению с исходной). Таким образом, марковская последовательность
может описываться обратной матрицей D = B−1 (матрицей точности [2]) вида (6), как и кор-
реляционной матрицей. Однако матрица точности марковской последовательности первого
порядка имеет характерную форму — она трехдиагональна. Переход от описания последова-
тельности корреляционной матрицей к описанию матрицей точности позволяет сформулиро-
вать необходимый признак принадлежности стационарной гауссовой последовательности
классу марковских первого порядка [3]: трехдиагональность матрицы точности D .
Если матрицы B и D разбиты на блоки
B
=
⎡ B11 ⎢⎢⎣B21
B12 ⎤
σ2n
⎥ ⎥⎦
,
D
=
⎡ D11 ⎣⎢D21
D12 d22
⎤ ⎥ ⎦
,
соответствующие условной плотности f ( xn | x1,..., xn−1 ) , их произведение (единичная мат-
рица) равно
BD
=
I
=
⎡B11D11 + B12D21
⎢ ⎢⎣
B21D11
+
σn2
D21
B11D12 + B12d22 B21D12 + σn2 d22
⎤ ⎥ ⎦⎥
=
⎡ I11 ⎣⎢I21
I12 1
⎤ ⎥ ⎦
,
(8)
где I21, I12 — строка и столбец нулей, I11 — единичная (n −1) -матрица, d22 — последний
элемент матрицы точности. Матрица связи C = B21B1−11, так что B21 = CB11 ; условная дисперсия σ2nC = σn2 | x1,..., xn−1 = σ2n − CB12 ,
так что CB12 = σn2 − σ2nC . В матричном уравнении (8) одно из соотношений B11D11 + B12D21 = I определяет равенство B11D11 = I − B12D21. Другое соотношение, таким образом, записывается как
B21D11 + σn2D21 = CB11D11 + σn2D21 = C (I − B12D21 ) + σn2D =
( )= C − σ2n − σ2nC D21 + σ2nD21 = C + σ2nCD21 = 0 ,
т.е. матрица
C = −σn2CD21 = [0 ... 0 a]
характеризует отличие от нуля одного последнего элемента в векторе связи, определяющее первый порядок последовательности. Так как вектор D21 подобен вектору C при трехдиагональной матрице точности, свойство ее трехдиагональности является также достаточным признаком первого порядка марковской последовательности.
Свойство трехдиагональности распространяется на нестационарные последовательности, корреляционная матрица которых имеет вид
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 1
26 С. Н. Воробьев, Н. В. Гирина, Л. А. Осипов
⎡ ⎢
σ12
⎢ bσ2σ1
B
=
⎢ ⎢
b2 σ3 σ1
⎢ ⎢
...
⎣⎢bn −1σn σ1
bσ1σ2 σ22
bσ3σ2 ...
...
b2σ1σ3 bσ2 σ3
σ32 ...
...
... ... ... ... bσn σn −1
bn−1σ1σn bn−2σ2σn
⎤ ⎥ ⎥
bn−3σ3σn
⎥ ⎥
,
σi
≠
σj,
...
⎥ ⎥
σ2n ⎥⎦
а матрица точности, подобно матрице (6), трехдиагональна с элементами главной диагонали
{ ( ) ( ) } ( )σ1−2 1 + b2 σ−22 ... 1+ b2 σ−n−21 σ−n2 1 − b2 и элементами следующих диагоналей
( )dij = −bσi−1σ−j1 1 − b2 , где i, j — номера строк и столбцов.
Например, пусть корреляционная матрица B стационарной последовательности трансформируется в матрицу Bm последовательности с переменной дисперсией:
⎡ 1 b b2 b3 ⎤
⎡ 1 2b 3b2 4b3 ⎤
⎢
B
=
⎢b ⎢⎢b2
1 b
b 1
b2
⎥ ⎥
b
⎥ ⎥
;
Bm
=
⎢ ⎢ 2b ⎢⎢3b2
4 6b
6b 9
8b2 12b
⎥ ⎥ ⎥ ⎥
,
⎣⎢b3 b2
b
1
⎥ ⎦
⎢⎣4b3
8b2
12b
16
⎥ ⎦
тогда матрица точности трехдиагональна:
⎡1
D
=
1 1− b2
⎢⎢−b / ⎢ ⎢0
2
⎢
⎢⎣ 0
−b / 2
( )1+ b2 / 4
−b / 6
0
0 −b / 6
( )1+ b2 / 9
−b /12
0⎤
0
⎥ ⎥
⎥.
−b /12⎥
⎥
1/16 ⎦⎥
Использование соотношения (8) позволяет получить еще один результат. Из равенства
B21D12 + σn2d22 = 1 следует
σ2
=
1 − B21D12 d22
;
условная дисперсия значения xn равна
σ2nC
=
σ2
− B21B1−11B12
=
1 d22
− B21D12
+ d22B21B1−11B12 d22
.
(9)
Из равенства B11D12 + d22B12 = I12 = 0 следует
D12 = −d22B1−11B12 .
(10)
Подстановка уравнения (10) в формулу (9) дает соотношение для условной дисперсии
σn2C
=
1 d22
−
−d22B21B1−11B12 + d22
d 22 B 21B1−11B12
=
1 d22
,
которая обратна последнему элементу матрицы точности.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 1
Гауссовы марковские последовательности
27
Этот результат справедлив также для нестационарных марковских последовательностей. Так, в предыдущем примере для b = 1/ 2 матрица связи
C = [0 0 2 / 3] , d22 = 1/12 ,
условная дисперсия
σ24C = d2−21 = σ24 − CB12 = 16 − 4 = 12 .
Гауссовы марковские последовательности k-го порядка. Марковская последова-
тельность k-го порядка определяется как последовательность с условной плотностью распре-
деления (1), т.е. последние значения зависят от k предыдущих [1]. Такая зависимость задает
общий вид матрицы связи (4): в ней отличен от нуля хотя бы один элемент каждого из k по-
следних столбцов:
⎡ 0 ... 0
C
=
⎢ ⎢
0
⎢⎢...
... ...
0 ...
c1( p−k +1) c2( p−k +1)
...
... c1p ⎤
... ...
c2 p ...
⎥
⎥ ⎥
.
⎥
⎢ ⎣
0
...
0
c(n− p)( p−k+1)
...
c(n−k
)
p
⎥ ⎦
(11)
Например, при наблюдении семи значений процесса третьего порядка с нулевыми сред-
ними математическое ожидание (3) шестого и седьмого значений равно
Μ[x6 ,
x7
|
x1,...x5 ]
=
CX
=
⎡ c13 x3 ⎢⎣c23 x3
+ c14 x4 + c24 x4
+ +
c15 x5 ⎤
c25
x5
⎥ ⎦
,
так как матрица связи (11) имеет вид
C
=
⎡0 ⎢⎣0
0 0
c13 c23
c14 c24
c15 c25
⎤ ⎥ ⎦
.
При умножении (8) блочных матриц BD = I одна их четырех сумм
B21D12 + B22D22 = I ,
где I — (n − p) × (n − p) -единичная матрица ( p первых значений фиксированы). Отсюда
B22 = D2−21 (I − B21D12 ) ; D2−21 = B22 + D−221B21D12 ,
(12)
следовательно, для матрицы связи и условной корреляционной матрицы имеют место соот-
ношения
C = −D2−21D21 ;
(13)
BC = D2−21 ,
(14)
так как в этом случае условная корреляционная матрица BC = B22 − CB12 и матрица (12) рав-
ны. Таким образом, если элементы l первых столбцов матрицы D21 равны нулю, а элементы
матрицы D2−21 отличны от нуля, матрица (13) имеет вид матрицы D21 : l первых столбцов ну-
левые. Равенство (14) в общем случае справедливо для уравнения (9).
На основе этих результатов в работе [3] формулируется утверждение о том, что матрица
точности марковской последовательности k -го порядка имеет 2k + 1 главных (ненулевых)
диагоналей (остальные элементы матрицы точности равны нулю).
Необходимость ( 2k + 1)-диагональности матрицы точности следует из того, что ее блок
D21 при k < p имеет p − k первых нулевых и k ненулевых столбцов, следовательно, матри-
ца связи имеет вид (11). Например, условно изображенную матрицу точности (звездочками
обозначены ненулевые элементы) с семью диагоналями можно разбить на блоки следующим
образом:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 1
28 С. Н. Воробьев, Н. В. Гирина, Л. А. Осипов
⎡* * * * 0 0 0⎤
⎢⎢* * * * * 0 0⎥⎥
⎢* D = ⎢⎢*
⎢0
* * *
* * *
* * *
* * *
* * *
0⎥
*
⎥ ⎥
*⎥
,
D21
=
⎡0 ⎢⎣0
0 0
∗ 0
∗ ∗
∗⎤ ∗⎦⎥
.
⎢⎢0
0
*
*
*
*
*
⎥ ⎥
⎣⎢0 0 0 * * * *⎦⎥
Произведение (13) преобразуется к матрице связи двух значений с пятью предыдущими
марковской последовательности третьего порядка:
C
=
⎡0 ⎣⎢0
0 0
∗ ∗
∗ ∗
∗⎤ ∗⎥⎦
.
Матрица связи (13) C = −D2−21D21 = −BCD21 , условная корреляционная матрица BC — положительно-определенная: det BC > 0 . Пусть элементы первого столбца матрицы C равны нулю (фиксированы первые p из n значений последовательности k -го порядка, rij — эле-
менты матрицы −BC ):
r( r(
p+1)( p+1)d( p+1)1 p+2)( p+1)d( p+1)1
+ +
rr((pp++12)()(pp++22))dd((pp++22)1)1++......++r(r(pp++1)2n)nddn1n1==c1c121==0;0;⎪⎫⎪
.....................................................................................
⎬ ⎪
rn( p+1)d( p+1)1 + rn( p+2)d( p+2)1 + ... + rnndn1 = c(n−k )1 = 0.
⎪ ⎭
(15)
При заданных rij система (15) представляет собой систему однородных линейных урав-
нений относительно dl1, l = n − p . Определитель BC не равен нулю, следовательно, система (15) имеет нулевое решение. Система уравнений вида (15) существует для второго, третьего и последующих столбцов матрицы связи, если столбец равен нулю. Таким образом, столбец матрицы (11) равен нулю только в том случае, если равен нулю соответствующий столбец матрицы D21 , что определяет достаточность условия ( 2k + 1)-диагональности матрицы точности.
Понятие ( 2k + 1)-диагональности матрицы точности распространяется на случай, когда диагонали с первой по ( k −1)-ю нулевые: порядок гауссовой марковской последовательности определяется номером k последних ненулевых диагоналей (главная диагональ имеет номер k = 0 ).
Пример 1. Отсчеты процесса с функцией корреляции R (τ) = e− τ cos πτ , взятые с ин-
тервалом ∆ = 0,5 , образуют марковскую последовательность второго порядка. Действитель-
но, n = 6 осчетов описываются пятидиагональной матрицей точности
⎡1,1565
⎢ ⎢
0
D
=
⎢0, ⎢ ⎢
4255 0
⎢0
⎢ ⎣
0
0 1,1565
0 0, 4255
0 0
0, 4255 0
1, 3130 0
0, 4255 0
0 0, 4255
0 1, 3130
0 0, 4255
0 0 0, 4255 0 1,1565 0
0⎤
0
⎥ ⎥
0,
0⎥ 4255⎥⎥
;
0⎥
1,1565
⎥ ⎦
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 1
Гауссовы марковские последовательности
29
при фиксировании первых трех значений последовательности матрица связи и условная корреляционная матрица определяются как
⎡0 C = ⎢⎢0
⎣⎢0
−0, 3679 0
0,1353
0⎤
⎡ 0,8647
−0, 3679⎥⎥
,
BC
=
⎢ ⎢
0
0 ⎥⎦
⎣⎢ −0, 3181
0 0, 8647
0
0, 3181⎤
0
⎥ ⎥
.
0, 9817 ⎥⎦
Условные математические ожидания равны
m4c = m4 − 0,3679x2 , m5c = m5 − 0, 3679x3 , m6c = m6 + 0,1353x4 .
Этот результат обусловлен корреляционными свойствами последовательности. Анализ четырех составляющих блочного произведения BD = I приводит также к смешанным соотношениям для матрицы связи
C = −B22D21D1−11B1−11 = −B22D21 (I − )B12D21 −1
и вектору связи последнего значения xn при фиксированных предыдущих [3]:
C
=
−
D21 dnn
=
−
1 dnn
⎣⎡0
...
0
d p−k+1
...
d p ⎦⎤ , D22 = dnn .
Аппроксимация немарковского гауссова процесса марковской последовательностью. Марковское приближение отсчетов X немарковского гауссова процесса с корреляционной матрицей BX реализуется приведением его матрицы точности DX к многодиагональному виду D путем замены нулями всех элементов за исключением элементов 2k + 1 главных диагоналей. Матрица D при условии положительной определенности матрицы B = D−1 есть матрица точности марковской последовательности k -го порядка (в общем случае нестационарной). Если обнуляются элементы dij ≈ 0 , можно ожидать, что погрешность такого пред-
ставления невелика, т.е. B ≈ B X . На основе корреляционной матрицы B можно построить программу-генератор марковской последовательности X′ , близкой к последовательности X по корреляционным свойствам. Условные матрицы (13) и (14) позволяют генерировать траектории X′ точка за точкой, парами, триадами точек и т. д. [3].
Пример 2. Рассмотрим матрицы D1, D2 точности отсчетов X1 и X2 процессов с функ-
циями корреляции R1 (τ) = 0, 5e− τ + 0, 5e−2 τ ; R2 (τ) = 2e− τ − e−2 τ ; ∆ = 0,5 , n = 5 :
⎡ 1,3118 ⎢⎢−0, 6269 D1 = ⎢−0, 0186 ⎢⎢−0, 0093 ⎢⎣−0, 0060
−0, 6269 1, 6114 −0, 6181 −0, 0142 −0, 0093
−0, 0186 −0, 6181 1, 6116 −0, 6181 −0, 0186
−0, 0093 −0, 0142 −0, 6181 1, 6114 −0, 6269
−0, 0060⎤ −0, 0093⎥⎥ −0, 0186⎥ , −0, 6269⎥⎥ 1,3118 ⎥⎦
⎡ 4, 2057
⎢⎢ −5,1474
D2
=
⎢ 2, 2201 ⎢⎢−0, 5406
⎣⎢ 0,1034
−5,1474 10, 5031 −7, 8513 2, 8272 −0, 5406
2, 2201 −7, 8513 11, 6055 −7, 8513 2, 2201
−0, 5406 2, 8272 −7, 8513 10, 5031 −5,1474
0,1034 ⎤
−0, 5406⎥⎥
2, 2201 ⎥ .
−5,1474
⎥ ⎥
4, 2057 ⎦⎥
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 1
30 С. Н. Воробьев, Н. В. Гирина, Л. А. Осипов
Элементы d15 , d14 , d13 , d24 , d25 , d35 матрицы D1 по абсолютной величине значительно меньше предыдущих, следовательно, можно, обнуляя их и оставляя пять или три ненуле-
вые диагонали, аппроксимировать X1 марковской последовательностью второго или первого порядка. Результаты аппроксимации показаны в таблице и на рисунке, а, где кривая 1 соответствует функции корреляции исходной немарковской последовательности (в таблице — R ), кривые 2 и 3 — функции корреляции аппроксимирующих последовательностей второго и первого порядков (в таблице — R2 и R1 ).
R 1,0000 0,4872
R2 0,9962 0,4822 R1 0,9857 0,4674
0,2516 0,2438 0,2188
0,1365 0,1218 0,1031
0,0768 0,0616 0,0493
Нестационарность аппроксимирующей последовательности первого порядка проиллюстрирована ниже, где представлены диагональные элементы корреляционной матрицы.
а) R
diag(B1)
0,9857
0,9780
0,9717 б) R
0,9780 0,9857
11
0,8 0,8
0,6 0,6
0,4
3 0,2 1
2
0,4 0,2
2 3
1
0
0,5 1
1,5 t
0
1 2t
Применение процедуры обнуления элементов к матрице D2 приводит к неудовлетвори-
тельным результатам: аппроксимация X2 последовательностью третьего порядка сопровождается заметными погрешностями воспроизведения корреляционных свойств (рисунок, б, кривая 2). Если увеличить протяженность X2 до n = 7 , то удовлетворительной становится аппроксимация последовательностью четвертого порядка (см. рисунок, б, кривая 3).
СПИСОК ЛИТЕРАТУРЫ
1. Тихонов В. И., Миронов М. А. Марковские процессы. М.: Сов. радио, 1977. 488 с.
2. Королюк В. С. и др. Справочник по теории вероятностей и математической статистике. М.: Наука, 1985. 640 с.
3. Осипов Л. А., Воробьева Ю. Г. Генерирование гауссовых марковских последовательностей // Информационно-управляющие системы. 2006. № 4 (23). С. 4—9.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 1
Гауссовы марковские последовательности
31
Сведения об авторах
Станислав Николаевич Воробьев — канд. техн. наук, доцент; Санкт-Петербургский государственный уни-
верситет аэрокосмического приборостроения, кафедра информацион-
но-сетевых технологий
Наталья Владимировна Гирина — аспирант; Санкт-Петербургский государственный университет аэро-
космического приборостроения, кафедра информационно-сетевых
технологий; E-mail: natalia.girina@gmail.com
Леонид Андроникович Осипов
— д-р техн. наук, профессор; Санкт-Петербургский государственный
университет аэрокосмического приборостроения, кафедра информа-
ционно-сетевых технологий
Рекомендована кафедрой информационно-сетевых технологий
Поступила в редакцию 15.10.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 1