Другие статьи


Операции с матрицами на C++.   Класс DMatrix



 

 

Self-similar processes in communications networks

(Самоподобные процессы в коммуникативных сетях)

 

Boris Tsybakov, Nicolas D. Georganas,  1998

 

 

2.  Самоподобный в широком смысле процесс с дискретным временем.

 

 

 

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

 

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

 

Некоторые основные свойства строго самоподобных процессов уже изучены и описаны; также в недавних работах введены определения строгого (exactly) и абсолютного (strictly) самоподобия. С этими рассуждениями можно познакомиться в [6], [9], [14] и [17] - [20].

 

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

 

Начнем с определения полубесконечного сегмента стационарного в широком смысле действительного стохастического процесса X = (X1 , X2 ,... ) с дискретным аргументом (время) t I1 = {1,2, ...}.

 

Обозначим   m = EXt < ∞ ,  σ2 = var Xt <   ( мат. ожидание и дисперсия Xt соответственно ).

Обозначим   r(k) = [ E(Xt + k - m)(Xt - m) ] / σ 2 , k I0 ={0,1,2,...}  ( коэффициент корреляции Xt ).

Обозначим f(l) спектральную плотность процесса.

Мат. ожидание, дисперсия  и коэффициент корреляции  не зависят от времени t, а r(k) = r(-k).

 

2.1. Строгое самоподобие в широком смысле слова.

 

Далее предложим два определения строгого самоподобия в широком смысле (ССШС). Как будет показано далее (см. Теорему 1), эти определения эквивалентны. Первое определение лучше подходит для доказательства ССШС специфического процесса, а также для обобщения ССШС на асимптотический случай. Второе определение более применимо для понимания свойства берстности самоподобных процессов и для оправдания термина «самоподобие».

 

Определение A.  Процесс X называется строго самоподобным в широком смысле слова (ССШС) с параметром H = 1 - β/2 , 0< β <1, если коэффициент корреляции процесса можно записать в виде:

 

r(k) = 1/2 * [(k +1)2 - β  - 2k2 - β  + (k -1)2- β ] =ˆ g(k), k I1 = {1,2, ...}. (2. 1)

 

 

Функция g(k) может быть записана в виде g(k) = ½ * d2 (k2 - β ), где d2 – оператор центрального двойного взятия разности, примененный к функции f(x) = x2 - β .

(   d(f(x)) = f(x+1/2) - f(x-1/2)   ).

 

 

Прежде чем дать второе определение, введем понятие усредненного (по блокам длины m) процесса X(m) , X(m) = (X(m)1 , X(m)2 , … ) ,

 

X(m)t = 1/m * ( Xtm-m+1 + … + Xtm ) , m, t I1 ;

 

этот процесс имеет коэффициент корреляции rm(k) и дисперсию Vm.

 

Усредненный процесс X(m), как и нормированный процесс X`(m) , который мы введем позднее, играет важную роль в понимании сути самоподобия процесса X.

 

Определение B.  Процесс X называется строго самоподобным в широком смысле слова (ССШС) с параметром H = 1 - β /2 , 0< β <1, если

 

rm(k) = r(k) ,          k I0 ,  m I1  .

 

Прежде, чем дать комментарий, расскажем о наиболее важных свойствах ССШС.

 

Теорема 1.  Для процесса X  и  0 < β < 1  следующие утверждения эквивалентны:

 

(a)       Xпроцесс ССШС в смысле определения A, то есть r(k) = g(k)

 

(b)       Vm =ˆ var X(m)t = σ 2 m- β,   m I2  = {2, 3, …}

 

(c)       f(l) = c | e2pil - 1 |2 ( 1 / | λ + l | 3 - β ) ,  -1/2 <= l <= 1/2

 

(d)       Xпроцесс ССШС в смысле определения B, то есть rm(k) = r(k) ,  k I0 ,  m I1  .

 

Теорема 1 демонстрирует эквивалентность как минимум двух определений, а также тот факт, что у процесса X с автокорреляционной функцией r(k) = g(k) не меняются основные численные характеристики, корреляция и спектральная функция, при усреднении по блокам некоторой длины m. Поэтому X и называется самоподобным. (То, что из (d) следует (a), утверждал Cox, см. [6], но без доказательства; поэтому мы докажем этот факт в конце данного подраздела.) Значимость функции g(k) состоит в том, что она дает невырождающуюся корреляционную структуру при сколь угодно масштабном усреднении процесса.

 

Так как g(k) ~ ½ (2 - β)(1 - b)k- β  = H(2H - 1)k- β , k , то процесс ССШС имеет автоковариационную функцию с тяжелым хвостом, причем  r(k) = ∞. (Здесь и далее запись f (x ) ~ h(x) означает [ f (x) / h(x)]1 при x .)  Это говорит о принадлежности процессов ССШС к процессам с медленно убывающей зависимостью (МУЗ), так как процессы с МУЗ были определены (см. [1], [6]) как процессы, у которых r(k) ~ ck- β ,  0 < β < 1 ,  c – константа. Таким образом, ССШС – процесс с МУЗ.

 

Какова роль параметра β  ?  Во-первых, β > 1 означает, что X – процесс с быстро убывающей зависимостью (БУЗ), у такого процесса Vm ~ cm-1 при m ; тогда как 0 < β < 1 означает, X – процесс с МУЗ. Во-вторых, при 0 < β < 1 величина β показывает уровень убывания зависимости.

 

Наряду со строго самоподобными в широком смысле (ССШС) процессами рассмотрим более известные самоподобные в узком смысле слова процессы. Дадим определение и сравним эти типы процессов.

 

Определение.  Стационарный в узком смысле процесс X = (X1, X2, … ) называется самоподобным в узком смысле (СУС) с параметром H = 1 - β /2,   0 < β < 1 , если

 

m1-H X(m) =dis X      

 

или, что эквивалентно,   X`(m) =dis X ,  

 

