Is it a Markov process?

Question

Consider the random variable $S_t:= x+ t-\sum_{i=1}^n X_i$, where $X_i \in \mathbb{N}_0$ and i.i.d. Can I state that I deal with a Markov process here?

Answer 1

I assume that you mean $S_t = x + t - \sum_{i=1}^t X_i$, not $\sum_{i=1}^n$. The conclusion is the same either way, but the sum going up to $t$ makes more sense as a process to look at.

We pick the sequence $X_1, X_2, X_3, \dots$ independently from whichever distribution they're drawn from, but we only do it once. So two partial sums like $X_1 + X_2$ and $X_1 + X_2 + X_3$ are not independent. For example:

• $\Pr[X_1 + X_2 = 1]$ and $\Pr[X_1 + X_2 + X_3 = 0]$ can in general be positive probabilities, assuming that the $X_i$ distribution can be $0$ or $1$ with positive probability.
• If the two sums were independent, then $\Pr[X_1 + X_2 = 1 \text{ and } X_1 + X_2 + X_3 = 0]$ would also be a positive probability: the product of the two probabilities above.
• However, $\Pr[X_1 + X_2 = 1 \text{ and } X_1 + X_2 + X_3 = 0]$ must be $0$, since $X_1+X_2=1$ and $X_1+X_2+X_3=0$ together imply that $X_3 = -1$.

---

For your random process, we have $S_{t+1} - S_t = 1 - X_{t+1}$, because the other terms all cancel in the difference. This means that, given $S_t$, everything about $S_{t+1}$ is determined entirely by $X_{t+1}$.

This should let you check the definition of a Markov process and conclude that this sequence is one.