Contemporary Problem Solving A Comprehensive Introduction with Real-World Examples

Subsection 1.1.1 An Example: Computing Degrees

• deg(A)=2 (edges to B and F), so A has even degree.

  🔗
  🔗
• deg(B)=3 (edges to A, C, and E), so B has odd degree.

  🔗
  🔗
• deg(C)=2 (edges to B and D), so C has even degree.

  🔗
  🔗
• deg(D)=2 (edges to C and E), so D has even degree.

  🔗
  🔗
• deg(E)=3 (edges to D, F, and B), so E has odd degree.

  🔗
  🔗
• deg(F)=2 (edges to E and A), so F has even degree.

  🔗
  🔗

Subsection 1.1.2 Very Small Graphs

Subsection 1.1.3 Why the Placement of Vertices Does Not Matter

• They use the same vertex labels (the same “named objects”).

  🔗
  🔗
• They connect exactly the same pairs of vertices with edges.

  🔗
  🔗

Subsection 1.1.4 A Real-Life Example of a Graph

Subsection 1.1.5 Example: A Schematic Rail Network Across the European Union

Subsection 1.1.6 A one-to-one correspondence of vertices

Subsection 1.2.1 Simple Graphs

Example 1.2.2. A graph that is simple.

The graph in Figure 1.2.3 is simple: it has no loops and no multiple edges. Each pair of vertices is connected by at most one edge.

🔗

🔗

Example 1.2.4. A similar graph that is not simple.

The graph in Figure 1.2.5 uses the same vertex labels as Figure 1.2.3, but it is not simple. It contains a loop at vertex C and it contains multiple edges between vertices A and B.

🔗

🔗

Subsection 1.2.2 More Practice: Simple Graphs

Subsection 1.2.3 Diagnostic Practice: Simple or Not?

Subsection 1.2.4 A Graph That Is Not Simple

Subsection 1.3.1 Path

Subsection 1.3.2 Length of a Path

Subsection 1.3.3 Circuit

Subsection 1.3.4 Subgraph

Subsection 1.3.5 Component

Subsection 1.3.6 Disjoint

Subsection 1.3.7 Connected

Subsection 1.3.8 Bridge

Subsection 1.4.1 Introduction

Subsection 1.4.2 Euler Paths and Euler Circuits

Example 1.4.7. A graph with an Euler circuit.

The following five-vertex graph has an Euler circuit: it is possible to traverse every edge exactly once and return to the starting vertex.

🔗

🔗

Example 1.4.9. A graph with an Euler path but no Euler circuit.

The following five-vertex graph has an Euler path, but it has no Euler circuit. A traversal using every edge exactly once must start and end at different vertices.

🔗

🔗

Example 1.4.11. Another graph with an Euler path but no Euler circuit.

The following five-vertex graph has an Euler path, but it has no Euler circuit. A traversal using every edge exactly once must start and end at different vertices.

🔗

🔗

Example 1.4.13. Counterexample: checking degrees is not enough.

A common mistake is to check only vertex degrees and forget the graph must be connected (for the edges you want to traverse). In the graph below, every vertex has even degree, but the graph has two separate parts, so there is no single closed walk that can use all edges exactly once.

🔗

🔗

Subsection 1.4.3 Euler’s Theorem

Subsection 1.4.4 Concept Check: Euler Paths, Euler Circuits, and Connectivity

Subsection 1.4.5 Exercise: Identifying Euler Paths and Circuits

Subsection 1.5.1 Why Eulerize?

Subsection 1.5.2 Adding Edges vs. Reusing Edges

Subsection 1.5.3 The Core Idea

Subsection 1.5.4 Easy Example

Checkpoint 1.5.3.

Determine the vertices of odd degree.

🔗

Reuse edges to make the graph Eulerian.

🔗

Solution.

By adding the edges as shown in the graph, all vertices now are even degree. Thus we can say this graph is Eulerian

🔗

🔗

🔗

Subsection 1.5.5 Example

