An outcome is a single possible result of a random experiment. It is the most basic element in the sample space.
An event is any subset of the sample space $\Omega$. It can be a single outcome or a collection of outcomes.
Examples for the experiment "rolling a standard six-sided die":
A random variable is a function that assigns a numerical value to each outcome in the sample space. Random variables are usually denoted by capital letters (e.g., $X, Y, H_t$).
While the outcome is the physical result (e.g., the number 3), the random variable maps that result to a quantity of interest.
Example: Dice Roll Random Variables
Let's define two different random variables, $X$ and $Y$, based on the roll of a die:
Random Variable $X$: Even or Odd
Random Variable $Y$: Smaller 4 or Greater 3
The key takeaway is that the random variable provides a structured, numerical framework for analyzing the underlying random process, allowing us to define probabilities like $P(X=1)$ or $P(Y=0)$.
A discrete probability distribution defines the likelihood of all possible outcomes for a discrete random variable. It is essentially a complete model of our belief regarding the state of the system at a given time.
A discrete probability distribution is a function that maps every unique, countable outcome of a random variable, e.g. $X$, to its corresponding probability value.
Since the possible outcomes are finite or countably infinite (like the number of grid cells), the distribution can be represented explicitly:
The distribution $P(X)$ provides a full picture of uncertainty—it doesn't just give the single most likely state, but quantifies how likely every possible state is.
Let's assume a small grid with $N=10$ cells (indices $0$ to $9$).
At a specific time, say $t=5$, our current knowledge (belief) about the robot's location is represented by the following distribution, $P(H_5)$:
| Grid Cell Index $i$ | Probability $P(H_5 = i)$ |
|---|---|
| 0, 1, 2 | 0.00 |
| 3 | 0.20 |
| 4 | 0.50 |
| 5 | 0.25 |
| 6 | 0.05 |
| 7, 8, 9 | 0.00 |
Interpretation: Quantifying Belief
This distribution represents the entirety of our knowledge about the robot's state at time $t=5$ (before any further motion or measurements occur).
Key Properties of Probability Distributions
Non-negativity: For any cell $i$, $P(H_t=h) \ge 0$.
Normalization: The sum of all probabilities must equal one:
$$\sum_{h \in \text{Val}(H_t)} P(H_t=h) = 1$$
In probability theory and filter design, we frequently use a shorthand known as "abuse of notation" to keep our equations readable.
In formal mathematics, a function should be defined by its name or symbol, e.g., for $f(x)$, the symbol is $f$, while the argument $x$ is just a placeholder. However, in this field, we identify the specific distribution by its argument:
In standard calculus, if $f(x) = x^2$, then $f(y)$ must be $y^2$. However, in probability, $P(H_t)$ might be a distribution representing a robot's position at time $t$, while $P(Y)$ could be a Bernoulli distribution representing a sensor's binary state. Even though we use the same letter $P$, the underlying mathematical functions are completely different. Analog for $P(x)$ vs. $P(h_t)$.
Rule of Thumb: Whenever you see $P(\cdot)$ (or $p(\cdot)$), look at the variable inside the parentheses. That variable tells you which physical "part" of the system the distribution belongs to.
The joint probability distribution of two or more random variables, $X$ and $Y$, specifies the probability of every possible combination of their values occurring simultaneously.
If we know $P(X, Y)$, we know the chance of $X=x$ and $Y=y$ happening at the same time. This is written as $P(X=x, Y=y)$.
Example: Dice Roll Joint Probability
Let's use our two random variables from the previous example based on the roll of a standard six-sided die ($\Omega = \{1, 2, 3, 4, 5, 6\}$):
We can construct the joint distribution $P(X, Y)$ by counting the outcomes for each combination:
| $X$ (Even/Odd) | $Y$ ($\le 3 / > 3$) | Outcomes | Count | Joint Probability $P(X=x, Y=y)$ |
|---|---|---|---|---|
| $X=1$ (Odd) | $Y=0$ ($\le 3$) | $\{1, 3\}$ | 2 | $2/6 \approx 0.333$ |
| $X=1$ (Odd) | $Y=1$ ($> 3$) | $\{5\}$ | 1 | $1/6 \approx 0.167$ |
| $X=0$ (Even) | $Y=0$ ($\le 3$) | $\{2\}$ | 1 | $1/6 \approx 0.167$ |
| $X=0$ (Even) | $Y=1$ ($> 3$) | $\{4, 6\}$ | 2 | $2/6 \approx 0.333$ |
| TOTAL | 6 | 1.000 |
Two random variables, $A$ and $B$, are independent if the occurrence of one does not change the probability distribution of the other.
The Mathematical Definition
In formal notation, $A$ and $B$ are independent if and only if their joint probability is equal to the product of their individual probabilities:
$$P(A, B) = P(A)P(B)$$
Think of this as "Information Silence." If you know the value of $A$, you gain zero new information about $B$.
Notation
If two random variables are independent, we use the notation:
$$A \perp B$$
The symbol $\perp$ signifies that $A$ and $B$ are "perpendicular" or orthogonal in an informational sense—they do not overlap or influence one another.
We can use the Joint Probability table from the previous section to check if $X$ (Even/Odd) and $Y$ (Small/Large) are independent.
If they were independent, the following would hold true for every row:
$$P(x, y) = P(x)P(y)$$
Let's check the first row ($X=1, Y=0$):
The Test: $$0.5 \times 0.5 = 0.25$$
Conclusion: Since $0.25 \neq 0.333$, these variables are not independent.
Why does this make sense?
In this specific die roll, knowing the number is "Small" ($Y=0$) increases the likelihood that it is "Odd" ($X=1$) because the set $\{1, 2, 3\}$ is 66% odd, whereas the full die is only 50% odd. Because one variable "hints" at the other, they are mathematically dependent.
A key property of the joint distribution is that you can calculate the individual (unconditional) probability distributions, $P(X)$ and $P(Y)$, from it. These are called marginal distributions because they are found by summing over the "margins" of the joint table.
Calculating $P(X)$ (Marginalizing Out $Y$)
To find the probability of $X=1$ (Odd), we sum the probabilities of all outcomes where $X=1$:
$$P(X=1) = \sum_{y \in \text{Val}(Y)} P(X=1, Y=y)$$
$$P(X=1) = P(X=1, Y=0) + P(X=1, Y=1) = \frac{2}{6} + \frac{1}{6} = \frac{3}{6} = 0.5$$
This matches our earlier finding that the probability of rolling an odd number is $0.5$.
The conditional probability of $X$ given $Y$ is defined as the joint probability of $X$ and $Y$ divided by the marginal probability of $Y$:
$$P(X \mid Y) = \frac{P(X, Y)}{P(Y)} $$
Where:
Example Calculation:
Let's calculate the probability of the roll being Odd ($X=1$), given that the roll was smaller or equal to 3 ($Y=0$).
$$P(X=1 \mid Y=0) = \frac{P(X=1, Y=0)}{P(Y=0)} = \frac{2/6}{3/6} = \frac{2}{3} \approx 0.667 $$
Interpretation
Note: This process of using observed information ($Y=0$) to update the probability of an unknown state ($X=1$) is the fundamental idea behind the Measurement Update step (Bayes' Rule) in localization and filtering.
A more intuitive way to think about independence is through the lens of conditional probability.
If $X \perp Y$, then knowing the value of $Y$ does not change our belief about $X$. Mathematically, this is written as: $$P(X \mid Y) = P(X)$$
Why this is equivalent:
If you take the standard independence formula $P(X, Y) = P(X)P(Y)$ and plug it into the conditional probability formula:
$$P(X \mid Y) = \frac{P(X, Y)}{P(Y)} = \frac{P(X)P(Y)}{P(Y)} = P(X)$$
Two random variables, $A$ and $B$, are conditionally independent given a third variable $C$ if knowing the value of $C$ makes $A$ and $B$ statistically unrelated.
In simpler terms, if $C$ is known, information about $B$ provides no additional information about $A$.
Formal Definition
$A$ and $B$ are conditionally independent given $C$ if the following holds:
$$P(A \mid B, C) = P(A \mid C)$$
This is equivalent to:
$$P(A, B \mid C) = P(A \mid C) P(B \mid C)$$
Notation for the conditionally independence: $$ A \perp B \mid C. $$
Application to Markov Chains (The Markov Assumption)
This concept is the bedrock of sequential estimation filters. In the context of your robot localization:
The Markov Assumption states that the future location of the robot ($H_t$) is conditionally independent of all history ($H_1, \dots, H_{t-2}$) given only the immediate previous location ($H_{t-1}$).$$P(H_t \mid H_1, \dots ,H_{t-1}) = P(H_t \mid H_{t-1})$$
Why it's Critical for Filtering
If we had to track the entire history of the robot's movement ($H_1, H_2, \dots$), the calculations would quickly become unmanageable (the complexity would grow exponentially with time).
By assuming conditional independence, the system gains the memoryless property: we only need to store and update the belief from the last time step, $P(H_{t-1})$, to predict the next state, $P(H_t)$. This dramatically simplifies the prediction step and makes recursive filters, like the Kalman Filter, computationally practical.
A Directed Graphical Model (or Bayesian Network) uses nodes to represent random variables and directed edges (arrows) to represent probabilistic dependencies (causation or correlation). The structure of the graph is defined such that it satisfies the Markov Property: given its parents, a node is independent of all its non-descendants.
Encoding Conditional Independence
The core rule for reading independence from a directed graph is based on tracing paths between nodes and observing the state of conditioning nodes (nodes whose values are known).
For the Markov Chain:
The structure $H_{t-2} \to H_{t-1} \to H_t$ forms a serial connection (or chain). In a serial connection, the start node ($H_{t-2}$) and the end node ($H_t$) are independent once the middle node ($H_{t-1}$) is observed (or known).
This graphical structure directly shows why the future state $H_t$ is conditionally independent of the past state $H_{t-2}$ given the present state $H_{t-1}$.
General Definition
For two random variables, $A$ and $B$, the joint probability $P(A, B)$ can be written in two symmetric ways, derived directly from the definition of conditional probability $P(A \mid B) = P(A, B) / P(B)$: $$P(A, B) = P(A) \cdot P(B \mid A)$$ or $$P(A, B) = P(B) \cdot P(A \mid B)$$
For a Sequence of Variables
When dealing with a sequence of $T$ random variables—like the robot's location over time, $H_1, H_2, \dots, H_T$—the Chain Rule can be expanded to express the full joint probability:$$P(H_1, H_2, \dots ,H_T) = P(H_1) \cdot P(H_2 \mid H_1) \cdot P(H_3 \mid H_1, H_2) \cdots P(H_T \mid H_1, \dots ,H_{T-1})$$
Application to Robot Localization
This general formula applies to any sequence of random variables. However, when we apply the Markov Assumption (Conditional Independence) to the Chain Rule, the formula simplifies dramatically.
Recall the Markov Assumption: $P(H_t \mid H_1, \dots, H_{t-1}) = P(H_t \mid H_{t-1})$.
Applying this assumption to the expanded Chain Rule above simplifies the terms:
$$P(H_1, H_2, \dots ,H_T) = P(H_1) \cdot P(H_2 \mid H_1) \cdot P(H_3 \mid H_2) \cdots P(H_T \mid H_{T-1})$$
This can be written compactly using product notation:$$P(H_1, \dots ,H_T) = P(H_1) \prod_{t=2}^{T} P(H_t \mid H_{t-1})$$
Conclusion for Filtering
This simplified form, derived from the Chain Rule and the Markov Assumption, is what makes recursive state estimation possible. It means that the long-term dependency of the system's state is encapsulated entirely by a sequence of short-term, one-step transitions $P(H_t \mid H_{t-1})$. This directly translates to your Prediction Step (convolution), where you only need the previous belief to compute the next.
Bayes' Rule is the mathematical foundation for updating a belief (prior) with new evidence (measurement) to achieve a refined belief (posterior). It provides a way to calculate $P(A \mid B)$ when we only know the reverse conditional, $P(B \mid A)$.
The Rule
For two events (or random variables) $A$ and $B$:
$$P(A \mid B)=\frac{P(B \mid A) \cdot P(A)}{P(B)}$$
Components Explained:
| Term | Name | Meaning |
|---|---|---|
| $P(A \mid B)$ | Posterior Probability | Our goal. The probability of the hypothesis $A$ being true, after observing the evidence $B$. |
| $P(B \mid A)$ | Likelihood | The probability of observing the evidence $B$, if the hypothesis $A$ were true. This is the Measurement Model in filtering. |
| $P(A)$ | Prior Probability | Our existing belief in the hypothesis $A$ before observing the evidence $B$. This comes from the Prediction Step. |
| $P(B)$ | Evidence / Normalizer | The total probability of observing the evidence $B$ across all possible hypotheses $A$. It ensures the final posterior distribution sums to one. |
The Core Idea: Reversing Logic
Bayes' Rule allows us to "invert" a model. It is often easy to know the Likelihood—e.g., "If the robot is at the door, how likely is the sensor to see a wall?"—but we actually need the Posterior: "If the sensor sees a wall, how likely is it that the robot is at the door?"
Calculating the "Evidence
Often the denominator is calculated by: $$P(B) = \sum_{a \in Val{(A)}}P(B \mid A=a) \cdot P(A=a)$$