Movatterモバイル変換

Markov property

From Wikipedia, the free encyclopedia

Memoryless property of a stochastic process

This article is about the property of a stochastic process. For the class of properties of a finitely presented group, seeAdian–Rabin theorem.

A single realisation of three-dimensionalBrownian motion for times 0 ≤ t ≤ 2. Brownian motion has the Markov property, as the displacement of the particle does not depend on its past displacements.

Inprobability theory andstatistics, the termMarkov property refers to thememoryless property of astochastic process, which means that its future evolution is independent of its history. It is named after theRussian mathematician Andrey Markov. The termstrong Markov property is similar to the Markov property, except that the meaning of "present" is defined in terms of arandom variable known as astopping time.

The termMarkov assumption is used to describe a model where the Markov property is assumed to hold, such as ahidden Markov model.

AMarkov random field extends this property to two or more dimensions or to random variables defined for an interconnected network of items.^[1] An example of a model for such a field is theIsing model.

A discrete-time stochastic process satisfying the Markov property is known as aMarkov chain.

Introduction

[edit]

A stochastic process has the Markov property if theconditional probability distribution of future states of the process (conditional on both past and present values) depends only upon the present state; that is, given the present, the future does not depend on the past. A process with this property is said to beMarkov orMarkovian and known as aMarkov process. Two famous classes of Markov process are theMarkov chain andBrownian motion.

Note that there is a subtle, often overlooked and very important point that is often missed in the plain English statement of the definition: the statespace of the process is constant through time. The conditional description involves a fixed "bandwidth". For example, without this restriction we could augment any process to one which includes the complete history from a given initial condition and it would be made to be Markovian. But the state space would be of increasing dimensionality over time and does not meet the definition.

History

[edit]

Main article:Markov chain § History

Definition

[edit]

Let $(\Omega ,{\mathcal {F}},P)$ be aprobability space with afiltration $({\mathcal {F}}_{s},\ s\in I)$ , for some (totally ordered) index set $I {\displaystyle I}$ ; and let $(S,\Sigma )$ be ameasurable space. An $(S,\Sigma )$ -valued stochastic process $X=\{X_{t}:\Omega \to S\}_{t\in I}$ adapted to the filtration is said to possess theMarkov property if, for each $A\in \Sigma$ and each $s,t\in I$ with $s<t$ ,

P(X_{t}\in A\mid {\mathcal {F}}_{s})=P(X_{t}\in A\mid X_{s}).

^[2]

In the case where $S {\displaystyle S}$ is a discrete set with thediscrete sigma algebra and $I=\mathbb {N}$ , this can be reformulated as follows:

P(X_{n+1}=x_{n+1}\mid X_{n}=x_{n},\dots ,X_{1}=x_{1})=P(X_{n+1}=x_{n+1}\mid X_{n}=x_{n}){\text{ for all }}n\in \mathbb {N} .

In other words, the distribution of $X {\displaystyle X}$ at time $n+1$ depend solely on the state of $X {\displaystyle X}$ at time $n {\displaystyle n}$ and is independent of the state of the process at any time previous to $n {\displaystyle n}$ , which corresponds precisely to the intuition described in the introduction.

If $I=[0,\infty )$ , then $X {\displaystyle X}$ is calledtime-homogeneous if for all $t,s\geq 0$ the weak Markov property holds:^[3]

P(X_{t+s}\in A\mid {\mathcal {F}}_{s})=P(X_{t}\in A\mid X_{0}=x)|_{x=X_{s}}=:P^{X_{s}}(X_{t}\in A)

The newly introduced probability measure $P^{x}(X_{t}\in \cdot )$ , $x\in S$ , has the following intuition: It gives the probability that the process $X {\displaystyle X}$ lies in some set at time $t {\displaystyle t}$ , when it was started in $x {\displaystyle x}$ at time zero. The function $P_{t}(x,A):=P^{x}(X_{t}\in A)$ , $(t,x,A)\in \mathbb {R} _{+}\times S\times \Sigma$ , is also called thetransition function of $X {\displaystyle X}$ and the collection $(P_{t})_{t\geq 0}$ itstransition semigroup.

Alternative formulations

[edit]

There exists multiple alternative formulations of the elementary Markov property described above. The following are all equivalent:^[4]^[5]

For all $t\geq 0$ the $\sigma$ -algebras ${\mathcal {F}}_{t}$ and ${\mathcal {F}}_{t}':=\sigma (X_{s}:s\geq t)$ areconditionally independent given $X_{t}$ . In other words, for all $A\in {\mathcal {F}}_{t}$ , $B\in {\mathcal {F}}_{t}'$ :