Checkpoint 1.5.7.

Determine the vertices of odd degree.

🔗

Reuse edges to make the graph Eulerian.

🔗

Solution.

By adding BD and DG it now makes every vertex have even degree. Thus making the graph Eulerian.

🔗

🔗

🔗

Subsection 1.6.1 Why Avoid Bridges?

Subsection 1.6.2 Worked Examples

Subsubsection 1.6.2.1 Example 1: An Euler Circuit

Since every vertex has even degree, an Euler circuit exists. Start at A. At each step, you may choose among several edges, but you should avoid choosing a bridge if one occurs. Continuing until all edges are used produces an Euler circuit.

🔗

One valid Euler circuit for this graph is: A–B–C–D–E–B–D–A–C–E–A.

🔗

🔗

Subsubsection 1.6.2.2 Example 2: An Euler Path (No Bridges)

This graph has exactly two vertices of odd degree (A and C), so an Euler path exists. Start at A (or at C). In this graph, no edge is a bridge at the beginning, so Fleury’s rule does not restrict your first choices.

🔗

One valid Euler path starting at A is: A–B–C–D–A–C.

🔗

🔗

Subsubsection 1.6.2.3 Example 3: A Bridge Becomes Necessary

The vertices of odd degree are D and E, so an Euler path exists and must start at D or E. Start at D. The edge D–E is a bridge, so Fleury’s Algorithm tells you to avoid it as long as there is another unused edge incident to D. Therefore, you should traverse the cycle first, and only take D–E at the end.

🔗

One valid Euler path starting at D is: D–A–B–C–D–E.

🔗

🔗

Subsection 1.6.3 Concept Check: Identifying Bridges

Subsection 1.6.4 Notes

Subsection 1.7.1 Complete Graphs

Subsection 1.7.2 Small Examples: Building Intuition

Checkpoint 1.7.10. Concept Check.

In Figure 1.7.9, how many different ways can you arrange the vertices B, C, D to form a Hamiltonian circuit starting and ending at A?

🔗

Solution.

You can arrange B, C, D in \(3! = 6\) different orders. However, if we consider \(A–B–C–D–A\) and \(A–D–C–B–A\) as the same circuit (one is the reverse of the other), then there are \(\frac{3!}{2} = 3\) distinct Hamiltonian circuits. These are:

🔗

🔗

🔗

Subsection 1.7.3 Counting Hamiltonian Circuits in Complete Graphs

Subsection 1.7.4 Not Every Graph Is Hamiltonian

Subsection 1.9.1 Weighted Graphs and the TSP

Subsection 1.9.2 Kristen’s Sales Trip: A Concrete Example

Checkpoint 1.9.3. Concept Check.

Using Table 1.9.2, compute the total cost of the route: Kansas City → Chicago → Minneapolis → Denver → Nashville → Kansas City.

🔗

Solution.

$249 + $137 + $247 + $462 + $466 = $1,561.

🔗

🔗

🔗

Subsection 1.9.3 The Brute Force Algorithm

Checkpoint 1.9.7. Brute Force Circuit Count.

A traveling salesman must visit 7 cities. Using the brute force algorithm, how many Hamiltonian circuits would need to be evaluated?

🔗

Solution.

\(\frac{(7-1)!}{2} = \frac{6!}{2} = \frac{720}{2} = 360\) circuits. That obviously would be very time consuming

🔗

🔗

🔗

Subsection 1.9.4 The Nearest Neighbor Algorithm

Example 1.9.10. Applying NNA to Kristen’s Problem.

Apply the Nearest Neighbor Algorithm to Kristen’s problem, starting in Kansas City.

🔗

Solution.

Start: Kansas City.

🔗

Step 1: From Kansas City, closest unvisited city is Minneapolis ($194). Go to Minneapolis.

🔗

Step 2: From Minneapolis, closest unvisited city is Chicago ($137). Go to Chicago.

🔗

Step 3: From Chicago, closest unvisited city is Denver ($250). Go to Denver.