где X` = (X`1, X`2, … ),     X`(m)t = 1/mH  * ( Xtm-m+1 + … + Xtm ) ;

 

знак =dis означает равенство в смысле конечномерных распределений.

 

 

Проведем сравнение ССШС и СУС в терминах следующих соотношений:

 

[rm(k) = r` m(k) = r(k)]  <=  [X`(m) =dis X]  =>  [var X`(m)t = σ 2 =^ var X t] ,       (2.2)

 

[rm(k) = r` m(k) = r(k)]  <=  [var X`(m)t = σ 2  <=>  [r(k) = g(k)]  <=>  [var X(m)t = σ 2m]   ,     (2.3)

 

 

где r`m(k) – корреляционный коэффициент нормализованного процесса X`(m) и соотношения (2.2) и (2.3) верны для всех r, m I1  . (Имеется в виду, что случай m = 1 – тривиальный; случай k = 0 – не рассматривается, т.к. rm(0) = r`m(0) = r(0) = 1, а g(0) – не определена.)

 

 

 

Эти соотношения показывают, что процесс СУС имеет r(k) = g(k). Это, в частности, означает, что процесс СУС является процессом ССШС; обратное утверждение - неверно. Однако, если X – гауссовский ССШС и EXt = 0, то он является процессом СУС. Верны следующие логические цепочки для гауссовского процесса с EXt = 0:

 

[X – гауссовский с нулевым средним и СУС]  =>  { [rm(k) = r`m(k) = r(k)=g(k)] , [var X`(m)t = σ 2] , [var X(m)t = σ 2m-β]  } ,                  (2.4)

 

[X – гауссовский с нулевым средним и r(k) = g(k)]  =>  { [???] , [rm(k) = r`m(k) = r(k)=g(k)] , [var X`(m)t = σ 2] , [var X(m)t = σ 2m-β]  } ,                  (2.5)

 

