Probability and Stochastic Processes

Introduction

Computer systems operate under uncertainty. A network packet may be delayed, a sensor may fail, a user request may arrive at an unpredictable time, and a machine-learning classifier may produce an incorrect prediction. Probability provides a mathematical language for describing uncertainty, while stochastic processes describe how uncertain quantities evolve over time.

This chapter develops the foundations required to model uncertain events and systems. It begins with conditional probability and Bayes’ theorem, then introduces random variables and probability distributions. Expectation and variance provide numerical summaries of uncertainty. The laws of large numbers explain why observed frequencies often stabilize as experiments are repeated. Finally, Markov chains, Poisson processes, and queueing models are developed as important tools for computer science and engineering.

Learning Objectives

By the end of this chapter, you should be able to:

1. Define sample spaces, events, probability, independence, and conditional probability.
2. Apply the law of total probability and Bayes’ theorem.
3. Distinguish discrete and continuous random variables and use their probability models.
4. Calculate expectation, variance, covariance, and conditional expectation.
5. Explain the weak law of large numbers and the central limit theorem at an introductory level.
6. Construct and analyze finite-state Markov chains.
7. Model arrivals using Poisson processes.
8. Analyze simple queueing systems and interpret their assumptions and limitations.
9. Select appropriate stochastic models for practical computing problems.

1. Probability as a Model of Uncertainty

A random experiment is a procedure whose outcome cannot be predicted with certainty before it occurs. The sample space, denoted by Ω, is the set of all possible outcomes. An event is a subset of Ω.

A probability measure assigns a number P(A) to every event A such that:

• 0 ≤ P(A) ≤ 1;
• P(Ω) = 1;
• for mutually exclusive events A₁, A₂, …, P(∪Aᵢ) = ∑P(Aᵢ).

The complement of A is written Aᶜ and represents the event that A does not occur. Therefore,

For any two events A and B, the addition rule is

The subtraction prevents the intersection from being counted twice. If A and B are mutually exclusive, then P(A ∩ B) = 0.

Counting and equally likely outcomes

If a finite sample space contains N equally likely outcomes and event A contains n(A) favorable outcomes, then

This formula applies only when the elementary outcomes are equally likely. In computing, the outcomes of an experiment are often not equally likely, so a probability model must be justified rather than assumed.

2. Conditional Probability, Independence, and Bayes’ Theorem

The conditional probability of A given B is the probability that A occurs when B is known to have occurred:

Rearranging gives the multiplication rule:

The corresponding alternative form is

Two events A and B are independent if knowledge of one does not change the probability of the other. Equivalent conditions, when probabilities are defined, include

and

Mutual exclusivity and independence are different concepts. If two events have positive probability and are mutually exclusive, they cannot be independent because their intersection has probability zero.

Law of total probability

Suppose B₁, B₂, …, Bₖ form a partition of Ω: they are mutually exclusive and their union is Ω. Then, for any event A,

This law is useful when an event can arise through several distinct cases.

Bayes’ theorem

Bayes’ theorem reverses conditional probabilities:

Here, P(Bⱼ) is a prior probability, P(A | Bⱼ) is a likelihood, and P(Bⱼ | A) is a posterior probability. Bayes’ theorem is fundamental in diagnosis, spam filtering, intrusion detection, medical decision support, and machine learning.

Worked Example 1: Intrusion detection

Suppose 2% of network sessions are malicious. An intrusion detector identifies a malicious session with probability 0.95, while it incorrectly flags a legitimate session with probability 0.04. Let M denote “malicious” and F denote “flagged.” Then

P(M) = 0.02, P(F | M) = 0.95, and P(F | Mᶜ) = 0.04.

First calculate the probability of a flag:

Bayes’ theorem gives

Thus, only about 32.65% of flagged sessions are malicious. The result illustrates the base-rate effect: even a relatively accurate detector can produce many false alarms when the event being detected is rare.

3. Random Variables and Probability Distributions

A random variable X is a function that assigns a numerical value to each outcome in Ω. It is not necessarily a variable that changes freely; it is a numerical representation of a random outcome.

A random variable is discrete if it takes a finite or countably infinite set of values. It is continuous if it can take values throughout an interval or collection of intervals.

