Proving that a process is not a Markov chain. I want to prove that the queue length at a store is not a Markov Chain.
$Q_k$ is the queue length at time instant $k$, $V_k$ is the number of arrivals. At every time instant one customer is processed. Now if the queue length at $k= 2$ is $Q_2 = 3$. So at the next time instant the queue length would be $Q_3 = 2 + V_3$.
Here $V_k$ is a discrete parameter MC with $6$ states: $\{0,1,...,5\}$. This states depends on $5$ gates which can be either 'ON' or 'OFF'.
Although I know the answer that $Q_k$ is not a MC but I cant figure it out why.
How can I mathematically see/derive this using the definition? Any hint is highly appreciated. Thank u. 
 A: I think the answer will depend on the matrix $\mathcal{P}$.  If all the transition probabilities $p_{ij}$ for the gates are $1/2$, then all the $G_{mk}$ are independent, hence all the $V_k$ are independent, hence $Q_k$ is a random walk and hence Markov.
So let's consider an explicit example.  Say $\mathcal{P} = \begin{pmatrix} 3/4 & 1/4 \\ 1/4 & 3/4 \end{pmatrix}$.
Now suppose you observe that $Q_0 = 0$ and $Q_1 = 4$.  What can you deduce about the state of the gates at time 1 (i.e. what are $G_1^1, \dots, G_1^5$?)  As a result, given this observation, what is the conditional probability that $Q_2 = 8$?  (What has to happen to the gates in order to have $Q_2 = 8$?  What is the probability that this happens?)
On the other hand, suppose you observe $Q_0 = 5$ and $Q_1 = 4$.  Now what do you deduce about the gates?  Now what is the conditional probability that $Q_2 = 8$?
By this argument, you can show that
$$P(Q_2 = 8 \mid Q_0 = 0, Q_1 = 4) \ne P(Q_2 = 8 \mid Q_0 = 5, Q_1 = 4).$$
If (1) held, these would have to be equal, since they would both equal $P(Q_2 = 8 \mid Q_1 = 4)$.  So this shows that (1) does not hold, and the process is not Markov.
