# How to determine if a process can be modeled by a Markov Chain?

In a version of the popular arcade game “Whack-a-Mole”, the player stands in front of a board with ﬁve holes in it. The (animatronic) mole pops up brieﬂy in one of the holes each second and the player scores a point if they “whack” the mole with a soft hammer. The board is 60cm × 60cm with holes in the middle of each side and one in the middle of the board. The player stands 15cm from the front hole. The board is shown in the diagram below (the units are in 30cm increments) with the ﬁve holes shown along with the position of the player (as an X):

The mole moves as follows:

• it starts in any of the 5 holes with equal probability;

• from one second to the next it either moves to an adjacent hole (as shown by the connecting lines) or stays in its current hole, e.g., from the hole at (−1,1) the mole could move to any of the holes at (0,0),(0,1),(0,2) or stay in (−1,1). It stays in its current hole 16% of the time, otherwise it moves to one of the adjacent holes, each with equal probability. We are going to model the position of the mole as a Markov chain whose states are the (x, y)-coordinates of the holes.

QUESTION: Explain why we can use a Markov chain to model the position of the mole.

-

A discrete stochastic process, i.e. a series $(X_n)$ of random variables, is a Markov process exactly if for every event $A$ $$\mathbb{P}(X_{n+1} \in A\,|\,X_1,\ldots,X_n) = \mathbb{P}(X_{n+1} \in A\,|\,X_n) \text{.}$$ In other words, the probability distribution of $X_{n+1}$ depends only the previously observed value $X_n$, not on the whole history $X_1,\ldots,X_n$.
The described Whack-A-Mole game satisfies this because the mole doesn't remember its previous moves - it simply moves from hole to hole with certain probabilities. Thus knowing where the mole appeared at step $n$ gives you the same amount of information about where it may appear next as knowing the full history of appearances.