Discrete random variables

The probability mass function (PMF) of a discrete random variable X is

It satisfies p_X(x) ≥ 0 and ∑ₓ p_X(x) = 1. For a set S,

Important discrete distributions include:

For the binomial distribution, n is a positive integer, 0 ≤ p ≤ 1, and k ∈ {0, …, n}. For the Poisson distribution, λ is the expected number of events in the interval and must be nonnegative.

Continuous random variables

A continuous random variable is described by a probability density function (PDF) f_X(x). The density is nonnegative and has total area one:

Probabilities are areas over intervals:

For a continuous variable, P(X = x) = 0 for every individual x. The cumulative distribution function (CDF) works for both discrete and continuous variables:

Important continuous distributions include:

• Uniform(a,b): every value in [a,b] has equal density, f(x) = 1 ÷ (b−a).
• Exponential(λ): models a nonnegative waiting time, f(x) = λe⁻λx for x ≥ 0, λ > 0.
• Normal(μ,σ²): a symmetric bell-shaped distribution with mean μ and variance σ², where σ > 0.

The exponential distribution has the memoryless property:

This property is useful for modeling interarrival times in a Poisson process.

Joint and conditional distributions

For two random variables, the joint distribution describes their behavior together. For discrete variables,

The marginal PMF is obtained by summing out the other variable:

Independence means

for all x and y. Conditional distributions are obtained by dividing the joint distribution by the relevant marginal probability.

4. Expectation, Variance, and Covariance

The expected value or mean of a discrete random variable is

For a continuous random variable,

The expectation is a weighted average, not necessarily a value that X can actually take. For any function g,

in the discrete case, or the corresponding integral in the continuous case. This is known as the law of the unconscious statistician.

Linearity of expectation is especially important:

It holds whether or not X and Y are independent, provided the expectations exist.

Variance measures spread around the mean μ = E[X]:

The standard deviation is σ_X = √Var(X), and has the same units as X. For constants a and b,

For two variables, covariance is

and

If X and Y are independent, their covariance is zero, so variances add. The converse is not generally true: zero covariance does not always imply independence.

Worked Example 2: Packet retransmissions

Suppose a packet succeeds on each independent transmission with probability p = 0.8. Let X be the number of transmissions needed for the first success. X has a geometric distribution. Therefore,

and

The model assumes a constant success probability and independent attempts. Congestion, correlated interference, or adaptive retransmission policies would violate these assumptions.

5. Laws of Large Numbers and the Central Limit Theorem

Let X₁, X₂, … be independent and identically distributed random variables with finite mean μ. Their sample average is

The weak law of large numbers states that for every ε > 0,

Thus, the sample average converges in probability to the population mean. This explains why repeated performance measurements can estimate average latency, failure probability, or resource consumption.

The strong law of large numbers gives a stronger form of convergence: under suitable independence and integrability conditions, X̄ₙ converges to μ with probability one.

The central limit theorem (CLT) explains the approximate distribution of averages. If the variables are independent and identically distributed with mean μ and finite variance σ², then for large n,

Equivalently, X̄ₙ is approximately normal with mean μ and variance σ² ÷ n. The CLT does not say that individual observations are normal; it concerns standardized sums or averages. Dependence, heavy tails, and small samples can make the approximation unreliable.

6. Markov Chains

A stochastic process is a sequence of random variables indexed by time. A discrete-time process {X₀, X₁, …} is a Markov chain if it satisfies the Markov property:

The current state contains all information needed to predict the next state. This is a modeling assumption, not a universal property of real systems.

For a finite chain, transition probabilities are represented by a matrix P, where

Each entry is nonnegative and every row sums to one. If πₜ is a row vector containing state probabilities at time t, then

and therefore πₜ = π₀Pᵗ.

A stationary distribution π satisfies

For an irreducible, positive recurrent, aperiodic finite chain, the distribution converges to the unique stationary distribution regardless of the initial distribution. These conditions matter: reducible or periodic chains may fail to converge in the ordinary sense.

Worked Example 3: Server condition chain

Consider a server with two states: U = operational and D = failed. Suppose

• P(U → U) = 0.9;
• P(U → D) = 0.1;
• P(D → U) = 0.4;
• P(D → D) = 0.6.

