Notes of UC Berkeley’s STAT 134 Notes created by Yunhao Cao (Github@ToiletCommander)

Disclaimer:

1. Some of the images and resources are taken from notes on STAT 134’s official site and official textbook(Jim Pitman’s “Probability”).

2. Some of the stuffs are from CS70’s class materials

3. Some of the images and resources are taken from google image search, or other websites

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Last Update: 2022-05-08 21:00 PST ⇒ Updated through Ch 6.5 + MGF + Additional Topics(MLE and MAP)

Notations

Sets

$|A|$ ⇒ Cardinality of set A, the number of elements in A

$\emptyset = \{\}$ ⇒ Empty Set Notation

$A \sube B$ or $B \supe A$ ⇒ A is a subset of B, or B is a superset of A

$A \sub B$ or $B \sub A$ ⇒ A is a strict subset of B, or B is a strict superset of A

$\alpha \in A, \beta \notin A$ ⇒ $\alpha$ is a member in the set of $A$, but $\beta$ is not a member in the set of A

$A \cup B$ ⇒ The UNION of A and B(place taken by either A or B or both)

$A \cap B$ ⇒ The INTERSECTION of A and B

$A \cap B = \emptyset$ ⇒ A and B are disjoint

$B - A = B \setminus A$ ⇒ Relative Complement of A in B, or Set Difference between B and A.

Note that $A \setminus \emptyset = A, A \setminus \emptyset = A$

$A^\complement = \overline{A} = A'$ ⇒ A’s Complement

Significant Sets

$\mathbb{N}$ ⇒ Natural Numbers

$\mathbb{Z}, \mathbb{Z^+}, \mathbb{Z^-}$ ⇒ Integers, Positive Integers, Negative Integers

$\mathbb{Q}$ ⇒ Rational Numbers, $\mathbb{Q} = \{\frac{a}{b}: a,b \in \mathbb{Z}, b \neq 0\}$

$\mathbb{R}$ ⇒ Real Numbers

$\mathbb{C}$ ⇒ Complex Numbers, $\mathbb{C} = \{a+bi:a,b \in \mathbb{R}\}$

Boolean Logic

Not P

P and Q

P or Q

P implies Q, equivalen to not P or Q, and equivalent to its contrapositive(not Q implies not P)

Probability Notations

$\Omega$ ⇒ Outcome Space

$\omega$ ⇒ Single Event

Basic Principle of Probability

“Complement Rule”

“Principle of Inclusion-Exclusion”

Similarly, “Principle of Inclusion-Exclusion” of Probability...

“Two Events are DISJOINT”

“Two Events are INDEPENDENT”

Conditional Probability

$P(A|B)$ denotes the probability of event A happening when we know that event B is already happening.

Bayes’ Rule

Counting & Sampling

Counting

Counting Sequence(Order Matters) Without Replacement

First Rule of Counting: If an object can be made by a succession of $k$ choices, where there are $n_1$ ways of making the first choice, and for every way of making the first choice there are $n_2$ ways of making the second choice, and for every way of making the first and second choice there are $n_3$ ways of making the third choice, and so on up to the $n_k$-th choice, then the total number of distinct objects that can be made in this way is the product $n_1 \times n_2 \times n_3 \times \dots \times n_k$.

Counting Sequence With Replacement

Counting Sets without replacement

“n choose k”

Second Rule of Counting: Assume an object is made by a succession of choices, and the order in which the choices are made does not matter. Let A be the set of ordered objects and let B be the set of unordered objects. If there exists an m-to-1 function $f: A \rightarrow B$, we can count the number of ordered objects (pretending that the order matters) and divide by $m$ (the number of ordered objects per unordered objects) to obtain $|B|$, the number of unordered objects.

Counting Sets with replacement

Say you have unlimited quantities of apples, bananas and oranges. You want to select 5 pieces of fruit to make a fruit salad. How many ways are there to do this? In this example, S = {1, 2, 3}, where 1 represents apples, 2 represents bananas, and 3 represents oranges. k = 5 since we wish to select 5 pieces of fruit. Ordering does not matter; selecting an apple followed by a banana will lead to the same salad as a banana followed by an apple.

It may seem natural to apply the Second Rule of Counting because order does not matter. Let’s consider this method. We first pretend that order matters and observe the number of ordered objects is 35 as discussed above. How many ordered options are there for every un-ordered option? The problem is that this number differs depending on which unordered object we are considering. Let’s say the unordered object is an outcome with 5 bananas. There is only one such ordered outcome. But if we are considering 4 bananas and 1 apple, there are 5 such ordered outcomes (represented as 12222, 21222, 22122, 22212, 22221).

