CS5239 Chap.4 Probability Distributions for Workload Models
Probability Distributions for Workload Models
Why a performance course needs probability
How fast a computer system responds depends on what is asked of it, and what is asked of it is rarely fixed. Requests arrive in bursts, service demands vary from one job to the next, and devices fail at unpredictable moments.
Capacity planning, analytic queueing models and simulation all take a description of that variability as input, so the first job is to describe it precisely.
The lecture frames this as the groundwork for the queueing material that follows: modelling workloads and service centres, then solving the resulting models.
Random variables and their three descriptions
An experiment here is anything whose result is uncertain, and its sample space is the set of everything that could happen. A random variable attaches a real number to each outcome.
Counts, such as arrivals in a window, give discrete variables described by a probability mass function whose values are non-negative and total one. Durations, such as CPU time per request, give continuous variables described by a density whose area over an interval is the probability of landing there.
A cumulative distribution function serves both types, rising from zero to one without ever falling, and the difference of two of its values gives the probability of any interval.
Summaries and parameter roles
Expectation is the weighted average of possible values, computed with a sum or an integral.
Variance is the expected squared distance from that average, and the shortcut of subtracting the squared mean from the mean of the square is usually quicker. Taking its square root returns the standard deviation in the original units. Distribution families are steered by up to three kinds of parameter: location shifts the whole curve, scale stretches it, and shape alters its form.
The chapter tabulates six families, from the discrete uniform and Poisson to the continuous uniform, exponential, normal and triangular, with the mean and variance formula for each and the situation each typically models, such as bounded seek times or estimates known only by their limits and most likely value.
The arrival pair at the centre of queueing
The single most reused idea is that Poisson counts and exponential gaps describe one process from two sides.
If counts in any window of length t are Poisson with mean proportional to t, then waiting for the first arrival beyond t means seeing zero arrivals in that window, which yields an exponential gap whose mean is the reciprocal of the rate. That exponential gap is memoryless, so time already spent waiting does not shorten the wait still to come.
Poisson streams also behave well under routing: random splitting yields smaller Poisson streams, and merging independent ones yields a Poisson stream whose rate is the sum. These properties are what make the M/M family of queues solvable in closed form later in the course.
Choosing the right average for measurements
The lecture closes by moving from distributions to measured data.
Arithmetic means suit quantities that add up, such as execution times. Harmonic means suit rates, because averaging reciprocals keeps the result tied to total time. Geometric means keep comparisons of normalised results consistent whatever reference machine is chosen. Mode, median and quantiles round out the toolkit for describing where measured values concentrate.
Expect to apply these ideas in both open-book tests, where the challenge is less recalling a formula than choosing the correct one quickly.
What this chapter covers
- 01
Random variables as numeric outcomes of uncertain experiments
- 02
Probability mass, density and cumulative distribution functions
- 03
Expectation, variance and standard deviation
- 04
Location, scale and shape parameters across six distribution families
- 05
Poisson arrivals and exponential inter-arrival times
- 06
Memoryless property, splitting and pooling of Poisson streams
- 07
Arithmetic, harmonic and geometric means for measured data
Worked example · free
Rescaling a Poisson rate for a mail relay
- 2Rescale the rate to the 10-second window to get the Poisson mean.
- 2Apply the Poisson pmf for exactly three arrivals.
- 2Sum P(0) and P(1) for at most one, and take the complement for two or more.
- 2Use mean equals variance, then convert the rate to an exponential mean gap and an empty-window probability.
Key terms
- Random Variable
- A real-valued function that assigns a number to each outcome in the sample space of an uncertain experiment.
- Probability Mass Function
- A function giving the probability of each value of a discrete random variable; its values are non-negative and sum to one.
- Probability Density Function
- A non-negative function for a continuous random variable whose integral over an interval gives the probability of that interval and whose total area is one.
- Cumulative Distribution Function
- The function F(x) = P(X less than or equal to x), which never decreases, runs from 0 to 1, and gives interval probabilities as F(b) minus F(a).
- Variance
- A measure of spread equal to the expected squared deviation from the mean, computed as E(X squared) minus the square of E(X).
- Poisson Distribution
- A discrete distribution for the number of events in an interval, with pmf e^-lambda lambda^x / x! and mean and variance both equal to lambda.
- Exponential Distribution
- A continuous distribution for waiting times with pdf lambda e^-lambda x, mean 1/lambda and variance 1/lambda squared.
- Memoryless Property
- A property of the exponential distribution stating that P(X > t + u given X > u) equals P(X > t), so elapsed waiting time does not change the remaining wait.
- Harmonic Mean
- An average equal to n divided by the sum of reciprocals of the n values, suited to summarising rates because it stays inversely proportional to total time.
Probability Distributions for Workload Models FAQ
How do Poisson arrivals relate to exponential inter-arrival times?
They are two views of the same process. If arrivals in a window of length t are Poisson with mean lambda t, the first arrival comes after t only when that window holds zero arrivals, which has probability e^-lambda t. That is the exponential tail, so gaps are exponential with mean 1/lambda, and the reverse implication also holds.
What does the memoryless property mean in practice for a server?
It means the time a server has already waited without a request carries no information about how much longer it will wait. With exponential gaps, the conditional chance of waiting a further t seconds is the same as the unconditional chance. This is why queueing models with exponential arrivals can ignore how long the system has been idle.
When should I use the harmonic mean instead of the arithmetic mean?
Use the harmonic mean when averaging rates such as instructions per second measured over the same amount of work, because it remains inversely proportional to total execution time. Use the arithmetic mean for execution times themselves, since it is directly proportional to total time. Geometric means are reserved for comparing normalised results across reference systems.
What happens to a Poisson stream when it is split or merged?
Randomly routing each event to one of two types with probability p and 1 minus p produces two independent Poisson streams with rates lambda p and lambda times (1 minus p). Merging independent Poisson streams produces another Poisson stream whose rate is the sum of the individual rates, which keeps load balancer and multi-client models tractable.
Why is variance often computed as E(X squared) minus the squared mean?
The definition as the expected squared deviation from the mean requires knowing the mean first and then integrating or summing squared distances. The shortcut needs only two moments, which are often easier to obtain by integration by parts, and it is less error prone when a test asks for both the mean and the standard deviation.
Assessment move
Build a one-page table of the six distribution families with parameters, mean and variance, then solve one Poisson count question and its matching exponential gap question for the same rate and check that the zero-arrival probability agrees. Repeat with a rate that must be rescaled to a different window length until the conversion is automatic.
Working through Probability Distributions for Workload Models in CS5239? Sia is AskSia’s AI Computer Science tutor — ask any CS5239 Probability Distributions for Workload Models question and get a clear, step-by-step explanation grounded in how CS5239 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
