Additive Markov chain

An additive Markov chain is a Markov chain with the additive condition probability function.

Formal definition

An additive Markov chain of order m is a sequence of random variables X₁, X₂, X₃, ..., possessing the following property: the probability of variable X_n to have a certain value under the condition that the values of all previous variables are fixed depends on the values of m previous variables only, and the influence of previous variables on a generated one is additive,

$\Pr(X_{n}=x_{n}|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{1}=x_{1})=\sum _{r=1}^{m}f(x_{n},x_{n-r},r)$

for all n>m.

Binary case

A binary additive Markov chain is where the state space of the chain consists on two values only, X_n   ∈   { x₁, x₂ }. For example, X_n   ∈   { 0, 1 }. The conditional probability function of a binary additive Markov chain can be presented as

$\Pr(X_{n}=1|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots )={\bar {X}}+\sum _{r=1}^{m}F(r)(x_{n-r}-{\bar {X}})$,

$\Pr(X_{n}=0|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots )=1-\Pr(X_{n}=1|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots )$.

Here ${\bar {X}}$ is the probability to find X_n=1 in the sequence;
$F(r)$ is referred to as the memory function.
The value ${\bar {X}}$ and the function $F(r)$ contain complete information about correlation properties of the Markov chain.

Relation between the memory function and the correlation function

In binary case, the correlation function between the variables $x_{n}$ and $x_{m}$ of the chain depends on the distance m-n only. It is defined as follows: K(r) = K2(r) = (a0 ¡ ¹a)(ar ¡ ¹a) = a0ar ¡ ¹a2: (1.6) By definition, the correlation function is even, K(¡r) = K(r), and the variance of the random variable ai for the binary chain is K(0) = ¹a(1 ¡ ¹a).

See also

• Markov chain
• Hidden Markov model
• Examples of Markov chains
• Markov process
• Semi-Markov process
• Variable-order Markov model
• Quantum Markov chain

References

• A.A. Markov. "Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie drug ot druga". Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 2-ya seriya, tom 15, pp. 135–156, 1906.

• A.A. Markov. "Extension of the limit theorems of probability theory to a sum of variables connected in a chain". reprinted in Appendix B of: R. Howard. Dynamic Probabilistic Systems, volume 1: Markov Chains. John Wiley and Sons, 1971.

• S. Hod and U. Keshet. "Phase transition in random walks with long-range correlations", Phys. Rev. E, Vol. 70, p. 015104, 2004.

• S.L. Narasimhan, J.A. Nathan, and K.P.N. Murthy. "Can coarse-graining introduce long-range correlations in a symbolic sequence?", Europhys. Lett. Vol. 69 (1), p. 22, 2005.

• S.S. Melnyk, O.V. Usatenko, and V.A. Yampol’skii. "Memory functions of the additive Markov chains: applications to complex dynamic systems", Physica A, Vol. 361, I. 2, pp. 405-415, 2006.