Using the order (U,D),

Let π = (u,d) be stationary. From π = πP and u + d = 1,

Substituting d = 1 − u gives u = 0.8 and d = 0.2. In the long run, the server is operational 80% of the time and failed 20% of the time, assuming the transition probabilities remain stable.

Markov chains are used in web-navigation models, reliability analysis, natural-language modeling, recommendation systems, robot localization, and reinforcement learning. In a hidden Markov model, the state is not directly observed; observations are generated probabilistically from hidden states.

7. Poisson Processes

A Poisson process {N(t), t ≥ 0} with rate λ > 0 counts events over time and satisfies:

1. N(0) = 0.
2. Counts in disjoint time intervals are independent.
3. The number of events in an interval of length t has a Poisson distribution with mean λt.
4. The probability of two or more events in a sufficiently small interval is negligible compared with the probability of one event.

Consequently,

The expected number and variance of events in time t are both λt. The interarrival times are independent exponential random variables with rate λ. The expected interarrival time is 1 ÷ λ, measured in the same time unit used for λ.

Worked Example 4: API requests

An API receives requests according to a Poisson process with rate λ = 120 requests per minute. In 10 seconds, the interval length is t = 1 ÷ 6 minute, so the mean count is λt = 20. The probability of no request in 10 seconds is

The probability of at least one request is 1 − e⁻²⁰, which is approximately 0.999999998. The conversion of units is essential: using t = 10 with λ measured per minute would be incorrect.

A homogeneous Poisson process assumes a constant rate. Web traffic often varies by time of day, in which case a nonhomogeneous Poisson process with rate λ(t) may be more appropriate. Its expected count over [a,b] is ∫ₐᵇ λ(s) ds.

8. Queueing Models

A queueing system consists of arrivals, waiting space, service facilities, and departures. Important descriptors include:

• λ: arrival rate;
• μ: service rate per server;
• c: number of parallel servers;
• ρ: utilization;
• L: expected number in the system;
• L_q: expected number waiting in the queue;
• W: expected time in the system;
• W_q: expected waiting time before service.

For a single-server system, utilization is

A stable long-run system generally requires ρ < 1. For c identical servers, a basic utilization measure is ρ = λ ÷ (cμ), with stability again requiring ρ < 1 under standard assumptions.

Little’s law

Little’s law applies to a stable system in long-run average conditions:

Similarly,

The units are consistent: customers = customers/time × time. Little’s law does not require Poisson arrivals or exponential service times, although the averages must be well defined and the system must be appropriately stable.

M/M/1 queue

The M/M/1 model assumes Poisson arrivals, exponentially distributed service times, one server, unlimited waiting space, and first-come, first-served service. For λ < μ,

Here λ and μ must use the same time unit. Since W = L ÷ λ, these formulas are mutually consistent.

Queueing calculation

Suppose requests arrive at λ = 8 per second and one server processes μ = 10 per second. Then ρ = 0.8. The expected number in the system is

The expected time in the system is

The queue is highly sensitive to utilization. Increasing ρ from 0.8 to 0.9 changes L from 4 to 9, even though the utilization increases by only 0.1. This nonlinear behavior explains why systems designed near full capacity often experience severe delays.

9. Applied Case: Capacity Planning for a Cloud API

Background

This illustrative case concerns a cloud API used by a university learning platform. During a normal period, requests arrive at approximately 90 requests per second. A server can process 120 requests per second when requests are independent and service times are approximately exponential.

Problem

The operations team must determine whether one server is sufficient and estimate the delay experienced by users.

Analysis

Using an M/M/1 approximation,

The expected number of requests in the system is

The expected response-system time is

The expected queue waiting time is

Approach and solution

The calculations suggest that one server can be stable under the stated average load. However, a production decision should not rely solely on average rates. Traffic may be bursty, requests may have different service requirements, and a short-term overload may create a backlog. The team could add a second server, use load balancing, introduce admission control, or reserve capacity for peak periods.

Outcome

