Engineering / Mathematics — Discrete Probability
Random Variables
Random variables, their distributions, joint behaviour and independence.
Executive summary
A random variable is a function on the sample space. It converts a probability distribution into a distribution over numbers, which is what makes averaging and concentration arguments available.
Indicator variables are the workhorse: nearly every counting argument in randomised algorithm analysis is a sum of indicators.
Learning objectives
- Define random variables and their induced distributions.
- Use indicator variables to express counts.
- State independence for random variables.
01Definition and induced distribution
Random variable
A function X : Ω → S for some set S, usually the integers or reals.
It induces a distribution on S by P(X = s) = P({ω : X(ω) = s}).
The sample space frequently disappears from view once the induced distribution is known, which is convenient and occasionally dangerous — two random variables can have identical distributions while being wildly different as functions, and their joint behaviour depends on the functions, not the distributions.
02Indicator variables
For an event A, the indicator 1_A takes value 1 on A and 0 elsewhere. Its expectation is exactly P(A), which is the bridge between counting and probability.
X = Σᵢ 1_{Aᵢ} ⇒ E[X] = Σᵢ P(Aᵢ)Because expectation is linear regardless of dependence, this identity holds with no independence assumption whatever. It is the reason so many expected-value computations in algorithm analysis are one line.
03Independence of random variables
Independent random variables
X and Y are independent if P(X = a, Y = b) = P(X = a)P(Y = b) for all a, b.
| Property | Holds when |
|---|---|
| E[X + Y] = E[X] + E[Y] | Always |
| E[XY] = E[X]E[Y] | X, Y independent |
| Var[X + Y] = Var[X] + Var[Y] | X, Y independent (pairwise suffices for sums) |
| f(X), g(Y) independent | X, Y independent |
The first row is the important one: linearity of expectation needs nothing. The second and third do need independence, and forgetting that is a standard source of wrong variance calculations.
04Frequently asked questions
Why is linearity of expectation independent of independence?
Because it is just rearranging a finite sum over the sample space. Each outcome contributes its weight times the sum of the values, and reordering summation gives the result with no structural assumption.
Can uncorrelated variables be dependent?
Yes. Let X be uniform on {−1, 0, 1} and Y = X². Then E[XY] = E[X³] = 0 = E[X]E[Y], so they are uncorrelated, yet Y is a function of X.
Do identically distributed variables behave identically?
Individually, yes; jointly, no. X and X have the same distribution as X and an independent copy, but their sum behaves completely differently — 2X versus a genuinely averaged quantity.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 104-111.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.