# A queuing process where customers must be detected

Imagine a scenario where customers arrive in some queue according to a Poisson process with rate parameter $\lambda_{arr}$, and where the process of responding to the customers has a kind of "hysteresis" s.t. no agents are assigned to customers until at least one is detected. Here, this "detection" occurs at a rate $\lambda_{det}$ per customer. Once at least a single customer is detected, immediately all of the customers are assigned an agent that serially and sequentially handles their complaints with a "per-complaint time" given by an exponentially distributed parameter $\mu$. No further customers are admitted to the queue while this takes place. Finally, once all customers have been dealt with, the process resets.

The twist is that, the longer a customer waits in the queue prior to being assigned an agent, he'll generate new complaints that need to be dealt with by the agent at a rate $\lambda_{com}$. Thus, it's not simply the case that we have an $M/M/\infty$ queuing process once at least a single customer is detected. Let me stress that no further complaints will be thought of after a customer is assigned an agent.

Provided the above scenario, what fraction of the time is the queue empty? Can we derive a probability distribution for number of customers in the queue at a random time point?

(Update) I suppose we can decompose the above queuing scenario into a cycle of three sequential/successive stages $(...$ $\to 3 \to 1 \to 2 \to 3 \to 1 \to 2 \to$ $...)$:

(1) Time until first customer arrives in queue. The duration of this stage can be characterized by a simple exponential decay function with rate parameter $\lambda_{arr}$.

(2) Time between the first customer entering the queue and until at least one customer in the queue is detected.

(3) Time to empty the queue.

GOTO (1).

It would be really neat to be able to explicitly describe the probability distribution for the duration of events (2) and (3).

## 1 Answer

You didn't mention how many complaints each customer comes into the queue with, so I'm going to assume it's 0. This is a bit silly, but it makes the presentation nicer and the solution can be modified to be more general if necessary. I'm also going to combine your events (1) and (2), so we start at $t=0$ with no customers in the queue, and no complaints among those customers. Let $p_{n,m}(t)$ denote the probability that, after time t, we still haven't detected a customer and there are $n$ customers in the queue, with a total of $m$ complaints. Let $q_m(t)$ denote the probability that, after time t, we have detected a customer, and the customers in the queue had a total of $m$ complaints. To keep the notation sensible, I'll make the time dependence implicit and just write $p_{n,m}$ and $q_m$.

It's easier to keep track of everything with generating functions, especially if you don't worry about convergence, and I won't. So consider the following formal power series: $$\mathbf{p}(x,y) = \sum_{n,m} p_{n,m} x^n y^m \\ \mathbf{q}(y) = \sum_m q_m y^m.$$

I'll use notation like $\mathbf{p}_x(x,y)$ to denote the formal derivative of a power series with respect to $x$, and notation like $\frac{d}{dt} \mathbf{p}(x,y)$ to denote the actual componentwise derivative with respect to time. (Remember that the coefficients are time-dependent.)

From our setup, at $t=0$, we have $\mathbf{p}(x,y) = 1$ and $\mathbf{q}(y) = 0$, and we have the following equations: \begin{align} \frac{d}{dt} \mathbf{p}(x,y) &= - \lambda_{arr} (1-x) \mathbf{p}(x,y) - \lambda_{com}(1-y) x \mathbf{p}_x(x,y) - \lambda_{det} x \mathbf{p}_x(x,y) & (1)\\ \frac{d}{dt} \mathbf{q}(y) &= \lambda_{det} \mathbf{p}_x(1,y) & (2) \end{align}

Solving equation (1) gives us $$\mathbf{p}(x,y) = \exp\left(-\lambda_{arr} t + \rho(y) x \left(1 - e^{-\lambda_{arr}t/\rho(y)}\right) \right),$$ where $\rho(y) = \frac{\lambda_{arr}}{(1-y)\lambda_{com} + \lambda_{det}}.$

Messing around with this generating function should be enough to answer most of your questions.

For example, combining equations (1) and (2) tells us that $\mathbf{p}(1,y) + \left(1+\frac{\lambda_{com}}{\lambda_{det}}(1-y)\right) \mathbf{q}(y)$ is constant, so from our initial conditions it must always be $1$. Thus, $$\mathbf{q}(y) = \left(1+\frac{\lambda_{com}}{\lambda_{det}}(1-y)\right)^{-1}\left( 1 - \exp \left( \lambda_{arr}t + \rho(y)\left(1-e^{-\lambda_{arr}t/\rho(y)}\right) \right) \right).$$

The probability that we haven't detected a customer by time $t$ is $1-\mathbf{q}(1)$, so the expected time until we detect a customer is \begin{align} \int_0^\infty (1-\mathbf{q}(1))\,dt &= \int_0^\infty \exp \left( \lambda_{arr}t + \rho(1)\left(1-e^{-\lambda_{arr}t/\rho(1)}\right) \right)\,dt \\ &= \frac{\rho}{\lambda_{arr}} \left(\frac{e}{\rho}\right)^\rho \gamma(\rho,\rho) \\ &= \frac{\rho}{\lambda_{arr}} \frac{(e/\rho)^\rho}{\Gamma(\rho)} P(\rho,\rho), \end{align} where $\rho = \rho(1) = \frac{\lambda_{arr}}{\lambda_{det}}$, and $\gamma(z,x)$ is the lower incomplete gamma function, and $P(s,x)$ is the cumulative distribution function for the Gamma distribution. That's how long events (1) and (2) together take, on average.

The generating function of the distribution of the final number of complaints is $$\mathbf{\tilde q}(y) = \lim_{t \rightarrow \infty} \mathbf{q}(y) = \left(1+\frac{\lambda_{com}}{\lambda_{det}}(1-y)\right)^{-1}.$$ This is a geometric distribution, and the expected total number of complaints is $\mathbf{\tilde q}_y(1) = \frac{\lambda_{com}}{\lambda_{det}}$. So event (3), on average, takes up time $\frac{\lambda_{com}}{\mu\,\lambda_{det}}$.

• Thanks for the very nicely presented answer! If we assume that customers arrive with a single complaint, how would we modify the time for process (3) (the only place where this matters)? – Bill Jan 6 '14 at 19:55
• If customers arrive with $k$ complaints, would the average time for process (3) then just be $\frac{k\rho \lambda_{com}}{\mu \lambda_{det}}$? How might we correspondingly update the distribution? – Bill Jan 6 '14 at 21:38
• @Bill: the expected number of customers in the queue at the time a customer is detected is $\rho (e/\rho)^\rho \gamma(\rho,\rho)$. You can either work this out directly with more generating functions, or note that it has to be true because of the expected time to detection and the rate of customer arrival. So you'd add $k/\mu$ times this to the expected time for process (3), giving you $$\frac{1}{\mu}\left( \frac{\lambda_{com}}{\lambda_{det}} + k \rho \left(\frac{e}{\rho}\right)^k \gamma(\rho, \rho) \right).$$ – Anton Malyshev Jan 7 '14 at 3:06
• Just to make sure we're on the same page (given my poor writing style): once a single customer is detected, all are detected, all are assigned agents at this point, and agents handle each customers complaint sequentially (i.e. there is no "load" of complaints spread out optimally among the agents, they have to deal sequentially with a particular stack of complaints from a particular customer). Does this make sense? – Bill Jan 7 '14 at 5:21
• I have no problem with the handling of events (1) + (2), but for three, shouldn't we be talking about an average complaint load per customer (since a single agent has to handle this load) rather than a total complaint load (which we're not spreading out optimally)? – Bill Jan 7 '14 at 5:25