In an M/M/1 queue, we know that inter-arrival times are exponentially distributed, and that service times are the same. What is the distribution of to-server inter-arrival times (aka service start times)? Put another way, what is the distribution of times between when a server starts helping a customer?
Some intuition:
if $\lambda \ll \mu$, then there is rarely a wait, and the server just experiences arrivals at the same rate as arrivals to the queue.
if $\lambda \approx \mu$, then the server is almost always busy and experiences arrivals at the same rate of service/arrivals.
However, when $\lambda < \mu$, there will be cycles where customers arrive to both empty and occupied lines. So, the server will at times see the true arrival rate $\lambda$, and at other times, arrivals to them will be $\mu$
Burke's Theorem shows that the distribution of departure time from a server is the same as arrival times. One proof this theorem use weighted sums, and the probability that the server is busy. I think there may be a similar approach to solve this problem.
Best Answer
It's a mixture of three distributions, and can be found pretty easily by brute force, if one allows oneself to handwave over some important details (e.g., "is $\lambda < \mu$").
Let $n$ be the number of customers in the system; $n=0$ means no-one is being served or waiting, $n=1$ means one customer is being served but no-one is waiting, etc. Let $p_n$ be the steady-state (assumed from here on) probability that $n$ customers are in the system.
Clearly, if $n=0$, the time $t$ to the next service start is distributed $f(t|n=0) = \text{Exp}\{\lambda\}$, and if $n \geq 2$, the time to the next service start is distributed $f(t|n \geq 2) = \text{Exp}\{\mu\}$, since the next service will start immediately upon completion of the current one. If $n=1$, the time to the next service start is the maximum of the time to the next arrival and the time to the next service completion. This latter distribution has the following easily-derived form:
$f(t|n=1) = \lambda e^{-\lambda t} + \mu e^{-\mu t} - (\lambda + \mu)e^{-(\lambda+\mu)t}$
The mixture probabilities correspond to $p_0$, $1-p_0-p_1$, and $p_1$ respectively. The probabilities $p_0$, $p_1$, and $1-p_0-p_1$ can be written as:
$$p_0 = \left[\sum_{k=0}^{\infty}\left({\lambda \over{\mu}}\right)^k\right]^{-1} = 1 - {\lambda\over{\mu}}$$ $$p_1 = \left({\lambda \over{\mu}}\right)p_0 = {\lambda\over{\mu}} - \left({\lambda\over{\mu}}\right)^2$$ $$1-p_0-p_1 = \left({\lambda\over{\mu}}\right)^2$$
Writing the whole thing out, with some rearranging of terms, gives:
$$f(t) = {\lambda(\mu-\lambda)\over{\mu}}\left(e^{-\lambda t} + e^{-\mu t}\right) + \left({\lambda\over{\mu}}\right)^2\left(\lambda e^{-\lambda t} + \mu e^{-\mu t} - (\lambda+\mu)e^{-(\lambda+\mu)t}\right)$$
My source for probability formulae was Kleinrock, Queuing Systems.
Edit: The derivation of $f(t|n=1)$ is below, written as the derivation of the maximum of two independent exponential variates $x \sim \text{Exp}\{\lambda\}$ and $y \sim \text{Exp}\{\mu\}$. The corresponding CDFs are $F_X(x) = 1-\exp{\{-\lambda x\}}$ and $F_Y(y) = 1-\exp{\{-\mu y\}}$.
We'll approach this using the "cumulative distribution function technique". Note first that the statement "$\max(x,y) \leq t$" is equivalent to "$x \leq t$ and $y \leq t$". The probability that $\max(x,y) \leq t$ is just the product of the probabilities that $x \leq t$ and $y \leq t$ (as $x$ and $y$ are independent.) Writing this out gives:
$$F_{\max(x,y)}(t) = \left(1-e^{-\lambda t}\right)\left(1-e^{-\mu t}\right) = 1 - e^{-\lambda t} - e^{-\mu t} + e^{-(\lambda+\mu) t}$$
and taking the derivative with respect to $t$ gets you to the density function.