🔗

Step 4: From Denver, only unvisited city is Nashville ($462). Go to Nashville.

🔗

Step 5: From Nashville, return to Kansas City ($466).

🔗

Route: Kansas City → Minneapolis → Chicago → Denver → Nashville → Kansas City.

🔗

Total cost: $194 + $137 + $250 + $462 + $466 = $1,509.

🔗

🔗

🔗

Subsection 1.9.4.1 Expanding NNA: Trying different starting points

Since NNA’s result depends on where you start, a natural consequence to recieve different results from different starting points.

🔗

• For each vertex in the graph, apply the Nearest Neighbor Algorithm starting from that vertex.

  🔗
  🔗
• Compare all circuits found and select the one with the minimum total weight.

  🔗
  🔗

🔗

This approach often finds better solutions than a single NNA run, though it requires \(n\) times as much computation (still very fast compared to brute force).

🔗

Checkpoint 1.9.12. Question on different starting points for NNA.

For Kristen’s 5-city problem, how many times would the Nearest Neighbor Algorithm need to run if using the Repetitive NNA approach?

🔗

Solution.

5 times (once starting from each city).

🔗

🔗

🔗

Checkpoint 1.9.13. A different starting point using NNA.

What would Kristen’s solution be if she started at Minneapolis

🔗

Solution.

Route: M → C → K → D → N → M

🔗

Total: $137 + $249 + $272 + $462 + $410 = $1,530

🔗

🔗

🔗

🔗

🔗

Subsection 1.9.5 The Side Sorted Algorithm

Example 1.9.16. Applying the Cheapest Link Algorithm to Kristen’s Problem.

Recall that Kristen needs to fly from Kansas City (K) to visit Minneapolis (M), Chicago (C), Denver (D), and Nashville (N), then return home. We apply the Cheapest Link Algorithm by sorting all edges by cost and adding them one at a time, provided no vertex reaches degree 3 and no early circuit forms.

🔗

Edge	Cost	Action	Reason
M–C	$137	Add	Cheapest available
K–M	$194	Add	Cheapest available
D–M	$247	Skip	Would give M degree 3
K–C	$249	Skip	Would create early circuit K–M–C–K
D–C	$250	Add	Connects D to component
K–D	$272	Skip	Would create early circuit K–M–C–D–K
C–N	$345	Skip	Would give C degree 3
M–N	$410	Skip	Would give M degree 3
D–N	$462	Add	Connects final vertex N
K–N	$466	Add	Closes the circuit

The resulting Hamiltonian circuit is \(K \to M \to C \to D \to N \to K\text{,}\) with a total cost of \(\$194 + \$137 + \$250 + \$462 + \$466 = \$1{,}509\text{.}\)

🔗

🔗

Subsection 1.11.1 Trees and Forests

Subsection 1.11.2 Small Examples of Trees and Forests

Subsection 1.11.3 Key Properties of Trees

Subsection 1.12.1 Example: Spanning Trees of a Small Graph

Subsection 1.12.2 Every Connected Graph Has a Spanning Tree

Subsection 1.13.1 Example: Connecting Islands by Cable

Checkpoint 1.13.3. Concept Check.

Using Table 1.13.2, which cable is cheapest?

🔗

Solution.

B–C with cost 1 million.

🔗

🔗

🔗

Subsection 1.14.1 Applying Kruskal’s Algorithm to the Islands Problem

Example 1.14.2. Connecting Islands with Minimal Cost.

Apply Kruskal’s Algorithm to Table 1.13.2 to find the minimal spanning tree.

🔗

Solution.

Step 1: Sort edges by cost.

🔗

Edge	Cost	Action	Vertices Connected
B–C	1	Add	{B, C}
C–D	2	Add	{B, C, D}
A–B	2	Add	{A, B, C, D}
C–E	3	Add	{A, B, C, D, E} — Done!

Result: Minimal spanning tree uses edges B–C, C–D, A–B, C–E.

