Suppose I have a sequence of iid random variable, $Z_i$ for $i=0,1,2,3…$ such that $$\Bbb P(Z_i=z)=
\begin{cases}
p, &\text{if } z=1 \\
1-p, & \text{if } z=0.
\end{cases}$$
Define $S_k=\sum^k_{i=0}Z_i$ and $\prod_n=\prod^k_{i=0}Z_i$ .
So I have to determine as an exercise in my textbook whether $X_n=S_n$ and $Y_n=\prod_n$ are markov chains.
What I tried to do is express $X_{n+1}$ in terms of $X_n$ and something only generated at time $n + 1$: $X_{n+1}=Z_{n+1}+ \sum^n_{i=0}Z_i$ from this I somehow can show that $X_n$ is markov? I'm not quite sure how to use $Z_i$'s probabilities. I'm stuck here, any help would be appreciated.
Edit:
I solved this using the reasoning in the commments below and I would like to check whether my reasoning is correct:
1) So since $X_{n+1}= X_n +Z_{n+1}$ , it follows that $X_{n+1}$ is Markov since the $ n+1$-th value depends not on any of $X_0,…,X_{n-1}$ . It only depends on $X_n$ and a random variable $Z_{n+1}$ independent of $X_0,…,X_{n-1}$.
This I kind of don't understand myself. Why is $X_{n+1}= X_n +Z_{n+1}$ independent of $X_0,…,X_{n-1}$ ? Isn't $X_n=X_{n-1} + Z_n$?(And if we iterate this to $X_1$ then we could say that $X_{n+1}$ is equal to $X_0 + Z_1 +…+Z_n+Z_{n+1}$ so this means that it does depend on those values?
For example what if I take that $Z_0,…,Z_n=(0,….,0)$ and hence $X_{n+1}$ would be equal to $0$ or $1$ but what if I choose $Z_0$ to be $1$ then the sum would be $1$ or $2$ ? So this means that it is dependent of $X_0…X_{n-1}$? Am I missing something here? Also, since the exercise gives probabilities with which $Z_i$ takes value $\{0,1\}$ , how are we supposed to use these?
2) It's markov for the same reason as 1)
I have the same doubts about the second one. What if $Z_0$ is equal to $0$? Then the whole product is equal $0$? And if $Z_0$ is 1 and all others are $1$ then it will be $1$ or $0$(depending on the $Z_{n+1}$-th value)? So this again is dependent of the preceeding values? Could someone please explain me if these answers are correct and explain why my reasoning is wrong, and maybe intuitively explain why these are Markov's. I would really like to understand this intuitively.
Also, if possible, could someone please say whether 3) $X_n= S_0+…+S_n$ and 4) $X_n= (S_n,S_0+…+S_n)$ are Markov.
I'm also interested in how could I prove these answers rigourously by definition which is if $\Bbb P(X_{n+1}=x_{n+1} | X_0=x_0,…,X_n=x_n)= \Bbb P(X_{n+1}=x_{n+1} | X_n=x_n)$ then $X_{n+1}$ is Markov
Best Answer
I think you are somehow mixing independence and conditional independence.
The idea is not that $X_{n+1}$ is independent from $X_0 ... X_{n-1}$, but that it is conditionally independent given $X_n$.
This simply means that, once you know the value of $X_n$, the previous values $X_0...X_{n-1}$ are irrelevant for the distribution of $X_{n+1}$.
Taking your example, let us assume that $X_n = 5$. Now, when we want to predict the value of $X_{n+1}$, knowing the values of $X_0...X_{n-1},Z_0...Z_{n-1}$ is completely irrelevant. Nothing changes in your prediction if $X_{n-1}=4$ or $X_{n-1}=5$, once you know that $X_n = 5$.
Now: $$\mathbb{P}(X_{n+1}=x_{n+1}|X_0=x_0,...,X_n=x_n)$$ $$\mathbb{P}( \sum_0^{n+1}Z_i =x_{n+1}|X_0=x_0,...,X_n=x_n)$$ $$\mathbb{P}( X_n + Z_{n+1} =x_{n+1}|X_0=x_0,...,X_n=x_n)$$ $$\mathbb{P}( Z_{n+1} =x_{n+1}-x_n|X_0=x_0,...,X_n=x_n)$$ $$\mathbb{P}( Z_{n+1} =x_{n+1}-x_n|X_n=x_n)$$ $$\mathbb{P}( X_{n+1} =x_{n+1}|X_n=x_n)$$ We were able to remove the conditioning on all $X_i$ for i smaller than $n$ because our probability is only a function of $Z_{n+1}$ (which is independent from them as a consequence of its independence from all $Z_i$), and of $x_n$ which is a given value.
This gives you a Markov Chain with infinite states, where every state has a transition probability of $p$ to the next state (+1) and $1-p$ to itself.
The same reasoning applies to $\Pi_n$. This will instead only have two states ${0,1}$. State $0$ is an attractor, so it has transition probability $p=1$ to itself, while from state $1$ has probability $p$ of transition to itself, and probability $1-p$ of going to state $0$.
Now, (3) is NOT a Markov chain. $$\mathbb{P}(X_{n+1}=x_{n+1}|X_0=x_0...X_n=x_n)$$ $$\mathbb{P}(X_n + S_n+Z_{n+1}|X_0=x_0 ... X_n=x_n)$$ Here, however, we have no way of knowing the value of $S_n$ just by $X_n$. Knowing for example that $X_n=10$ would simply mean that $\sum_0^nS_i=10$, but we cannot infer the value of $S_n$ without peeking at the previous "history". Therefore, the markovian property does not hold.
(4), on the other hand, is a Markov Chain (I will use $(x,y)$ notation since now $X$ is multivariate). $$\mathbb{P}(X_{n+1}=(x_{n+1},y_{n+1})|X_0=(x_{0},y_{0})...X_n=(x_{n},y_{n}))$$ $$\mathbb{P}((S_{n+1},\sum_0^{n+1}S_i)=(x_{n+1},y_{n+1})|X_0=(x_{0},y_{0})...X_n=(x_{n},y_{n}))$$ $$\mathbb{P}((S_{n}+Z_{n+1},\sum_0^{n}S_i+S_{n}+Z_{n+1})=(x_{n+1},y_{n+1})|X_0=(x_{0},y_{0})...X_n=(x_{n},y_{n}))$$ $$\mathbb{P}((x_{n}+Z_{n+1},y_n+x_{n}+Z_{n+1})=(x_{n+1},y_{n+1})|X_0=(x_{0},y_{0})...X_n=(x_{n},y_{n}))$$ Again, this is only a function of $Z_{n+1}$ (which is independent of previous $S_i$) and of $(x_n,y_n)$, and we can therefore remove conditioning on previous values as they are redundant. $$\mathbb{P}((x_{n}+Z_{n+1},y_n+x_{n}+Z_{n+1})=(x_{n+1},y_{n+1})|X_n=(x_{n},y_{n}))$$ $$\mathbb{P}(X_{n+1}=(x_{n+1},y_{n+1})|X_n=(x_{n},y_{n}))$$ Which makes it Markovian.
I hope the logical passages are clear enough, otherwise let me know!