[X – гауссовский с нулевым средним и var X`(m)t = σ 2 (или, что то же самое, var X(m)t = σ 2m-β)]  =>  { [X`(m) =dis X] , [rm(k) = r` m(k) = r(k) = g(k)] } ,                  (2.6)

 

[X – гауссовский с нулевым средним и r` m(k) = r(k)]  =>  [X`(m) =dis X]  =>  { [rm(k) = r` m(k) = r(k) = g(k)] , [var X`(m)t = σ 2] , [var X(m)t = σ 2m-β] } ,                  (2.7)

 

Где k, m I1.

 

 

 

Цепочки (2.4) – (2.7) показывают эквивалентность следующих высказываний: «Гауссовский процесс с нулевым средним - СУС», «rm(k) = r`m(k) = r(k)», «var X`(m)t = σ 2» и «r(k) = g(k)».

 

 

 

Из вышесказанного также следует, что решение r(k) = g(k) функционального уравнения rm(k) = r(k),   k, m I1  является единственным в классе корреляционных коэффициентов r(k), то есть в классе неотрицательно определенных функций. Так как доказательство данного утверждения также не было опубликовано, приведем его здесь. А именно, из (2.4) и (2.5) следует, что гауссовский процесс X с нулевым средним является СУС, если r(k) = g(k), k I1 . Так как   rm(k) = r`m(k),   k, m I1 ,  то из (2.7) следует, что если у гауссовского процесса X с нулевым средним  rm(k) = r(k) ,  k, m I1 ,  то он – СУС. Из этих двух рассуждений следует уникальность решения r(k) = g(k) для уравнения rm(k) = r(k),   k, m I1 .

Процесс СУС не может иметь ненулевое среднее, в то время как ССШС – может. Более того, если X – положительный и невырожденный процесс, то ни X, ни X-m не могут быть СУС.

 

 

2.2. Асимптотическое самоподобие в широком смысле.  Существуют разные определения асимптотического самоподобия. Ниже дано определение, которое будет использоваться в данной статье, а также рассказано о определениях, сформулированных другими авторами. В нашем определении будут использованы те же обозначения, что и раньше.

 

 

Определение.  Процесс X называется асимптотически самоподобным в широком смысле (АСШС) с параметром  H = 1 - β /2,  0 < β < 1,  если  

 

lim rm(k) = g(k),                 m→∞,     k I1 .                   (2. 8)

 

 

Таким образом, процесс X является АСШС, если после усреднения по блокам длины m, при стремлении m→∞, его корреляционная структура становится идентичной структуре некоторого ССШС-процесса (не обязательно самого X, как в определениях других авторов). Например, определение в статье [12]  выглядит так:  процесс X – АСШС, если r(k) →L(k)k-β  ,  k→∞  и  rm(k) → r(k) , m→∞ для достаточно большого k, где L(k) – медленно меняющаяся функция. А в статье [19] – такое определение: процесс X – АСШС, если rm(k) → r(k) , m→∞, k I1 .

Другими словами, если X(m) стремится к некоторому строго самоподобному в широком смысле процессу, то X – асимптотически самоподобный в широком смысле (это определение дано Cox’ом в [6]). АСШС – процессы в определениях [12] и [19] будут рассмотрены ниже.

Очевидно, что строго самоподобный процесс (ССШС) является асимптотически самоподобным (АСШС).

Следующая теорема дает необходимое и достаточное условие АСШС в различных терминах:  дисперсии Vm, усредненного процесса X(m), а также достаточное условие в терминах корреляционного коэффициента r(k). В теореме использована концепция медленных и регулярных вариаций (см. приложение E).

 

 

Теорема 2.  Для процесса X и H = 1 - β /2,  0 < β < 1,  следующие предложения эквивалентны:

 

(e)       X – АСШС-процесс, в смысле (2. 8),

 

(f)        Vkm / Vm ~ k- β,    m→∞, k I1 .

 

Асимптотические уравнения

 

(g)  Vm ~ L(m)m- β ,    m→∞, m I1

и

(h)  r(k) ~ σ 2H(2H-1)L(k)k- β ,    m→∞, k I1

 

(где L(x)>0 в пункте (g) - медленно меняющаяся функция, а L(x) в пункте (h) – та же, что и в (g))

 

эквивалентны и из них следуют (e) и (f).

 

Доказательство дано в приложении A.

 

 

Асимптотическое уравнение (f) является определением регулярно изменяющейся последовательности Vm с целой переменной (см. Приложение E). Таким образом, в теореме 2 утверждается, что асимптотическое самоподобие процесса X эквивалентно регулярному изменению дисперсии X(m). Подчеркнем, что регулярно изменяющаяся последовательность с целой переменной не обязательно ведет себя так же, как регулярно изменяющаяся последовательность с действительной переменной.

Каждое из условий (g) и (h) достаточно для АСШС. Использование медленно меняющихся функций ограничивается здесь целыми точками m. В условии (g) требуется, чтобы дисперсия Vm рассматривалась как регулярно меняющаяся функция; то же требуется в условии (h) для корреляционного коэффициента r(k).

Условие (h) иногда является более удобным, чем (f) и (g), так как (f) и (g) выражены с помощью характеристик усредненного процесса X(m), а (h) выражено с помощью корреляционного коэффициента собственно процесса X. Условие (h) является более общим, чем достаточное условие для АСШС, данное в [20]:     r(k) ~ ck- β,   k→∞,   c=const.

Из (h) следует, что каждый процесс с медленно убывающей зависимостью (в определениях из [1], [6]) является АСШС.

 

 

Для полноты картины скажем, что существует также концепция асимптотически самоподобных в узком смысле процессов (АСУС). Процесс X является АСУС, если условие X`(m) =dis X сохраняется при m→∞. АСУС-процесс не является АСШС-процессом в смысле (2.8), но является АСШС-процессом в определениях из статей [12] и [19]. Если принять это определение, то есть «X – АСУС, если X`(m) – АСУС при m→∞», мы приходим к путанице: АСУС-процесс является АСШС-процессом в определении (2.8), но не является АСШС-процессом в определении из [12] и [19].

 

 

Отметим, что множество корреляционных функций, которым соответствует АСШС-процесс в определении из [12], состоит из одной функции r(k) = g(k). Это так, потому что из r(k) → L(k)k- β  в соответствии с теоремой 2 следует, что rm(k) → g(k). Таким образом, класс АСШС в смысле [12] совпадает с классом ССШС.

 

 

Также легко заметить, что пересечение классов АСШС в смысле [19] и в смысле определения Cox’а (принятом нами) содержат только один процесс, а именно – ССШС-процесс. Следовательно, процессы с МУЗ, удовлетворяющие (h), исключая ССШС-процесс, не находятся в классе АСШС-процессов в смысле [19]. В заключение отметим, что белый шум в широком смысле (то есть  r(k) = 0,  k I1) являющийся пределом усредненных процессов с быстро убывающей зависимостью с Vm ~ cm-1,  m→∞,  есть процесс АСШС в определении из [19], но не в определении Cox’а.

 

 

ОГЛАВЛЕНИЕ

 

ЧИТАТЬ  СТАТЬЮ  ПОЛНОСТЬЮ