Additive Markov chain: Information from Answers.com

In probability theory, an additive Markov chain is a Markov chain with the additive condition probability function.

1 Definition
2 Binary case
- 2.1 Relation between the memory function and the correlation function
3 See also
4 References

Definition

An additive Markov chain of order m is a sequence of random variables X₁, X₂, X₃, ..., possessing the following property: the probability that a random variable X_n has 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 l$ of the chain depends on the distance $m - l$ 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,$

here symbols $\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:

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

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.

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	The stereochemistry of the hydroboration mechanism is. a. anti-Markov b. Markovnikov addition c. syn addition d. anti addition? Read answer...
	For a fission reaction to fail to be maintained as a chain reaction each fission must produce less than additional fission reactions? Read answer...
	The answer to an addition is? Read answer...

	Transitional matrix of a markov chain is given byPp q .Classify the states of the markov chain p q?
	What is the rate in rate out theory to calculate initial state probability in Markov Chain?
	How to design a Markov chain to analyze the saturation throughput of a 4x4 input buffered switch with the FIFO scheme and each packet is equally likely to be destined for any output?

Additive Markov chain

Contents

Definition

Binary case

Relation between the memory function and the correlation function

See also

References