Modified M/M/1 Queue

Question

I have queueing system in which the arrival rate is Poisson with rate $\lambda$ and the service times are exponentially distributed with rate $\mu > \lambda$. The twist in this problem that a user who gets serviced reenters the queue with probability $1-\alpha$ where $\alpha \in (\lambda/\mu, 1)$ and leaves the system with probability $\alpha$. The goal is to 1) find the stationary distribution for the number of customers in the system and 2) use Little's formula to find the average time spent in the queue while being served for the first time.
Now I know this that approach to go about it is to modify an $M/M/1$ queue. But how? I can begin with the jump rates or transition rates $q(n,n+1)$ and $q(n,n-1)$. $q(n,n+1)= \lambda$ as in a $M/M/1$ queue. But what about $q(n, n-1)$?

Answer 1

It's occasionally convenient to switch between one of two equivalent models for a continuous-time Markov chain.

• In one model, if a state $X$ has transitions with rates $\lambda_1, \lambda_2, \dots, \lambda_n$ to states $X_1, X_2, \dots, X_n$, we first sample $n$ waiting times $\mathbf T_i \sim \textit{Exp}(\lambda_i)$. Then, if $\mathbf T_j = \min\{\mathbf T_1, \dots, \mathbf T_n\}$, we go to state $X_j$ after time $\mathbf T_j$.
• In the other model, if a state $X$ has transitions with rates $\lambda_1, \lambda_2, \dots, \lambda_n$ to states $X_1, X_2, \dots, X_n$, we first sample a waiting time $\mathbf T \sim \textit{Exp}(\lambda_1 + \dots + \lambda_n)$. Then, after time $\mathbf T$, we go to a randomly chosen state: $X_i$ with probability $\frac{\lambda_i}{\lambda_1 + \dots + \lambda_n}$.

It might be initially more natural for you to think of the M/M/1 queue as being the first situation. State $n$ has transitions to $n-1$ with rate $\mu$ and to $n+1$ with rate $\lambda$, because there's an $\textit{Exp}(\mu)$ waiting time until a customer is serviced, and an $\textit{Exp}(\lambda)$ waiting time until a new customer arrives.

But thinking about it in the other way makes the problem easier: we have a time $\mathbf T \sim \textit{Exp}(\lambda + \mu)$ until something happens, and then we go to $n-1$ with probability $\frac{\mu}{\lambda+\mu}$, and $n+1$ with probability $\frac{\lambda}{\lambda+\mu}$. If we now adjust the transition to take re-entry into account, we go to $n-1$ only with probability $\alpha \cdot \frac{\mu}{\lambda+\mu}$, and back to $n$ with probability $(1-\alpha) \cdot \frac{\mu}{\lambda+\mu}$.

Now we turn this back into the first model, where we have a $n \to n-1$ transition with rate $\alpha\mu$, an $n \to n$ transition with rate $(1-\alpha)\mu$, and an $n \to n+1$ transition with rate $\lambda$. We can ignore the $n\to n$ transition without changing anything.