Self-similar process

Self-similar processes are stochastic processes satisfying a mathematically precise version of the self-similarity property. Several related properties have this name, and some are defined here.

A self-similar phenomenon behaves the same when viewed at different degrees of magnification, or different scales on a dimension. Because stochastic processes are random variables with a time and a space component, their self-similarity properties are defined in terms of how a scaling in time relates to a scaling in space.

A continuous-time stochastic process ${\displaystyle (X_{t})_{t\geq 0}}$ is called self-similar with parameter ${\displaystyle H>0}$ if for all ${\displaystyle a>0}$, the processes ${\displaystyle (X_{at})_{t\geq 0}}$ and ${\displaystyle (a^{H}X_{t})_{t\geq 0}}$ have the same law.^[1]

• The Wiener process (or Brownian motion) is self-similar with ${\displaystyle H=1/2}$.^[2]
• The fractional Brownian motion is a generalisation of Brownian motion that preserves self-similarity; it can be self-similar for any ${\displaystyle H\in (0,1)}$.^[3]
• The class of self-similar Lévy processes are called stable processes. They can be self-similar for any ${\displaystyle H\in [1/2,\infty )}$.^[4]

A wide-sense stationary process ${\displaystyle (X_{n})_{n\geq 0}}$ is called exactly second-order self-similar with parameter ${\displaystyle H>0}$ if the following hold:

(i) ${\displaystyle \mathrm {Var} (X^{(m)})=\mathrm {Var} (X)m^{2(H-1)}}$, where for each ${\displaystyle k\in \mathbb {N} _{0}}$, ${\displaystyle X_{k}^{(m)}={\frac {1}{m}}\sum _{i=1}^{m}X_{(k-1)m+i},}$

(ii) for all ${\displaystyle m\in \mathbb {N} ^{+}}$, the autocorrelation functions ${\displaystyle r}$ and ${\displaystyle r^{(m)}}$ of ${\displaystyle X}$ and ${\displaystyle X^{(m)}}$ are equal.

If instead of (ii), the weaker condition

(iii) ${\displaystyle r^{(m)}\to r}$ pointwise as ${\displaystyle m\to \infty }$

holds, then ${\displaystyle X}$ is called asymptotically second-order self-similar.^[5]

In the case ${\displaystyle 1/2<H<1}$, asymptotic self-similarity is equivalent to long-range dependence.^[1] Self-similar and long-range dependent characteristics in computer networks present a fundamentally different set of problems to people doing analysis and/or design of networks, and many of the previous assumptions upon which systems have been built are no longer valid in the presence of self-similarity.^[6]

Long-range dependence is closely connected to the theory of heavy-tailed distributions.^[7] A distribution is said to have a heavy tail if

${\displaystyle \lim _{x\to \infty }e^{\lambda x}\Pr[X>x]=\infty \quad {\mbox{for all }}\lambda >0.\,}$

One example of a heavy-tailed distribution is the Pareto distribution. Examples of processes that can be described using heavy-tailed distributions include traffic processes, such as packet inter-arrival times and burst lengths.^[8]

• The Tweedie convergence theorem can be used to explain the origin of the variance to mean power law, 1/f noise and multifractality, features associated with self-similar processes.^[9]
• Ethernet traffic data is often self-similar.^[5] Empirical studies of measured traffic traces have led to the wide recognition of self-similarity in network traffic.^[8]

Sources

• Kihong Park; Walter Willinger (2000), Self-Similar Network Traffic and Performance Evaluation, New York, NY, USA: John Wiley & Sons, Inc., doi:10.1002/047120644X, ISBN 0471319740