Intro

When someone tells you that the probability of something happening is so and so what do they actually mean? (Let’s assume that person is “properly trained” in the mathematical theory of probability. Otherwise, my answer below is has lower probability of being correct).

Here’s what they mean:

• They are observing some experiment (it could be rolling a die, a soccer match, spread of an epidemic, change in crude oil prices a week from today) whose outcome is (usually) not known in advance, but is in some set of possible outcomes (e.g. the number appearing on the top when rolling a die).
• “something” refers to a collection of one or more possible outcomes (“even”, “@@@70\%@@@ of the population of NYC will be infected by tomorrow”, “the price of a barrel will not exceed @@@\$75@@@”), which they can determine whether occurred or not after their observation is complete. Such sets are known as “events”.
• They have a mathematical model that assigns a numerical weight to each event, the weight being a number between @@@0@@@ and @@@1@@@ (@@@0\%@@@ to @@@100\%@@@), that can be interpreted as a quantitative measurement of “likelihood” or “chance” of the event, AKA “probability” of the event. You can think of the model as a mathematical scale, weighing each possible event. When an event weighs zero it is essentially not observable, and when it weighs one it is guaranteed to be observed, and then there’s in between: a range of uncertainty… The probability can be also viewed as a (careful form of) prediction. That’s it. It is important to understand that the probability assigned is dictated by the model used. Very often we all agree on the model (fair die or fair coin), but this is not always the case. Did you ever notice that Weather.com, NOAA and Weather Underground very often give different “chances of rain” for the same day? If not, try right now.

In this chapter we will explore the mathematical framework for what we just described, particularly the structure of the mathematical models assigning probabilities, AKA probability spaces.

A probability space consists of three components we will now try to briefly explain.

1. The sample space. This is a set including all possible outcomes for the experiment.

   The experiment should be thought of a mechanism resulting in an outcome. This mechanism is often not fully understood (how financial markets work) or is too complex (we know all physics involving rolling a die, yet still we cannot predict what will happen when we roll it), and can be thought of the “randomness”. Whatever the mechanism is at the end it spits out an outcome (value of your portfolio at the end of the year, the number on the top of the die). This procedure of obtaining an outcome is known as sampling, and the collection of all possible outcomes is the sample space. To visualize the sample space and the sampling, think of a claw machine, with sample space being all prize plus on more element a “null” prize. The sampling is the procedure of playing the game, and the outcome of each sampling is the prize.

2. The sigma-algebra (or @@@\sigma@@@-algera) (just a name, don’t dwell on it yet). This represents the information the observer has on the outcome at the conclusion of the observation. In some cases, the observer may not have complete information on the outcome. An event is a statement (“coin landed Heads”) we will be able to determine as true or false at the conclusion of our observation regardless of the outcome, and the sigma-algebra is the collection of all events. To understand the concept, let’s think of the following case. Two dice are rolled. The sample space therefore @@@\Omega= \{1,\dots,6\}^2 = \\{(i,j):i,j \in \\{1,\dots,6\\}\\}@@@. We, as the observers, may have
   • complete information and will be able to identify the outcome, so we will be able to determine whether any statement about the outcome is true of false. For example, we will be able to tell whether first roll is @@@6@@@. Here every statement is an event.
   • partial information on the outcome. For example, we are only told what the sum was, so with the exception of a number of outcomes (how many?) - cannot determine if the statement “first roll is a @@@6@@@” is true or false. Therefore such a statement is not part of the information we have. Another example: “the two dice landed the same number”, and there are many other. We gave two examples of statements which are not events. What are the events then: any statement on the sum is an event, because the sum is exactly the information we are given. Even the statement “the sum is @@@\pi@@@” is an event (we don’t event have to wait for the outcome to determine its truth value though…).
