Probability Basics for Robotics

• Rolling a single die
  • Possible outcomes, a number 1 - 6: these are the outcomes and they form the sample space
  • The sample space could also consist of (literally) the face of the die that is showing.
    • \(S=\{⚀,⚁,⚂,⚃,⚄,⚅\}\)
  • For this example the sample space is finite
• Breaking a stick in half at a random location
  • Could define the sample space as a set of pairs of stick halves
  • Sample space could be set of all possible distances from the left end where the break occurred
  • For this example, the sample space is uncountably infinite (i.e., a real number)
    • (Aside: Is it really though? The stick is made up of a finite number of atoms. Although maybe the space between those atoms can vary infinitely…)
• At the end of the day, no matter how complicated the system is, there is always
  1. A random experiment
  2. A sample space

• Specify a random experiment by defining
  1. A procedure of what happens:
     • Roll a die one time
     • Command diff-drive robot to drive forward with speed of 0.5 m/s for 2 seconds
  2. At least one observation, for example
     • Note the position of the robot relative to the world coordinate frame)
     • Observe if the number showing at the top of the die is a 1
     • Observe if the number showing at the top of the die is even or odd
     • Observe the distance the robot has traveled from its initial to final position
     • Observe the (theta, x, y) pose of the robot in a world coordinate frame
• Define the sample space \(S\) as the set of possible outcomes (i.e., possible things you have observed)
• Thus all outcomes in the sample space are mutually exclusive (no two outcomes occur at the same time)
  1. For a single die and observing the number at the top it is \(S=\{1,2,3,4,5,6\}\)
  2. For a single die and observing if the number at the top of the die is a 1 it is \(S=\{1 \text{is showing}, 1 \text{is not showing}\}\)
  3. For the robot driving forward when we measure distance it is the set of positive real numbers (since distance is positive)
     • You can also define the sample space as all real numbers, with some outcomes being impossible
  4. For the robot driving forward and measuring the pose it is multimensional cartesian product of intervals: \((-\pi, \pi) \times \mathbb{R} \times \mathbb{R}\).
• Sample space depends not just on the experiment but also on the observation:
  • Toss a coin twice, and note the sequence: \(S = {HH, HT, TH, TT}\)
  • Toss a coin twice, and count the number of heads: \(S ={0, 1, 2}\)

• Relative frequency: number of times a 1 appears divided by \(n\) times
• As \(n\) goes to infinity, relative frequency of the die goes to \(1/6\), just as 1 out of 6 elements in the sample space is a 1
• This is the probability of rolling a 1.

• If you can use a computer to repeat an experiment many times, you can sometimes brute-force an estimate for probability.
• In the real world, it is (technically) impossible to repeat the same exact experiment more than once, but we rely on controlling as many of the initial conditions as possible.

1. Each outcome has relative frequency between 0 and 1
   • You can't get an outcome more than the number of times you run the experiment
2. The sum of the number of number of occurrences across possible outcomes is \(n\) (and thus the sum of relative frequencies is 1)
   • Every experiment yields an outcome
3. The frequency of an event is the sum of the individual frequencies of individual outcomes
   • relative frequency of odd dice rolls = relative frequency of rolling a 1 + rolling a 3 + rolling a 5

• Discrete: Sample space is a finite or countably infinite
  • Countably infinite sample space example: Flip a coin until it is heads. Observe the numbers of tails
  • {0, 1, 2, 3, …}
• Continuous: Sample space is uncountable
  • Spin a wheel, observe the angle
  • Throw a dart on a board, note its x and y coordinates

• Informally: anything that can happen as a result of an experiment that we might want to know the probability of.
• An event is a subset of the sample space.
  • The event occurs if any outcome in the event set occurs
• The certain event: the full sample space, it occurs if any of the outcomes
• The impossible event - never occurs, the empty set.
• Event Class:
  • Contains the events of interest, which are assigned probabilities
  • Compliments, countable unions and countable intersections of events are also in the event class
• For discrete sample spaces: this is (usually) the set of all subsets of \(S\) (this does not hold for continuous sample spaces)
• For continuous sample spaces: complements, countable unions and countable intersections of intervals of the real line \((a, b] \text{ or } (-\infty, b]\)
  • Not set of all subsets (for technical reasons).

