Additive Markov chain

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In probability theory, an additive Markov chain is a Markov chain with an additive conditional probability function. Here the process is a discrete-time Markov chain of order m and the transition probability to a state at the next time is a sum of functions, each depending on the next state and one of the m previous states.


An additive Markov chain of order m is a sequence of random variables X1X2X3, ..., possessing the following property: the probability that a random variable Xn has a certain value xn under the condition that the values of all previous variables are fixed depends on the values of m previous variables only (Markov chain of order m), 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_{n-m}=x_{n-m}) = \sum_{r=1}^{m} f(x_n,x_{n-r},r).

Binary case[edit]

A binary additive Markov chain is where the state space of the chain consists on two values only, Xn ∈ { x1x2 }. For example, Xn ∈ { 0, 1 }. The conditional probability function of a binary additive Markov chain can be represented 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 Xn = 1 in the sequence and F(r) is referred to as the memory function. The value of \bar{X} and the function F(r) contain all the information about correlation properties of the Markov chain.

Relation between the memory function and the correlation function[edit]

In the binary case, the correlation function between the variables X_n and X_k of the chain depends on the distance n - k only. It is defined as follows:

K(r) = \langle (X_n-\bar{X})(X_{n+r}-\bar{X}) \rangle = \langle X_n X_{n+r} \rangle -{\bar{X}}^2,

where the symbol \langle \cdots \rangle denotes averaging over all n. By definition,

K(-r)=K(r),   K(0)=\bar{X}(1-\bar{X}).

There is a relation between the memory function and the correlation function of the binary additive Markov chain:[1]

K(r)=\sum_{s=1}^m K(r-s)F(s), \, \, \, \, r=1, 2, \dots\,.

See also[edit]


  1. ^ S.S. Melnyk, O.V. Usatenko, and V.A. Yampol’skii. (2006) "Memory functions of the additive Markov chains: applications to complex dynamic systems", Physica A, 361 (2), 405–415 doi:10.1016/j.physa.2005.06.083


  • A.A. Markov. (1906) "Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie drug ot druga". Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 2-ya seriya, tom 15, 135–156
  • A.A. Markov. (1971) "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
  • S. Hod and U. Keshet (2004). "Phase transition in random walks with long-range correlations". Phys. Rev. E 70: 015104. doi:10.1103/PhysRevE.70.015104. 
  • S.L. Narasimhan, J.A. Nathan, and K.P.N. Murthy (2005). "Can coarse-graining introduce long-range correlations in a symbolic sequence?". Europhys. Lett. 69 (1): 22. arXiv:cond-mat/0409042. doi:10.1209/epl/i2004-10307-2. 
  • Ramakrishnan, S. (1981) "Finitely Additive Markov Chains", Transactions of the American Mathematical Society, 265 (1), 247-272 JSTOR 1998493