1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$
  • "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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.