General framework to calculate probability consists of the following steps:

  • Specify the sample space \(\Omega\).
  • Specify the probability law/distribution
  • Identify an event \(A\) of interest
  • Calculate…

Sample Space

A sample space is legitimate when its elements are:

  • mutually exclusive
  • collectively exhaustive
  • at the right granularity

Probability Law

The mathematical function that describes the probabilities of different possible outcomes are mainly of two types:

  • discrete, in which case the probability of an event \(A\) can be computed as the ratio of the number of elements \(k\) in \(A\) to the number of elements \(n\) in \(\Omega\), and defined as \(\mathbb P(A)=\frac{k}{n}\). Examples of discrete distributions include Uniform, Geometric, Binomial, Poisson distributions.
  • continuous, in which case the probability of an event \(A\) can be computed as the integral of the probability density function (PDF) over the range in \(A\), and defined as \(\mathbb P(A)=\int_A f_X(x)dx\). Examples of continuous distributions include Uniform, Exponential, Normal distributions.

Axioms

Assuming \(A\), \(B\) and \(C\) are events \(\subseteq\Omega\), the following axioms are defined:

Axiom Formula
Non negativity \(\mathbb P(A)\geq 0\)
Normalization \(\mathbb P(\Omega)=1\)
(finite) Additivity \(\begin{align}A_i\cap A_j=\emptyset, i\neq&j\implies\\\mathbb P(A_1\cup A_2\cup\dots A_n)&=\sum_{i=1}^n\mathbb P(A_i)\end{align}\)
(applies if \(A_i\) are countable)

Putting together the three axioms above, it follows that \(\mathbb P(A)\leq 1\) and \(\mathbb P(\emptyset)=0\). Further relationships are summarized below.

Formula Equivalent form
\(\mathbb P(A)\) \(\mathbb P(A\cap B)+\mathbb P(A\cap B^C)\)
\(\mathbb P(A^C)\) \(1-\mathbb P(A)\)
\(\mathbb P(A\cup B)\) \(\begin{cases}\mathbb P(B),&\text{if }A\subseteq B\\\mathbb P(A)+\mathbb P(B)-\mathbb P(A\cap B),&\text{otherwise}\end{cases}\)
(it follows that \(\mathbb P(A)\le\mathbb P(B)\) if \(A\subseteq B\))
\(\mathbb P(A\cap B)\) \(\begin{cases}\mathbb P(A),&\text{if }A\subseteq B\\\mathbb P(A)+\mathbb P(B)-\mathbb P(A\cup B),&\text{otherwise}\end{cases}\)

From \(\mathbb P(A\cup B)=\mathbb P(A)+\mathbb P(B)-\mathbb P(A\cap B)\) we can derive two inequalities: (a) the union bound, \(\mathbb P(A\cup B)\le\mathbb P(A)+\mathbb P(B)\), because \(\mathbb P(A\cap B)\ge0\); and (b) the Bonferroni inequality, that is obtained by swapping the union with the intersection, \(\mathbb P(A\cap B)\ge\mathbb P(A)+\mathbb P(B)-1\), because \(\mathbb P(A\cup B)\le1\). Both inequalities can be generalized using the method of mathematical induction.

Formula Equivalent form
union bound \(\displaystyle\mathbb P\left(\bigcup_{i=1}^n A_i\right)\le\sum_{i=1}^n\mathbb P(A_i)\)
Bonferroni inequality \(\displaystyle\mathbb P\left(\bigcap_{i=1}^n A_i\right)\ge\sum_{i=1}^n\mathbb P(A_i)-(n-1)\)

Since \(\mathbb P(B)-\mathbb P(A\cap B)=\mathbb P(A^C\cap B)\), then \(\mathbb P(A\cup B)=\mathbb P(A)+\mathbb P(A^C\cap B)\) is an alternative expression of the union, using complements. Note that if we join another event, we have \(\mathbb P((A\cup B)\cup C)=\mathbb P(A\cup B)+\mathbb P(C)-\mathbb P((A\cup B)\cap C)\), which can be further expanded into \(\mathbb P(A)+\mathbb P(B)+\mathbb P(C)-\mathbb P(A\cap B)-\mathbb P(B\cap C)-\mathbb P(A\cap C)+\mathbb P(A\cap B\cap C)\). In general, this relationship is known as the inclusion-exclusion formula.

\[\mathbb P\left(\bigcup_{i=1}^n A_i\right)=\sum_{i=1}^n\mathbb P(A_i)-\sum_{i\lt j}\mathbb P(A_i\cap A_j)+\sum_{i\lt j\lt k}\mathbb P(A_i\cap A_j\cap A_k)+\dots(-1)^{n+1}\mathbb P\left(\bigcap_{i=1}^n A_i\right)\]

Miscellanea

Worthy of mention is the De Morgan’s law

\[\begin{align}(A\cap B)^C&=A^C\cup B^C\\ (A\cup B)^C&=A^C\cap B^C\end{align}\]

Finally, refreshing memory on the geometric series is also a good thing.

\[\begin{align}\sum_{i=0}^n q^i&=\frac{1-q^{n+1}}{1-q}&\sum_{i=0}^\infty q^i&=\frac{1}{1-q}, \lvert q\rvert<1\end{align}\]

Which leads to the following general formula.

\[\sum_{i=k}^\infty q^i=\sum_{i=0}^\infty q^i-\sum_{i=0}^{k-1} q^i=\frac{1}{1-q}-\frac{1-q^{k-1+1}}{1-q}=\frac{q^k}{1-q}\]

Go back to the syllabi breakdown.

Back-up

Set algebra

The properties below come from the basic properties of set algebra. You should know them by heart (especially the De Morgan’s law). You may add them in the case you have some spare space and if they keep slipping out of your mind.

Property Formula
Commutative \(\begin{align}A\cup B&=B\cup A\\ A\cap B&=B\cap A\end{align}\)
Associative \(\begin{align}A\cup(B\cup C)&=(A\cup B)\cup C\\ A\cap (B\cap C)&=(A\cap B)\cap C\end{align}\)
Distributive \(\begin{align}A\cup(B\cap C)&=(A\cup B)\cap(A\cup C)\\ A\cap (B\cup C)&=(A\cap B)\cup(A\cap C)\end{align}\)
Identity \(\begin{align}A\cap\Omega&=A\\ A\cup\emptyset&=A\end{align}\)
Complement \(\begin{align}A\cup A^C&=\Omega\\ A\cap A^C&=\emptyset\\\Omega^C&=\emptyset\\\emptyset^C&=\Omega\end{align}\)
Idempotent \(\begin{align}A\cup A&=A\\ A\cap A&=A\end{align}\)
Domination \(\begin{align}A\cup\Omega&=\Omega\\ A\cap\emptyset&=\emptyset\end{align}\)
Absorption law \(\begin{align}A\cup(A\cap B)&=A\\ A\cap (A\cup B)&=A\end{align}\)