3. The probability measure. Probability measure is a function assigning a numerical value between @@@0@@@ and @@@1@@@ to every event, representing the “weight” of this event. The weight assigned to each event is also known as the probability of the event. This function must satisfy some rules, but very loosely generalizes the idea of proportion (what proportion of the sample space the event occupies), and in many cases - but not always - coincides with proportions, like in real life some objects “weigh” or are “more typical” than other. Note that with the exception of trivialities, there are many different probability measures for the same sigma-algebra, and therefore saying that the probability of event @@@A@@@ is @@@p@@@ is - with a few exceptions - model specific. We choose what probability measure to use. To understand this better, think again of the dice rolling example, and assume we have complete information.
   • The most intuitive setup is where we weigh each event proportionally to the number of corresponding outcomes. To make this clearer, recall first that we have a total of @@@36@@@ elements in the sample space. The event “sum is @@@6@@@”, corresponds to the five outcomes @@@\\{(1,5),(2,4),(3,3),(4,2),(5,1)\\}@@@, and will be assigned probability of @@@5/36@@@. Similarly, the event “the two dice landed the same number” corresponds to six outcomes and will be assigned probability of @@@1/6@@@.

   • Suppose that there’s some magnet under the table causing both dice to land @@@6@@@ every time. A choice of probability measure that will be faithful to this setup is to assign every statement in which at least one of the dice is not a @@@6@@@ a weight or probability @@@0@@@, and assign all remaining statements probability @@@1@@@. For example, the statement “sum is @@@6@@@” will be assigned probability @@@0@@@ and the statement “the two landed the same number” will be assigned probability @@@1@@@ (this always happens!).

     We just described two distinct probability measures for the same sample space, with the same information available to us (there are many, many more). The choice of which to use was based on the sampling, trying to be faithful to the mechanism. We will discuss how to choose the right probability measure when we talk about the Law of Large Numbers. Until then, we will be always provided with a probability measure, so don’t get stressed about that, yet.

Before the real misery begins, let’s enjoy a fun video. Try to think of the concepts we just discussed as you watch it. https://www.youtube.com/watch?v=Kgudt4PXs28

Sample Spaces

Remember we are observers of an experiment? In probability theory, a sample space is the set of all outcomes in the experiment. Why “sample”? This is because we can turn the experiment around and consider it as some mechanism (usually not fully understood to us - can you tell exactly what happens when you toss a coin?) for “sampling” an element from that set of all possible outcomes, the sample space. We usually denote a sample space by the Greek letter Omega, @@@\Omega@@@, and we usually use @@@\omega@@@ to denote an element in the sample space. Let’s introduce a number of examples.

• I’m tossing a coin. The possible outcomes are Heads and Tails, which we will write as @@@H@@@ and @@@T@@@ respectively. Then @@@\Omega= \{H,T\}@@@.
• I’m tossing three coins (or tossing a coin three times in a row). Then each outcome is a sequence of length @@@3@@@ consisting of @@@H@@@ and/or @@@T@@@, representing the outcome of the first, second and third toss respectively. In this case @@@\Omega = \{H,T\}^3 = \{HHH,HHT,HTH,THH,HTT,THT,TTH,TTT\}@@@, a product set. In many cases our experiment will involve repeating some smaller experiment several (or maybe even infinitely many) times, and this is where product sets come handy.
• I’m recording the price of a stock of Google at the end of the next trading day. We will assume the prices form a continuum. The sample space is all nonnegative numbers, @@@\Omega = [0,\infty)@@@.

Mathematically, a sample space is nothing but a nonempty set.

The following example describes what is perhaps the most important sample space in all of probability:

Events and sigma-algebras

Warm up

As already mentioned, depending on the details, we, the observers of the sampling, may have full or partial information on the outcome. Here we will describe what we mean by “information”.

What is knowledge? Ability to answer questions. One can summarize all our information about the outcome as all yes/no questions we will be able to answer for any possible outcome.

Consider the following scenario. Three coins are tossed. The sample space is @@@\Omega= \{H,T\}^3@@@. During the tossing we were blindfolded, and the blindfold was removed at the conclusion of the tossing. The information available to us is therefore the number of Heads (or Tails), but not the order. We can answer all of the following questions about the outcome:

1. Are all tosses @@@T@@@?
2. Is there exactly one @@@H@@@?
3. Are there exactly two @@@H@@@?
4. Are there exactly three @@@H@@@?

