A Refresher on Probability
From Events and Bayes' Theorem to Random Variables and Markov Chains
This is a quick recap on some basic probability concepts. I assume most of the notation is at least somewhat familiar and move fairly quickly from events and conditional probability to random variables, sampling, and Markov chains.
I'll use one small example. A delivery robot can be at its charging dock, in a hallway, or in a delivery room. A location sensor tries to report the robot's state, but sometimes gets it wrong.
A probability model
Outcomes and the sample space
Let \(S\in\mathcal S\) be the robot's true state and \(Y\in\mathcal S\) the state reported by its sensor. Both take one of three values:
\[ \mathcal S = \{D^{\mathrm{dock}},H^{\mathrm{hallway}},R^{\mathrm{delivery}}\}. \]
In our example, one outcome must specify both the true state and the sensor report. For example, \((H^{\mathrm{hallway}},R^{\mathrm{delivery}})\) means that the robot is in the hallway while the sensor reports the delivery room. The sample space is therefore
\[ \Omega = \mathcal S \times \mathcal S. \]
It contains nine outcomes. A probability model consists of this sample space, a collection \(\mathcal F\) of events, and a probability measure \(P\) that assigns a number to each event[1]. In a finite example, \(\mathcal F\) can simply contain every subset of \(\Omega\).
Events and probabilities
An event is a set of outcomes. Let \(\mathcal C\) be the event that the sensor is correct. It contains the three diagonal outcomes
\[ \mathcal C = \{(D^{\mathrm{dock}},D^{\mathrm{dock}}),(H^{\mathrm{hallway}},H^{\mathrm{hallway}}),(R^{\mathrm{delivery}},R^{\mathrm{delivery}})\}. \]
Let \(\mathcal H\) be the hallway event: the robot's true state is \(H^{\mathrm{hallway}}\). It contains every outcome whose first component is \(H^{\mathrm{hallway}}\):
\[ \mathcal H = \{(H^{\mathrm{hallway}},D^{\mathrm{dock}}),(H^{\mathrm{hallway}},H^{\mathrm{hallway}}),(H^{\mathrm{hallway}},R^{\mathrm{delivery}})\}. \]
Assume that the robot is at the dock with probability \(0.20\), in the hallway with probability \(0.50\), and in the delivery room with probability \(0.30\). Conditional on the true state, the sensor reports it correctly with probability \(0.80\) and reports each of the other two states with probability \(0.10\). These assumptions produce the joint distribution below.
| \(P(S=s,Y=y)\) | \(Y=D^{\mathrm{dock}}\) | \(Y=H^{\mathrm{hallway}}\) | \(Y=R^{\mathrm{delivery}}\) | \(P(S=s)\) |
|---|---|---|---|---|
| \(S=D^{\mathrm{dock}}\) | 0.16 | 0.02 | 0.02 | 0.20 |
| \(S=H^{\mathrm{hallway}}\) | 0.05 | 0.40 | 0.05 | 0.50 |
| \(S=R^{\mathrm{delivery}}\) | 0.03 | 0.03 | 0.24 | 0.30 |
| \(P(Y=y)\) | 0.24 | 0.45 | 0.31 | 1.00 |
The probability of an event is the sum of the probabilities of its constituent outcomes. The highlighted diagonal gives \(P(\mathcal C)=0.16+0.40+0.24=0.80\). The hallway row gives \(P(\mathcal H)=0.50\). Their intersection contains only \((H^{\mathrm{hallway}},H^{\mathrm{hallway}})\), so \(P(\mathcal H\cap \mathcal C)=0.40\).
Probabilities are nonnegative, \(P(\Omega)=1\), and the probability of a union of disjoint events is the sum of their probabilities. The usual rules follow from them. For example,
\[ P(\neg \mathcal C)=1-P(\mathcal C)=0.20. \]
For the union of the hallway and correct-sensor events,
\[ P(\mathcal H\cup \mathcal C)=P(\mathcal H)+P(\mathcal C)-P(\mathcal H\cap \mathcal C)=0.90. \]
Events \(\mathcal H\) and \(\mathcal C\) overlap, so adding their probabilities without subtracting the intersection would count \((H^{\mathrm{hallway}},H^{\mathrm{hallway}})\) twice. By contrast, the three true-state events are mutually exclusive: the robot cannot be at the dock and in the hallway at the same time.
Conditioning on information
Conditional probability
Suppose the robot is known to be in the hallway. The relevant outcomes are no longer all of \(\Omega\); they are the three cells in the hallway row. Within that row, the sensor is correct with probability
\[ P(\mathcal C\mid \mathcal H)=\frac{P(\mathcal C\cap \mathcal H)}{P(\mathcal H)}=\frac{0.40}{0.50}=0.80. \]
Conditioning removes outcomes outside \(\mathcal H\) and renormalizes what remains. The denominator makes the probability of the reduced space equal to one.
The multiplication and total-probability rules
Rearranging the definition gives the multiplication rule:
\[ P(\mathcal C\cap \mathcal H)=P(\mathcal C\mid \mathcal H)P(\mathcal H). \]
The order can also be reversed. Both expressions describe the same intersection:
\[ P(\mathcal C\mid \mathcal H)P(\mathcal H)=P(\mathcal H\mid \mathcal C)P(\mathcal C). \]
The true-state events form a partition of the sample space. A sensor report can therefore be calculated by considering each possible true state. For a delivery-room report,
\[ \begin{aligned} P(Y=R^{\mathrm{delivery}}) &= \sum_{s\in\{D^{\mathrm{dock}},H^{\mathrm{hallway}},R^{\mathrm{delivery}}\}} P(Y=R^{\mathrm{delivery}}\mid S=s)P(S=s) \\ &= (0.10)(0.20)+(0.10)(0.50)+(0.80)(0.30) \\ &= 0.31. \end{aligned} \]
This is the law of total probability. It is a weighted average over mutually exclusive cases.
Independence and conditional independence
Two events \(A\) and \(B\) are independent if their joint probability factorizes:
\[ P(A\cap B)=P(A)P(B). \]
When \(P(B)>0\), this is equivalent to \(P(A\mid B)=P(A)\): learning that \(B\) occurred does not change the probability of \(A\). Sensor correctness \(\mathcal C\) is independent of the true state in this particular model because the assumed accuracy is \(0.80\) at all three locations. The report \(Y\) is not independent of \(S\); a useful sensor must make some reports more likely in some states.
Conditional independence is different. Imagine taking two sensor readings \(Y_1\) and \(Y_2\). If their errors are independent once the true state is fixed, then
\[ p(y_1,y_2\mid s)=p(y_1\mid s)p(y_2\mid s). \]
The readings are still related before \(S\) is known because both carry information about the same hidden state. Conditional independence is an assumption about what separates variables, not a claim that they are unrelated in every setting.
Bayes' theorem
Reversing the condition
The sensor model gives \(P(Y=R^{\mathrm{delivery}}\mid S=R^{\mathrm{delivery}})=0.80\): if the robot is in the delivery room, the sensor reports that state 80% of the time. The controller usually needs the reverse probability. If the sensor reports the delivery room, how likely is the robot to actually be there?
The two multiplication rules for the same joint event give
\[ \begin{aligned} &P(S=R^{\mathrm{delivery}},Y=R^{\mathrm{delivery}}) \\ &\quad=P(Y=R^{\mathrm{delivery}}\mid S=R^{\mathrm{delivery}})P(S=R^{\mathrm{delivery}}) \\ &\quad=P(S=R^{\mathrm{delivery}}\mid Y=R^{\mathrm{delivery}})P(Y=R^{\mathrm{delivery}}). \end{aligned} \]
Solving for the desired conditional produces Bayes' theorem for events with \(P(A)>0\) and positive evidence probability \(P(B)>0\):
\[ \underbrace{P(A\mid B)}_{\text{posterior}} = \frac{ \overbrace{P(B\mid A)}^{\text{likelihood}} \overbrace{P(A)}^{\text{prior}} }{ \underbrace{P(B)}_{\text{evidence}} }. \]
Substituting the robot's state and sensor report gives
\[ P(S=R^{\mathrm{delivery}}\mid Y=R^{\mathrm{delivery}}) = \frac{P(Y=R^{\mathrm{delivery}}\mid S=R^{\mathrm{delivery}})P(S=R^{\mathrm{delivery}})}{P(Y=R^{\mathrm{delivery}})} = \frac{(0.80)(0.30)}{0.31} = \frac{24}{31} \approx 0.774. \]
Prior, likelihood, evidence, and posterior
The prior \(P(S=R^{\mathrm{delivery}})=0.30\) describes the state before reading the sensor. The likelihood \(P(Y=R^{\mathrm{delivery}}\mid S=R^{\mathrm{delivery}})=0.80\) describes how compatible the report is with that state. The evidence \(P(Y=R^{\mathrm{delivery}})=0.31\) accounts for every state that could have produced the report. The posterior \(P(S=R^{\mathrm{delivery}}\mid Y=R^{\mathrm{delivery}})\approx0.774\) is the updated probability after observing it.
The posterior is below the sensor's 80% accuracy because the sensor can also produce the same report from the more common hallway and the dock. Bayes' theorem handles this base-rate effect. It updates probabilities within the assumed model; it does not establish that the prior probabilities or sensor model are correct.
Random variables and distributions
From outcomes to values
An event asks whether an outcome belongs to a set. A random variable assigns a value to every outcome. The state \(S\) is a categorical random variable. A numerical random variable \(X\) can instead record the robot's position along its route:
\[ X = \begin{cases} 0 & \text{at the charging dock},\\ 5 & \text{in the hallway},\\ 9 & \text{in the delivery room}. \end{cases} \]
The numerical values are distances in meters from the dock.
Discrete distributions
A probability mass function (PMF) assigns an actual probability to each exact value of a discrete random variable:
\[ p_X(x)=P(X=x). \]
Here, \(p_X(5)=0.50\) literally means \(P(X=5)=0.50\). The three probability masses sum to one and contain the same state probabilities as before, expressed over positions rather than labels.
Continuous distributions
Now let \(E\) be the sensor's continuous position error in meters. A simple model is
\[ E\sim\mathcal N(0,1). \]
The mean-zero Gaussian represents errors centered at zero with standard deviation one meter. A probability density function (PDF) is different from a PMF: \(f_E(e)\) describes how concentrated probability is near \(e\), but is not itself a probability. For a continuous variable, \(P(E=e)=0\) at any exact value; probability is the area over an interval:
\[ P(a\leq E\leq b)=\int_a^b f_E(e)\,de. \]
The cumulative distribution function works for either kind of random variable:
\[ F_X(x)=P(X\leq x). \]
For a discrete variable it increases in steps. The CDF of a continuous random variable is continuous; for the Gaussian error \(E\), it is smooth.
Expectation and uncertainty
Expected value
The expected value is a probability-weighted average. For the robot's position,
\[ \mathbb E[X] = \sum_x x p_X(x) = (0)(0.20)+(5)(0.50)+(9)(0.30) = 5.2\text{ m}. \]
The robot never occupies position \(5.2\) in this model. Expectation summarizes a distribution; it need not be a value the random variable can take.
Variance and standard deviation
Variance measures squared deviation around the mean:
\[ \operatorname{Var}(X)=\mathbb E[(X-\mathbb E[X])^2]=\mathbb E[X^2]-\mathbb E[X]^2. \]
For this distribution, \(\mathbb E[X^2]=36.8\), so \(\operatorname{Var}(X)=9.76\text{ m}^2\). The standard deviation returns to the original unit:
\[ \operatorname{SD}(X)=\sqrt{9.76}\approx3.12\text{ m}. \]
Two distributions can have the same mean but different variances. The mean records their center; the variance distinguishes how concentrated they are around it.
Conditional expectation
Given a delivery-room sensor report, the posterior state probabilities are \(2/31\) for the dock, \(5/31\) for the hallway, and \(24/31\) for the room. The expected position becomes
\[ \mathbb E[X\mid Y=R^{\mathrm{delivery}}] = (0)\frac{2}{31}+(5)\frac{5}{31}+(9)\frac{24}{31} = \frac{241}{31} \approx7.77\text{ m}. \]
The law of total expectation recovers the unconditional mean by averaging conditional means over every possible report:
\[ \mathbb E[X]=\sum_y \mathbb E[X\mid Y=y]P(Y=y). \]
Expectation is also linear. For any random variables \(X_1,\ldots,X_n\),
\[ \mathbb E\!\left[\sum_{i=1}^n X_i\right]=\sum_{i=1}^n\mathbb E[X_i]. \]
whether or not they are independent. Independence becomes important for quantities such as the variance of a sum, but not for its expected value.
Joint distributions
Marginals, conditionals, and factorizations
The first table is a joint distribution \(p(s,y)\). Summing across a row removes the sensor variable and returns a marginal state probability:
\[ p(s)=\sum_y p(s,y). \]
Dividing a joint probability by its marginal produces a conditional probability. Equivalently, a joint distribution can be factored as
\[ p(s,y)=p(y\mid s)p(s)=p(s\mid y)p(y). \]
These expressions contain the same information arranged in different directions. The factorization \(p(y\mid s)p(s)\) is convenient for specifying how a state generates a sensor report. The reverse \(p(s\mid y)\) is convenient for inferring the state from the report.
Covariance and correlation
Suppose the continuous sensor measurement is \(Z=X+E\), where the error \(E\) has mean zero and is independent of \(X\). The true and measured positions vary together:
\[ \operatorname{Cov}(X,Z)=\mathbb E[(X-\mathbb E[X])(Z-\mathbb E[Z])]=\operatorname{Var}(X)=9.76\text{ m}^2. \]
Correlation normalizes covariance by the standard deviations. With error variance \(1\text{ m}^2\),
\[ \operatorname{Corr}(X,Z)=\frac{9.76}{\sqrt{(9.76)(10.76)}}\approx0.95. \]
The strong positive correlation means large true positions tend to produce large measurements. It does not mean the variables are identical: \(Z\) still contains noise. Independence implies zero covariance when the relevant moments exist, but zero covariance alone does not generally imply independence.
Estimating probabilities from samples
Model probabilities and empirical frequencies
So far, probabilities such as \(P(S=R^{\mathrm{delivery}})=0.30\) have been treated as known. A real system would estimate them from observed robot snapshots. Given \(n\) sampled states, an empirical estimate is
\[ \widehat P(S=R^{\mathrm{delivery}})=\frac{1}{n}\sum_{i=1}^n \mathbf 1\{S_i=R^{\mathrm{delivery}}\}. \]
The indicator is one when snapshot \(i\) places the robot in the delivery room and zero otherwise. The same idea estimates an expectation:
\[ \widehat{\mathbb E}[g(S)]=\frac{1}{n}\sum_{i=1}^n g(S_i). \]
This is Monte Carlo estimation: replace a probability-weighted sum or integral with an average of samples.
Why estimates stabilize
Under independent sampling from the same distribution, the law of large numbers says that the empirical average converges to the expected value. The estimate can fluctuate substantially with a few observations, then tends to settle as more are collected.
The central limit theorem explains why many sample averages are approximately Gaussian around the true mean for large \(n\). Their standard error typically decreases in proportion to \(1/\sqrt n\), subject to the theorem's assumptions.
More observations reduce sampling noise. They do not correct a biased collection process. If snapshots are recorded mostly while the robot charges, their empirical distribution will not describe its state during deliveries, no matter how many such snapshots are collected.
States over time
A stochastic process
A single snapshot ignores movement. Let \(S_t\) be the robot's state at time \(t\). The sequence
\[ S_0,S_1,\ldots,S_T \]
is a stochastic process. Adjacent states are not independent: a robot currently at the dock is more likely to remain there or enter the hallway than to appear directly in the delivery room.
The Markov property
A first-order Markov model assumes that the current state contains all past information needed to predict the next state:
\[ P(S_{t+1}\mid S_t,S_{t-1},\ldots,S_0)=P(S_{t+1}\mid S_t). \]
Consider the following transition model, where one time step is short enough for the robot to stay put or make at most one adjacent move. Direct transitions between the dock and delivery room therefore have probability zero: reaching one from the other requires two adjacent moves through the hallway.
| \(P_{ij}\) | \(S_{t+1}=D^{\mathrm{dock}}\) | \(S_{t+1}=H^{\mathrm{hallway}}\) | \(S_{t+1}=R^{\mathrm{delivery}}\) |
|---|---|---|---|
| \(S_t=D^{\mathrm{dock}}\) | 0.75 | 0.25 | 0.00 |
| \(S_t=H^{\mathrm{hallway}}\) | 0.20 | 0.55 | 0.25 |
| \(S_t=R^{\mathrm{delivery}}\) | 0.00 | 0.30 | 0.70 |
Factoring a trajectory
The general chain rule factors a trajectory into increasingly long conditional distributions. The Markov assumption removes the unnecessary history:
\[ p(s_0,s_1,\ldots,s_T) =p(s_0)\prod_{t=0}^{T-1}p(s_{t+1}\mid s_t). \]
Conditioned on starting at the dock, the probability of the displayed path \(D^{\mathrm{dock}}\rightarrow H^{\mathrm{hallway}}\rightarrow H^{\mathrm{hallway}}\rightarrow R^{\mathrm{delivery}}\) is
\[ (0.25)(0.55)(0.25)=0.034375. \]
The factorization turns one distribution over \(3^{T+1}\) possible state sequences into an initial distribution and a set of one-step transitions. Its usefulness depends on the state representation. Location alone may not be Markov if the next movement also depends on the robot's destination, battery level, or earlier instructions. Those variables would have to become part of the state before the assumption is credible.