Bayes' Theorem Explained

Bayes' Theorem

• Describes the probability of an event based on prior knowledge of conditions related to the event.
• Expressed as: $P(A|B) = \frac{P(B|A)P(A)}{P(B)}$
• $P(A|B)$ is the conditional probability of A given B is true.
• $P(B|A)$ is the conditional probability of B given A is true.
• $P(A)$ and $P(B)$ are the independent probabilities of A and B being true.

Deduction of Bayes' Theorem

• Can be derived from basic definitions of conditional probability.
• $P(A|B) = \frac{P(A \cap B)}{P(B)}$ and $P(B|A) = \frac{P(B \cap A)}{P(A)}$.
• Since $P(A \cap B) = P(B \cap A)$, it follows that $P(A|B) \cdot P(B) = P(B|A) \cdot P(A)$.
• Dividing by $P(B)$ gives the theorem: $P(A|B) = \frac{P(B|A)P(A)}{P(B)}$.

Example of Bayes' Theorem Application

• Scenario: Two factories (A and B) produce light bulbs, with A producing 60% and B producing 40% of total production.
• Factory A has a 5% defect rate, while Factory B has a 10% defect rate.
• Objective: Determine the probability a defective bulb was produced in Factory A.
• Define A as the event a bulb was from Factory A, and B as the event a bulb is defective.
• Given: $P(A) = 0.60$, $P(B|A) = 0.05$, $P(\bar{A}) = 0.40$, and $P(B|\bar{A}) = 0.10$.
• First, calculate $P(B)$: $P(B) = P(B|A) \cdot P(A) + P(B|\bar{A}) \cdot P(\bar{A}) = 0.07$.
• Applying Bayes' Theorem: $P(A|B) = \frac{P(B|A)P(A)}{P(B)} = \frac{0.05 \cdot 0.60}{0.07} \approx 0.4286$.
• Conclusion: There is approximately a 42.86% chance a defective bulb was produced at Factory A.

Complex Numbers Definitions and Examples

• Has the form $a + bi$, where $a$ and $b$ are real numbers, and $i$ satisfies $i^2 = -1$.
• The real part is $a$, denoted as Re$(z)$, its the part on the x-axis of a graph.
• The imaginary part is $b$, denoted as Im$(z)$, its the part on the y-axis of a graph.
• $3 + 2i$ has Re$(z) = 3$, Im$(z) = 2$
• $-2 - i$ has Re$(z) = -2$, Im$(z) = -1$
• $5i$ has Re$(z) = 0$, Im$(z) = 5$
• $6$ has Re$(z) = 6$, Im$(z) = 0$

Argand Diagram, Modulus, and Argument

• Complex numbers can be graphically represented with the x-axis as the real part and the y-axis as the imaginary part.
• The complex number $3 + 4i$ is represented by the point $(3, 4)$.
• The modulus of $z = a + bi$, denoted as $|z|$, is the distance from origin to point where z is placed for the plot, and $|z| = \sqrt{a^2 + b^2}$.
• For and example $z = 3 + 4i$, then $|z| = 5$.
• The argument of $z$, denoted as arg$(z)$, is the angle between the positive real axis and the line connecting the origin to $z$ , and $\theta = \tan^{-1}\left(\frac{b}{a}\right)$.
• The principal value of the argument, denoted Arg$(z)$, is between $(-\pi, \pi]$.
• Example: If $z = 1 + i$, then $\theta = \frac{\pi}{4}$

Complex Number Arithmetic

• Addition: $(a + bi) + (c + di) = (a + c) + (b + d)i$
• Subtraction: $(a + bi) - (c + di) = (a - c) + (b - d)i$
• Multiplication: $(a + bi)(c + di) = (ac - bd) + (ad + bc)i$
• To divide complex numbers, multiply the numerator and denominator by the conjugate of the denominator.
• Division: $\frac{a + bi}{c + di} = \frac{(ac + bd) + (bc - ad)i}{c^2 + d^2}$

Complex Conjugate

• Conjugate of $z = a + bi$ is $\bar{z} = a - bi$.
• $\overline{z + w} = \bar{z} + \bar{w}$
• $\overline{z - w} = \bar{z} - \bar{w}$
• $\overline{zw} = \bar{z} \cdot \bar{w}$
• $\overline{\left(\frac{z}{w}\right)} = \frac{\bar{z}}{\bar{w}}$
• $z + \bar{z} = 2\text{Re}(z)$
• $z - \bar{z} = 2i\text{Im}(z)$
• $z \cdot \bar{z} = |z|^2$

Polar and Exponential Forms

• A complex number $z = a + bi$ can be represented in polar form as $z = r(\cos\theta + i\sin\theta)$
• $r = |z|$ is the modulus and $\theta = \text{arg}(z)$ is the argument of $z$.
• Euler's formula: $e^{i\theta} = \cos\theta + i\sin\theta$
• Using Euler's formula, the polar form can be written in exponential form as $z = re^{i\theta}$.

De Moivre's Theorem

• For $z = r(\cos\theta + i\sin\theta)$ and any integer $n$:
• $z^n = r^n(\cos(n\theta) + i\sin(n\theta))$
• or equivalently, $(e^{i\theta})^n = e^{in\theta}$

Algorithmic Game Theory Fundamentals

• Game Theory studies multi-agent decision problems.
• Central concept is the Nash Equilibrium.

Selfish Routing Description

• A game played on a network.
• Players route traffic from source to destination quickly.
• Cost depends on traffic.

Selfish Routing Key Questions

• What does a Nash Equilibrium look like?
• How inefficient is a Nash Equilibrium?
• How hard is it to compute a Nash Equilibrium?
• How can the network to improve the outcome?

Braess's Paradox Explanation

• N players want to travel from S to E.
• Each player controls 1 unit of flow, can go from S to A to E or S to B to E.
• Edge SA has Cost is Traffic, i.e. $x$, Edge AE: Cost is 1, Edge SB: Cost is 1, Edge BE: Cost is Traffic again, i.e. $x$.
• Nash Equilibrium has traffic split equally with a total cost of $1.5$.
• Adding a free edge from A to B, the Nash Equilibrium is the traffic goes S to A to B to E which each participant paying $2$ cost overall, leading things to be worse!

Formal Model Parameters

• Graph $G = (V, E)$
• $r$ players
• Player $i$ wants to move $f_i$ units of flow from $s_i$ to $t_i$
• A strategy for player $i$ is a path from $s_i$ to $t_i$
• $P_i$ is the set of possible strategies for player $i$.
• Strategy vector $P = (P_1, \dots, P_r)$
• $f_e(P) =$ total flow on edge $e$ in strategy vector $P$
• Each edge $e$ has a cost function $c_e(x)$
• Cost to player $i: C_i(P) = \sum_{e \in P_i} c_e(f_e(P))$

Nash Equilibrium Formally

• A strategy vector $P$ is a Nash Equilibrium if no player can improve its cost by unilaterally changing its strategy
• $C_i(P) \le C_i(P_i', P_{-i})$ for all players $i$ and all strategies $P_i' \in P_i$
• $P_{-i}$ denotes the strategies of all players except $i$.

Social Cost

$SC(P) = \sum_{i=1}^r C_i(P) = \sum_{e \in E} f_e(P) \cdot c_e(f_e(P))$

Price of Anarchy (PoA)

• Measures the inefficiency of Nash Equilibrium
• $PoA = \frac{\max_{P \text{ is NE}} SC(P)}{\min_{P} SC(P)}$

Goal of Price of Anarchy

• To bound the Price of Anarchy for different cost functions.