🔗

Total cost: 1 + 2 + 2 + 3 = 8 million dollars.

🔗

🔗

🔗

Subsection 1.14.2 Real-World Application: Building a Water Network

Example 1.14.8. Connecting Towns with Water Pipes.

A water authority must connect 6 towns to a central water treatment facility. The following table shows the cost (in thousands of dollars) to lay pipe between each pair of locations. What is the minimum cost to connect all towns?

🔗

	Plant	Town A	Town B	Town C	Town D	Town E
Plant	—	15	20	18	22	25
Town A	15	—	10	12	14	30
Town B	20	10	—	16	13	17
Town C	18	12	16	—	11	19
Town D	22	14	13	11	—	9
Town E	25	30	17	19	9	—

Solution.

We apply Kruskal’s Algorithm to find the minimal spanning tree — the network of pipes that connects all locations at minimum total cost. At each step we add the cheapest available edge that does not create a circuit.

🔗

Edge	Cost	Action	Reason
D–E	9	Add	Cheapest available
A–B	10	Add	Cheapest available
C–D	11	Add	Cheapest available
A–C	12	Add	Joins A–B chain to C–D–E chain
B–D	13	Skip	Would create circuit A–B–D–C–A
A–D	14	Skip	Would create circuit A–C–D–A
Plant–A	15	Add	Connects Plant — spanning tree complete

The minimal spanning tree consists of edges D–E, A–B, C–D, A–C, and Plant–A, with a total cost of \(\$9{,}000 + \$10{,}000 + \$11{,}000 + \$12{,}000 + \$15{,}000 = \$57{,}000\text{.}\)

🔗

🔗

🔗

Subsection 2.1.1 Listing Outcomes and Tree Diagrams

Example 2.1.3. Three Coin Flips.

You flip a coin three times and record the sequence of heads and tails. How many different sequences are possible?

🔗

Solution.

At each flip there are two choices, so the tree has three levels of branching. The complete tree, shown in Figure 2.1.4, produces 8 paths: HHH, HHT, HTH, HTT, THH, THT, TTH, TTT. There are \(8\) possible sequences.

🔗

🔗

🔗

Example 2.1.5. Filling Two Tutor Slots.

The Center for Academic Support needs to fill two time slots with math tutors. There are four tutors available: Kayley (K), Josh (J), Sam (S), and Becca (B). If the same tutor can work both slots, how many different assignments are possible?

🔗

Solution.

We draw a tree with two levels, shown in Figure 2.1.6. At the first slot we have 4 choices. At the second slot we again have 4 choices since repetition is allowed. The tree produces \(4 \times 4 = 16\) possible assignments.

🔗

🔗

🔗

Subsection 2.1.2 With and Without Repetition

Subsection 2.1.3 The Fundamental Counting Principle

Example 2.1.15. Building a Burrito.

A local burrito place offers 5 choices of meat, 2 choices of beans, and 4 choices of salsa. If you must choose exactly one of each, how many different burritos can you build?

🔗

Solution.

Using the slot diagram in Figure 2.1.16:

🔗

\(5 \times 2 \times 4 = 40\) different burritos are possible.

🔗

🔗

🔗

Subsection 2.1.4 Handling Special Conditions

Example 2.1.19. Seating a Choir with a Duet Pair.

A choir director is assigning spots in an eight-seat front row. The choir has 18 members. Sam and Julie have a duet and must stand next to each other. In how many ways can the front row be filled?

🔗

Solution.

Task 1: Choose two adjacent spots for Sam and Julie. In a row of eight seats there are 7 pairs of adjacent spots.

🔗

Task 2: Arrange Sam and Julie in those two spots — 2 ways.

🔗

Task 3: Fill the remaining 6 spots from the 16 remaining singers: \(16 \times 15 \times 14 \times 13 \times 12 \times 11 = 5{,}765{,}760\text{.}\)

🔗

Total: \(7 \times 2 \times 5{,}765{,}760 = 80{,}720{,}640\) ways.