Assume we have one bin for each element of S, so n bins in total. For example, if we selected 2 apples and 1 banana, bin 1 would have 2 elements and bin 2 would have 1 element. In order to count the number of multisets, we need to count how many different ways there are to fill these bins with k elements. We don’t care about the order of the bins themselves, just how many of the k elements each bin contains. Let’s represent each of the k elements by a 0 in the binary string, and separations between bins by a 1.

Counting the number of multisets is now equivalent to counting the number of placements of the k 0’s

The length of our binary string is k + n − 1, and we are choosing which k locations should contain 0’s. The remaining n − 1 locations will contain 1’s.

Zeroth Rule of Counting: If a set A can be placed into a one-to-one correspondance with a set B (i.e. you can find a bijection between the two — an invertible pair of maps that map elements of A to elements of B and vice-versa), then |A| = |B|.

Sampling

A population of N total, G good and B bad. sample size of n = g + b, with 0 ≤ g ≤ n

Sampling Sets with replacement

Sampling Sets without replacement (Hypergeometric Dist.)

Probability Concepts

Consecutive Odds Ratios

Mainly used for binomial distribution

“Analyze the chance of k successes with respect to k-1 successes”

Law of Large Numbers

As $n \rightarrow \infin$, the sampled mean will have a higher and higher probability of being in the actual distribution mean, $\mathbb{P}(|\frac{1}{n}S_n-\mu| < \epsilon) \rightarrow 1$, no matter how small $\epsilon$ is.

Random Variable

A random variable $X$ on a sample space $\Omega$ is a function $X:\Omega \rightarrow R$ that assigns to each sample point $\omega \in \Omega$ a real number $X(\omega)$.

Probability of a value of a discrete random variable

Has to satisfy:

Note:

For discrete r.v., the CDF(cumulative distribution function) would be a step function

Probability of a value of a continuous random variable

Probability of a range of value of a continuous random variable

Has to satisfy:

Continuous Random Variable

For continuous r.v.

There’s a Probability Density Function(PDF) and a Cumulative Distribution Function(CDF)

Inverse Distribution Function

For what value of x is there probability 1/2 that X ≤ x?

Either calculate the inverse function of $F(x)$ or solve equation $F(x) = p$, treating $p$ as the variable.

Inverse CDF applied to standard norm

For any cumulative distribution function with inverse function $F^{-1}$, if $U$ has uniform (0,1) distribution, then $F^{-1}(U)$ has shape of CDF $F(x)$.

Probability Distribution

The distribution of a discrete random variable $X$ is the collection of values $\{(a, P[X = a]): a \in A \}$, where $A$ is the set of all possible values taken by $X$.

The distribution of a continuous random variable $X$ is defined by its Probability Density Function $f(x)$.

Example, For a dice, where X denotes the number on the dice when we roll the dice once.

Joint Distribution

The joint distribution for two discrete random variables $X$ and $Y$ is the collection of values $\{(\forall(a, b), P[X = a,Y = b]) : a \in A , b \in B\}$, where $A$ is the set of all possible values taken by $X$ and $B$ is the set of all possible values taken by $Y$

And the joint distribution for two continuous random variables X and Y is defined by the joint probabilty density function $f(x,y)$. It gives the density of probability per unit area for values of (X,Y) near the point (x,y). $P(X\in dx, Y \in dy)=f(x,y)dxdy$.

In other words, list all probabilities of all posible X and Ys.

Has to satify the following constraint:

One useful equation:

Symmetry of Joint Distribution

If $X_1,X_2,\dots,X_n$ be random variables with joint distribution defined by

Then the joint distribution is symmetric if $P(x_1,\dots,x_n)$ is a symmetric function of $(x_1,\dots,x_n)$. In other words, for the value of $P(x_1,\dots,x_n)$ is unchanged if we swap the positions of arbitrary number of parameters.

If the joint distribution is symmetric, then all $n!$ possible orderings of the random variables $X_1, \dots, X_n$ have the same joint distribution and this means that $X_1, \dots, X_n$ are exchangeable. Exchangeable random variables have the same distribution.

Independence of random variables

Random variables X and Y on the same probability space are said to be independent if the events $X=a$ and $Y=b$ are independent for all values a, b. Equivalently, the joint distribution of independent r.v.’s decomposes as

