# Example of a stochastic process which does not have the Markov property

According to this definition,

A stochastic process has the Markov property if the conditional probability distribution of future states of the process depends only upon the present state. [...] given the present, the future does not depend on the past.

From this, it seems to me that any stochastic processes arising from Newtonian physics, for example, would have the Markov property - right?

Could you please give an example or three of (preferably simple) stochastic processes which do not have the Markov property? Are these necessarily purely mathematical constructs, or do they also occur in what we might loosely consider "everyday life"?

-
 Even stochastic processes arising from Newtonian physics don't have the Markov property, because parts of the state (say, microscopic degrees of freedom) tend not to be observed or included in the state description, but can affect the later evolution of the observed degrees of freedom. – mjqxxxx Dec 7 '11 at 22:40 Got something from an answer below? – Did Aug 11 '12 at 9:24 @did I've accepted an answer now, if that's what you mean. I've upvoted yours, but I found the other one somewhat clearer. – romkyns Aug 14 '12 at 9:01 Perfect.   – Did Aug 14 '12 at 9:05

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".

1. 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 "r,r,g" and "g,r,r".

2. 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.

Update: For any random experiment, there can be several related processes some of which have the Markov property and others that don't.

For instance, if you change sampling "without replacement" to sampling "with replacement" in the urn experiment above, the process of observed colors will have the Markov property.

Another example: if $(X_n)$ is any stochastic process you get a related Markov process by considering the historical process defined by $$H_n=(X_0,X_1,\dots ,X_n).$$ In this setup, the Markov property is trivially fulfilled since the current state includes all the past history.

In the other direction, you can lose the Markov property by combining states, or "lumping". An example that I used in this MO answer, is to take a random walk $(S_n)$ on the integers, and define $Y_n=1[S_n>0]$. If there is a long string of time points with $Y_n=1$, then it is quite likely that the random walk is nowhere near zero and that the next value will also be 1. If you only know that the current value is 1, you are not as confident that the next value will be 1. Intuitively, this is why $Y_n$ doesn't have the Markov property.

For cases of lumping that preserve the Markov property, see this MSE answer.

-
 From a different point of view, the distribution for tomorrow's color still depends only on the present state (of the entire system), however this present state is not known in its entirety. If I could look at the entire state, this process would be Markovian, right? – romkyns Dec 7 '11 at 23:29 Any stochastic process needs a precise definition of state. In my example, the state consists of a single color. It makes sense to say "Yesterday's state was green", or "Tomorrow's state might be green". But the phrase "state of the entire system" makes no sense. I think I understand what you mean, though, and I've added an update to my answer. Let me know if anything is unclear. – Byron Schmuland Dec 8 '11 at 15:23

Actually, from Newtonian physics things would be completely deterministic, so Markov in a trivial sense. The usual use (speaking as a physicist) for Markov processes in physics is when you consider open systems; that is, you want to (or are only able to) look at a subpart of a whole. An nice example is Brownian motion --- you want to consider the movement of a "big" particle like pollen (which you can see) but its motion is tied to all the particles (molecules) you can't see. In general, the impulse delivered in a given time is given by an integral, but this integral can be approximately by a Markovian process because the relevant timescales (the ones you can see) are much larger than the microscopic one (mean collision time of molecules). This example also provides a nice situation where even on large timescales this approximation breaks down: if you have lots of particles in suspension, such as a colloid, then their motions are actually correlated on quite appreciable time and length scales because they set up macroscopic drifts in the fluid they're sitting in.

-
 That's right, I've seen this example already. I'm looking for an example of a process that does not have the Markov property. – romkyns Dec 7 '11 at 22:43 @romkyns: so when the timescales you're concerned with are getting smaller, then it is no longer a good approximation, so non-Markovian...? – genneth Dec 7 '11 at 23:12

That is quite simple to construct such a process by embedding stochastic differential equations, for example :

$dX_t/X_t=Y_t. dW_t$ and $dY_t/Y_t=dB_t$

with $B_t$ and $W_t$ two independent Brownian motions.

Then $X_t$ is not Markovian, only the couple $(X_t,Y_t)$ is.

You can construct plenty of examples this way.

Regards

-

1.1 Consider your favorite Markov process, say the standard symmetric random walk $(X_n)_{n\geqslant0}$ on the integer line, defined by $X_0=0$ and $X_n=Y_1+\cdots+Y_n$ for every $n\geqslant1$, where $(Y_n)_{n\geqslant1}$ is i.i.d. and symmetric Bernoulli, hence $\mathrm P(Y_n=1)=\mathrm P(Y_n=-1)=\frac12$. The process of the maxima of $(X_n)_{n\geqslant0}$ is the process $(M_n)_{n\geqslant0}$defined by $M_n=\max\{X_k\,;\,0\leqslant k\leqslant n\}$. Then:

The process $(M_n)_{n\geqslant0}$ is not a Markov process, nor a Markov process of any higher order.

To see this, note that $M_{n+1}$ is either $M_n$ or $M_n+1$, and that the probability that $M_{n+1}=M_n+1$ depends on the time $T_n=\max\{0\leqslant k\leqslant n\,;\,M_{n-k}=M_n\}$ spent at $M_n$ by the process before time $n$. Then, due to the symmetry of the increments of the random walk, $\mathrm P(M_{n+1}=M_n+1\,\mid\,\mathcal M_n)=u(T_n)$, where $\mathcal M_n=\sigma(M_k\,;\,0\leqslant k\leqslant n)$ and, for every $k\geqslant0$, $u(k)=\frac12\mathrm P(X_k=0)$. Thus, $u(2k-1)=0$ and $u(2k)=\frac12{2k\choose k}2^{-2k}$ for every $k\geqslant1$, hence the sequence $(u(2k))_{k\geqslant1}$ is decreasing. Since, for every $0\leqslant k\leqslant n$, $[T_n\geqslant k]=[M_{n-k}=M_n]$, this shows that the conditional probability that $[M_{n+1}=M_n+1]$ depends on the past in a possibly unlimited way.

1.2 The analogue continuous time process is a standard Brownian motion $(B_t)_{t\geqslant0}$. Consider $S_t=\sup\{B_s\,;\,0\leqslant s\leqslant t\}$. Then $(B_t)_{t\geqslant0}$ is a Markov process but $(S_t)_{t\geqslant0}$ is not.

2.1 Other examples without the Markov property are the processes of local times. In the discrete setting, consider $Z_n=\sum\limits_{k=1}^{n}[X_{2k}=0]$. Then $Z_{n+1}$ is either $Z_n$ or $Z_n+1$, and the probability that $Z_{n+1}=Z_n+1$ depends on the time $\max\{0\leqslant k\leqslant n\,;\,X_{2n-2k}=0\}$ elapsed since the last zero of the random walk. For reasons similar to the ones explained for the maxima processes, $(Z_n)_{n\geqslant0}$ is not a Markov process, nor a Markov process of any higher order.

2.2 The analogue for the standard Brownian motion $(B_t)_{t\geqslant0}$ is the so-called local time at zero $(L_t)_{t\geqslant0}$. Likewise, $(L_t)_{t\geqslant0}$ is not a Markov process, nor a Markov process of any higher order.

-