Random Variables

Math for CS · Axiom Academy

Discrete RVs, PMF, and independence A random variable (RV) is a function that assigns a numerical value to each outcome of a random experiment. It bridges the gap between abstract outcomes and the numbers we can compute with. Takes values in a countable set (finite or countably infinite). Number of server requests per minute: Takes values in an interval of real numbers. For continuous RVs, P(X = x) = 0 for any single point. We use probability density functions (PDFs) instead. Probability Mass Function (PMF) For a discrete RV X , the PMF tells us the probability of each value: Check: 0.1 + 0.1 + 0.1 + 0.2 + 0.2 + 0.3 = 1 Independence of Random Variables Two random variables X and Y are independent if knowing the value of one gives no information about the other: Hash functions: Ideally, hash outputs are independent of each other Random sampling: IID (independent, identically distributed) samples are the basis of Monte Carlo methods Parallel processes: Independent threads simplify probabilistic analysis If X is a random variable and g is a function, then Y = g(X) is also a random variable. The expected value of g(X) is computed via the law of the unconscious statistician : Let X = number of collisions when inserting n items into a table of size m . Understanding P(X = k) lets us analyze expected lookup time. Let X = number of comparisons in randomized QuickSort. X is a random variable whose expected value tells us average-case performance.

This is the written version of the interactive lesson above. See the full Math for CS course.