🔗

🔗

🔗

Checkpoint 2.1.22. Kristen’s Wedding Table.

Kristen and Tim are planning seating for the nine-seat head table at their wedding. The bridal party consists of 4 bridesmaids, 3 groomsmen, plus Kristen and Tim. In how many ways can the party be seated if anyone can sit in any seat?

🔗

Solution.

There are 9 people and 9 distinct seats. \(9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 362{,}880\) ways.

🔗

🔗

🔗

Checkpoint 2.1.24. Kristen’s Wedding Table with Restrictions.

Kristen and Tim are planning seating for the nine-seat head table at their wedding. The bridal party consists of 4 bridesmaids, 3 groomsmen, plus Kristen and Tim. In how many ways can the party be seated if the bride and groom sit in the middle and the bridesmaids and groomsmen sit on their respective sides?

🔗

Solution.

The restriction fixes the structure of the table: bridesmaids occupy seats 1–4 on Kristen’s left, Kristen and Tim occupy the two center seats (5 and 6), and groomsmen occupy seats 7–9 on Tim’s right. We handle each group separately.

🔗

Task 1 — Seat the couple (seats 5 and 6): Kristen and Tim can swap places, so there are 2 ways to arrange them in the two center seats.

🔗

Task 2 — Seat the groomsmen (seats 7, 8, and 9): There are 3 choices for seat 7, then 2 remaining choices for seat 8, and 1 remaining choice for seat 9. That gives \(3 \times 2 \times 1 = 6\) arrangements.

🔗

Task 3 — Seat the bridesmaids (seats 1, 2, 3, and 4): There are 4 choices for seat 1, then 3 for seat 2, then 2 for seat 3, and 1 for seat 4. That gives \(4 \times 3 \times 2 \times 1 = 24\) arrangements.

🔗

By the Fundamental Counting Principle, the total number of arrangements is

\begin{equation*} 2 \times 6 \times 24 = 288 \text{ ways.} \end{equation*}

🔗

🔗

🔗

Subsection 2.2.1 Factorial Notation

Subsection 2.2.2 Permutations: When Order Matters

Example 2.2.6. Arranging Colored Marbles.

You have three differently colored marbles: red (R), blue (B), and yellow (Y). How many different orderings of all three marbles are there?

🔗

Solution.

We are arranging all 3 marbles, so \(n = 3\) and \(r = 3\text{.}\) \(P(3, 3) = 3 \times 2 \times 1 = 6\text{.}\) The six orderings are: RBY, RYB, BRY, BYR, YRB, YBR.

🔗

🔗

🔗

Checkpoint 2.2.10. French Club Officers.

The university French Club needs to select a President, Vice President, Treasurer, and Secretary from its 15 members. How many ways can the four positions be filled?

🔗

Solution.

We are choosing 4 people from 15 and assigning them to distinct roles, so order matters. We can think of this as filling four labeled slots — one for each office — where each slot reduces the available members by one.

🔗

There are 15 choices for President. Once that person is chosen, 14 members remain for Vice President, then 13 for Treasurer, and 12 for Secretary. By the Fundamental Counting Principle:

\begin{equation*} 15 \times 14 \times 13 \times 12 = 32{,}760. \end{equation*}

🔗

Using permutation notation, this is \(P(15, 4) = 32{,}760\) ways.

🔗

🔗

🔗

Subsection 2.2.3 Combinations: When Order Does Not Matter

Subsection 2.2.4 Combining Counting Methods

Example 2.2.17. Choosing Students for a Study Session.

An extra study session requires exactly 3 men and 2 women from a class of 10 men and 8 women. In how many ways can the 5 students be chosen?

🔗

Solution.

Note that the answer is not \(C(18,5)\) since that would include groups of all men or all women.

🔗

Step 1: Choose 2 women from 8: \(C(8,2) = 28\text{.}\)

🔗

Step 2: Choose 3 men from 10: \(C(10,3) = 120\text{.}\)