Conditional Distribution

Usually used when two variables are dependent.

“Conditional Distribution of Y given X=x”

Continuous Variables:

Rule of Average Conditional Probabilities:

Conditional Expectation

$\mathbb{E}(Y|X)$ is defined by the function of X whose value is $\mathbb{E}(Y|X=x)$

Properties of Conditional Expectation

Identical Distribution

X and Y has the same range, and for every possible value in the range,

If X and Y has same distribution, then...

1. any statement of X has the same probability of the same statement of Y

2. g(X) has the same distribution with g(Y)

Combination of Random Variables

If $Z=Y/X$, Then $Z \in dz$ is drawn in the following diagram

Note the area of the heavily shaded region here. It looks similar to a parallelogram. So area would be $dx \cdot [(z+dz)x-zx]=dxdz|x|$.

Therefore, if we integrate out X,

Equality of random variables

“Equality implies identical distribution”

Probability of Events of two Random Variables

Symmetry of R.V.

The random variable X said to be symmetric around 0 if:

Linear Function Mapping of Continuous Random Variable

suppose $Y = aX+b$ and $X$ has PDF $f_X(x)$

then $Y$ has PDF $f_Y(y) = \frac{1}{|a|}f_X(\frac{y-b}{a})$

One-to-one Differentiable Function of Continuous Random Variable

Let $X$ be a r.v. with density $f_X(x)$ on the range $(a,b)$. Let $Y = g(x)$ where $g$ is strictly increasing or decreasing on interval $(a,b)$.

For an infinitestimal interval $dy$ near $y$, the event $Y \in dy$ is identical to the event $X \in dx$.

Thus $f_Y(y)|dy| = f_X(x)|dx|$. The absolute values are added in because for a decreasing function $g(x)$, only the ratio of the magnitudes of $dx$ and $dy$ matters, thus:

Change of Variable Principle

If $X$ has the same distribution as $Y$, then $g(X)$ has the same distribution as $g(Y)$, for any function $g(\cdot)$

Max and Min of Independent R.V.s

CDF makes it easy to find dist of max and mins.

For any number x:

1. $X_{max} \le x \equiv (\forall i, X_i \le x)$

2. $X_{min} \ge x \equiv (\forall i, X_i \ge x)$

So...

Expectation

For Discrete R.V.

For continuous R.V.

If we have a non-negative r.v.

Linearity of Expectation

Independent R.V. Expectation

For Independent R.V. $X, Y$, we have:

Variance

Variance of the sum of n variables

Coefficient Property

Independent R.V. Variance

For Independent R.V. $X, Y$, we have:

Standard Deviation $\sigma$

Standardizations of Random Variable

“X in standard units” with $\mathbb{E}(X^*)=0, Var(X) = \sigma_x = 1$

Skewness of R.V.

Let $X$ be a random variable with $E(X) = \mu$ and $Var(X) = \sigma_x^2$, Let $X^* = \frac{X-\mu}{\sigma}$ be $X$ in standard units.

Markov’s Inequality

Note: For nonnegative R.V.s only

Chebychev’s Inequality

Order Statistics

Let $X_1, X_2, X_3, \dots, X_n$ be random variables with the independent and identical distribution pdf $f(x)$ and cdf $F(x)$

Then if we denote $X_{(1)}, X_{(2)}, \dots, X_{(n)}$ being the smallest, the second smallest, etc. among $X_1, \dots, X_n$. Then what is the distribution of $X_{(i)}$?

Covariance $Cov(X,Y)$

Covariance of the same variable

Bilinearity of Covariance

Standard Form:

Simpler Form:

Correlation

Because it is hard to interpret magnitude of $Cov(X,Y)$, we standardize this to correlation

Moment Generating Function

Let $X$ be a random variable, then the MGF(Moment Generating Function) of $X$ is defined as

Important Properties

Equality of MGF means Equality of CDF

Jensen’s Inequality

Upper tail of random variable using Markov’s Inequality

Linear Transformation of Random Variable

Linear Combination of Independent Random Variables

Additional Topic - MLE and MAP

What are Maximum Likelihood (ML) and Maximum a posteriori (MAP)? ("Best explanation on YouTube")

