Does an n-order Markov chain still represent a Markov process?

Question

I am trying to understand Markov processes but am still confused by their definition. In particular, the Wikipedia page gives this example of a non-Markov process. The example is of pulling different coins out of a bag at random, and the article seems to imply that any time information is required about previous states to determine the next state, it's not a Markov process.

But isn't that what higher-order Markov chains are for? In the Wikipedia article, couldn't you have represented the process with an n-order Markov chain where n is the number of coins in the bag? (I feel sure I am wrong here but I can't see exactly how).

Disclaimer: Apologies if this question is below the normal quality - it's because I study computer science, not mathematics.

---

EDIT

Just clarifying what my confusion is. Why couldn't we represent the coins being removed from a bag with states such as:

• initial states {coin1, coin2, ..., coinN}
• states at t=1 {coin1&coin2, coin1&coin3, ..., coin(N-1)&coin(N)}

...where each state represents the coins that have been chosen so far? Probabilities could be assigned to these states that would reflect the previous states, but you still would only need to know the current state in order to predict the next one. So why isn't drawing coins from a bag a Markov process?

Answer 1

I think the idea of somehow redefining the state space is dubious. If we use the Wiki definition, or that in most texts, a discrete stochastic process is simply a sequence X_1, X_2, X_3, ... of random variables, and this particular stochastic process is said to satisfy the Markov property provided the probability that X_n = x_n depends only on the value of X_(n-1) [for the "homogeneous case"] or else on both the value of n and the value of X_(n-1) [for the "nonhomogeneous case"].

In other words, I think that to refer to a specific stochastic process and then ask if it has a certain property involves sticking to the specific sequence X_n of random variables while determining whether the stochastic process has the property, in this case the Markov property. We cannot change our sequence X_n and say "the process is Markov after all" or the like. Of course we may define another sequence of random variables Y_n = F(X_1, ..., X_n) and check if this Y_n is Markov. But that seems unrelated to whether the original sequence X_1, ... is Markov or not, at least to me.

Here's a variation on the coins out of bag example to have the full set of positive integers as the "time set". Re-set the bag to hold initially 1 quarter, 6 pennies, and 6 nickels. We progressively draw coins from the bag without replacing them, and let X_n be the sum so far drawn. There being initially 13 coins in the bag, we can say with probability 1 that X_13 = 56 cents; we simply DEFINE X_14, X_15, ... to all be 56 cents with probability 1.

Now look at X_6. There are two ways to have X_6 = 30 cents, which come from using one quarter and 5 pennies, or else using 6 nickels. In the first case the remaining coins in the bag are 6 nickels and 1 penny, and in the second case the remaining coins in the bag are 1 quarter and 6 pennies. So certainly one can say that knowing that X_6 = 30 cents, even including knowing that the "time" is 6, i.e. that this is the sixth draw, does not help in finding the probability that X_7 = 31 cents.

On the other hand, knowing the values of X_1 through X_6 inclusive, we can certainly find the probability that X_7 = 31.

Answer 2

The Wiki article is a bit misleading: If the bag has 5 each of quarters, nickels, and dimes, then after 15 draws the bag is empty, so there can be no X_16. Even though the example mentioned in the article uses the countable time space of all positive integers {1,2,3...}, the discussion indicates the coins are not being replaced after each draw. So they will run out and one does not have a distribution on {1,2,3,...} but only on {1,2,..,15}. It seems to me this dooms it as a "non Markov" process. At lease it is NOT a "non Markov process" on the set {1,2,3,...} of positive integers as claimed in the example of the Wiki article.

If the coins ARE replaced after each draw, then the state space will be {1,2,3,...} as desired, but the process is then clearly a Markov process, since given X_n the value of X_(n+1) is one of the three numbers (X_n)+5, (X_n)+10, (X_n)+25, each with probability 1/3.

Answer 3

Every random process $(\xi_n)_{0\leqslant n\leqslant N}$ of finite length $N+1$ can be realized as an inhomogenous Markov chain of order $N$.

To see this, define for every $1\leqslant n\leqslant N$ the transition kernel $Q_n$ at time $n$ by $$ Q_n(x\mid (x_k)_{1\leqslant k\leqslant N})=\mathbb P(\xi_n=x\mid\xi_{n-k}=x_k\,\text{for all}\,1\leqslant k\leqslant n). $$ Then the distribution of the process is determined by an initial distribution $\nu$, that is, the distribution of $\xi_0$, and by the sequence of kernels $(Q_n)_{1\leqslant n\leqslant N}$, using the canonical formula for Markov chains of order $N$, namely, $$ \mathbb P(\xi_{n}=x_n\,\text{for all}\,0\leqslant n\leqslant N)=\nu(x_0)\cdot\prod_{n=1}^NQ_n(x_n\mid (x_{n-k})_{1\leqslant k\leqslant N}), $$ for every sequence $(x_n)_{0\leqslant n\leqslant N}$ of states, where the values $(x_k)_{-N+1\leqslant k\leqslant-1}$ can be set to any value one wants since they are never used in the actual computation of the kernels $Q_n$.

In this representation, the present state at time $n$ in fact reflects the whole past of the process. No wonder one needs nothing more to predict the future of the process knowing its whole past than its present state, as Markov property requires.