ML Interview Q Series: Analyzing No-Buffer Workstation Busy Time and Job Loss Using Renewal-Reward Theorem.
Browse all the Probability Interview Questions here.
Suppose that jobs arrive at a work station according to a Poisson process with rate λ. The work station has no buffer to store arriving jobs. An arriving job is accepted only if the station is idle at the time of arrival, and is lost otherwise. The processing times of the jobs are i.i.d. with finite mean β. Use the renewal-reward theorem to find:
a. The long-run fraction of time the work station is busy. b. The long-run fraction of jobs that are lost.
Show that these two fractions coincide and that they depend on the processing-time distribution only through its mean β.
Short Compact solution
Define a “cycle” to start whenever a job arrives and finds the station idle. In each cycle, the work station is busy for an expected duration β (the mean processing time) and is then idle for an expected duration 1/λ (the mean interarrival time under the Poisson process) until the next job arrives. Hence, one cycle has an expected length β + 1/λ, and the fraction of time the station is busy is
Next, the long-run fraction of lost jobs equals the expected number of arrivals that occur while the station is busy (which is λβ, on average, in each cycle) divided by the total expected number of arrivals per cycle (which is 1 + λβ when scaled appropriately). Thus the fraction of jobs that are lost is
These two quantities are equal:
and both depend on the processing-time distribution only through its mean β.
Comprehensive Explanation
Renewal-Reward Framework
A central insight is that each time the station becomes idle and then immediately accepts a job, we initiate a new “regenerative cycle.” Over each cycle:
The station remains busy for a (random) processing time, with mean β.
Once that service completes, the station is idle until the next job arrives, which—due to the Poisson property—happens on average after 1/λ time units.
Hence, each cycle has two distinct phases: a busy phase of mean β and an idle phase of mean 1/λ. Let T_cycle denote the random length of one cycle, and B_cycle denote the random amount of time the station is busy during that cycle. Then, by linearity of expectation:
E[T_cycle] = β + 1/λ
E[B_cycle] = β
The renewal-reward theorem states that in the long run, the fraction of time spent in a certain condition (here, “station is busy”) is E[B_cycle] / E[T_cycle]. Plugging in the values:
Fraction of time station is busy = β / (β + 1/λ).
Fraction of Jobs Lost
Next, we examine the fraction of jobs that are turned away because they arrive while the station is busy. The Poisson arrival process is memoryless, and in any interval of length x, the expected number of arrivals is λx. Since the busy portion of one cycle is β on average, the expected number of arrivals that occur during the busy period is λβ. Meanwhile, over a whole cycle, the total expected number of arrivals is 1 + λβ (namely 1 arrival that starts the cycle plus the ones that occur during the busy phase). Another equivalent way to see it is that each cycle “accepts exactly 1 job” (the one that finds the station idle) and “loses λβ on average” while busy.
Hence, by the renewal-reward theorem again, the fraction of lost jobs in the long run is:
Fraction of jobs that are lost = (λβ) / (1 + λβ).
Equivalence of Fractions
It is straightforward algebra to verify:
β / (β + 1/λ) = (λβ) / (1 + λβ).
Thus, the long-run fraction of time the station is busy equals the long-run fraction of arrivals that see the station busy (and hence are lost). This equality also confirms the “Poisson Arrivals See Time Averages” (PASTA) property for this system.
Dependence Only on Mean Service Time
Interestingly, neither the specific shape of the service-time distribution nor its higher moments affect these fractions. All that matters is the mean processing time β. This is because the renewal-reward argument only requires the expected length of a busy period and the memoryless arrivals of the Poisson process.
Follow-up Question 1: What if the arrival process is not Poisson?
If the arrival process were not Poisson, the property that “arrivals see time averages” might no longer hold. In particular, under many non-Poisson processes (e.g., a renewal arrival process with non-exponential interarrivals), the fraction of jobs that arrive while the station is busy may differ from the fraction of time the station is busy. The renewal-reward theorem can still be applied to calculate the fraction of time the station is busy, but it may not be correct to identify that fraction with the fraction of arrivals that see it busy unless the arrival process is memoryless or has the PASTA property.
Follow-up Question 2: Do we need to assume anything about the distribution of service times besides having a finite mean?
For the fraction of time the station is busy, we only require a finite mean β of the service times. No specific assumption about the service-time distribution (exponential, deterministic, or otherwise) is needed. The key step is that one cycle busy period has expected length β, and the idle period (due to Poisson arrivals) has expected length 1/λ. Thus the result uses only the mean of the processing-time distribution.
Follow-up Question 3: How would we simulate this system to empirically verify these fractions?
We can simulate by incrementing time in events: arrivals and service completions. Each arrival either seizes the machine if idle or is lost if the machine is busy. Below is a simple Python code snippet illustrating such a simulation:
import numpy as np
def simulate_no_buffer(lambda_rate=2.0, beta=1.0, num_jobs=10_000_00):
"""
Simulate a workstation with Poisson arrivals (rate=lambda_rate),
i.i.d. service times with mean=beta (using Exponential for simplicity),
and no buffer. Returns the fraction of time busy and fraction of lost jobs.
"""
np.random.seed(42) # for reproducibility
# Statistics
total_time = 0.0
busy_time = 0.0
lost_jobs = 0
total_arrivals = 0
# State
station_busy = False
time_next_service_ends = np.inf
# Generate initial next arrival time
time_next_arrival = np.random.exponential(1.0 / lambda_rate)
while total_arrivals < num_jobs:
# Determine which event happens next: arrival or service completion
next_event_time = min(time_next_arrival, time_next_service_ends)
dt = next_event_time - total_time
# Accumulate busy time if station is busy
if station_busy:
busy_time += dt
total_time = next_event_time
if time_next_arrival < time_next_service_ends:
# An arrival event
total_arrivals += 1
if not station_busy:
# Station is idle, job is accepted
station_busy = True
service_duration = np.random.exponential(beta)
time_next_service_ends = total_time + service_duration
else:
# Station is busy, job is lost
lost_jobs += 1
# Schedule next arrival
time_next_arrival = total_time + np.random.exponential(1.0 / lambda_rate)
else:
# A service completion event
station_busy = False
time_next_service_ends = np.inf
fraction_time_busy = busy_time / total_time
fraction_jobs_lost = lost_jobs / total_arrivals
return fraction_time_busy, fraction_jobs_lost
if __name__ == "__main__":
frac_busy, frac_lost = simulate_no_buffer(lambda_rate=2.0, beta=1.0, num_jobs=500_000)
print(f"Fraction of time busy: {frac_busy:.4f}")
print(f"Fraction of jobs lost: {frac_lost:.4f}")
In this simulation:
We track the time of the next arrival (drawn from an exponential distribution with parameter lambda_rate) and the time the current job (if any) will finish.
If an arrival happens when the station is idle, it begins service; otherwise, it is lost.
We keep track of how much time is spent busy and how many jobs are lost.
After a large number of arrivals, we compute the fraction of time the station was busy and the fraction of jobs that were lost. These should converge to β / (β + 1/λ) and λβ / (1 + λβ), respectively, in line with our theoretical results.
Follow-up Question 4: What happens if λβ ≥ 1?
If λβ ≥ 1 in this no-buffer scenario, the fraction of time that the station is busy is quite high, and the fraction of jobs lost can also be high. Unlike a queue with infinite waiting space, you do not have to worry about stability in the classic sense (there is no infinite queue). Jobs that arrive when the station is busy are simply lost. Hence, the system does not become “unstable” in a classic queueing sense—any job not processed is discarded, and the station never has a backlog. However, in practice, one may find that nearly all arriving jobs are lost if λβ is large, and the server is almost always busy.
Follow-up Question 5: Can the approach generalize to multiple servers or buffer sizes bigger than zero?
Once a queue has either multiple servers or a positive buffer capacity, the analysis typically requires more nuanced queueing theory (M/M/c queue, M/G/1 queue, etc.). The neat equality between “fraction of time busy” and “fraction of lost jobs” holds particularly simply for the single server with zero buffer (the Erlang loss model M/G/1/0). In multi-server or positive-buffer scenarios, the fraction of lost jobs depends on more intricate system states. The renewal-reward approach can still be used in certain cycle definitions, but the computations can become more involved.
Below are additional follow-up questions
What if the arrival rate λ is time-varying rather than constant?
A time-varying arrival rate λ(t) breaks the memoryless property that underpins the simple fraction-of-time and fraction-of-lost-jobs results. In particular, the station may still have no buffer, but the idle intervals between jobs would no longer have a constant average duration 1/λ. Instead, the length of the idle period could depend on the instantaneous arrival rate at different times.
A key complication is that, if λ(t) increases during the busy period, more jobs might arrive (and be lost) than if λ(t) decreases. If λ(t) is periodic (e.g., with daily or weekly cycles), the fraction of time busy might also reflect these fluctuations. In such scenarios, the renewal-reward argument still applies on a cycle-by-cycle basis if you define a “regenerative cycle” the same way (job arrives and finds station idle). But since the arrival rate is no longer constant, you would need to integrate or average the time-varying λ(t) over the busy period to estimate the total lost arrivals.
In real-world applications with seasonal or time-varying demand, you may need to analyze the system via time-dependent queueing theory, discrete-event simulations, or approximate fluid/diffusion models. One subtlety is that job arrivals might cluster in high-demand intervals, making it more likely that new arrivals will be lost in those intervals. Hence, even if the long-run average arrival rate is the same, the fraction of lost jobs could differ from the simpler constant-rate formula λβ / (1 + λβ).
Potential pitfalls:
Overlooking large spikes in λ(t) can underestimate loss.
Assuming a constant rate might be acceptable if λ(t) changes slowly relative to service times, but if it changes rapidly, the system may exhibit complicated transient behaviors.
What if there are different classes of jobs with different service-time distributions?
When multiple job classes exist, each class can have a different mean service time and potentially different arrival rates (still possibly Poisson per class). In the zero-buffer scenario, the fundamental approach remains: a job is admitted only if the station is idle at arrival. However, cycles might have variable lengths since each admitted job’s service time depends on the class of the job that arrived.
In a multi-class setting with class-specific arrival rates λ_i and mean service times β_i, you might define a regenerative cycle as “the station becomes idle, then the next job to arrive belongs to some class i,” with probability proportional to λ_i. Once accepted, the workstation is busy for a random time with mean β_i. Then the idle period begins, which, under a Poisson superposition assumption, has mean 1/(∑λ_i).
A potential source of complexity is that each cycle might have different lengths depending on which class arrived to start the cycle. You might use the law of total expectation, weighting each class by its fraction of accepted arrivals, to compute an overall average busy time and idle time.
Potential pitfalls:
Skipping the need to do a conditional analysis per job class.
Failing to realize that if one job class has a very large β_i, it increases the fraction of time busy substantially and can also increase overall lost arrivals.
How does the analysis change if there is a non-negligible setup time whenever the station transitions from idle to busy?
In some practical systems, there may be a setup or startup delay S each time the workstation begins processing after being idle. If a job arrives and the station is idle, you enter a “setup phase” of length S before actual processing starts. The machine is effectively unavailable to new jobs (still no buffering) during that setup phase, so any job arriving then would also be lost.
One can treat this setup time as an additional busy-like interval in each cycle. A cycle would then consist of:
A (stochastic or deterministic) setup time S.
The regular service time with mean β.
The idle period until the next arrival that finds the station idle.
The mean length of a cycle becomes S + β + 1/λ. During S + β, the workstation is “not accepting any arrivals” (either in setup or actual service). Hence, the fraction of time busy-or-in-setup is (S + β) / (S + β + 1/λ). If we interpret “busy” strictly as “processing a job,” then the fraction of time truly in service is β / (S + β + 1/λ). However, jobs arriving during S are lost, which effectively raises the fraction of lost arrivals.
Potential pitfalls:
Confusion over whether the setup time counts as busy or idle.
Overlooking that arrivals during setup are lost, which can drastically increase the loss fraction if setup times are long.
How do correlated arrivals or bursty arrival processes (e.g., self-similar traffic) affect the analysis?
Bursty or self-similar arrival processes, often observed in network traffic or certain load scenarios, deviate from the independent increments property of Poisson processes. As a result, arrivals may cluster in bursts. Whenever the station is busy, a burst of arrivals might occur, leading to a large number of lost jobs. Then, there might be lulls (periods with very few arrivals).
The standard fraction-of-time-busy formula from the renewal-reward theorem can still be applied to compute the station’s fraction of time busy if you can define a proper regenerative cycle (job arrives and finds station idle). However, the fraction of jobs lost can differ from that fraction-of-time-busy if arrivals cluster disproportionately while the station is busy.
In particular, the memoryless arrival assumption that leads to “arrivals see time averages” (i.e., PASTA) no longer holds for correlated or bursty processes. An arrival is more likely to land in a burst, which might coincide with the machine being busy. Therefore, the lost-job fraction can be higher than you would predict by simply taking the ratio of busy time to total time.
Potential pitfalls:
Using the Poisson-based fraction-of-lost-jobs formula λβ / (1 + λβ) blindly.
Underestimating the fraction of jobs lost when bursts cause frequent arrivals during busy periods.
Could we incorporate a cost model where the “reward” is the number of processed jobs and the “penalty” is lost jobs?
Instead of just tracking fractions of lost jobs or fractions of time busy, a real-world scenario might attach a profit or cost structure:
Each successfully processed job yields some revenue R.
Each lost job might incur a penalty (or represent an opportunity cost) C.
Over a cycle of length T_cycle, you would then define the expected “reward” as R minus any penalty for lost arrivals. For the Poisson case, the expected number of arrivals during the busy period is λβ (assuming mean busy time β). All of those are lost except the first one that was admitted to start the busy phase. If the penalty for each lost job is C, the expected penalty per cycle is approximately C(λβ).
The renewal-reward theorem can then yield the long-run average net reward per unit time = (Expected reward or cost over one cycle) / (Expected length of one cycle).
Potential pitfalls:
Not considering how large the penalty C might be compared to R.
Misinterpreting the cycle structure if the cost needs to be allocated differently for partial cycles, or if the machine is shut down.
What if the service times are correlated with each other (e.g., a job with a longer service time is likely to be followed by another that also has a longer service time)?
If the service times are no longer i.i.d. but have some dependency structure (e.g., correlation in job lengths), then the cycle analysis can become more complicated. In principle, the fraction-of-time-busy formula from renewal-reward still holds if we properly define each cycle as “start busy → back to idle.” However, the expected length of the busy portion in a cycle may not be simply the average of a single job’s processing time if, for example, acceptance of one job can lead to a chain reaction of back-to-back correlated tasks.
But in the zero-buffer model, only one job is ever in service at a time, so a single busy period corresponds exactly to that single job’s service time. Correlation between successive jobs’ service times might not matter as much because you accept at most one job per cycle anyway. The main requirement remains that each cycle has one busy period with an expected duration that you can still call β, but you must confirm that the correlation does not alter the distribution of the busy period when a job arrives to find the station idle.
Potential pitfalls:
Incorrectly averaging multiple correlated service times if the system might accept more than one job in a single cycle in other models (though not in a zero-buffer scenario).
Failing to verify that the distribution of service time for “the job that arrives and gets admitted” is indeed the same as the unconditional distribution.
How can we handle a situation where the workstation can partially process a job, pause, and then resume?
If the system is allowed to preempt the service or if there is partial processing (e.g., the job can be split into sub-tasks), the zero-buffer model no longer matches the scenario exactly. The concept of “arriving job is accepted only if idle” might not apply if the machine can pause one job, switch to another, or hold partial completions.
You would have to define precisely when a newly arriving job can displace a partially processed job. If preemption is not allowed, the machine is effectively still busy until the job completes. If preemption is allowed, you might or might not lose the partial progress made on the current job. The fraction-of-jobs-lost measure also changes meaning if you can partially accept arrivals.
In practice, for a no-buffer, single-machine scenario with partial processing, you might still treat the machine as “busy” for the entire time from job acceptance to completion. New jobs arriving in that interval are lost. However, if partial acceptance is truly possible, then the situation is more akin to a scheduling problem with continuous or time-sliced allocation. The fraction-of-time-busy might remain close to 1 if there is always partial work to do, but analyzing job losses requires specifying how partial acceptance is decided.
Potential pitfalls:
Assuming the same formula for fraction-of-lost-jobs if partial acceptance is allowed. This formula can be invalid because multiple jobs might share the machine in subdivided intervals.
Overlooking overheads in switching or context switching between partially processed tasks.
How do we extend these results when service times might become infinite if a job fails or restarts repeatedly?
In rare but practical cases (e.g., computing tasks that might get stuck in a loop or produce repeated errors), a job might never successfully complete. Such scenarios can cause the workstation to remain busy indefinitely, effectively blocking all future arrivals. In a theoretical model, a single infinite service time leads to zero throughput after that event, and the fraction-of-lost-jobs would approach 1 as time goes on.
One way to handle this analytically is to impose an assumption of almost sure finiteness of service times. Alternatively, you can incorporate a mechanism to detect job failure after some maximum threshold, at which point the job is forcibly terminated. This effectively bounds the service time.
Potential pitfalls:
Failing to realize that a single “never ending job” starves the system forever.
Not modeling real-world fail-safes, where such a job might be killed after a maximum time.