Furthermore, the answers to all these questions (any three are enough, right?), determine everything we know about the outcome: the number of Heads. There are more questions we can answer: “is the number of @@@H@@@ even?” “are there more @@@T@@@ than @@@H@@@?”, etc… On the other hand, the question “was the first toss @@@H@@@?” is one we cannot always answer. Of course, if we see @@@3@@@ @@@H@@@ or @@@3@@@ @@@T@@@, we can answer it, but we cannot answer it for any of the @@@6@@@ remaining outcomes. This is an example of a question we cannot always answer, and will be removed from our bank of questions.

The point we’re trying to make here is that “information” is synonymous with what yes/no questions we can answer. A long list of questions does not render as a good candidate for a mathematical object. However, everything one can learn from a question is captured in the answers to it. Particularly for a yes/no question on the outcome, an element in the sample space, all that information is captured in the subset of outcomes corresponding to a “yes” answer (all the remaining automatically correspond to a “no” answer). Therefore one can identify the question with the set of outcomes corresponding to a “yes” answer. The question “is the number of @@@H@@@ odd?” which is one we can answer, corresponds to the subset @@@\{HTT,THT,TTH,HHH\}@@@. The question “is the number of @@@T@@@ equal to @@@3.14@@@?” corresponds to the subset @@@\emptyset@@@, the empty set, etc.

Therefore, each question we can always answer will be replaced by a subset of @@@\Omega@@@, representing all outcomes corresponding to a “yes” answer. Each such subset is called an event and the collection of all events in called a sigma-algebra or @@@\sigma@@@-algebra. An event can be also identified with a statement about the outcome: the statement whose veracity the corresponding question aims to determine. The event @@@\{HTT,THT,TTH,HHH\}@@@ corresponds to the statement “the number of @@@H@@@ is odd” (or “number of @@@H@@@ is @@@1@@@ or @@@3@@@” or “number of @@@T@@@ is even”) and the event @@@\{HHH\}@@@ corresponds to the statement “all tosses are @@@H@@@” (or “no @@@T@@@”). The event @@@\emptyset@@@ corresponds to any statement which is always false, like “number of @@@H@@@ is @@@-1@@@” or “stocking on toilet paper is an act of rationality”.

Definition and first properties

In the last section we saw that the seemingly ambiguous notion of “information” can be made quite precise as the collection of subsets of the sample space, each representing all outcomes corresponding to a “yes” answer to a question we, the observers of the experiment, can answer always answer. pro We observe that any such collection satisfies the following properties:

1. @@@\Omega@@@ is always an event, corresponding to the question “the the outcome in @@@\omega@@@?
2. Suppose @@@A@@@ is an event. If we negate the corresponding question, this we get a new question we can also answer, and the set of outcomes corresponding to a “yes” answer to the new question is exactly @@@A^c@@@. Therefore @@@A^c@@@ is an event. # Suppose @@@A@@@ and @@@B@@@ are events. We can therefore answer “is outcome in @@@A@@@?” and “is outcome in @@@B@@@?”. Therefore we can answer “is outcome in @@@A@@@ or in @@@B@@@?” and as the set of outcomes corresponding to “yes” for the latter question is the union @@@A\cup B@@@, we conclude that @@@A\cup B@@@ is an event. By iterating, the union of any finite number of events is an event.

A collection of subsets of @@@\Omega@@@ satisfying the three properties above is called an algebra of sets on @@@\Omega@@@. Reverse-engineering, we will use these properties as the basis for our mathematical definition of “information”. I said “basis” because there’s going to be one change associated with infinite unions, as - similarly to real life - some structure can be only viewed from birds’ eye, from space, from infinity… and beyond:

Any sigma-algebra is an algebra. Indeed, if @@@{\cal F}@@@ is a sigma-algebra, then @@@\Omega\in {\cal F}@@@ and therefore its complement, @@@\emptyset \in {\cal F}@@@. Now suppose @@@A_1,A_2\in {\cal F}@@@. Then letting @@@A_3=A_4=\dots =\emptyset@@@, we have @@@A_1 \cup A_3 = \cup_{i=1}^\infty A_i \in {\cal F}@@@.

With this definition, we have a new tool. The information about the outcome of the experiment will be always expressed as a corresponding sigma-algebra. Now for concrete sigma-algebras. We begin with two extreme cases.