1. \(P[A^c] = 1 - P[A]\) (because \(S = A \cup A^c\), \(P[S] = 1\), and \(P[A \cup A^c] = P[A] + P[A^c]\))
2. \(P[A] <= 1\): (from 1, and the fact that \(P[A^c] \geq 0\)).
3. \(P[\emptyset] = 0\) (Let \(A = S\) then \(A^c = \emptyset\), result follows from 1.)
4. \(P[A \cup B] = P[A] + P[B] - P[A \cap B]\)

Random Experiment: Flip two coins, count the number of Heads

• Sample space \(\{0, 1, 2\}\)
• Event Space is \(\{\emptyset, \{0\}, \{1\}, \{2\}, \{0, 1\}, \{0, 2\}, \{1, 2\}, \{0, 1, 2\}\}\)
• Probability: \(P[0] = \frac{1}{4}\), \(P[1] = \frac{1}{2}\), \(P[2]= \frac{1}{4}\)

• Question What is the probability of there having been 1 head given that either 1 or two heads were obtained:

  \begin{align} P[\{1\} | \{1, 2\}] &= \frac{P[\{1\} \cap \{1, 2\}]}{P[\{1, 2\}]} \notag \\ &= \frac{P[\{1\}]}{P[\{1\}\cup\{2\}]} \notag \\ &= \frac{P[{1}]}{P[{1}] + P[{2}]} \notag \\ &= \frac{1}{2}/\frac{3}{4}\notag \\ &= \frac{2}{3} \notag \end{align}
• Note: the probability is higher then the probability of \(\{1\}\) on its own, which makes sense because we've eliminated the possibility of 0 heads.
• We can also write \(P[A \cap B] = P[A | B]P[B] = P[B | A] P[A]\)

• Hypothesis: \(H\) (There is a fire in Tech)
• Evidence: \(E\) (The fire alarm is going off)
• \(P[H]\) is the prior This is the probability of the hypothesis is true in the absence of any evidence. (Probability of a fire in Tech)
  • We are assumed to have some prior understanding of the world
• \(P[E | H]\) is the likelihood. How likely would the evidence be were our hypothesis correct. (Probability of fire alarm going off given that there is a fire).
• \(P[H | E]\) is the posterior - How likely is our hypothesis, now that we've seen the evidence (this is what we are computing
• \(P[E]\) - A "normalization factor". By seeing the evidence we are restricting the size of the sample space to only those samples consistent with the Evidence event having occurred.

• Linus is a computer programmer. He likes writing bash scripts and is a git expert. What is the probability that Linus uses Linux?

  • H - Linus uses Linux
  • Not H - Linus uses Windows (or something else)
  • E - Linus is a computer programmer who likes writing bash scripts and is a git expert.
  • Bayes' Theorem tells us that, even though that there is a high probability that Linux users fit the evidence (they program, like writing bash scripts and are masters at using git), that is P(E | H) is large, and Windows/other users likely don't fit the evidence (that is P(E | not H) is small), the prior probability that a user is a Linux user P(H) is so low that there is actually a greater chance of Linus using Windows/Other rather than Linux.

• Flip two coins. \(\xi \in S\). \(X(\xi)\) is a random variable counting the number of heads. \(Y(X(\xi))\) is a random variable that is twice the number of heads

  \(\xi\)	HH	HT	TH	TT
  X(ξ)	2	1	1	0
  Y(ξ)	4	2	2	0

• Function of a random variable is also a random variable
• If the sample space is already numerical, the random variable is just \(X(\xi) = \xi\)
• So \(X : S \to S_x\), \(S_x \subset \mathbb{R}\), thus \(S\) is the domain and \(S_X\) is the range of the random variable.

• The random variable maps items in the sample space to a finite set of values
• Probability for events \(A_k = \{\xi: X(\xi) = x_k\}\)
• Probability mass function (pmf) \(p_x(x) = P[X = x] = P[\{\xi : X(\xi) = x\}]\), where \(x\) is a real number.
• The event \(A_k = \{\xi : X(\xi) = x_k\}\) is the equivalent event to \(X(\xi) = x_k\)

