probability theory Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...

, an additive Markov chain is a

Markov chain A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happen ...

with an

additive Additive may refer to: Mathematics * Additive function, a function in number theory * Additive map, a function that preserves the addition operation * Additive set-functionn see Sigma additivity * Additive category, a preadditive category with f ...

conditional probability In probability theory, conditional probability is a measure of the probability of an event occurring, given that another event (by assumption, presumption, assertion or evidence) has already occurred. This particular method relies on event B occu ...

function. Here the process is a

discrete-time In mathematical dynamics, discrete time and continuous time are two alternative frameworks within which variables that evolve over time are modeled. Discrete time Discrete time views values of variables as occurring at distinct, separate "po ...

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.

Definition

An additive Markov chain of order ''m'' is a sequence of

random variable A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the p ...

s ''X''₁, ''X''₂, ''X''₃, ..., possessing the following property: the probability that a random variable ''X''_''n'' has a certain value ''x''_''n'' under the condition that the values of all previous variables are fixed depends on the values of ''m'' previous variables only (

of order ''m''), and the influence of previous variables on a generated one is additive, :

\Pr(X_n=x_n\mid X_=x_, X_=x_, \dots, X_=x_) = \sum_^ f(x_n,x_,r).

Binary case

A binary additive Markov chain is where the

state space A state space is the set of all possible configurations of a system. It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory. For instance, the t ...

of the chain consists on two values only, ''X''_n ∈ . For example, ''X''_''n'' ∈ . The conditional probability function of a binary additive Markov chain can be represented as :

\Pr(X_n=1\mid X_=x_, X_=x_, \dots) = \bar + \sum_^ F(r) (x_-\bar),

\Pr(X_n=0\mid X_=x_, X_=x_, \dots) = 1 - \Pr(X_n=1\mid X_ = x_, X_ = x_, \dots).

Here

\bar

is the probability to find ''X''_''n'' = 1 in the sequence and ''F''(''r'') is referred to as the memory function. The value of

\bar

and the function ''F''(''r'') contain all the information about

correlation In statistics, correlation or dependence is any statistical relationship, whether causal or not, between two random variables or bivariate data. Although in the broadest sense, "correlation" may indicate any type of association, in statisti ...

properties of the Markov chain.

Relation between the memory function and the correlation function

In the binary case, the

correlation function A correlation function is a function that gives the statistical correlation between random variables, contingent on the spatial or temporal distance between those variables. If one considers the correlation function between random variables re ...

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_-\bar) \rangle = \langle X_n X_ \rangle -^2,

where the symbol

\langle \cdots \rangle

denotes averaging over all ''n''. By definition, :

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

There is a relation between the memory function and the correlation function of the binary additive Markov chain: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 :

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

Notes

References

* 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 * * *Ramakrishnan, S. (1981) "Finitely Additive Markov Chains", ''Transactions of the American Mathematical Society'', 265 (1), 247–272 {{DEFAULTSORT:Additive Markov Chain Markov processes

Definition

Binary case

Relation between the memory function and the correlation function

See also

Notes

References