Verification of a process is Markovian or not? Let $\left(X_t\right)_{t \in \mathbb{N}}$ is a $(\lambda,P)$ markov chain on $\mathbb{Z}$, where $\lambda$ is the initial propability and $P$ is the transition matrix. Now define the following processes as 
$~(1)~Q_t:=\left(X_t\right)^3~,~(2) ~Y_t :=\left(X_t\right)^2~,~(3)~Z_t:=e^{X_t}~,~ (4)~W_t:=\left| X_t\right|$ Are these valid markov chains ? what is the initial probability and the transition matrix ?
For the first case i tried like this :
$$\begin{align}\mathbb{P}&(Q_{t+1}=j|Q_t=i,Q_{t-1}=i_{t-1},\ldots,Q_0=i_0)\\&=\mathbb{P}(X^3_{t+1}=j|X^3_t=i,X^3_{t-1}=i_{t-1},\ldots,X^3_0=i_0)\\&=\mathbb{P}(X_{t+1}=j^{1/3}|X_t=i^{1/3})\end{align}$$ So this is a markov chain and the initial probability will be $\mathbb{P}(Q_0=i)=\mathbb{P}(X_0=i^{1/3})=\lambda^{1/3}$ and the transition matrix would be then $p_{i^{1/3}j^{1/3}}$. Is it correct ?
And i'm confused about the other ones $Y_t;=(X_t)^2$ and $W_t;=|X_t|$ is  problematic i think as these maps are not injective...how to prove or disprove this formally and find out $(\lambda,P)$ ?
 A: Several things going on here...


*

*You have correctly proved that (1) is a Markov Chain.  A similar proof works for (3).  The proof relies on the mapping being injective.

*For (1), I would not say that the transition matrix is $P' = P_{i^{1/3}j^{1/3}}$ (which I interpret to mean, e.g. $P'_{8,8} = P_{2,2}$).  The state space of (1) consists of integers which are perfect cubes.  Each row of its transition matrix corresponds to one state.  So e.g. since $2$ is not a perfect cube, the transition matrix would not have any row corresponding to the state $2$ at all (since $2$ is not a state).  Instead, I would say its transition matrix $P'$ is still $P'_{ij}=P_{ij}$, but now row (and column) $i$ refers the the state $i^3$.  For a similar reason, I would say its initial distribution is still $\lambda$.


*

*If you insist row $i$ means state $i$ (where $i$ is a perfect cube), and you insist on having e.g. $P'_{8,8} = P_{2,2}$, then let me ask you: what is $P'_{2,2}$?  It is nonsense because $2$ is not a state.  But $P'$ is a transition matrix, it cannot have undefined entries.  You also cannot simply say the entire row $P'_{2,j} = 0$ and/or the entire column $P'_{i,2}=0$ because then $P'$ is not a stochastic matrix.

*If you need further convincing: the state space of (3) does not consist of integers (except $e^0 = 1$), so how are you gonna write its transition matrix?  Again, I would argue the transition matrix is simply $P$ but now the $i$th row represent the state $e^i$.


*For (2) and (4), your instinct is correct that the $2$-to-$1$ nature of the mapping makes them not Markov Chains.  The easiest "formal disproof" is to give a counter-example, i.e. invent an $X_t$ s.t. for some $a,b,c$ you have $P(Y_{t+1}=a \mid Y_t=b) \neq P(Y_{t+1}=a \mid Y_t=b, Y_{t-1}=c)$.  You just need one such example.


*

*Further hint: Perhaps the easiest counter-example is to have an $X_t$ that evolve deterministically but differently for positive and negative values.  Then knowing $Y_t=b$ you don't know whether the underlying $X_t$ is on the positive or negative path, but construct the example s.t. knowing two steps $Y_t=b, Y_{t-1}=c$ tells you whether $X_t$ is on the positive or negative path.



Can you finish from here?