🔗

Total: \(28 \times 120 = 3{,}360\) ways.

🔗

🔗

🔗

Checkpoint 2.2.21. Checkpoint: Putting It All Together.

A student club of 15 members needs to choose a President and Vice President, and then separately choose a 3-person social committee from the remaining members. How many ways can all positions be filled?

🔗

Solution.

This problem has two separate tasks. The key is recognizing which tool applies to each one.

🔗

Step 1 — Choose the officers (order matters): The President and Vice President are distinct roles, so the order of selection matters. There are 15 choices for President and 14 remaining choices for Vice President:

\begin{equation*} P(15, 2) = 15 \times 14 = 210 \text{ ways.} \end{equation*}

🔗

Step 2 — Choose the committee (order does not matter): The two officers cannot serve on the committee, leaving 13 members. A committee has no ranked roles, so order does not matter:

\begin{align*} C(13, 3) \amp= \frac{13 \times 12 \times 11}{3 \times 2 \times 1}\\ \amp= \frac{1{,}716}{6} = 286 \text{ ways.} \end{align*}

🔗

By the Fundamental Counting Principle, the total number of ways to fill all positions is

\begin{equation*} 210 \times 286 = 60{,}060 \text{ ways.} \end{equation*}

🔗

🔗

🔗

Subsection 2.3.1 What Is Probability?

Subsection 2.3.2 Sample Spaces and Events

Subsection 2.3.3 Computing Probability

Subsection 2.4.1 Complement, Union, and Intersection

Example 2.4.8. Union and Intersection: Dice Sums.

Roll two six-sided dice. Let \(E\) be the event the sum is less than 10 and \(F\) be the event the sum is even. Find the outcomes in \(E \cup F\) and \(E \cap F\text{.}\)

🔗

Solution.

\(E = \{2,3,4,5,6,7,8,9\}\text{.}\) \(F = \{2,4,6,8,10,12\}\text{.}\)

🔗

\(E \cup F = \{2,3,4,5,6,7,8,9,10,12\}\) (all sums that are either less than 10 or even).

🔗

\(E \cap F = \{2,4,6,8\}\) (sums that are both less than 10 and even).

🔗

🔗

🔗

Subsection 2.4.2 The Five Core Properties

Example 2.4.13. Applying the Addition Rule.

Using the events from Example 2.4.8, find \(P(E)\text{,}\) \(P(F)\text{,}\) \(P(E \cap F)\text{,}\) and \(P(E \cup F)\text{.}\) Recall that there are 36 equally likely outcomes when recording ordered pairs.

🔗

Solution.

Counting ordered pairs with the given sums: \(n(E) = 30\text{,}\) so \(P(E) = \dfrac{30}{36} = \dfrac{5}{6}\text{.}\)

🔗

\(n(F) = 18\text{,}\) so \(P(F) = \dfrac{18}{36} = \dfrac{1}{2}\text{.}\)

🔗

\(n(E \cap F) = 14\text{,}\) so \(P(E \cap F) = \dfrac{14}{36} = \dfrac{7}{18}\text{.}\)

🔗

By the addition rule:

\begin{equation*} P(E \cup F) = \frac{5}{6} + \frac{1}{2} - \frac{7}{18} = \frac{30}{36} + \frac{18}{36} - \frac{14}{36} = \frac{34}{36} = \frac{17}{18}. \end{equation*}

🔗

🔗

🔗

Example 2.4.15. Working from Given Probabilities.

Events \(A\) and \(B\) satisfy \(P(A) = 0.73\text{,}\) \(P(B) = 0.4\text{,}\) and \(P(B \cap \bar{A}) = 0.12\text{.}\) Find \(P(A \cap B)\text{,}\) \(P(A \cup B)\text{,}\) and \(P(\bar{A})\text{.}\)

🔗

Solution.

Since \(B = (B \cap A) \cup (B \cap \bar{A})\) and the two pieces are disjoint:

\begin{equation*} P(A \cap B) = P(B) - P(B \cap \bar{A}) = 0.4 - 0.12 = 0.28. \end{equation*}

🔗

\(P(A \cup B) = 0.73 + 0.4 - 0.28 = 0.85.\)

🔗

\(P(\bar{A}) = 1 - 0.73 = 0.27.\)

🔗

🔗

🔗

Subsection 2.4.3 Probability Trees

Example 2.4.17. Three Coin Flips Revisited.

You flip a fair coin three times. What is the probability of getting HHT?

🔗

Solution.

Each branch has probability 0.5. Multiplying along the H-H-T path:

\begin{equation*} P(HHT) = 0.5 \times 0.5 \times 0.5 = 0.125. \end{equation*}

Since all 8 outcomes have equal probability, each has probability \(\frac{1}{8} = 0.125\text{,}\) and the sum of all eight is exactly 1.

🔗

🔗

🔗

Example 2.4.20. Drawing Marbles from Two Boxes.

Box A contains 5 blue and 8 red marbles. Box B contains 10 blue and 6 red marbles. You draw one marble from Box A, place it in Box B, then draw one marble from Box B. Find the probability that the second marble drawn is red.

🔗

Solution.

There are two paths that end in a red second draw.

🔗

Path 1 (Blue then Red): Draw blue from A: \(\frac{5}{13}\text{.}\) Box B now has 11 blue and 6 red (17 total). Draw red from B: \(\frac{6}{17}\text{.}\) \(P(\text{BR}) = \frac{5}{13} \times \frac{6}{17} = \frac{30}{221}\text{.}\)

🔗

Path 2 (Red then Red): Draw red from A: \(\frac{8}{13}\text{.}\) Box B now has 10 blue and 7 red (17 total). Draw red from B: \(\frac{7}{17}\text{.}\) \(P(\text{RR}) = \frac{8}{13} \times \frac{7}{17} = \frac{56}{221}\text{.}\)

🔗

\begin{equation*} P(\text{second draw is red}) = \frac{30}{221} + \frac{56}{221} = \frac{86}{221} \approx 0.389. \end{equation*}

🔗

🔗

🔗

Subsection 2.5.1 Conditional Probability

Definition 2.5.1. Conditional Probability.

The conditional probability of event \(E\) given that event \(F\) has occurred is

\begin{equation*} P(E \mid F) = \frac{P(E \cap F)}{P(F)} \end{equation*}

provided \(P(F) \neq 0\text{.}\)

🔗

🔗

Subsection 2.5.2 Bayes’ Theorem

Example 2.5.10. Drug Testing and False Positives.

A test for a certain drug gives a false positive in 2% of tests on non-users, and a false negative in 1% of tests on users. Suppose that 1% of the population uses this drug. A randomly selected person tests positive. What is the probability that they actually use the drug?

🔗

Solution.

Let \(U\) = uses the drug and \(S\) = tests positive. We know: \(P(U) = 0.01\text{,}\) \(P(\bar{U}) = 0.99\text{,}\) \(P(S \mid U) = 0.99\text{,}\) \(P(S \mid \bar{U}) = 0.02\text{.}\)

🔗

Step 1: Find \(P(S)\) using the probability tree. \(P(U \cap S) = 0.01 \times 0.99 = 0.0099\text{.}\) \(P(\bar{U} \cap S) = 0.99 \times 0.02 = 0.0198\text{.}\) \(P(S) = 0.0099 + 0.0198 = 0.0297\text{.}\)

🔗

Step 2: Apply Bayes’ Theorem.

\begin{equation*} P(U \mid S) = \frac{P(S \mid U) \cdot P(U)}{P(S)} = \frac{0.0099}{0.0297} \approx 0.33. \end{equation*}

🔗

Even with a positive test, the probability of actually using the drug is only about 33%. This surprises most people — but because users are rare (only 1% of the population), most positive tests come from the large pool of non-users even though the false positive rate is small.

🔗

🔗

🔗