If the service rate remains 120 requests per second and the Poisson/exponential assumptions are reasonable, the predicted mean response time is about 33.3 milliseconds. If peak arrival rate reaches 130 requests per second, the one-server model becomes unstable because λ > μ. A second server may restore stability, but a multi-server model such as M/M/2 should then be analyzed.

Learning points

1. Average capacity must exceed average demand for stability.
2. High utilization can cause disproportionately large delays.
3. Model assumptions must be checked against measurements.
4. Tail latency may be much worse than mean latency.
5. Queueing analysis supports capacity decisions but does not replace load testing.

10. Practical Modeling, Limitations, and Governance

Probability models are abstractions. Their usefulness depends on how well assumptions match the system.

Common modeling errors

• Confusing P(A | B) with P(B | A).
• Treating mutually exclusive events as independent.
• Using a Poisson model when the event rate changes substantially over time.
• Applying M/M/1 formulas when there are multiple servers or finite capacity.
• Ignoring dependence between observations.
• Reporting a mean without variance, percentiles, or uncertainty intervals.
• Mixing units, such as requests per minute with seconds.

Simulation and empirical validation

When analytic formulas are unsuitable, simulation can estimate quantities such as queue length, delay, reliability, or risk. A sound simulation requires a clearly specified random-number model, reproducible seeds where appropriate, sufficient replications, and uncertainty estimates. Simulated results should be compared with observed data.

Probability in machine learning and AI

Classifiers often estimate conditional probabilities such as P(class | features). Calibration asks whether predicted probabilities correspond to observed frequencies. A model that assigns probability 0.8 to many cases should be correct approximately 80% of the time within that group. Poor calibration can create unsafe decisions even when classification accuracy is high.

Training data may contain historical bias, and probability estimates can affect access to services, employment, security controls, or medical support. Responsible practice requires documenting data sources, monitoring performance across relevant groups, protecting privacy, and communicating uncertainty rather than presenting predictions as certainties.

Best practices

1. Define the random experiment and unit of observation.
2. State assumptions explicitly.
3. Check independence, stationarity, and distributional fit.
4. Maintain consistent units.
5. Report variability and sensitivity, not only point estimates.
6. Validate analytical models using data or simulation.
7. Reassess models when system behavior changes.
8. Use conservative capacity margins for safety-critical systems.

Chapter Summary

Probability models uncertainty through sample spaces, events, probability measures, conditional probability, and independence. The law of total probability decomposes an event into cases, while Bayes’ theorem updates prior beliefs using evidence. Random variables translate uncertain outcomes into numerical form. Discrete variables use PMFs, continuous variables use PDFs, and CDFs apply to both.

Expectation describes long-run average behavior, variance measures dispersion, and covariance describes joint variation. The laws of large numbers justify estimation from repeated observations, while the central limit theorem explains why averages are often approximately normal. Markov chains model systems whose next state depends on the present state, and stationary distributions describe long-run state proportions under appropriate conditions.

Poisson processes model event counts with independent increments and constant rate; exponential distributions model their interarrival times. Queueing theory uses arrival and service rates to analyze congestion. Little’s law links average population, throughput, and time, while M/M/1 formulas quantify the behavior of a single-server queue. Across all applications, assumptions, units, validation, uncertainty, and ethical use of predictions are essential.

Key Terms

Sample space: Set of all possible outcomes of a random experiment.

Event: A subset of the sample space.

Conditional probability: Probability of an event given that another event has occurred.

Independence: Condition in which knowledge of one event does not alter the probability of another.

Bayes’ theorem: Formula for reversing conditional probabilities using prior probabilities and likelihoods.

Random variable: Function that assigns numerical values to random outcomes.

PMF: Probability mass function for a discrete random variable.

PDF: Probability density function for a continuous random variable.

CDF: Cumulative distribution function F_X(x) = P(X ≤ x).

Expectation: Probability-weighted average value of a random variable.

Variance: Expected squared deviation from the mean.

Covariance: Measure of joint linear variation between two random variables.

Law of large numbers: Result stating that sample averages approach the population mean under suitable conditions.

Central limit theorem: Result describing the approximate normal behavior of standardized sums or averages.

Markov chain: Stochastic process whose next state depends on the current state, not the full history.

Stationary distribution: Probability distribution unchanged by application of the transition matrix.