1. No information at all. The only questions we can answer are those which have only one answer: either always “yes” or always “no”. Therefore the sigma-algebra consists of exactly two sets: @@@\Omega@@@ and @@@\emptyset@@@. WE can write this as @@@{\cal F} = \{\emptyset,\Omega\}@@@. For trivial reasons, this is known as the trivial sigma-algebra.
2. We have all information about the outcome. We can answer any question: if @@@A@@@ is any subset of @@@\Omega@@@, we can answer the question “is the outcome in @@@A@@@?”. Therefore every subset of @@@\Omega@@@ is in the sigma-algebra. This sigma-algebra, the set of all subsets of @@@\Omega@@@ is called the power set of @@@\Omega@@@, and will be denoted by @@@{\cal P}(\Omega)@@@. If @@@\Omega@@@ is finite then the number of elements in its power set is always a power of @@@2@@@. Can you think why?

I want to pause here for a few seconds and make sure we’re all on the same page, regarding the

When @@@\Omega@@@ has more than one element, there are other sigma-algebras than the trivial and the power set. Here’s an example.

We required sigma-algebras to be closed under countable unions. What about intersections? If we look back at the argument that lead to closure under finite unions, then we can guess that algebras and sigma-algebras are also closed under countable intersections. To see why, this follows from the definition we just presented, recall two important identities about sets widely known as De Morgan’s laws:

\begin{equation} \label{eq:demorgan} \boxed { (\bigcap A_i)^c= \bigcup A_i^c. } \end{equation}

On rewriting this (how?) and using the fact that @@@(A^c)^c=A@@@ for any set @@@A@@@, we obtain

\begin{equation} \label{eq:demorgan2} \boxed { (\bigcup A_i)^c = \bigcap A_i^c. } \end{equation}

We comment that \eqref{eq:demorgan} and \eqref{eq:demorgan2} hold regardless whether we are considering finitely many indices @@@i@@@ or not.

Why now? Because De Morgan’s laws give the following property:

In words, sigma-algebras are closed under countable intersections. Of course, they are also closed under finite intersections, as @@@\Omega@@@ is an element in any sigma-algebra. Simply put: if you have any (finite or countable) number of events, then what obtained by taking unions, complements, intersections of any of them is an event. Of course you can iterate that. The only way to “split” an event is by intersecting it with another event. The only way to “enlarge” an event is by taking its union with another event.

Let’s take a quick pause and make sure we understand the relation between the mathematical operations of union, intersection and complements and words. This is something many find confusing. Remember this:”

• “Event A and event B” or any other way to say it in words (e.g. “Both events A and B”) is the intersection of @@@A@@@ and @@@B@@@, @@@A\cap B@@@, with the immediate generalization for more than just two.
• : “and” means “all” means intersection.
• “Event A or event B” or any other way to say it, most commonly “at least one of the Events A and B”, corresponds to the union of @@@A@@@ and @@@B@@@, @@@A\cup B@@@
• : “or” means “at least one” means union.

Here is a more verbal example.

Back to manipulating events:

Let’s look at an example where we perform infinitely many operations.

Two things to note about our last example:

1. It shows how complex events can be obtained by repeatedly applying unions, intersections and complements. Want a challenge? Try to show that “the limit of the proportion of @@@H@@@ among the first @@@N@@@ tosses tends to @@@1/2@@@ as @@@N\to\infty@@@” is also an event. The rule of thumb is this: every statement one can express in words about your observation corresponds to an event.
2. It is an example of a sigma-algebra with infinitely many elements. Such sigma-algebras are pretty complex, and are usually not defined explicitly. Though it may be tempting to think it is actually the power set, it is not. This seems like it is contradicting our rule of thumb, but it doesn’t, due to subsets provided by the axiom of choice. Ask your teacher!

Generation of sigma-algebras

In this section we will discuss some properties of families of sigma-algebras. Suppose you have some information on the outcome and I have some information, representing by the sigma-algebras @@@{\cal F}_1@@@ and @@@{\cal F}_2@@@. Consider the following questions:

1. What is the sigma-algebra representing only information we both know? In terms of questions, this is all question both of us can answer. In terms of subsets, this corresponds to all subsets both in @@@{\cal F}_1@@@ and @@@{\cal F}_2@@@. That is the collection @@@{\cal F}={\cal F}_1\cap {\cal F}_2@@@. It is not surprising that this latter object is itself a sigma-algebra. Thus, one expects intersections of sigma-algebras to be a sigma-algebra.
2. What about our combined information, that is, all questions we can answer collectively? Does this correspond to the union of @@@{\cal F}_1@@@ and @@@{\cal F}_2@@@? No, unless @@@{\cal F}_1={\cal F}_2@@@. Why? Suppose @@@A_1 \in {\cal F}_1@@@ and @@@A_2 \in {\cal F}_2@@@, but @@@A_1 \not \in {\cal F}_1@@@ and @@@A_2\not \in {\cal F}_2@@@ (otherwise, why bother?). Now “is outcome in @@@A_1@@@ or in @@@A_2@@@?” is an answer we can answer with joint efforts: I can tell whether it is in @@@A_1@@@ and you can tell whether it is in @@@A_2@@@, so after consulting we can determine whether determine whether the outcome is in @@@A_1@@@ or in @@@A_2@@@, that is whether it is in @@@A_1\cup A_2@@@. As a result, the event @@@A_1\cup A_2@@@ must be in the sigma-algebra corresponding to our combined information. However @@@{\cal F}_1\cup {\cal F}_2@@@ consists entirely of subsets in @@@{\cal F}_1@@@ or in @@@{\cal F}_2@@@, and @@@A_1 \cup A_2@@@ is in neither sigma-algebras. But by our assumption, this event is in neither sigma-algebras. Indeed, the union is, say, in @@@{\cal F}_1@@@, then @@@A_2\cap A_1^c = (A_1 \cup A_2 )\cap A_1^c \in {\cal F}_1@@@ and @@@A_2\cap A_1 = (A_1 \cup A_2) \cap A_1 \in {\cal F}_1@@@. Therefore @@@A_2 = (A_2 \cap A_1^c) \cup (A_2 \cap A_1) \in {\cal F}_1@@@, a contradiction to our assumption. Bottom line: when it comes to information, the “sum” is bigger than its parts.

In the rest of this section we discuss topics around these very two questions. We begin with a rather general answer to the first.

An application of the proposition gives:

In words, @@@\sigma({\cal R})@@@ represents the minimal amount of information needed in order to be able determine if the outcome is in any given element @@@R@@@ of @@@{\cal R}@@@. It count be thought as the smallest sigma-algebra containing all elements of @@@{\cal R}@@@. Seems complicated?

The last example gave us two very simple of examples of sigma-algebras generated by some sets. Let’s look at a much more general setup, where the notion is actually needed because we cannot list all elements explicitly. Take @@@\Omega= \R@@@, the real line, and let @@@{\cal R}@@@ be the set subset consisting of all intervals. Then any sigma-algebra containing @@@{\cal R}@@@ must contain all countable unions of intervals, intersections of these objects, unions of complements of the resulting objects, etc… This is a pretty large family, and we do not have a good direct description of all of its elements. We call this sigma-algebra the Borel sigma-algebra on @@@\R@@@. This is the smallest sigma-algebra containing all intervals.

You may ask now why even bother defining the Borel sigma-algebra, rather than simply working with thew power set directly. The source of the problem comes from the reason why we defined sigma-algebras in the first place: objects we will eventually assign weights to. There will be some reasonable assumptions the weighing function, the probability measure must satisfy, which, if attempted to be defined on a too-large sigma-algebra, may be impossible.

We also have the Borel sigma-algebra in higher dimensions:

What I want you to take from here is the following. Let’s take @@@n=1@@@. The Borel sigma-algebra is a sigma-algebra containing all intervals (open or not) and anything that can be obtained from intervals through repeated countable unions, complements of unions, etc. This is NOT the power set, but it is a class rich enough to cover all subsets of the real line you are familiar with. Same in higher dimensions. The Borel sigma-algebra contains all nice (and many not so nice) sets, because each can be approximated with rectangles.

In first reading you can skip from here until the end of the section.

To illustrate the versatility of the idea of sigma-algebra, consider the following.

