Inferring distribution over concurrent events given arrival and duration distributions

Question

Suppose you're working on infrastructure for web service and you're tasked with determining the probability distribution of concurrent requests to your services.

In example, suppose the first request arrives at 6:05:00 am with a duration of two seconds (until 6:05:02), the second arrives at 6:05:01 am with a duration of one second (6:05:02) and the third arrives at 6:05:03 with a duration of three seconds (6:05:06.) Of these three requests, only two were concurrent (the first two.)

Suppose you have two distributions, first, when requests arrive over time and second, the length of requests. (Perhaps arrivals are uniformly distributed throughout the day and durations are distributed as lognormal.)

In a real world, if total concurrent requests exceed some threshold, one of the following would result: 1/ request dropped (0 duration), 2/ requests added to a queue (increased duration if queue time is counted), new infrastructure spin-up (increased duration to only the requests arriving duration spin-up time.)

However, to simplify the problem, suppose that computational resources are limitless and none of the above three scenarios would be realized.

How would you go about deriving the probability distribution over concurrent requests given the distributions presented (request arrivals and request durations.)

Answer 1

The probability that the next call becomes concurrent is $$P[A<D]$$ where $A$ is the time between call arrivals and $D$ is the duration of calls.

Similarly, the cdf for the lengths of concurrent calls is $$F(x)=\frac{P[x<D-A\ |\ A<D]}{P[A<D]}$$

For the example in the post, these probabilities might not have closed-form expressions.

A similar example with a closed-form expression is where $A$ is distributed exponentially with rate $\lambda$ and $D$ is distributed as $\max(0,N(\mu,\sigma))$. Then

$$P[A<D]=1-P[\lambda \sigma^2<D]\exp(-\lambda\mu + \lambda^2\sigma^2/2).$$