Probability

Probability theory is a branch of mathematics concerned with the science of chance. Probability describes the real world. The data we collect and models we build involve statistics and statistical learning.

Basic terminology

A random experiment is one where there’s a varied outcome each time. We define the sample space $S$ (or $U$) as an atomic set of all possible outcomes. We define the likelihood of each outcome in $n$ trials as $N_k(n)$, and the relative frequency of an event $k$ in $n$ trials as $f_k(n)=\frac{N_k(n)}{n}$, such that the probability of an event $k$ is:

$$P(k)=P_k=\underset{n\to \infty }{\lim }{f}_k(n)$$

In practice, an infinite number of trials is impossible, so we instead define several axioms to model probability:

• The probability of an event $A$, $P(A)\in [0,1]$.
• Total probability, i.e., of the sample space, is $P(S)=1$.
• If events $A,B$ are mutually exclusive, then $P(A\cup B)=P(A)+P(B)$.

We have some handy formulas, but it’s nice to first define some terms.

• An event is a condition on an outcome. For example, an event $A$ such that a roulette result is even and is non-zero.
  • If an event produces one outcome (instead of a subset of $S$), then we call this an elementary event.
  • Complicated events are a set union of elementary events.
• The complement of an event $A$ is the event that $A$ does not occur. Complementary events are mutually exclusive and exhaustive events; i.e., their probabilities will together sum to 1.
  • We additionally define the complement of $A$ as $A^{\prime }$ or $\bar{A}$ or $A^C$. Then, $\bar{A}=S\backslash A$.
• Mutual exclusivity of two events suggest that they cannot occur at the same time.
• Events are exhaustive if at least one event must occur, i.e., when rolling a six-sided die.
• Events are independent if one event occurring does not affect the probability of another event occurring.
• Conditional probability is the probability of event $A$ occurring given that event $B$ has occurred.

And some useful axioms:

• For complementary events, $P(A)+P(A^{\prime })=1=S$.
• For combined events, $P(A\cup B)=P(A)+P(B)-P(A\cap B)$.
• For mutually exclusive events, $P(A\cup B)=P(A)+P(B)$. In fact, if $S$ is the union of $k$ distinct mutually disjoint subsets, then $P(S)$ is the sum of the probability of each subset.
• For conditional events, $P(A|B)=\frac{P(A\cap B)}{P(B)}$.
• For independent events, $P(A\cap B)=P(A)P(B)$.

Extensions

It also helps us to define a few formulas given certain situations. If every outcome is equally likely, then the probability of an event $E$ is:

$$P(E)=\frac{\text{number of outcomes in }E}{\text{total outcomes in}S}$$

Constructing statements for the probability of certain events often takes combinatorial approaches, including permutations and combinations.

For situations that involves us successively making decisions (like sampling from a set of items more than once). In this case, we can refer to the rule of products. This holds regardless of how the preceding steps were formed:

If an operation consists of $k$ steps, and the first step can be performed in $n_1$ ways, second in $n_2$ ways, $k$th step in $n_k$ ways, then the entire operation is performed in: $n_1{n}_2\cdots n_k$.

From here, we can obviously tell that if $n_1=n_2=n_k$, then the operation has $n^k$ possibilities. If we don’t replace an element in the sample space (i.e., we can’t repeat an element), then we have $n_1=n_2+1$, and the operation has $n!$ possibilities.

Over feature vectors

We have (like CSPs):

• A set of variables $V_1,V_2,\cdots ,V_n$.
  • This represents a different feature of the world that we might be interested in knowing.
  • Each different total assignment to these variables will be an atomic event $e\in U$.
• A finite domain of values for each variable $\text{Dom}(V_1),\cdots ,\text{Dom}(V_n)$.

For 3 variables with a domain of size 3, we get 27 atomic events. The number of atomic events grows exponentially with the number of variables $n$ for a size of domain $m$: $\mathcal{O}(m^n)$.

One way we can compactly express probability with feature vectors is to indicate a subset:

$$P(V_1=1)=\sum _{d_2\in \text{Dom}(V_2)}\cdots \sum _{d_n\in \text{Dom}(V_n)}P(V_1=1,V_2=d_2,\cdots ,V_n=d_n)$$

There are a couple of problems with working over feature vectors:

• There are an exponential number of atomic probabilities to specify, so we can’t get all that data.
• Computing requires summing up an exponential number of items, so even if we had the data, we wouldn’t be able to compute efficiently with it.

The main way this is mitigated is with conditional independence to simplify the problem and reduce the data/computational requirements.

Sub-pages

• Independent probability
• Conditional probability
• Random variable
  • Probability distribution
    • Probability mass function
    • Probability density function
    • Cumulative distribution function
  • Law of large numbers
  • Central limit theorem

Resources

• Probability, Statistics, and Random Processes for Electrical Engineering, by Alberto Leon-Garcia
• Probability Theory: the Logic of Science, by E.T. Jaynes

See also

• ECE302 — Probability and Applications