Why am I bugging you with all these theoretical nonsense? Suppose we can toss a coin indefinitely, and we can record the outcome of each toss. The sample space in this case is the one from Example 12, and the sigma-algebra is all subsets of this space determined by observing the outcome of each toss (won’t go into details, but surprisingly enough it is not all subsets of the sample space. Strange things happen at infinity). With this, for any @@@n@@@, the set “@@@n@@@-th toss is a Heads” is an event. And therefore by Example 13, “At least @@@i@@@ Heads” is an event for any @@@i@@@, and then by Proposition 1 the intersection of all of these newly created events is itself an event. What is this intersection? “infinitely many Heads” (at least @@@i@@@ for any @@@i@@@). Similarly, the first part of Exercise 10 tells us that “exactly @@@i@@@ Heads” is an event as well. Ok, but why do we care? because all the beautiful structure (which is also highly useful for applications!) is only fully revealed when we go to infinity (think of it as watching us from space), and very important statements like “asymptotically the proportion of Heads tends to @@@1/2@@@ with probability @@@1@@@” (the law of large numbers) which require being able to assign probabilities to sets involving infinitely many tosses.

Essentially, whatever we can describe in words is an event, but this won’t qualify as a mathematical definition, while sigma-algebras are well-defined mathematical objects, and are pretty easy to describe.

Probability Measures

Warmup discussion

Quick recap. We are the observers of a sampling, an experiment in which an element is sampled from our sample space @@@\Omega@@@. The element sampled is called the outcome (of the experiment). We have a sigma-algebra @@@{\cal F}@@@, a collection of subsets of @@@\Omega@@@, each representing a statement about the outcome, we the observers, are able to determine whether true or false at the conclusion of our observation. These subsets, the elements of @@@{\cal F}@@@, are called events. The pair @@@(\Omega,{\cal F})@@@ is called a measurable space.

This entire structure was just preparation for what we describe in this section, the notion of a probability measure. Probability measure is a mathematical weighing tool. What does it weigh? Events. At an intuitive level it is good to think of the weights as a measure of the size of an event in the sample space, or what portion of the sample space it occupies. The weights assigned are always between @@@0@@@ and @@@1@@@, which is the same as from @@@0\%@@@ to @@@100\%@@@. The weight assigned to the event is referred to as the probability of the event.

Before getting into the formal definition, let’s begin with a concept we’re all familiar with, that of relative frequency or proportion. Suppose @@@\Omega@@@ is finite. The relative frequency of any subset @@@A@@@ is given by @@@|A|/|\Omega|@@@. The relative frequency if a function from the power set of @@@\Omega@@@ to the interval @@@[0,1]@@@ satisfying the following two properties:

1. The relative frequency of @@@\Omega@@@ is @@@1@@@ (normalization)
2. If @@@A@@@ and @@@B@@@ are disjoint (do not share any elements, @@@A\cap B = \emptyset@@@), then the relative frequency of the union @@@A \cup B@@@ is the sum of the relative frequencies of @@@A@@@ and @@@B@@@ (property known as additivity).

Note that by iterating the additivity property, the relative frequency of the union of any (finite) number of disjoint subsets is the sum of the respective relative frequencies.

The two properties will continue to hold if we were to assign each element @@@\omega@@@ some value @@@p_\omega\ge 0@@@, with @@@\sum_{\omega\in \Omega} p_\omega =1@@@, and then define the weight of an event @@@A@@@ as the sum of the weighs of its elements, @@@\sum_{\omega\in A} p_\omega@@@. Note that relative frequency corresponds to setting @@@p_\omega = \frac{1}{|\Omega|}@@@ for all @@@\omega \in \Omega@@@. Why do we even care about such cases? They come up naturally, even from relative frequencies…

Definition and first examples

A probability measure is a mathematical object satisfying the two properties we listed in the last section, but a little more:

The triple of consisting of sample space @@@\Omega@@@, a sigma-algebra @@@{\cal F}@@@ and a probability measure @@@P@@@ on @@@{\cal F}@@@ is called a probability space and we denoted it by @@@(\Omega,{\cal F},P)@@@. The probability space describes, in this order, what the outcomes are (what we sample), what are the events, and what are the weighs assigned to each event.

The three conditions @@@P(A)\ge 0@@@, 1., and 2. are known as the probability axioms. The countable additivity axiom generalizes the additivity property for relative frequencies beyond a finite number of sets.