Explains Maximum Likelihood (ML) and Maximum a posteriori (MAP) estimation/detection using a Gaussian measurement/sampling example. Related videos: (see: htt...

https://youtu.be/9Ahdh_8xAEI

Maximum Likelihood, clearly explained!!!

If you hang out around statisticians long enough, sooner or later someone is going to mumble "maximum likelihood" and everyone will knowingly nod. After this...

https://youtu.be/XepXtl9YKwc

(ML 6.1) Maximum a posteriori (MAP) estimation

Definition of maximum a posteriori (MAP) estimates, and a discussion of pros/cons.A playlist of these Machine Learning videos is available here:http://www.yo...

https://youtu.be/kkhdIriddSI

Say we have observations $\vec{x}$, we want to estimate a parameter $\theta$, where $\theta$ is a random variable.

MLE does the following:

MAP does the following:

MLE - iterate through distribution parameters and find the distribution parameter such that producing $\vec{x}$ is most likely using the parameter.

MAP - iterate through distribution parameters and find the distribution parameter that is most likely to be right given the observed data.

By Bayes Theorem,

Note that

Since $\mathbb{P}(x)$ is independent of individual $\theta$, we can view $\mathbb{P}(x)$ as a constant, and therefore,

Therefore, MAP can also be written as

Properties of MLE and MAP

1. Note that both MLE and MAP are point estimators, that is if the parameter is continuous (and usually this is the case), then it picks the max point on the PDF function, not the midpoint of the points where their areas are the biggest.

2. MLE is more prune to overfitting then MAP, since the prior in MAP kind of restricts the parameter estimated in an area.

3. the asymptotic behavior of MAP and MLE are the same, that is as we collect more data, the result of MAP and MLE tends to converge.

4. Special Property of MLE (not applicable to MAP): $\Tau = g(\theta) \implies \Tau_{MLE} = g(\theta_{MLE})$

Distribution

Bernoulli(Indicator) Distribution $I_n \sim Bernoulli(p)$

Uniform Distribution on a finite set

Let we have a list of uniform events, $\Omega = \{\omega_1, \omega_2, \dots, \omega_n\}$

Uniform(a,b) distribution

Distribution of a point picked uniformly at random from the interval (a,b)

For a < x < y < b the probability that a point falls in the interval (x,y) is...

for b-a= 1, long-run frequency is almost exactly equal to y-x.

Empirical Distribution

Opposed to theoretical distribution, empirical distribution is the distribution of your observed data.

Suppose we have $X = \{x_1, x_2, \dots, x_n\}$

In other words, $P_n(a,b)$ gives the proportion of the numbers in the list that lies in-between range of (a,b)

Estimating Empirical Distribution With Continuous PDF

The distribution of a data list can be displayed in a histogram, and such histogram smoothes out the data to display the general shape of the empirical distribution.

Such histograms often follows a smooth curve $f(x)$. And it is safe to assume $\forall x, f(x) \ge 0$

Idea is that if (a,b) is a bin interval, then the area under the bar between (a,b) should roughly equal to the area under the curve between (a,b) ⇒ the proportion of data from a to b is roughly equal to the area under $f(x)$.

$f(x)$ functions like a continuous PDF estimation for distribution of data.

Now we can also use an indicator distribution to estimate its average

So $I_{(a,b)}(x_i)$ is an indicator stating if $x_i$ is in range of $(a,b)$

Integration Approximation of Averages

If the empirical distribution of list $(x_1,x_2,\dots,x_n)$ is well approximated by the theoretical distribution with PDF $f(x)$, then the average value of a function $g(x)$ over the n values can be approximated by

Binomial Distribution $X \sim B(n,p)$

“probability of k successes in n trials with success rate of p”

Note: “Binomial Expansion”

Square Root Law

For large n, in n independent trials with probability p of success on each trial:

• the number of success will, with high probability, lie in a ralatively small region centered on $np$, with width a moderate multiple of $\sqrt{n}$ on the numerical scale

• the proportion of success will, with high probability, lie in a small interval centered on $p$, with width a moderate multiple of $\frac{1}{\sqrt{n}}$

Normal Distribution as an approximation for Binomial Distribution

provided n is large enough in $X \sim B(n,p)$, $X$ can be approximated with normal distribution

If approximating a to b success in a bionomial distribution, use $b + \frac12$ and $a - \frac12$ as the boundary instead of using $b$ and $a$, this is called continuity correction. Very important for small values of $\sqrt{npq}$.

Note: for $f(x)$, use $\mu = \mathbb{E}(X)$ and $\sigma^2 = Var(X)$ of the Binomial distribution