$P(A\cap B\mid X_{t})=P(A\mid X_{t})P(B\mid X_{t})$ .

For all $t\geq 0$ , $B\in {\mathcal {F}}_{t}'$ :

$P(B\mid {\mathcal {F}}_{t})=P(B\mid X_{t})$ .

For all $t\geq 0$ , $A\in {\mathcal {F}}_{t}$ :

$P(A\mid {\mathcal {F}}_{t}^{'})=P(A\mid X_{t})$ .

For all $t\geq 0$ and $Y:\Omega \rightarrow \mathbb {R}$ bounded and ${\mathcal {F}}_{t}'$ -measurable

$\operatorname {E} [Y\mid {\mathcal {F}}_{t}]=\operatorname {E} [Y\mid X_{t}]$ .

For all $t\geq s\geq 0$ and $f:S\rightarrow \mathbb {R}$ bounded and measurable

$\operatorname {E} [f(X_{t})\mid {\mathcal {F}}_{s}]=\operatorname {E} [f(X_{t})\mid X_{s}]$ .

For all $t\geq s\geq 0$ and $f:S\rightarrow \mathbb {R}$ continuous with compact support

$\operatorname {E} [f(X_{t})\mid {\mathcal {F}}_{s}]=\operatorname {E} [f(X_{t})\mid X_{s}]$ .

For all $0\leq s_{1}<...<s_{n}<s<t$ and $f:S\rightarrow \mathbb {R}$ continuous with compact support

$\operatorname {E} [f(X_{t})\mid X_{s},X_{s_{n}},...,X_{s_{1}}]=\operatorname {E} [f(X_{t})\mid X_{s}]$ .

If there exists a so-calledshift-semigroup $(\theta _{t})_{t\geq 0}$ , i.e., functions $\theta _{t}:\Omega \to \Omega$ such that

$\theta _{0}=\mathrm {id} _{\Omega }$ ,
$\theta _{t}\circ \theta _{s}=\theta _{t+s}\quad \forall s,t\geq 0$ (semigroup property),
$X_{t}\circ \theta _{s}=X_{t+s}\quad \forall s,t\geq 0$ ,

then the Markov property is equivalent to:^[4]

For all $t\geq 0$ and $\Lambda \in {\mathcal {F}}_{0}'$

$P(\theta _{t}^{-1}(\Lambda )\mid {\mathcal {F}}_{t})=P(\theta _{t}^{-1}(\Lambda )\mid X_{t})$ .

For all $t\geq 0$ and $Y:\Omega \rightarrow \mathbb {R}$ bounded and ${\mathcal {F}}_{0}'$ -measurable

$\operatorname {E} [Y\circ \theta _{t}\mid {\mathcal {F}}_{t}]=\operatorname {E} [Y\circ \theta _{t}\mid X_{t}]$ .

Depending on the situation, some formulations might be easier to verify or to use than others.

Strong Markov property

[edit]

Suppose that $X=(X_{t}:t\geq 0)$ is astochastic process on aprobability space $(\Omega ,{\mathcal {F}},P)$ withnatural filtration $\{{\mathcal {F}}_{t}\}_{t\geq 0}$ . Then for anystopping time $\tau$ on $\Omega$ , we can define

{\mathcal {F}}_{\tau }=\{A\in {\mathcal {F}}:\forall t\geq 0,\{\tau \leq t\}\cap A\in {\mathcal {F}}_{t}\}

Then $X {\displaystyle X}$ is said to have the strong Markov property if, for eachstopping time $\tau$ , conditional on the event $\{\tau <\infty \}$ , we have that for each $t\geq 0$ , $X_{\tau +t}$ is independent of ${\mathcal {F}}_{\tau }$ given $X_{\tau }$ . This is equivalent to

P(X_{\tau +t}\in A,\tau <\infty \mid {\mathcal {F}}_{\tau })=1_{\{\tau <\infty \}}P(X_{t}\in A\mid X_{0}=X_{\tau })

for all

A\in {\mathcal {F}}

where $1_{\{\tau <\infty \}}$ denotes to indicator function of the set $\{\tau <\infty \}$ .

The strong Markov property implies the ordinary Markov property since by taking the stopping time $\tau =t$ , the ordinary Markov property can be deduced.^[6] The converse is in general not true.

The strong Markov property only leads to non-trivial results in continuous time (i.e., results which do not hold with merely the Markov property), as in the discrete case the strong and the elementary Markov property are equivalent.^[7]

Feller property

[edit]

Main article:Feller process

Although the strong Markov property is in general stronger than the elementary Markov property, it is fulfilled by Markov processes with sufficiently "nice" regularity properties.

A continuous time Markov process is said to have theFeller property, if its transition semigroup $(P_{t})_{t\geq 0}$ (see above) fulfills^[4]

$P_{t}f:=\int f(x)P_{t}(\cdot ,dx)\in C_{0}(S)$ for all $f\in C_{0}(S)$ ,
$\lim _{t\to 0}||P_{t}f-f||_{\infty }=0$ for all $f\in C_{0}(S)$ ,

where $C_{0}(S)$ denotes the set ofcontinuous functions vanishing at infinity and $||\cdot ||_{\infty }$ thesup norm. Then one can show that (if the filtration isaugmented) such a process has aversion with right-continuous (evencàdlàg) paths, which in turn fulfills the strong Markov property.

Examples

[edit]

Intuitive example

[edit]

Assume that an urn contains two red balls and one green ball. One ball was drawn yesterday, one ball was drawn today, and the final ball will be drawn tomorrow. All of the draws are "without replacement".

Suppose you know that today's ball was red, but you have no information about yesterday's ball. The chance that tomorrow's ball will be red is 1/2. That's because the only two remaining outcomes for this random experiment are:

Day	Outcome 1	Outcome 2
Yesterday	Red	Green
Today	Red	Red
Tomorrow	Green	Red

On the other hand, if you know that both today and yesterday's balls were red, then you are guaranteed to get a green ball tomorrow.

This discrepancy shows that the probability distribution for tomorrow's color depends not only on the present value, but is also affected by information about the past. This stochastic process of observed colors doesn't have the Markov property. Using the same experiment above, if sampling "without replacement" is changed to sampling "with replacement," the process of observed colors will have the Markov property.^[8]

Stochastic processes

[edit]

Many prominent stochastic processes are Markov processes: TheBrownian motion, theBrownian bridge, thestochastic exponential, theOrnstein-Uhlenbeck process and thePoisson process have the Markov property.

More generally, any semimartingale $X {\displaystyle X}$ with values in $\mathbb {R} ^{n}$ that is given by thestochastic differential equation

X_{t}=X_{0}+\sum _{i=1}^{d}{\Big [}\int _{0}^{t}g_{i}(X_{s})ds+\int _{0}^{t}f_{i}(X_{s})dB_{s}^{i}{\Big ]}

where $B=(B^{1},...,B^{d})$ is a $d {\displaystyle d}$ -dimensional Brownian motion and $f_{1},...,f_{d},g_{1},...,g_{d}:\mathbb {R} ^{n}\to \mathbb {R} ^{n}$ are autonomous (i.e., they do not depend on time) Lipschitz functions, is time-homogeneous and has the strong Markov property. If $f_{1},...,f_{d},g_{1},...,g_{d}$ are not autonomous, then $X {\displaystyle X}$ still has the elementary Markov property.^[3]

Applications

[edit]

Forecasting

[edit]

In the fields ofpredictive modelling andprobabilistic forecasting, the Markov property is considered desirable since it may enable the reasoning and resolution of the problem that otherwise would not be possible to be resolved because of itsintractability. Such a model is known as aMarkov model.

Markov Chain Monte Carlo

[edit]

An application of the Markov property in a generalized form is inMarkov chain Monte Carlo computations in the context ofBayesian statistics.

References

[edit]

^Dodge, Yadolah. (2006)The Oxford Dictionary of Statistical Terms,Oxford University Press.ISBN 0-19-850994-4
^Durrett, Rick.Probability: Theory and Examples. Fourth Edition.Cambridge University Press, 2010.
^^a ^bProtter, Philip (1992).Stochastic Integration and Differential Equations (2nd ed.). Springer-Verlag Berlin Heidelberg. pp. 235–242.ISBN 978-3-662-02619-9.
^^a ^b ^cChung, Kai Lai; Walsh, John B. (2005).Markov Processes, Brownian Motion, and Time Symmetry (2nd ed.). Springer Science+Business Media. pp. 1–5,49–56.ISBN 978-0387-22026-0.
^Øksendal, Bernt K. (2003).Stochastic Differential Equations: An Introduction with Applications. Springer, Berlin.ISBN 3-540-04758-1.
^Ethier, Stewart N. andKurtz, Thomas G.Markov Processes: Characterization and Convergence. Wiley Series in Probability and Mathematical Statistics, 1986, p. 158.
^Klenke, Achim (2020).Probability Theory (3rd ed.). Springer Cham. p. 397.ISBN 978-3-030-56402-5.
^"Example of a stochastic process which does not have the Markov property".Stack Exchange. Retrieved2020-07-07.

v t e Stochastic processes
Discrete time	Bernoulli process Branching process Chinese restaurant process Galton–Watson process Independent and identically distributed random variables Markov chain Moran process Random walk Loop-erased Self-avoiding Biased Maximal entropy
Continuous time	Additive process Airy process Bessel process Birth–death process pure birth Brownian motion Bridge Dyson Excursion Fractional Geometric Meander Cauchy process Contact process Continuous-time random walk Cox process Diffusion process Empirical process Feller process Fleming–Viot process Gamma process Geometric process Hawkes process Hunt process Interacting particle systems Itô diffusion Itô process Jump diffusion Jump process Lévy process Local time Markov additive process McKean–Vlasov process Ornstein–Uhlenbeck process Poisson process Compound Non-homogeneous Quasimartingale Schramm–Loewner evolution Semimartingale Sigma-martingale Stable process Superprocess Telegraph process Variance gamma process Wiener process Wiener sausage
Both	Branching process Gaussian process Hidden Markov model (HMM) Markov process Martingale Differences Local Sub- Super- Random dynamical system Regenerative process Renewal process Stochastic chains with memory of variable length White noise
Fields and other	Dirichlet process Gaussian random field Gibbs measure Hopfield model Ising model Potts model Boolean network Markov random field Percolation Pitman–Yor process Point process Cox Determinantal Poisson Random field Random graph
Time series models	Autoregressive conditional heteroskedasticity (ARCH) model Autoregressive integrated moving average (ARIMA) model Autoregressive (AR) model Autoregressive moving-average (ARMA) model Generalized autoregressive conditional heteroskedasticity (GARCH) model Moving-average (MA) model
Financial models	Binomial options pricing model Black–Derman–Toy Black–Karasinski Black–Scholes Chan–Karolyi–Longstaff–Sanders (CKLS) Chen Constant elasticity of variance (CEV) Cox–Ingersoll–Ross (CIR) Garman–Kohlhagen Heath–Jarrow–Morton (HJM) Heston Ho–Lee Hull–White Korn-Kreer-Lenssen LIBOR market Rendleman–Bartter SABR volatility Vašíček Wilkie
Actuarial models	Bühlmann Cramér–Lundberg Risk process Sparre–Anderson
Queueing models	Bulk Fluid Generalized queueing network M/G/1 M/M/1 M/M/c
Properties	Càdlàg paths Continuous Continuous paths Ergodic Exchangeable Feller-continuous Gauss–Markov Markov Mixing Piecewise-deterministic Predictable Progressively measurable Self-similar Stationary Time-reversible
Limit theorems	Central limit theorem Donsker's theorem Doob's martingale convergence theorems Ergodic theorem Fisher–Tippett–Gnedenko theorem Large deviation principle Law of large numbers (weak/strong) Law of the iterated logarithm Maximal ergodic theorem Sanov's theorem Zero–one laws (Blumenthal,Borel–Cantelli,Engelbert–Schmidt,Hewitt–Savage, Kolmogorov,Lévy)
Inequalities	Burkholder–Davis–Gundy Doob's martingale Doob's upcrossing Kunita–Watanabe Marcinkiewicz–Zygmund
Tools	Cameron–Martin theorem Convergence of random variables Doléans-Dade exponential Doob decomposition theorem Doob–Meyer decomposition theorem Doob's optional stopping theorem Dynkin's formula Feynman–Kac formula Filtration Girsanov theorem Infinitesimal generator Itô integral Itô's lemma Kolmogorov continuity theorem Kolmogorov extension theorem Kosambi–Karhunen–Loève theorem Lévy–Prokhorov metric Malliavin calculus Martingale representation theorem Optional stopping theorem Prokhorov's theorem Quadratic variation Reflection principle Skorokhod integral Skorokhod's representation theorem Skorokhod space Snell envelope Stochastic differential equation Tanaka Stopping time Stratonovich integral Uniform integrability Usual hypotheses Wiener space Classical Abstract
Disciplines	Actuarial mathematics Control theory Econometrics Ergodic theory Extreme value theory (EVT) Large deviations theory Mathematical finance Mathematical statistics Probability theory Queueing theory Renewal theory Ruin theory Signal processing Statistics Stochastic analysis Time series analysis Machine learning
List of topics Category