1

It is given that $$X_n = \min(X_{n-1}, X_{n-2}) + \epsilon_n \quad \forall n\ge2 $$

where $X_0=X_1=0$, and $\{\epsilon_n:n\ge2\}$ are i.i.d random variables equal to either -1 or 1 with probability $1/2$.

The question asks if $(X_n:n\ge0)$ is a Markov chain. If not, construct a new stochastic process $(Y_n:n\ge0)$ such that

(i) $(Y_n:n\ge0)$ is a Markov chain, and

(ii) for every $n\ge0$, $X_n$ can be identified if $Y_n$ is known

My attempt to solve this problem

$(X_n:n\ge0)$ is not a Markov chain becuase when we subsititue $X_3=\min(\epsilon_2,0)+\epsilon_3$ and $X_2=\epsilon_2$ into $X_4$, we get: $$X_4 = \min(\min(\epsilon_2,0)+\epsilon_3),\epsilon_2)+\epsilon_4$$ which depends on the previous two time-steps.

Now, if we want to know $X_n$, we need to know $\epsilon_{n-1}$ and $\epsilon_{n-2}$. Possible well-known Markovian $Y_n$ are

  1. $Y_n = \sum^n_2(\epsilon_i)$ and

  2. $Y_n =\min(\epsilon_{n-1},\epsilon_{n-2},...,\epsilon_1)$

However, knowing $Y_n$ in these cases won't get $\epsilon_{n-1}$ and $\epsilon_{n-2}$ explicitly, and $X_n$ cannot be determined without knowing exactly what $\epsilon_{n-1}$ and $\epsilon_{n-2}$ are.

To get a more explicit knowledge on $\epsilon_{n-1}$ and $\epsilon_{n-2}$, we need to have something like $$Y_n =\epsilon_{n-1}+\epsilon_{n-2}$$

Then if $Y_n = 2$, we know that $\epsilon_{n-1}=\epsilon_{n-2}=1$;

if $Y_n = -2$, $\epsilon_{n-1}=\epsilon_{n-2}=-1$;

if $Y_n = 0$, one of the $\epsilon$ is 1 and -1 for the other one.

However, this $Y_n$ is not Markovian in this case.

Can anyone gives me some hints?

Ilmari Karonen
  • 26,117
Raven Cheuk
  • 264

1 Answers1

1

Your original process $X_n = \min(X_{n-1}, X_{n-2}) + \epsilon_n$ is a second order Markov chain, where each state depends on the previous two states. Such $k$-th order Markov chains can be converted into normal (first order) Markov chains by replacing each state of the original chain with an $k$-element vector/tuple containing the original state and the other $k-1$ previous states that the next state will depend on.

In your example, the first order version of your chain would have states consisting of the pairs $Y_n = (X_n, X'_n)$, with the initial state $Y_1 = (X_1, X'_1) = (0, 0)$ and the update rule: $$\begin{aligned} X_n &= \min(X_{n-1}, X'_{n-1}) + \epsilon_n \\ X'_n &= X_{n-1}. \end{aligned}$$

(I deliberately reused the symbol $X_n$ here, since the $n$-th state of your original second order chain will indeed simply be equal to the first component of the state vector $Y_n$. You can easily verify this just by substituting the second line of the update rule given above into the first line.)

In the same way, if you had, say, the third order Markov chain $X_n = \min(X_{n-1}, X_{n-2}, X_{n-3}) + \epsilon_n$, you could turn it into a first order Markov chain by expanding the state into a three-element vector $Y_n = (X_n, X'_n, X''_n)$ and the update rule: $$\begin{aligned} X_n &= \min(X_{n-1}, X'_{n-1}, X''_{n-1}) + \epsilon_n \\ X'_n &= X_{n-1} \\ X''_n &= X'_{n-1}. \end{aligned}$$ The same mechanical conversion process can be applied to any higher order Markov chain with a dependence on some finite number of previous states. (Of course, there's also nothing special about the $\min$ function here; it can be replaced with any arbitrary function $f$ of the previous $k$ states.)

Ilmari Karonen
  • 26,117