Recall that no matter what @@@{\cal F}@@@ is, @@@\Omega@@@ and @@@\emptyset@@@ are events. The probability of @@@\Omega@@@ is set by the normalization axiom. What about the probability of the empty set? Let’s see. Set @@@\alpha = P(\emptyset)@@@. Set @@@A_1=\Omega@@@, @@@A_2=A_3=\dots =\emptyset@@@. Then the normalization and countably additive axioms tell

Therefore @@@\alpha=0@@@.

Suppose @@@A_1,A_2,\dots,A_N@@@ are pairwise disjoint events. Set @@@A_{N+1}=A_{N+2}=\dots = \emptyset@@@. Then

In particular, letting @@@A\in{\cal F}@@@, @@@A_1=A,A_2 =A^c@@@, we conlcude

The first and second inequalities are both due to the fact that probabilities are nonnegative.

We proved the following:

Time for actual examples. Here’s the most natural one.

We’ve seen two examples. Both are special cases of the following result.

In the sequel whenever @@@\Omega@@@ is finite, we tacitly assume that @@@P@@@ is the uniform probability measure, also, when we say “randomly” without specifying a probability measure, we mean that we use the uniform probability measure. It’s a convention (“I randomly pick pants and a shirt” to be understood that the probability of each combination is the same).

The definition of the @@@\delta@@@-measure may seem a little awkward at first sight. The simplest and most common instances of it are when @@@A_0@@@ has exactly one element, say @@@x_0@@@. In this case, it is often common to refer to the @@@\delta@@@ measure as @@@\delta_{x_0}@@@.

Don’t be fooled to think that @@@\Omega@@@ must always be finite or countable. After all, there has to be a reason why Calculus is a prerequisite… Here is a result discussing some very important probability measures on @@@\R@@@.

Note that if @@@P@@@ is a probability measure with density as in the theorem, then for any real @@@a\le b@@@, @@@P([a,b]) = P((a,b]) = P([a,b)) = P((a,b)) = \int_a^b f(x) dx@@@. In particular, the second equality gives the following:

More properties of probability measures

In what follows, we omit the reference to @@@\Omega@@@ and @@@{\cal F}@@@.

Note the connection between item 2 and the addition rule from combinatorics.

Here is a very simple implementation of all three parts of the Proposition.

Let’s combine combinatorics and the very little probability we know so far. This example also uses the first part of the proposition, the probability of the complement. It shows that sometimes switching to the complement makes life easier.

The birthday problem is a true classic https://www.youtube.com/watch?v=KtT_cgMzHx8&vl=en

The next example uses the second part of the proposition.

Computing the probability of a union of events may be gruesome. There is a general formula, the inclusion/exclusion formula we will discuss in more detail in the next section, a snapshot of which we saw in the second part of Proposition 8, and it uses the probabilities of intersections of the events, something we may not be able to calculate. Here is a pretty crude but very useful bound known as the union bound.

This results somewhat complements the additivity property in the Definition 3 of probability measures: probability of a union is bounded above by the sum of the probabilities, and an equality holds if the events are disjoint.

Here is an illustration of the usefulness of the bound.

The Inclusion/Exclusion Formula

Proposition 8-2 generalizes the addition rule from number of elements in sets to probabilities of events. It states that if @@@A@@@ and @@@B@@@ are events, then the probability of their union @@@A\cup B@@@ can be expressed in terms of the probabilities of the events themselves and their intersection. In this section we generalize this formula. The generalization is known as the inclusion/exclusion formula. It may seem complicated at first sight, but it is nothing but the result of applying the rule for two events repeatedly. The principle is simple, the resulting formula is less. Sometimes understanding is better than memorizing… Let’s list it:

Here’s a compact way to write the inclusion/exclusion formula:

\begin{equation} \label{eq:incl_exclusion} \boxed { P(\cup_{i=1}^n A_i)= \sum_{k=1}^n (-1)^{k+1}\sum_{I \subset{1,\dots,n},|I|=k} P(\cap_{i\in I}A_i) . } \end{equation}

How likely is everything to go wrong? Here is a theoretical answer, a true classic, known as the Old Hats Problem, or the Matching Problem, or Absent minded secretary problem, and probably other names as well.

Probability measures on @@@\R^n@@@ with densities

