Example 20.13. Consider again our biased die with $\Pr(1) = \frac 3 4$ and $\Pr(\omega) = \frac1{20}$ for $\omega = 2,3,4,5,6$. Suppose you go to a dice thrift store to pick up some second-hand dice. Unfortunately, there is a tendency for about 5% of the dice available to be biased in the way we described above and the remaining 95% of the dice are regular old fair dice. Because of this, the store will let you test-roll some dice. If you pick a die at random and roll two 1s, what is the probability that you picked up a biased die?
What we essentially want to do is compute the probability that, given that we rolled two 1s, we picked up a biased die. If we let $B$ denote the event that we picked up a biased die and we denote by $R_{1,1}$ the event that we rolled two 1s, then we want to compute $\Pr(B \mid R_{1,1})$. Bayes' Theorem tells us that $$\Pr(B \mid R_{1,1}) = \frac{\Pr(R_{1,1}) \mid B) \cdot \Pr(B)}{\Pr(R_{1,1})}.$$ We know $\Pr(B) = 5\% = \frac 1 {20}$ and we know that $\Pr(R_{1,1} \mid B) = \left( \frac 3 4 \right)^2 = \frac{9}{16}$. All we need to do is to calculate $\Pr(R_{1,1})$.
Recall that the Law of Total Probability tells us that $$\Pr(R_{1,1}) = \Pr(R_{1,1} \mid B) \cdot \Pr(B) + \Pr(R_{1,1} \mid \overline B) \cdot \Pr(\overline B)$$ where $\overline B$ is the non-biased die event, or in other words, the fair dice. This gives us \begin{align*} \Pr(R_{1,1}) &= \Pr(R_{1,1} \mid B) \cdot \Pr(B) + \Pr(R_{1,1} \mid \overline B) \cdot \Pr(\overline B) \\ &= \frac{9}{16} \cdot \frac 1{20} + \frac 1{36} \cdot \frac{19}{20} \\ &= \frac{157}{2880} \end{align*} Then plugging these into the formula for Bayes' Theorem gives us $$\Pr(B \mid R_{1,1}) = \frac{\frac{9}{320}}{\frac{157}{2880}} = \frac{81}{157} \approx 0.516.$$
Example 20.14. Recall the Monty Hall problem. We will use Bayes' theorem to formally describe the probability of the outcomes for each choice. Let $C$ be the random variable that indicates which door has the car behind it and let $D$ be the random variable that tells us which door Monty Hall opens. We denote each door by 1, 2, or 3. Suppose we choose door $i$.
First, we observe that $\Pr(C = j) = \frac 1 3$ for $j = 1,2,3$. That is, each door is equally likely to have the car behind it.
Next, we need to think about which door Monty is likely to open. Recalling that we chose door $i$, we have $$ \Pr(D = k \mid C = j) = \begin{cases} 1 & \text{if $i \neq j \neq k$,} \\ 0 & \text{if $k = i$ or $k = j$,} \\ \frac 1 2 & \text{if $i = j$ and $k \neq i$.} \\ \end{cases} $$ The first case says that if we didn't choose the door with the car, then Monty must open the remaining door with the goat. The second case says that Monty will not open the door we chose or the door containing the car. The last case occurs when we choose the door with the car, in which case Monty opens one of the other two doors with equal probability.
Putting this together, we can consider two cases: if we chose the correct door ($C = i$) or if we chose the wrong door ($C = j \neq i$). In each case, Monty opens a door $k$. We know from the rules that $k \neq i$, since we chose $i$ and $k$ cannot be the door with the car behind it.
If we chose the correct door, we have $$\Pr(C = i \mid D = k) = \frac{\Pr(D = k \mid C = i) \Pr(C = i)}{\Pr(D = k)}.$$ We must compute $\Pr(D = k)$, but that's not hard because we've exhausted all the possibilities above. We have \begin{align*} \Pr(D = k) &= \sum_{n=1}^3 \Pr(D = k \mid C = n) \Pr(C = n) \\ &= 1 \cdot \frac 1 3 + 0 \cdot \frac 1 3 + \frac 1 2 \cdot \frac 1 3 \\ &= \frac 1 2 \end{align*} Then going back to our equation above, we have $$\Pr(C = i \mid D = k) = \frac{\frac 1 2 \cdot \frac 1 3}{\frac 1 2} = \frac 1 3.$$ That is, if we picked the correct door to begin with, then Monty revealing the door doesn't change our odds of winning and we're still at $\frac 1 3$. Now, if we repeat this analysis but with $C = j \neq i$, we have $$\Pr(C = j \mid D = k) = \frac{1 \cdot \frac 1 3}{\frac 1 2} = \frac 2 3.$$ This says that if we picked door $i$, then the probability that the car is behind the other door after Monty makes the revelation is $\frac 2 3$. Therefore, the best strategy is always to switch.
Something that we've run into despite my best efforts to shield you from it until now so I could avoid getting into specifics is the notion of graphs. You may be familiar with graphs as either graphical charts of data or from calculus in the form of visualizing functions in some 2D or 3D space. Neither of these are the graphs that are discussed in graph theory.
We saw two examples where graphs snuck in. The first is from our application of the pigeonhole principle to a problem about whether two people know each other or don't know each other at a party. The second is from the example of our ambitious travelling salesperson, who wants to visit as many cities as possible with the least cost.
Both of these examples model relationships between sets of objects. In the first case, we are modelling what's basically a social network. Our objects are people and the relationships are described as: two people are connected by either a "knows each other" relationship or a "doesn't know each other" relationship. In the second case, our objects are cities and their relationship is described not only by a connection, but by a weight or cost on that connection, representing the cost to travel between the two cities.
Definition 21.1. A graph $G = (V,E)$ is a pair with a non-empty set of vertices $V$ together with a set of edges $E$. An edge $e \in E$ is an unordered pair $(u,v)$ of vertices $u,v \in V$.
This graph is called the Petersen graph. The Petersen graph is a particularly interesting graph, not just because it looks neat, but because it happens to be a common counterexample for many results in graph theory.
Note that, since edges are unordered, we really should be writing them as $\{u,v\}$, but we don't.
One can define graphs more generally and then restrict consideration to our particular definition of graphs, which would usually be then called simple graphs. The more general definition of graphs allows for things like multiple edges between vertices or loops. Other enhancements may include asymmetric edges (which we call directed edges), equipping edges with weights, and even generalizing edges to hyperedges that relate more than two vertices. Instead, what we do is start with the most basic version of a graph, from which we can augment our definition with the more fancy features if necessary (it will not be necessary in this course).
Definition 21.2. Two vertices $u$ and $v$ of a graph $G$ are adjacent if they are joined by an edge $(u,v)$. We say the edge $(u,v)$ is incident to $u$ and $v$.
Definition 21.3. Two vertices $u$ and $v$ are neighbours if they are adjacent. The neighbourhood of a vertex $v$ is the set of neighbours of $v$ $$N(v) = \{u \in V \mid (u,v) \in E\}.$$ We can extend this definition to sets of vertices $A \subseteq V$ by $$N(A) = \bigcup_{v \in A} N(v).$$
Definition 21.4. The degree of a vertex $v$ in $G$, denoted $\deg(v)$, is the number of its neighbours. A graph $G$ is $k$-regular if every vertex in $G$ has degree $k$.
Observe that every vertex in the Petersen graph has degree 3, so the Petersen graph is 3-regular, or cubic.
The following results are some of the first graph theory results, proved by Leonhard Euler in 1736.
Theorem 21.5 (Handshaking Lemma). Let $G = (V,E)$ be an undirected graph. Then $$\sum_{v \in V} \deg(v) = 2 \cdot |E|.$$
Proof. Every edge $(u,v)$ is incident to exactly two vertices: $u$ and $v$. Therefore, each edge contributes 2 to the sum of the degrees of the vertices in the graph. $\tag*{$\Box$}$
Corollary 21.6. Let $G$ be a graph. Then the number of vertices of odd degree in $G$ is even.
Proof. Let $V_1, V_2 \subseteq V$ be the sets of odd and even vertices of $G$, respectively. Then $$2|E| = \sum_{v \in V_1} \deg(v) + \sum_{v \in V_2} \deg(v).$$ We observe that since $\deg(v)$ for $v \in V_2$ is even, then the sum $\sum_{v \in V_2} \deg(v)$ is even. Then since $2|E|$ is even, this must mean that the sum $\sum_{v \in V_1} \deg(v)$ is even. But since $\deg(v)$ is odd for $v \in V_1$, this implies that $|V_1|$ must be even. $\tag*{$\Box$}$
It's the corollary that gives the name for the handshaking lemma. When rephrased as a bunch of people shaking hands, the lemma says that there must be an even number of people who have shaken an odd number of hands.
Definition 21.7. The complete graph on $n$ vertices is the graph $K_n = (V,E)$, where $|V| = n$ and
$$E = \{(u,v) \mid u,v \in V\}.$$
That is, every pair of vertices are neighbours.
Definition 21.8. The cycle graph on $n$ vertices is the graph $C_n = (V,E)$ where $V = \{v_1, v_2, \dots, v_n\}$ and $E = \{(v_i,v_j) \mid j = i + 1 \bmod n\}$. It's named so because the most obvious way to draw the graph is with the vertices arranged in order, on a circle.
Definition 21.9. The $n$-(hyper)cube graph is the graph $Q_n = (V,E)$, where $V = \{0,1\}^n$ (i.e., binary strings of length $n$) and $(u,v)$ is an edge if, for $u = a_1 a_2 \cdots a_n$ and $v = b_1 b_2 \cdots b_n$, there exists an index $i, 1 \leq i \leq n$ such that $a_i \neq b_i$ and $a_j = b_j$ for all $j \neq i$. In other words, $u$ and $v$ differ in exactly one symbol.
It's called a cube (or hypercube) because one of the ways to draw it is to arrange the vertices and edges so that they form the $n$th-dimensional cube.
Consider the following graphs.
These two graphs happen to be the "same". Furthermore, it turns out that these are also basically the same graph as $Q_3$, or at least, we feel that it should be. This means we don't need to necessarily draw a $3$-cube like a cube (and we certainly wouldn't expect this for $n \gt 3$).
Although the visual representation of the graph is very convenient, it is sometimes misleading, because we're limited to 2D drawings. In fact, there is a vast area of research devoted to graph drawing and the mathematics of embedding graphs in two dimensions. The point of this is that two graphs may look very different, but turn out to be the same.
But even more fundamental than that, we intuitively understand that just because the graph isn't exactly the same (i.e., the vertices are named something differently) doesn't mean that we don't want to consider them equivalent. So how do we discuss whether two graphs are basically the same, just with different names or drawings?