This lecture note is still being edited: the text may contain typos, inaccuracies, and locally unpolished spots. If you find something, please let the author know (contact information on the course page).
This entire first week relies on what you already know from school: classical probability (coins, dice, cards β probability equals the ratio of the number of favorable outcomes to the total number of outcomes) and geometric probability (for example, the meeting problem β probability equals the ratio of areas or lengths). Our goal here is not to tell you something fundamentally new, but to carefully formalize what you can already compute intuitively. We will start with the classical model (everything is simple there), then move on to the geometric one β and there we will run into a crack in this intuition: it will turn out that, unlike in the classical case, we cannot declare every subset of the sample space to be an event. This very crack is the main motivation for the whole course: to patch it up, in the second half of the semester we will build measure theory from scratch.
Classical Probability
The subject of study of probability theory is random events and their probabilities. By a random event we mean a collection of outcomes of some experiment.
Suppose some random experiment admits \(N\) distinct outcomes (for example, when tossing a coin there are only two outcomes: heads and tails). Denote these outcomes by \(\omega_{1}, \ldots , \omega_{N}\). The outcomes \(\omega_{1}, \ldots , \omega_{N}\) are called elementary events, and the set \(\Omega =\left\{ \omega_{1}, \ldots , \omega_{N}\right\}\) is the sample space (space of elementary events). In general, the sample space need not be finite, or even countable.
Definition 1 The elements \(\omega \in \Omega\) are called elementary events or elementary outcomes, and their collection \(\Omega\) is the sample space (space of elementary outcomes).
An event is an arbitrary subset \(A \subset \Omega\). We say that the event \(A\) has occurred if the experiment ended in one of the elementary outcomes belonging to \(A\).
As long as \(\Omega\) is finite (as in all the examples above), no difficulties arise regarding which subsets should count as events: any subset of \(\Omega\) can be taken as an event, i.e., as the collection of all events we take \(\mathcal{F} = 2^{\Omega }\) β the set of all subsets of \(\Omega\). Subtleties will appear later, in the section on geometric probability, once \(\Omega\) becomes infinite.
Let, as before, \(\left|\Omega \right| = N \in \mathbb {N}\), \(\mathcal{F} = 2^{\Omega }\). Assume in addition that all elementary outcomes are equally likely, i.e.,
\[
\forall i \in \{ 1, \ldots , N\} \quad \mathbb {P}\left(\omega \right) := \mathbb {P}\left(\left\{ \omega \right\} \right) =\frac{1}{N}
\]
This can also be written as \(\mathbb {P} = \frac{1}{N}\#\), where \(\#\) is the counting measure, which in general is defined by
\[
\# (A) = \begin{cases} n, & \text{ if $A$ is finite and has $n$ elements} \\ + \infty , & \text{otherwise} \end{cases}
\]
An experiment described by such a probability space is called a classical probability model. Rolling a die can serve as an example of such an experiment. Here \(\Omega =\{ 1,2,3,4,5,6\} , \mathcal{F}=2^{\Omega }\) and \(\mathbb {P}\left(i\right)=\frac{1}{6}\).
As examples of the classical probability model, let us consider the standard urn schemes: from a basket of \(n\) items, \(k\) items are chosen at random. We assume that the appearance of any item is equally likely.
Describe the probability space for the scheme of ordered sampling without replacement.
Suppose the choice of the \(i\)-th element corresponds to the elementary outcome \(\omega_{i}\). This is the scheme of ordered sampling without replacement. For this scheme, the sample space is as follows:
\[
\Omega =\left\{ \omega = \left(\omega _{i_{1}}, \omega _{i_{2}}, \ldots , \omega _{i_{k}}\right) \; , \; i_{1}, i_{2}, \ldots , i_{k} \text{ -- distinct numbers from }\{ 1, \ldots , n\} \right\}
\]
That is, \(\omega\) is a tuple (an order-sensitive structure) of \(\omega_i\)βs, each denoting the drawing of one item or another; since sampling is without replacement, all the indices are distinct.
The number of elements in \(\Omega\) equals \(A_{n}^k = n(n-1)\cdots (n-k+1)\): at the first step we can equally likely choose any of the \(n\) items, at the second step β any of the remaining \(n-1\), and so on. Owing to this symmetry, any tuple occurs with equal probability. That is, \(\mathbb {P} = \frac{1}{A_{n}^k}\#\). Hence the probability space for this model is classical.
From a basket of \(n\) items, \(k\) items are chosen at random. Describe the probability space for the scheme of unordered sampling with replacement.
Two \(M\)-sided dice, with the numbers from 1 to \(M\) written on their faces, are thrown at random. Describe the probability space whose events correspond to all possible outcomes of this experiment. Find the probability of the event \(A_{i}\) defined by \(A_{i}=\{\) the sum of the numbers shown on the dice equals \(i\} , i=2,3, \ldots , 2 M\).
A random subset is chosen from a set of \(N\) objects. Describe the corresponding probability space and find the probability that this random subset has even cardinality.
A set of \(n\) balls is randomly distributed among \(m\) boxes. Find the probability that all boxes are nonempty, given that the balls are distinguishable.
We are interested in the event
\[
B = \{ \text{all boxes are nonempty}\} .
\]
We have
\[
\mathbb {P}\left(B\right) = 1 - \mathbb {P}\! \left(\bigcup _{i=1}^m A_i\right), \quad A_i = \{ \text{the $i$-th box is empty}\} .
\]
By the inclusionβexclusion formula:
\[
\mathbb {P}\! \left(\bigcup _{i=1}^m A_i\right) = \sum _{j=1}^m (-1)^{j+1} \sum _{1\le i_1<\cdots <i_j\le m} \mathbb {P}\left(A_{i_1}\cap \cdots \cap A_{i_j}\right).
\]
But
\[
\mathbb {P}\left(A_{i_1}\cap \cdots \cap A_{i_j}\right) = \frac{(m-j)^n}{m^n},
\]
since all \(n\) balls must land in the remaining \(m-j\) boxes. Consequently,
\[
\mathbb {P}\left(B\right) = \frac{1}{m^n} \sum _{j=0}^{m} (-1)^j \binom {m}{j} (m-j)^n.
\]
Thus,
\[
\boxed {\; \mathbb {P}\left(\{ \text{all boxes are nonempty}\} \right) = \frac{\sum _{j=0}^{m} (-1)^j \binom {m}{j} (m-j)^n}{m^n}\; }
\]
is the desired probability.
Geometric Probability
Another construction familiar from school is geometric probability: a point is thrown at random into a region \(\Omega\) (a segment, a planar figure, a solid in space), and the probability of landing in a subregion \(A \subset \Omega\) is computed as the ratio of βsizesβ (lengths, areas, volumes).
By analogy with the classical model, one would like to declare all subsets of \(\Omega\) to be events β just as we did for finite \(\Omega\). But here, for the first time in this course, this simple idea breaks down.
It turns out that there is no way to assign an βareaβ to all subsets of a square (a segment, a cube) such that the following reasonable requirements simultaneously hold: it should be countably additive (the area of a countable union of disjoint pieces equals the sum of their areas), it should not change under translations, and it should agree with the usual area at least for rectangles. The proof of this fact essentially uses the axiom of choice and is not given here (an explicit example of such a βnon-measurableβ set β the Vitali set β will be constructed in the second part of the course). But the fact itself already tells us: in geometric probability we cannot declare all subsets of \(\Omega\) to be events β we need to restrict in advance the collection of sets that we allow to have an βareaβ at all.
What properties, then, should this restricted collection \(\mathcal{F} \subset 2^{\Omega }\) of βgoodβ (measurable) sets have? It is reasonable to require that:
the whole space \(\Omega\) itself is an event;
the complement of an event is an event (if we can measure \(A\), we should also be able to measure βeverything elseβ);
the union of events is an event β and not just for finite unions, but also for countable ones: among other things we will need to find probabilities of limits of events, and this is impossible without countable unions.
(If we restrict ourselves to only finite unions, we get a weaker notion β an algebra of sets; we will study it, together with finer systems of sets β semirings and rings β in detail in the second part of the course.) A collection of sets closed under all three requirements above is called a sigma-algebra.
Definition 2 A system of sets \(\mathcal{F}\) is called a sigma-algebra if the following 3 properties hold:
\(\Omega \in \mathcal{F}\);
if a set \(A \in \mathcal{F}\), then its complement \(\bar{A} \in \mathcal{F}\) as well;
if the sets \(A_{1}, A_{2}, \ldots \in \mathcal{F}\), then their infinite union \(\bigcup_{i=1}^{\infty } A_{i} \in \mathcal{F}\) as well.
By De Morganβs rule it follows immediately that a sigma-algebra is also closed under countable intersections: \(\bigcap_{i=1}^{\infty } A_i = \overline{\bigcup_{i=1}^{\infty } \bar{A}_i} \in \mathcal{F}\). Also \(\varnothing = \bar{\Omega } \in \mathcal{F}\).
Suppose we are given a sample space \(\Omega\) and a sigma-algebra \(\mathcal{F}\) on it. A set \(A \in \mathcal{F}\) is called an event. (In the classical model we implicitly took \(\mathcal{F} = 2^{\Omega }\) β this is also a sigma-algebra, and in fact the largest possible one: all three properties hold for it automatically, which is why there was no need to think about any of this there.)
It remains to formalize probability itself.
Definition 3 A function \(\mathbb {P}: \mathcal{F} \to [0,1]\) is called a probability measure (or simply a probability) if \(\mathbb {P}\left(\varnothing \right) = 0\), \(\mathbb {P}\left(\Omega \right)= 1\), and \(\mathbb {P}\) is countably additive: \[
\mathbb {P}\left(\bigsqcup _{n=1}^{\infty } A_i\right) = \sum _{i=1}^{\infty } \mathbb {P}\left(A_i\right)
\] for any collection of pairwise disjoint sets \(\left\{ A_n\right\}_{n=1}^{\infty } \subset \mathcal{F}\). That is, \(A_n \in \mathcal{F}\) for all \(n\) and \(A_{n_1} \cap A_{n_2} = \varnothing\) for any distinct \(n_1 \neq n_2\).
Pairwise disjoint sets from \(\mathcal{F}\) are also called mutually exclusive events. Countable additivity means that the probability of the occurrence of a countable family of mutually exclusive events (at least one of them) can be computed as the sum of the series of their probabilities.
In the classical model this additivity is trivial: there are only finitely many (nonempty) events there, and countable additivity degenerates into ordinary finite additivity.
Definition 4 A triple \((\Omega , \mathcal{F}, \mathbb {P})\), consisting of a set of elementary events, a sigma-algebra of events, and a probability measure, is called a probability space or a Kolmogorov triple.
We now have a common language in which we can complete the formalization of geometric probability.
The classical geometric probability model is the class of probability models where:
Sample space: \(\Omega \in \mathscr {B}\left(\mathbb {R}^n\right)\) β a Borel subset of \(\mathbb {R}^{n}\) with finite \(n\)-dimensional volume (\(n = 1, 2, 3\));
Events: \(\mathcal{F} = \mathcal{B}(\Omega )\) β the Borel \(\sigma\)-algebra on \(\Omega\);
Probability: uniform, namely \(\mathbb {P}(A) = \frac{\lambda (A)}{\lambda (\Omega )}\), where \(\lambda\) is \(n\)-dimensional Lebesgue measure.
Thus, the probability space has the form:
\[
(\Omega , \mathcal{B}(\Omega ), \mathbb {P})
\]
where \(\mathbb {P}(A) = \dfrac {\lambda (A)}{\lambda (\Omega )}\) for any \(A \in \mathcal{B}(\Omega )\).
This model describes experiments in which a particle is uniformly distributed over the region \(\Omega\), and the probability of landing in a subregion \(A\) is proportional to its volume.
Borel sets and Lebesgue measureborel-lebesgue We have just referred to two specific objects that we have not defined: the Borel sigma-algebra \(\mathscr {B}\left(\Omega \right)\) (the chapter on systems of sets and the Borel sigma-algebra) and Lebesgue measure \(\lambda\) (the chapters on outer measure and CarathΓ©odoryβs theoremβon Lebesgue measure). We have already defined the abstract notion of a sigma-algebra above β it remains to understand why one takes specifically the Borel sigma-algebra (rather than some other one), and how to construct \(\lambda\) so that it is a genuine countably additive measure (rather than just an intuitive βsizeβ). For now, let us agree to understand them naively: Borel sets are all the βreasonableβ subsets of \(\mathbb {R}^{n}\) (in particular, any polygons, disks, as well as their countable unions and intersections), and \(\lambda (A)\) is the familiar length/area/volume of the set \(A\).
A point \(A\) is chosen uniformly at random inside a rectangle with sides \(1\) and \(2\). Find the probability that the distance from the point \(A\) to the nearest side of the rectangle does not exceed \(x\).
In this case \(\Omega = [0,2] \times [0,1]\), \(\mathcal{F} = \mathscr {B}\left(\Omega \right)\), \(\mathbb {P} = \frac{1}{\lambda (\Omega )}\lambda = \frac{1}{2} \lambda\), where \(\lambda\) is Lebesgue measure on \(\mathbb {R}^{2}\).
Let us consider when the distance from the point \(A\) to the nearest side is greater than \(x\). This is possible only if the point \(A\) lies inside the βinnerβ rectangle with sides \(1-2x\) and \(2-2x\), obtained by moving in from each side of the original rectangle by \(x\).
\[
\mathbb {P}\left(\rho (A,\partial R) > x\right) = \frac{(1-2x)(2-2x)}{\lambda (\Omega )} = (1-2x)(1-x)
\]
since the area of the original rectangle equals \(2\). Consequently,
\[
\mathbb {P}\left(\rho (A,\partial R) \leq x\right) = 1 - \mathbb {P}\left(\rho (A,\partial R) > x\right) = 1 - (1-2x)(1-x) = 3x - 2x^2
\]
Note that when \(x \geq 0.5\) the inner rectangle disappears, and the probability equals \(1\).
\(\begin{cases} 3x - 2x^2, & x < 0.5, \\ 1, & x \geq 0.5. \end{cases}\).
Consider a circle of radius \(R\). A chord of this circle is chosen at random. We want to find the probability that the length of the chord \(\xi\) exceeds the length of a side of an equilateral triangle inscribed in this circle, i.e., the probability \[
\Omega = [0, 2\pi) \times [0, 2\pi), \quad \mathcal{F} = \mathscr{B}\left(\Omega\right), \quad \mathbb{P} = \frac{\lambda}{\lambda(\Omega)} = \frac{\lambda}{4\pi^2}
\]
Bertrandβs paradox is the fact that this problem can have different probabilistic interpretations, leading to different answers. Let us consider three classical approaches.
A chord can be uniquely specified by its endpoints. These can be specified by angles from the horizontal axis. That is, in this case \[
\Omega = \{(x,y): x^2 + y^2 < R^2\}, \quad \mathcal{F} = \mathscr{B}\left(\Omega\right), \quad \mathbb{P} = \frac{\lambda}{\lambda(\Omega)} \frac{\lambda}{\pi R^2}
\] where \(\lambda\) is Lebesgue measure on \(\mathbb {R}^{2}\). In this case the elementary outcome consists of 2 angles: \(\omega = (\alpha , \beta ) \in \Omega\).
Construction of a chord from two random endpoints: the angles Ξ±, Ξ² β [0,2Ο) are chosen independently and uniformly. Hover over the chord or the arcs to see the exact values.
A chord is longer than a side of the equilateral triangle inscribed in the circle if \(\angle AOB > 120^\circ = \frac{2}{3}\pi\). One can compute that the following region \(S\) works for us:
The sample space \(\Omega = [0,2\pi)\times[0,2\pi)\) together with the appropriate region \(S\) (in green) and the point corresponding to the example in the previous figure.
Its area equals \(12\) small squares of side \(\frac{1}{3}\pi\), i.e., \(\lambda (S) = 12 \cdot \left(\frac{1}{3}\pi \right)^2 = \frac{4}{3} \pi^2\). In total, the probability: \(\frac{\lambda (S)}{\lambda (\Omega )} = \frac{1}{3}\).
A chord is uniquely determined by its center. Consider all chords whose center lies inside the disk. Then:
\[
\Omega = [0, 2\pi) \times [-R, R], \quad \mathcal{F} = \mathscr{B}\left(\Omega\right), \quad \mathbb{P} = \frac{\lambda}{4\pi R}
\] A chord is longer than a side of the equilateral triangle if its center lies inside a disk of radius \(R/2\) (where \(R\) is the radius of the original circle). This corresponds to the area:
Construction of a chord from a random center C, uniform inside the disk: the chord is uniquely determined by its center (perpendicular to OC). The green region S consists of the centers of chords longer than a side of the inscribed triangle (radius R/2).
Area of the region: \(\lambda (S) = \pi (R/2)^2 = \pi R^2/4\). Probability: \(\frac{\lambda (S)}{\lambda (\Omega )} = \frac{1}{4}\).
We choose the direction of the chord, then choose the position of its center on the diameter perpendicular to that direction.
\[
\label{CondProb:Def}
\mathbb{P}\left(A \mid B\right) = \begin{cases}
\frac{\mathbb{P}\left(A \cap B\right)}{\mathbb{P}\left(B\right)}, & \mathbb{P}\left(B\right) > 0 \\
\text{undefined}, & \mathbb{P}\left(B\right) = 0 \\
\end{cases}
\]
Construction of a chord from a random direction Ξ± and position x on the perpendicular diameter: x is uniform on [-R, R]. The point C is the center of the chord found from (Ξ±, x).
In this case \(\omega = (\alpha , x)\). A chord is longer than a side of the equilateral triangle if the distance from the center to the chord satisfies \(|x| < R/2\):
The sample space \(\Omega = [0,2\pi)\times[-R,R]\) together with the appropriate region \(S\) (in green) and the point corresponding to the example in the previous figure.
Area of the region: \(\lambda (S) = 2\pi R\). Probability: \(\frac{\lambda (S)}{\lambda (\Omega )} = \frac{2\pi R}{4\pi R} = \frac{1}{2}\).
Below is an empirical check of the paradox: for each of the three methods, \(N=120\) random chords were generated; shown in green are chords longer than a side of the inscribed triangle, and in gray the rest. The fraction of green chords \(\hat P\) approaches its theoretical probability β three different numbers for what appears to be one and the same random chord.
Monte Carlo check of Bertrandβs paradox: the same geometric problem (βis the chord longer than a side of the inscribed triangle?β) yields three different probabilities depending on how the βrandomβ chord is chosen. Hover over any chord to see its length.
Depending on the model, the answer can be either \(\frac{1}{2}\), \(\frac{1}{3}\), or \(\frac{1}{4}\).
Find the probability that from three segments of length at most 1, chosen at random, a triangle can be formed. Set up the probability space.
The class monitor noticed that the seminar instructor arrives to class with a random delay of up to \(15\) minutes, and only lets into the room those students who arrive no more than \(5\) minutes after him. The monitor decided to be late for the seminar as well, but chose for herself a random delay bounded by only \(10\) minutes, with a waiting time for the instructor of 10 minutes too. Describe the probability space. What is the probability that the monitor will nevertheless attend the seminar?
Discrete Model: The General Case
In the classical discrete model, all elementary outcomes are assumed to be equally likely. Let us consider a situation where this is not the case. Let \(\Omega = \{ \omega_1, \ldots , \omega_N\}\), \(\mathcal{F} = 2^{\Omega }\), and let the probability of each outcome be \(p_i = \mathbb {P}\left(\{ \omega_i\} \right)\). Then, clearly, \(\sum_{i=1}^{N} p_i = 1\) holds, and the probability of an arbitrary event is computed as follows: \(\mathbb {P}\left(A\right) = \sum_{i: \omega_i \in A} p_i\). This fully determines the probability space with a finite number of outcomes \((\Omega , \mathcal{F}, \mathbb {P})\).
Everything said carries over verbatim to a countable \(\Omega = \{ \omega_1, \omega_2, \ldots \}\): one need only replace the finite sum \(\sum_{i=1}^{N} p_i = 1\) by the sum of the series \(\sum_{i=1}^{\infty } p_i = 1\), while \(\mathcal{F} = 2^{\Omega }\) remains a sigma-algebra as before (a countable union of subsets of a countable set is again at most countable). Then for any \(A \subset \Omega\) the probability \(\mathbb {P}\left(A\right) = \sum_{i \, : \, \omega_i \in A} p_i\) is well defined β this is a series with nonnegative terms, so its sum does not depend on the order of summation.
A fair coin is tossed until the first heads appears. Describe the probability space and find the probability that an odd number of tosses is required.
The elementary outcome is the number of tosses until the first heads: \(\Omega = \mathbb {N} = \{ 1, 2, 3, \ldots \}\). The sample space is countable, but, unlike in the classical model, the outcomes are not equally likely. The event \(\{ \omega = k\}\) means: the first \(k-1\) tosses are tails, the \(k\)-th is heads; hence \[
p_k := \mathbb {P}\left(\omega = k\right) = \left(\frac{1}{2}\right)^{k-1}\cdot \frac{1}{2} = \frac{1}{2^k}, \qquad k \in \mathbb {N}
\] Let us check that this is a valid distribution: \(\sum_{k=1}^{\infty }p_k = \sum_{k=1}^{\infty }\frac{1}{2^k} = 1\). The desired probability: \[
\mathbb {P}\left(\text{the number of tosses is odd}\right) = \sum _{j=0}^{\infty }p_{2j+1} = \sum _{j=0}^{\infty }\frac{1}{2^{2j+1}} = \frac{1}{2}\sum _{j=0}^{\infty }\frac{1}{4^j} = \frac{1}{2}\cdot \frac{1}{1-1/4} = \frac{2}{3}
\]
A die is biased: the probability of face \(i\) coming up is proportional to the number \(i\) itself, i.e., \(\mathbb {P}\left(i\right) = ci\) for some constant \(c\), \(i = 1, \ldots , 6\). Find \(c\) and the probability that an even number of points comes up.
A die is thrown repeatedly and independently until either \(1\) or \(6\) comes up (whichever comes first). Find the probability that the game ends with a one coming up.
You need not write out the series explicitly β use the symmetry between the outcomes \(1\) and \(6\).
Conditional Probability
Let \((\Omega , \mathcal{F}, \mathbb {P})\) be a probability space (typically finite, for the definitions considered in this section) and let \(A \in \mathcal{F}\) be some event. One often needs to compute the probability of an event given that another event has occurred.
Definition 5 The conditional probability of \(A\) given \(B\) is defined as \[
\mathbb {P}\left(A \mid B\right) = \begin{cases} \frac{\mathbb {P}\left(A \cap B\right)}{\mathbb {P}\left(B\right)}, & \mathbb {P}\left(B\right) > 0 \\ \text{undefined}, & \mathbb {P}\left(B\right) = 0 \\ \end{cases}
\]
Three dice are thrown. Find the probability that all three dice show a βsix,β given that the first die shows a βsix.β
Denote \[
\begin{align} A & = \left\{ \text{the first die shows a "six"}\right\} \\ B & = \left\{ \text{all dice show a "six"}\right\} \end{align}
\] Then, clearly, \(\mathbb {P}\left(A\right) = \frac{1}{6}\), since showing a βsixβ is one of six equally likely outcomes in the experiment of throwing a single die. The event \(B \subset A\), so \[
\mathbb {P}\left(A \cap B\right) = \mathbb {P}\left(B\right) = \frac{1}{6^3},
\] since three βsixesβ showing up is one of \(6^{3}\) equally likely outcomes in the experiment of throwing three dice. Hence \[
\mathbb {P}\left(B \mid A\right) = \frac{1/6^3}{1/6} = \frac{1}{6^2}
\]
A partition of a probability space is a finite or countable system of events \(\left\{ A_1, A_2, \ldots \right\} = \left\{ A_n \; : \; n \in \mathcal{N}\right\}\) (\(\mathcal{N} = \left\{ 1, \ldots , N\right\}\) if the system is finite, and \(\mathcal{N} = \mathbb {N}\) if the system is countable) such that distinct events are disjoint (if \(i \neq j\), then \(A_i \cap A_j = \varnothing\); such a system is also called disjoint) and, taken together, these events cover the whole sample space:
\[
\bigsqcup _{n \in \mathcal{N}}A_n = \Omega
\]
Let there be some other event \(B\). Note that since \(B \subset \Omega\), we then have
\[
B = \left(B \cap A_1\right) \sqcup \left(B \cap A_2\right) \sqcup \ldots = \bigsqcup _{n \in \mathcal{N}} B \cap A_n
\]
Using the property of finite or countable additivity of the probability measure, we obtain
\[
\mathbb {P}\left(B\right) = \sum _{n \in \mathcal{N}} \mathbb {P}\left(B \cap A_n\right)
\]
Suppose additionally that \(\mathbb {P}\left(A_n\right) > 0\), \(\forall n\). Then by the formula for conditional probability we have \(\mathbb {P}\left(B \cap A_n\right) = \mathbb {P}\left(B \mid A_n\right) \mathbb {P}\left(A_n\right)\), \(\forall n\). This brings us to the following theorem.
Theorem 1 (Law of Total Probability) Suppose we have a partition \(\left\{ A_n\right\}_{n \in \mathcal{N}}\) (finite or countable) with \(\mathbb {P}\left(A_n\right) > 0\), \(\forall n\). Then for any event \(B\) the following formula holds: \[
\mathbb {P}\left(B\right) = \sum _{n \in \mathcal{N}} \mathbb {P}\left(B \mid A_n\right) \mathbb {P}\left(A_n\right)
\]
Suppose in addition that \(\mathbb {P}\left(B\right) > 0\). Then for an arbitrary \(i \in \mathcal{N}\) we have
\[
\mathbb {P}\left(A_i \mid B\right) = \frac{\mathbb {P}\left(A_i \cap B\right)}{\mathbb {P}\left(B\right)} = \frac{\mathbb {P}\left(B \mid A_i\right) \mathbb {P}\left(A_i\right)}{\mathbb {P}\left(B\right)}
\]
If, in addition, we replace \(\mathbb {P}\left(B\right)\) in the denominator using the law of total probability, we obtain the famous Bayesβ formula.
Theorem 2 (Bayesβ Formula) Suppose we have a partition \(\left\{ A_n\right\}_{n \in \mathcal{N}}\) (finite or countable) with \(\mathbb {P}\left(A_n\right) > 0\), \(\forall n\). Then for any event \(B\) with \(\mathbb {P}\left(B\right) > 0\) and for any \(i \in \mathcal{N}\) the following formula holds: \[
\mathbb {P}\left(A_{i} \mid B \right)=\frac{\mathbb {P}\left(B \mid A_i\right) \mathbb {P}\left(A_i\right)}{\sum _{n \in \mathcal{N}} \mathbb {P}\left(B \mid A_n\right) \mathbb {P}\left(A_n\right)}
\]
Young men pass by a donut shop with frequency \(0.6\), young women with frequency \(0.3\), and instructors with frequency \(0.1\). Young men buy a donut with probability \(0.4\), young women with probability \(0.9\), and instructors with probability \(0.2\). It is known that the last person bought a donut. Find the conditional probability that the donut was bought by an instructor.
Denote the events:
\(B = \{ \text{the last person bought a donut}\}\)
\(A_1 = \{ \text{this person is a young man}\}\)
\(A_2 = \{ \text{this person is a young woman}\}\)
\(A_3 = \{ \text{this person is an instructor}\}\)
By the conditions of the problem:
\[
\mathbb {P}\left(A_1\right) = 0.6,\quad \mathbb {P}\left(A_2\right) = 0.3,\quad \mathbb {P}\left(A_3\right) = 0.1
\] \[
\mathbb {P}\left(B \mid A_1\right) = 0.4,\quad \mathbb {P}\left(B \mid A_2\right) = 0.9,\quad \mathbb {P}\left(B \mid A_3\right) = 0.2
\]
By Bayesβ formula:
\[
\begin{align} \mathbb {P}\left(A_3 \mid B\right) & = \frac{\mathbb {P}\left(B \mid A_3\right) \mathbb {P}\left(A_3\right)}{\mathbb {P}\left(B \mid A_1\right) \mathbb {P}\left(A_1\right) + \mathbb {P}\left(B \mid A_2\right) \mathbb {P}\left(A_2\right) + \mathbb {P}\left(B \mid A_3\right) \mathbb {P}\left(A_3\right)} = \\ & = \frac{0.2 \cdot 0.1}{0.4 \cdot 0.6 + 0.9 \cdot 0.3 + 0.2 \cdot 0.1} = \frac{0.02}{0.24 + 0.27 + 0.02} = \frac{0.02}{0.53} \approx 0.038 \end{align}
\]
A batch of \(N\) items contains \(M \leqslant N\) defective ones. From this batch, \(n \leqslant N\) items are chosen. Find the probability that exactly \(m\) defective items are among those chosen, for the sampling schemes with and without replacement.
In the previous problem, let \(A_{k}\) denote the event that a defective item was drawn on the \(k\)-th step, and let \(B_{m}\) denote the event that a total of \(m\) defective items were drawn. Find \(\mathbb {P}\left(A_{k} \mid B_{m}\right)\) for the sampling schemes with and without replacement.
The unconditional probability \(\mathbb {P}\left(A\right)\) of an event \(A\) is also called the prior probability, and the conditional probability \(\mathbb {P}\left(A \mid B\right)\) is also called the posterior probability.
You have decided to go to a ski resort and call two of your friends to find out about the weather there. Both said there is no snow. According to your prior information, the probability of snow is \(0.8\). Moreover, your friends might be joking, each independently with probability \(0.3\). Find the posterior probability that it is snowing.
Independence
We say that an event \(B\) does not depend on an event \(A\) if the probability of their joint occurrence factors as the product of the individual probabilities:
\[
\mathbb {P}\left(A \cap B\right) = \mathbb {P}\left(A\right) \cdot \mathbb {P}\left(B\right)
\]
Let there be a collection of events \(A_{1}, \ldots , A_{n}\).
Definition 6 Arbitrary events \(A, B \in \mathcal{F}\) are called independent if \(\mathbb {P}\left(A \cap B\right) = \mathbb {P}\left(A\right) \cdot \mathbb {P}\left(B\right)\).
The events \(A_{1}, \ldots , A_{n}\) are called pairwise independent if for any distinct \(i, j \in \{ 1, \ldots , n\}\) the events \(A_i\) and \(A_j\) are independent.
The events \(A_{1}, \ldots , A_{n}\) are called mutually independent if for any collection of indices \(i_{1}, i_{2}, \ldots , i_{k}, 1 \leq i_{1}<i_{2}<\ldots <i_{k} \leq n\), we have
\[
\mathbb {P}\left(A_{i_1} \cap A_{i_2} \cap \ldots \cap A_{i_k}\right) = \mathbb {P}\left(A_{i_1}\right) \cdot \mathbb {P}\left(A_{i_2}\right) \cdot \cdots \cdot \mathbb {P}\left(A_{i_k}\right)
\]
It is easy to see that mutual independence implies pairwise independence. The converse, as the following example shows, is false.
Give an example of events that are pairwise independent but not mutually independent.
Consider a tetrahedron \(A C D E\). Let us color vertex \(A\) red, vertex \(C\) green, \(D\) blue, and \(E\) in all three colors at once. Consider the experiment of choosing a vertex of the tetrahedron uniformly at random. Introduce the events \[
\begin{align} R & = \left\{ \text{the chosen vertex is colored red}\right\} \\ G & = \left\{ \text{the chosen vertex is colored green}\right\} \\ B & = \left\{ \text{the chosen vertex is colored blue}\right\} \end{align}
\] Then \(\mathbb {P}\left(B\right) = \mathbb {P}\left(G\right) = \mathbb {P}\left(R\right) = \frac{1}{2}\), and the probabilities of the pairwise intersections are \(\mathbb {P}\left(B \cap G\right) = \mathbb {P}\left(G \cap R\right) = \mathbb {P}\left(B \cap R\right) = \frac{1}{4}\), i.e., the events \(B, G\), and \(R\) are pairwise independent. But \[
\mathbb {P}\left(B \cap G \cap R\right) = \frac{1}{4} \neq \frac{1}{8} = \mathbb {P}\left(B\right) \cdot \mathbb {P}\left(G\right) \cdot \mathbb {P}\left(R\right)
\] i.e., the events are not mutually independent.
Balls are drawn from a box containing black and white balls. Let the event \(A_{k}\) mean that a white ball was drawn on the \(k\)-th step. Prove that the events \(A_{1}, \ldots , A_{n}\)
are mutually independent if the balls are drawn with replacement;
are dependent if the balls are drawn without replacement.
Two players carry out a series of independent trials. In each trial, player \(A\) throws 3 dice, while player \(B\) throws \(2\) dice at the same time as player \(A\) and independently of him. They carry out these trials in sequence until a βsixβ first comes up on at least one of the dice. Find the probabilities of the following events:
\(\mathcal{C}=\{\) a βsixβ first came up for player \(B\), and not for \(A\}\)
\(\mathcal{D}=\{\) a βsixβ first came up simultaneously for \(A\) and \(B\}\).
Let \(A, B, C\) be pairwise independent equally likely events, with \(A \cap B \cap C=\varnothing\). Find the maximum possible value of \(\mathbb {P}(A)\).
Bernoulli Scheme
Let us now introduce the so-called Bernoulli scheme. Consider a series of identical, mutually independent experiments, each having 2 outcomes (for example, repeatedly tossing a coin). Call one of these outcomes success (denote it \(\{ 1\}\)), and the other failure (denote it \(\{ 0\}\)). It is known that the probability of success in one experiment equals \(\mathbb {P}\left(\left\{ 1\right\} \right) =: p\), and the probability of failure is \(\mathbb {P}\left(\left\{ 0\right\} \right) = 1 - p =: q\). Then the sample space consists of all binary sequences of length \(n\):
\[
\Omega = \left\{ \omega = (\varepsilon _1, \ldots , \varepsilon _n) \; : \; \varepsilon _1, \ldots , \varepsilon _n \in \left\{ 0,1\right\} \right\}
\]
and the probability of each elementary outcome equals
\[
\mathbb {P}\left(\omega \right) = p^{\sum _{i=1}^{n} \varepsilon _{i}} q^{n-\sum _{i=1}^{n} \varepsilon _{i}}
\]
It is easy to check that the sum of the probabilities of all outcomes in this case equals 1. One is often required to find the probability that, in a scheme of \(n\) Bernoulli trials, \(k\) successes occurred: this probability equals \(C_{n}^{k} p^{k} q^{n-k}\).
Two players carry out an infinite series of independent trials. In each trial, player \(A\) throws 3 dice, while player \(B\) throws 2 dice at the same time as player \(A\) and independently of him. They carry out these trials in sequence until a βsixβ first comes up on at least one of the dice. Find the probability that a βsixβ first came up for player \(A\), and not for \(B\).
Denote \[
A_k = \left\{ \text{a "six" came up on the $k$-th trial for at least one of the players}\right\}
\] Let \[
\begin{align} D_{k}& =\bigcap _{i=1}^{k-1} \overline{A_{i}} \\ B_k & = \left\{ \text{player $A$'s dice showed a "six" on the $k$-th trial}\right\} \\ C_k & = \left\{ \text{player $B$'s dice showed a "six" on the $k$-th trial}\right\} \end{align}
\] Call it a success on the \(k\)-th trial if, on the \(k\)-th trial, player \(A\)βs dice showed a βsixβ while \(B\)βs did not. This probability equals \[
\mathbb {P}\left(B_k \cap \overline{C_k}\right) = \mathbb {P}\left(B_k\right) \cdot \mathbb {P}\left(\overline{C_k}\right) = \left(1-\left(\frac{5}{6}\right)^{3}\right)\left(\frac{5}{6}\right)^{2}=\frac{91 \cdot 25}{6^{5}}
\] Since \(B_{k}\) and \(C_{k}\) are independent of each other and of \(D_{k}\) by assumption, the desired probability equals \[
\begin{align} \sum _{k=1}^{n} \mathbb {P}\left(B_{k} \cap \overline{C_{k}} \mid D_{k}\right) \mathbb {P}\left(D_k\right) = \sum _{k=1}^{n} \mathbb {P}\left(B_{k} \cap \overline{C_{k}}\right) \mathbb {P}\left(D_{k}\right) = \frac{25 \cdot 91}{6^{5}} \sum _{k=1}^{\infty } \mathbb {P}\left(D_k\right) = \\ =\frac{25 \cdot 91}{6^{5}}\left(1+\left(\frac{5}{6}\right)^{5}+\left(\frac{5}{6}\right)^{10}+\ldots \right)=\frac{25 \cdot 91}{6^{5}-5^{5}} \end{align}
\] where \(D_{1}=\Omega\).
Find the probability that, in \(2 n\) trials of a Bernoulli scheme with probability of success \(p\) and probability of failure \(q=1-p\), there are \(m+n\) successes and all trials with even indices end in success.
For the event whose probability we need to find to occur, given that the \(n\) trials with even indices ended in success (the probability of this event is clearly \(p^{n}\)), it is necessary and sufficient that \(m\) of the trials with odd indices end in success. Since the trials with even and odd indices are independent, the desired probability equals \(p^{n} C_{n}^{m} p^{m} q^{n-m}=C_{n}^{m} p^{n+m} q^{n-m}\).
