# Markov Chains examples

So I've been given four examples of stochastic processes, and asked which are Markov chains:

The four examples are henceforth:

• "Keep rolling a die and let $$X_n$$ be the value of the n-th roll."

• "Keep tossing a coin, let $$X_n$$ be the number of heads so far."

• "Let $$X_0$$ $$=$$ $$X_1$$ $$=$$ $$1$$ and then for each $$i$$ $$\geq$$ $$2$$ toss a coin and either let $$X_i$$ $$=$$ $$X_{i-1}$$ $$+$$ $$X_{i-2}$$ [heads] or $$X_i$$ $$=$$ $$0$$ [tails]"

• "Suppose you number all the websites in the world now 0,1,2,...,N. Let $$X_t$$ be the website you are currently on. You roll a die and if the answer is $$6$$ then pick a random site to visit $$\in$$ $$[0,N]$$ otherwise browse to a new site by clicking one of the current page's links (equiprobably). Call this next site $$X_{t+1}$$."

The only one I can see clearly isn't a Markov chain is Example 3, as to determine $$X_i$$ you need to know $$X_{i-1}$$ and $$X_{i-2}$$; so only knowing $$X_{i-1}$$ is not sufficient. Apparently you can also check is using the definition of the Markov property. But I'm not sure how to do this.

I'm quite new to this topic, but a bit confused, if anyone could help me out. I think that Examples 1 and 2 are Markov Chains, but I wouldn't know how to explain explicitly why. And Example 4 I have no idea.

• "Keep rolling a die and let $$X_n$$ be the value of the n-th roll."

Whereas the probability of the value of the (n+1)-th roll don't depend on the previous roll (no chain), knowing the full history is not helpful, too. Something as "useless Markov chain."

• "Keep tossing a coin, let $$X_n$$ be the number of heads so far."

The prediction of the "number of heads so far" after the (n+1)-th toss depends fully on the "number of heads so far" after the previous toss.

• "Let $$X_0$$ $$=$$ $$X_1$$ $$=$$ $$1$$ and then for each $$i$$ $$\geq$$ $$2$$ toss a coin and either let $$X_i$$ $$=$$ $$X_{i-1}$$ $$+$$ $$X_{i-2}$$ [heads] or $$X_i$$ $$=$$ $$0$$ [tails]"

You answered it correctly.

• "Suppose you number all the websites in the world now 0,1,2,...,N. Let $$X_t$$ be the website you are currently on. You roll a die and if the answer is $$6$$ then pick a random site to visit $$\in$$ $$[0,N]$$ otherwise browse to a new site by clicking one of the current page's links (equiprobably). Call this next site $$X_{t+1}$$."

The prediction of $$X_{t+1}$$ depends only on $$X_t$$ (the previous history don't matter).

So the answers are yes, yes, no, yes, respectively.