Self-similar processes in communications networks

Операции с матрицами на 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 = EX_t < ∞ , σ² = var X_t < ∞ ( мат. ожидание и дисперсия X_t соответственно ).

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

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

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

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

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

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

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

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

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

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

X^(m)_t = 1/m * ( X_tm-m+1 + … + X_tm ) , m, t € I1 ;

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

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

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

r_m(k) = r(k) , k € I0 , m € I1 .

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

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

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

(b) V_m =ˆ var X^(m)_t = σ ² m^{- β}, m € I2 = {2, 3, …}

(c) f(l) = c | e²^pⁱ^l - 1 |² ( 1 / | λ + l | ^{3 - β} ) , -1/2 <= l <= 1/2

(d) X – процесс ССШС в смысле определения B, то есть r_m(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 = (X₁, X₂, … ) называется самоподобным в узком смысле (СУС) с параметром H = 1 - β /2, 0 < β < 1 , если

m^1-^H X⁽^m⁾ =_dis X

или, что эквивалентно, X`⁽^m⁾ =_dis X ,

где X` = (X`₁, X`₂, … ), X`⁽^m⁾_t = 1/m^H * ( X_tm_-_m₊₁ + … + X_tm ) ;

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

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

[r_m(k) = r`_m(k) = r(k)] <= [X`^(m) =_dis X] => [var X`^(m)_t = σ ²=^ var X_t] , (2.2)

[r_m(k) = r`_m(k) = r(k)] <= [var X`^(m)_t = σ ² <=> [r(k) = g(k)] <=> [var X^(m)_t = σ ²m^-β] , (2.3)

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

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

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

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

[X – гауссовский с нулевым средним и var X`⁽^m)_t = σ ² (или, что то же самое, var X⁽^m)_t = σ ²m^-^β)] => { [X`⁽^m) =_dis X] , [r_m(k) = r`_m(k) = r(k) = g(k)] } , (2.6)

[X – гауссовский с нулевым средним и r`_m(k) = r(k)] => [X`⁽^m) =_dis X] => { [r_m(k) = r`_m(k) = r(k) = g(k)] , [var X`⁽^m)_t = σ ²] , [var X⁽^m)_t = σ ²m^-^β] } , (2.7)

Где k, m € I₁.

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

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

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

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

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

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

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

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

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

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

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

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

(f) V_km / V_m ~ k^-^β, m→∞, k € I₁.

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

(g) V_m ~ L(m)m^-^β , m→∞, m € I₁

(h) r(k) ~ σ ²H(2H-1)L(k)k^-^β , m→∞, k € I₁

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

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

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

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

Каждое из условий (g) и (h) достаточно для АСШС. Использование медленно меняющихся функций ограничивается здесь целыми точками m. В условии (g) требуется, чтобы дисперсия V_m рассматривалась как регулярно меняющаяся функция; то же требуется в условии (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 следует, что r_m(k) → g(k). Таким образом, класс АСШС в смысле [12] совпадает с классом ССШС.

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

ОГЛАВЛЕНИЕ

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