Probability
Welcome to Data Mining. We will study how machine-learning models work, from linear regression to transformers and reinforcement learning. The course assumes some linear algebra and programming experience. We will review the probability and matrix calculations as we need them.
Each topic has a reading, a demo, and a problem set. The reading explains the mathematics, the demo shows it in code, and the problems give you practice working through the calculations yourself. Quizzes and exams check your understanding. For the project, you will analyze data and explain what you found.
We start with probability. A measurement may change when we repeat an experiment, and a model’s error may change when we collect a different dataset. Random variables let us describe that variation. Expectation, variance, and covariance help us calculate what happens when we average several observations.
From Events to Random Variables
An event is a set of possible outcomes. If \(A\) is rain tomorrow and \(B\) is carrying an umbrella, then \(A\cap B\) means both occur and \(A\cup B\) means at least one occurs. Their probabilities obey \[ 0\leq \Pr(A)\leq1, \qquad \Pr(\neg A)=1-\Pr(A), \] and \[ \Pr(A\cup B)=\Pr(A)+\Pr(B)-\Pr(A\cap B). \] Conditioning restricts attention to outcomes where another event occurred: \[ \Pr(A\cap B)=\Pr(B)\Pr(A\mid B) = \Pr(A)\Pr(B \mid A) \]
If \(\Pr(A)>0\) and \(\Pr(B)>0\), conditioning the same intersection in both orders gives Bayes’ rule: \[ \Pr(A\mid B)=\frac{\Pr(B\mid A)\Pr(A)}{\Pr(B)}. \]
It combines a prior probability \(\Pr(A)\) with the likelihood of evidence \(\Pr(B\mid A)\) to obtain the posterior \(\Pr(A\mid B)\). Classification and maximum-a-posteriori estimation will use this reversal later. For now, \(\Pr(A\mid B)\) and \(\Pr(B\mid A)\) answer different questions.
Events \(A\) and \(B\) are independent when learning one does not change the probability of the other. In that case \(\Pr(A\cap B)=\Pr(A)\Pr(B)\). Independence requires justification: for example, rain generally changes the probability that someone carries an umbrella.
The overlap contains the outcomes where both events occur. Conditioning on one event restricts attention to its circle.
A random variable turns an uncertain outcome into a number. It might record a measurement, a count, or the loss of a prediction on a randomly selected observation. For a discrete variable \(X\), its distribution assigns probability \(\Pr(X=x)\) to each possible value \(x\). For any discrete random variable \(Z\), write \(\mathcal S_Z=\{z\in\mathbb R:\Pr(Z=z)>0\}\) for its support, which may be finite or countably infinite. A sum of random variables is another random variable, whose distribution depends on the distributions of its terms and their dependence.
Random variables may also be continuous. A Gaussian random variable \(X\sim\mathcal N(\mu,\sigma^2)\) has density \[ \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right). \] The parameter \(\mu\) sets its center and \(\sigma\) sets its width. We will use this distribution later as a model for measurement noise, but our rules for expectation and variance do not require a Gaussian distribution.
Expectation Locates the Balance Point
For a discrete random variable \(X\) with \(\sum_{x\in\mathcal S_X}|x|\Pr(X=x)<\infty\), the expectation is the probability-weighted average of its possible values: \[ \mathbb E[X]=\sum_{x\in\mathcal S_X} x\Pr(X=x). \] For a continuous variable the corresponding operation is an integral against its density. Expectation locates the center of a distribution. Individual observations can fall on either side. The expectation need not be a value the variable can actually take.
Claim: For random variables \(X,Y\) with \(\mathbb E[|X|],\mathbb E[|Y|]<\infty\) and constants \(a,b\), expectation is linear: \[ \mathbb E[aX+bY]=a\mathbb E[X]+b\mathbb E[Y]. \]
Proof
For discrete variables, begin from the definition of expectation: \[ \begin{aligned} \mathbb E[aX+bY] &=\sum_{x\in\mathcal S_X}\sum_{y\in\mathcal S_Y} (ax+by)\Pr(X=x,Y=y)\\ &=a\sum_{x\in\mathcal S_X} x\sum_{y\in\mathcal S_Y} \Pr(X=x,Y=y)\\ &\quad+b\sum_{y\in\mathcal S_Y} y\sum_{x\in\mathcal S_X} \Pr(X=x,Y=y)\\ &=a\sum_{x\in\mathcal S_X} x\,\Pr(X=x)+b\sum_{y\in\mathcal S_Y} y\,\Pr(Y=y)\\ &=a\mathbb E[X]+b\mathbb E[Y]. \end{aligned} \] Finite absolute expectations justify distributing and reordering these sums, even for countably infinite supports. The third equality uses the definitions of the marginal distributions. The joint probability never had to factor into \(\Pr(X=x)\Pr(Y=y)\), so independence was not used. For variables with a joint density, the same argument replaces sums by integrals and integrates out one coordinate to obtain each marginal. Thus the same linearity rule applies to the discrete and continuous variables used in this course.
The expected total of many contributions is the sum of their expected contributions, even if they interact.
We also need to measure how closely a random total stays near its center. Two quantities can share the same expectation while one is almost constant and the other swings wildly.
Variance Measures Spread
Assume the random variables in the variance and covariance calculations below have finite second moments. The variance is the expected squared distance from the mean: \[ \operatorname{Var}(X) =\mathbb E\left[(X-\mathbb E[X])^2\right]. \]
The definition measures spread directly, while data often make the second moment \(\mathbb E[X^2]\) easier to compute. Expanding the square connects the two forms: \[ \begin{aligned} \operatorname{Var}(X) &=\mathbb E[(X-\mathbb E[X])^2]\\ &=\mathbb E[X^2-2\mathbb E[X]X+(\mathbb E[X])^2]\\ &=\mathbb E[X^2]-2(\mathbb E[X])^2+(\mathbb E[X])^2\\ &=\mathbb E[X^2]-(\mathbb E[X])^2. \end{aligned} \] This proves the computational identity from the definition of variance.
Its square root is the standard deviation, which has the same units as \(X\). Shifting a random variable does not change its spread, while scaling it scales variance quadratically.
The definition also shows exactly how a change of units affects spread. Linearity gives \(\mathbb E[aX+c]=a\mathbb E[X]+c\), so \[ \begin{aligned} \operatorname{Var}(aX+c) &=\mathbb E[(aX+c-(a\mathbb E[X]+c))^2]\\ &=\mathbb E[a^2(X-\mathbb E[X])^2]\\ &=a^2\operatorname{Var}(X). \end{aligned} \] Thus setting \(a=1\) proves shift invariance, and setting \(c=0\) proves the quadratic scaling rule.
Variance is not linear on sums because the two deviations may move together. Their covariance is \[ \operatorname{Cov}(X,Y)= \mathbb E[(X-\mathbb E[X])(Y-\mathbb E[Y])]. \] It is positive when the variables tend to be above their means together, negative when one tends to be high as the other is low, and zero for independent variables.
Independence is sufficient to make covariance zero. For discrete independent variables, the joint probability factors, so the covariance factors into two centered expectations: \[ \begin{aligned} \operatorname{Cov}(X,Y) &=\sum_{x\in\mathcal S_X}\sum_{y\in\mathcal S_Y}(x-\mathbb E[X])(y-\mathbb E[Y]) \Pr(X=x)\Pr(Y=y)\\ &=\left(\sum_{x\in\mathcal S_X}(x-\mathbb E[X])\Pr(X=x)\right)\\ &\quad\cdot\left(\sum_{y\in\mathcal S_Y}(y-\mathbb E[Y])\Pr(Y=y)\right)\\ &=\mathbb E[X-\mathbb E[X]]\,\mathbb E[Y-\mathbb E[Y]]=0. \end{aligned} \] For continuous variables, the factorized joint density gives the same product of two integrals. Hence independence implies zero covariance.
Zero covariance does not, in general, imply independence. When both standard deviations are positive, dividing covariance by them gives the unitless correlation \[ \rho=\frac{\operatorname{Cov}(X,Y)}{\sigma_X\sigma_Y}. \] This normalization always satisfies \(-1\leq\rho\leq1\).
Why correlation stays between \(-1\) and \(1\)
Define \(U=(X-\mathbb E[X])/\sigma_X\) and \(V=(Y-\mathbb E[Y])/\sigma_Y\). Then \(\mathbb E[U^2]=\mathbb E[V^2]=1\) and \(\mathbb E[UV]=\rho\). Since a square has nonnegative expectation, \[ 0\leq\mathbb E[(U-\rho V)^2] =1-2\rho^2+\rho^2=1-\rho^2. \] Thus \(\rho^2\leq1\), which is equivalent to \(-1\leq\rho\leq1\). The same nonnegative-square technique will recur when we compare squared errors.
Why Sums Settle Down
Expectation located the center of a total without using independence. The remaining question is whether the total stays near that center. Expanding a squared deviation necessarily creates a product between the two centered terms. Covariance is precisely the name for that product’s expectation.
For a positive integer \(n\), we use subscripts to index \(n\) random variables: \(X_i\) is variable \(i\), for \(i=1,\ldots,n\), and \(X_i^2\) is its square. A sum over an empty index range is zero.
Claim: Let \(X_1,\ldots,X_n\) have finite second moments. Then \[ \mathbb E\!\left[\sum_{i=1}^n X_i\right] =\sum_{i=1}^n \mathbb E[X_i] \] and \[ \operatorname{Var}\!\left(\sum_{i=1}^n X_i\right) =\sum_{i=1}^n \operatorname{Var}(X_i) +2\sum_{i=1}^{n-1}\sum_{j=i+1}^n\operatorname{Cov}(X_i,X_j). \]
Proof
Linearity gives the expectation formula directly. For variance, center the sum and expand its square. There is one squared term per variable and two identical cross terms for each pair \(i<j\): \[ \begin{aligned} \operatorname{Var}\!\left(\sum_{i=1}^nX_i\right) &=\mathbb E\!\left[ \left(\sum_{i=1}^n(X_i-\mathbb E[X_i])\right)^2\right]\\ &=\sum_{i=1}^n\mathbb E[(X_i-\mathbb E[X_i])^2] +2\sum_{i=1}^{n-1}\sum_{j=i+1}^n \mathbb E[(X_i-\mathbb E[X_i])(X_j-\mathbb E[X_j])]\\ &=\sum_{i=1}^n\operatorname{Var}(X_i) +2\sum_{i=1}^{n-1}\sum_{j=i+1}^n\operatorname{Cov}(X_i,X_j). \end{aligned} \]
Two important formulas now follow without new proof. Taking \(n=2\) gives \[ \operatorname{Var}(X+Y) =\operatorname{Var}(X)+\operatorname{Var}(Y) +2\operatorname{Cov}(X,Y). \] Let \(\bar{X} = \frac1{n} \sum_{i=1}^n X_i\). Factoring out the constant \(\frac1{n}\) and applying the variance formula gives the mean \[ \mathbb E[\bar X]=\frac1n\sum_{i=1}^n\mathbb E[X_i] \] and its variance \[ \operatorname{Var}(\bar X) =\frac1{n^2}\left( \sum_{i=1}^n\operatorname{Var}(X_i) +2\sum_{i=1}^{n-1}\sum_{j=i+1}^n\operatorname{Cov}(X_i,X_j)\right). \] If the variables have common mean \(\mu\), common variance \(\sigma^2\), and are independent, then \(\mathbb E[\bar X]=\mu\) and \(\operatorname{Var}(\bar X)=\sigma^2/n\). Independence removes the covariance terms. Linearity of expectation already gives the mean for dependent variables as well.
There are \(n\) sources of uncertainty, but dividing the sum by \(n\) divides variance by \(n^2\). That mismatch is why the average becomes predictable. If the draws are correlated, covariance terms remain and the conclusion can change. This is why a large poll can retain an error floor when many responses share a common source of dependence.
We can now answer the question: many draws produce a predictable average when their individual spreads are finite and their dependence is weak enough that covariances do not accumulate. Next lecture turns this fact into the Monte Carlo estimator, using expectation to prove it is correct on average and variance to measure how quickly its error falls.