We talked mostly about probability measures on finite sample spaces and touched some probability measures on @@@\R@@@ in Theorem 6. In this section we will expand the discussion a little more, also going to the @@@n@@@-dimensional space @@@\R^n@@@.

Let’s first consider @@@\R@@@, the real line, as our sample space. In our to define a probability measure on it, we first need a sigma algebra. We’re already familiar with two ones: the trivial and the power set, yet the former is too small (has only two elements) and the latter is too big as this is beyond our level.

The most natural objects on the real line are intervals, and therefore it makes perfect sense to consider only those sigma algebras that contain all intervals. The smallest sigma algebra that contains all intervals is the Borel sigma algebra. Of course, it contains much more than just intervals, for example, it contains countable unions of intervals, complements of such objects (which themselves are not necessarily countable unions of intervals), intersections of those, etc…

The higher dimension analog of intervals is a measurable rectangles, that is products of intervals. If @@@I_1,I_2,\dots,I_n@@@ are intervals in @@@\R@@@, then the corresponding measurable rectangle in @@@\R^n@@@ is the set @@@ I_1\times \cdots \times I_n = \{ {\bf x} =(x_1,\dots,x_n)| x_1 \in I_1, \dots,x_n \in I_n\}@@@. The Borel sigma algebra on @@@\R^n@@@ is the smallest sigma algebra containing all measurable rectangles.

For compactness, we may sometimes refer to @@@\R@@@ as @@@\R^1@@@.

We will completely avoid the technical discussion but here is the important principle to remember:

• Any subset of @@@\R^n@@@ you can name, describe in words or write a formula for is a Borel set. Everything you saw in multivariable calculus, and much beyond. This is a huge set of objects, but it does not contain all subsets of @@@\R^n@@@.
• In light of the above, in what follows, whenever discussing probability measures on @@@\R^n@@@, we will always assume that the underlying sigma algebra is the Borel sigma algebra.

We begin with a result describing some of the most commonly used probability measures on @@@\R^n@@@, and which generalizes Theorem 6.

Before we discuss the result, we will need an important definition.

Time for an example.

We remind that not all probability measures on @@@\R^n@@@ have densities. One example is of the @@@\delta@@@ measure (with @@@A_0=\{x_0\}@@@).

Continuity of probability

This notion is of fundamental importance though we will rarely use it in our discussion. It concerns infinite sequences of events. We need some preparation.

Whenever dealing with an infinite sequence of events, it is convenient to re-express them as a sequence of pairwise disjoint events.

The first application is a proof for the union bound in the countable case. We will list it as an example.

Suppose that @@@A_1\subset A_2 \subset@@@. Clearly, @@@\cup_{i=1}^\infty A_i@@@ is contained in any set containing all of the @@@A_i@@@. That is, the union is the smallest set containing all of the @@@A_i@@@’s. Much in the same spirit that the limit of an non-decreasing sequence of numbers is the smallest number larger or equal to all of them (if there exists such a number), we declare @@@\cup_{i=1}^\infty A_i@@@ as the limit of the non-decreasing sequence of sets @@@A_1,A_2,\dots@@@. The following shows that that if we first take limit of the events then compute its probability; or first compute probabilities of the individual events, and then take their limits, we get the same number. This is a statement identical to limits of sequences under continuous functions, and is therefore dubbed as continuity of probability measure with respect to non-decreasing sequences of events:

What about decreasing limits? This is a simple consequence of the proposition.

We tasted some manipulation of infinite events, and we saw how in this infinite setting we may naturally encounter events of probability zero which are far from being empty of finite or even countably infinite… We also see how to identify complex statements on the entire sequence (“every pattern appears”) as events through the allowed operations in a sigma-algebra (though we did not provide a complete argument, there’s a missing detail that I’d like to ask you to try to find and complete. It’s in the paragraph above).

Problems

• Intro
• Sample Spaces
• Events and sigma-algebras
  • Warm up
  • Definition and first properties
  • Generation of sigma-algebras
• Probability Measures
  • Warmup discussion
  • Definition and first examples
  • More properties of probability measures
    • The Inclusion/Exclusion Formula
  • Probability measures on @@@\R^n@@@ with densities
• Continuity of probability
• Problems