Poisson process: Counting process with independent increments and a constant event rate.

Utilization: Ratio of demand rate to service capacity.

Little’s law: Relationship L = λW between average population, throughput, and time.

M/M/1 queue: Single-server queue with Poisson arrivals and exponential service times.

Review Questions

Short Answer Questions

1. What is the difference between mutually exclusive events and independent events?
2. State Bayes’ theorem and identify its prior, likelihood, and posterior terms.
3. Why is P(X = x) = 0 for an individual value of a continuous random variable?
4. What does the stationary distribution of a Markov chain represent?
5. State Little’s law and explain the units of its variables.

Long Answer Questions

1. Explain conditional probability, the law of total probability, and Bayes’ theorem using an intrusion-detection example.
2. Compare Bernoulli, binomial, geometric, Poisson, uniform, exponential, and normal distributions, including a suitable application for each.
3. Derive the relationship Var(X) = E[X²] − [E(X)]² and explain why variance is measured in squared units.
4. Explain the Markov property, transition matrices, stationary distributions, and the conditions supporting long-run convergence.
5. Describe the assumptions of an M/M/1 queue and explain why delay rises sharply as utilization approaches one.

Analytical / Application Questions

1. A fraud detector flags 6% of legitimate transactions and detects 90% of fraudulent transactions. If 1% of transactions are fraudulent, calculate the probability that a flagged transaction is actually fraudulent.
2. Requests arrive at 15 per minute and a single server processes 20 per minute. Using the M/M/1 model, calculate utilization, expected number in the system, and expected time in the system. Comment on stability.
3. A two-state reliability model has transition matrix P = [0.95 0.05; 0.30 0.70], with states operational and failed. Find the stationary probabilities and interpret them for system availability.

Multiple Choice Questions with Answers

Question 1

If P(A) = 0.4, P(B) = 0.5, and A and B are independent, what is P(A ∩ B)?

A. 0.1

B. 0.2

C. 0.4

D. 0.9

Correct Answer: B. 0.2

Question 2

A disease has prevalence 1%, sensitivity 90%, and false-positive rate 5%. Approximately what is P(disease | positive test)?

A. 1.0%

B. 5.0%

C. 15.4%

D. 90.0%

Correct Answer: C. 15.4%

Question 3

Which statement correctly describes a probability density function for a continuous random variable?

A. Its value at every point is a probability greater than zero

B. Its total integral is one and interval probabilities are areas

C. Its values must sum to one over all real numbers

D. It can take negative values when the variable has a large mean

Correct Answer: B. Its total integral is one and interval probabilities are areas

Question 4

If E[X] = 4 and Var(X) = 9, what is Var(2X + 5)?

A. 9

B. 13

C. 18

D. 36

Correct Answer: D. 36

Question 5

The weak law of large numbers states that, under suitable conditions, the sample average

A. equals every observation

B. converges in probability to the population mean

C. always has zero variance

D. is exactly normally distributed for every sample size

Correct Answer: B. converges in probability to the population mean

Question 6

For a Markov chain with row probability vector πₜ and transition matrix P, which equation gives the next distribution?

A. πₜ₊₁ = Pπₜ

B. πₜ₊₁ = πₜP

C. πₜ₊₁ = πₜ + P

D. πₜ₊₁ = πₜ ÷ P

Correct Answer: B. πₜ₊₁ = πₜP

Question 7

A Poisson process has rate 6 events per hour. What is the expected number of events in 30 minutes?

A. 2

B. 3

C. 6

D. 12

Correct Answer: B. 3

Question 8

For an M/M/1 queue with arrival rate 8 per second and service rate 10 per second, what is the utilization?

A. 0.2

B. 0.8

C. 1.25

D. 18

Correct Answer: B. 0.8

Question 9

Which condition is required for the standard M/M/1 queue to be stable?

A. λ = μ

B. λ > μ

C. λ < μ

D. λ = 0 regardless of μ

Correct Answer: C. λ < μ

Question 10

A system has an average of 12 jobs in it and throughput of 4 jobs per second. By Little’s law, what is the average time in the system?

A. 0.33 seconds

B. 3 seconds

C. 8 seconds

D. 48 seconds

Correct Answer: B. 3 seconds