My question is the following.
An $M/M/1$ queue has arrival rate $\nu$ and service rate $\mu$, where $\rho = \nu/\mu < 1$. Show that the sojourn time (ie the queueing time plus the service time) of a typical customer is exponentially distributed with parameter $\mu - \nu$. (Call this time $T$.)
Now, we're looking at a 'typical' customer, so we consider the chain in equilibrium (eg justified by the PASTA property). Now, I am able to solve this question. For example, one simply observes that if a customer joins a queue of size $j$, then she waits $\Gamma(j+1,\mu)$. Plus in the numbers, including the cdf for $\Gamma(j+1,\mu)$, and bash out some algebraic manipulation.
I'm interested in a more refined approach, however. The cdf for $\Gamma(j+1,\mu)$ isn't so nice, I feel. Of course, since $j$ is an integer here, we can just see it as a sum of Poisson probabilities -- alternatively, one could derive the waiting time when the queue has size $j$ like this.
I'd like to prove this lemma by showing that the time $T$ has the memoryless property. We then need only calculate the expectation. The expectation of $\Gamma(\alpha,\beta) = \alpha/\beta$ for any $\alpha$ and $\beta$, so it's fairly straightforward to show that $E(T) = 1/(\mu - \nu)$. So my issue is the following.
Show directly that the time $T$ has the memoryless property.
The key to solving this problem painlessly is to observe that in equilibrium, the number of customers in the system is distributed as a geometric random variable with "success probability" $1-\rho$: $$\Pr[k \text{ customers}] = \rho^k (1-\rho).$$ So an equivalent way to state your problem is the following claim:
(In our case, $p = 1-\rho = 1 - \frac{\nu}{\mu}$ and $\lambda = \mu$, so $\lambda p = \mu - \nu$ as desired.)
In this formulation, even the direct algebraic approach to the problem is not too bad. There's also a fairly clean indirect algebraic approach: in general, when dealing with a random sum of random variables, the identity $$ \widetilde{\mathbf S}(s) = \widehat{\mathbf N}(\widetilde{\mathbf X}(s)) $$ holds, where $\widetilde{\mathbf S}$ and $\widetilde{\mathbf X}$ are Laplace transforms and $\widehat{\mathbf N}$ is a $z$-transform. In this particular case, once you plug in the relevant formulas, the result falls out.
But there's also a completely non-algebraic approach along the lines of the solution you want. Interpret $\mathbf X_1, \mathbf X_2, \mathbf X_3, \dots$ as waiting times in a Poisson process with rate $\lambda$. Then $\mathbf S$ can be interpreted as a waiting time in a process which filters each of the events in that Poisson process, keeping them only with probability $p$. By Poisson splitting, the filtered process is itself a Poisson process with rate $\lambda p$, and therefore $\mathbf S$ is exponential with rate $\lambda p$, as desired.