• Properties of pmf (The events \(A_k\) partition \(S\), which each partition mapping to a value of the random variable).
  1. \(p_x(x) >= 0\)
  2. \(\sum_{x \in S_x} p_X(x) = \sum_{k}p_X(x_k) = \sum_{k}P[A_k] = 1\) (This is because the \(A_k\) partition \(S\))
  3. \(P[X \in B] = \sum_{x\in B}p_X(x),\text{ where }B \subset S_x\) - This is because the events in \(B\) are a union of elementary events.
• pmf provides probabilities for all events from the range of the random variable.
• Conditional pmf \(p_x(x|C) = P[X = x | C] = \frac{P[{X=x}\cap C]}{P[C]}\)

• \(X(\xi)\) is a function from \(S\) to \(\mathbb{R}\) such that \(A_b = \{\xi : X(\xi) \leq b\}\) is in the event class for every \(b\) in \(\mathbb{R}\).
  • Basically, there is an event consisting of all the sample space outcomes that \(X\) maps to a value \(\leq\) b, for any b

• Cumulative Distribution Function (cdf) for random variable X is the probability of the event that \(X \leq x\).

  \begin{equation} F_X(x) = P[X \leq x], -\infty < x < \infty. \end{equation}
• \(P[a < X \leq b] = F_X(b) - F_X(a)\)
• For continuous random variables \(P[X = x] = 0\).

• All types of random variables (continuous, discrete, and mixed) can be described in terms of a cdf.
• We'll use the pmf for discrete random variables and not worry about its cdf (its a staircase function)
• For continuous random variables, we are more used to dealing with a probability density function: \(F_x(x) = \int_{-\infty}^x f(t)dt\), although this does not always exist so is less general.

Probability Density function

• When it exists \(f_x(x) = \frac{dF_X(x)}{dx}\)
• \(f_x(x) >= 0\)
• \(P[a \leq X \leq b] = \int_{a}^{b}f_X(x)dx\)
• pdf completely specifies behavior of continuous random variables
• Conditional cdf

\(F_x(x | C) = \frac{P[{X \leq x} \cap C]}{P[C]}, \text{ if } P[C]>0\)

• Conditional pdf is derivative of conditional cdf with respect to x:

  \begin{equation} f_X(x|C) = \frac{d F_x(x | C)}{dx} \end{equation}

Let \(S_x\) be the range of the random variable \(X\). Then

• The "average of X" after observing X after many experiments.
  • Based on the relative frequency interpretation
  • \(p_x(x) = N(x)/n, n \to \infty\), then \(m_x = \sum_k x N(x_k)/n = \frac{1}{n}\sum_k x_k N(x_k)\)
• Thus, run the experiment many times, take the mean over each run, it should converge to E[X]
• It does NOT mean the value you could expect from any given experiment: For example, flip a coin, \(X(H) = 0\), \(X(T) = 1\), assuming a fair coin \(E[X] = 1/2\).

Expected value of \(Y = g(X)\) \(E[Y]= \int_{-\infty}^{\infty}g(x)f_x(x)dx\)

• This is expected value of X when \(Y = X\) and corresponds to the "center of mass" of the pdf
• Variance: \(g(X) = (X - E[X])^2\) - corresponds to the spread about the "center of mass" of the pdf

Let Z = g(X_1, … X_n).

• for continuous Then \(E[Z] = \int_{-\infty}^{\infty} \dots \int_{-\infty}^{\infty}g(X_1, ... X_n)f_{X_1...X_n}(x_1, ..., x_n) dx_1 \dots dx_n\)
• for discrete, replace integral with sum.
• Joint moment of X and Y: \(E[X^j Y^k] = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty}x^j y^k f_{XY}(x,y) dx dy\)
• When \(j = 0\) or \(k = 0\) we get the mean
• When \(j = k = 1\) we get the correlation. If two variables are not correlated, they are "orthogonal"
  • Subtracting out the mean yields the covariance \(E[(X - E[X])(Y-E[Y])]\).
• Covariance measures deviation from the mean.
• Variables are uncorrelated if covariance is zero
• Independence implies uncorrelated but not the opposite (unless jointly gaussian).