For a M/M/1 queue, we let $N_q(t)=(Q(t)-1)_+$ be the the number in the queue exclusive of the customer being served, where $Q_{ij}(t)$ is the probability of going from state $i$ to $j$ in time $t$. How do we show that the process $\{N_q(t), t\geq0\}$ is not a Markov chain?
My attempt so far: we recall that a process $\{X(t), t\geq0\}$ is Markov if for all $s, t \geq 0$
$P[X(t+s)=j|X(s)=i, X(u) = x(u), 0 \leq u < s] = P[X(t+s)=j|X(s)=i]$
Informally, we may reason that $N_q(s) = 0 \implies Q(s) \in \{0, 1\}$. For (very) small $h>0$, if $N_q(u) = N_q(s-h)=1$, then we can be almost certain that $Q(s)=1$, since it is unlikely that between time $s-h$ and $s$ the process had enough time to change states twice. But then, considering $P(N_q(t+s)=j|Q(s)=0)\neq P(N_q(t+s)=j|Q(s)=1)$, the value of $N_q(u), 0 \leq u < s$, matters for determining $N_q(t+s)$ and hence the Markov property does not hold.
However, I don't think my attempt is very formal. Could someone make a more precise argument?