MA279 - Modern Mathematics in Society

- Voting
- Division
- Apportionment
- Apportionment
- Graphs
- Exponential Growth
- Ginomons
- Mathematics of Money
- Motions
- Symmetry groups
- Fractals
- Sampling
- Statistics and Probability
- Final Review

**ballot** - ordering of candidates

**method** - way of counting ballots

**criterion** - requirements on the result of a method

**majority criteron** - a candidate with more than half of the votes should win

**condorcet criterion** - a candidate that wins head-to-head with all others should win

**plurality criterion** - a candidate with the most votes overall should win

**monotonicity criterion** - a change in votes which only favors a candidate should help that candidate

- the candidate with the most 1st place votes wins
- fails condorcet criterion

Plurality with elimination fails monotonicity

7 8 10 4 A B C A B C A C C A B B C wins

If 4 players vote for C instead of A...

7 8 14 A B C B C A C A B B wins, even though the votes for C increased

- a candidate with more than half of 1st place votes wins, otherwise eliminate the last place candidate and repeat
- fails condorcet,

- assign weights to each position on the ballot and sum total points for each candidate
- fails condorcet criterion

- count number of permutations of candidate pairs where X beats Y, give X one point
- the candidate with the most points wins
- passes plurality and condorcet

Copeland's method fails irrelevant alternatives criterion

**Original Ballot**2 6 4 1 1 4 4 A B B C C D E D A A B D A C C C D A A E D B D E D B C B E E C E E B A Running Copeland's method:

A > **B**7 **A**> C16 **A**> D13 **A**> E18 B > **C**10 **B**>**D**11 **B**> E14 **C**> D12 **D**> E18 C > **E**10 **A wins****Modified Ballot (candidate C removed)**2 6 4 1 1 4 4 A B B B D D E D A A A A A D B D D D B E B E E E E E B A Running Copeland's method

A > **B**7 **A**> D13 **A**> E18 **B**>**D**11 **B**> E14 **D**> E18 **B wins****A**lost even though votes were changed in this candidate's favor

Majority | Condorcet | Monotonicity | Independence | |
---|---|---|---|---|

Plurality | fail | fail | ||

Borda | fail | fail | fail | |

Plurality w/ elim. | fail | fail | fail | |

Copeland's | fail |

**Ken Arrow's Theorem**

All ballot methods fail at least one test

- use voting method, remove winner and repeat process

**borda**- rank by Borda number**pairwise**- rank by number of comparisons won**plurality**- rank by total first place votes

Each players vote has a weight \(w_n\) for either supporting or rejecting a motion

[q : \(w_1\), \(w_2\),...]

**quota**- minimum number of votes needed to carry a motion**gridlock**- q is more than all votes**anarchy**- the number of votes for and the number against a motion are more than the quota**dictator**- a player that has more votes than the quota**unsuspecting dummy**- a player that has no impact on the result- eg [30: 10, 10, 10, 9]

Characterizes voting power of a player

\[\beta_i = \frac{B_i}{B_1 + ... + B_N}\]

where \(B_i\) is the number of coalitions where player i is a critical player (removing them would cause the coalition to lose)

[5: 3, 2, 1, 1]

Winning coalitions: (with critical players bolded)

**A**B C D**A B**C**A B****A C D****A B**D\(B_A = 5\)

\(B_B = 3\)

\(B_C = 1\)

\(B_D = 1\)

\[\beta_A = \frac{5}{5 + 3 + 1 + 1} = \frac{1}{2}\]

**goods/booty** - things to be divided amongst players

**player preferences** - how each player values goods

**fair share** - at least \(\frac{1}{n}\) of the goods available to a player

**divisible goods** - money, pizza, land, etc.

**indivisible goods** - house, car, horse, etc.

- Two players. Player 1 divides the goods and player 2 chooses which share to take.
- Chooser always has an advantage. They can choose the share that caters to their own value system

- One player divides the booty into equal shares. A third party must allot the shares so that all players get what they consider a fair share

**Wedding Theory**

- N boys want to marry N girls
- boys can only marry girls they know

There can't be a good match if K players collectively like less than K unique items

Divider has broken booty into shares I, II and III. Fair shares for each player have been marked.

I II III \(D\) \(\frac{1}{3}\) \(\frac{1}{3}\) \(\frac{1}{3}\) \(C_1\) fair fair \(C_2\) fair fair - give I to \(C_2\)
- give II to \(D\)
- give III to \(C_1\)

Divider has broken booty into shares I, II and III, IV. Fair shares for each player have been marked.

I II III IV \(D\) \(\frac{1}{4}\) \(\frac{1}{4}\) \(\frac{1}{4}\) \(\frac{1}{4}\) \(C_1\) fair \(C_2\) fair fair \(C_3\) fair - give I to \(D\)
- give II or III to \(C_2\)
- give II, III, or IV to \(C_1\), \(C_2\)

- divide booty into 2 fair shares using above methods
- \(D_1\) and \(D_2\) each divide their share into 3 fair shares
- \(C\) chooses \(\frac{1}{3}\) of a share from \(D_1\) and \(D_2\)

- Player 1 takes a fair share of the booty and passes it to Player 2.
- Player 2 either cuts down the share to what he thinks is fair, or doesn't change it and passes it down
- Share continues to Player N. The share goes to the last player who considered it fair

This is fair to the last player because all pieces he rejected were less than a fair share, so the remaining piece must be a fair share.

- Put all goods in a line and have each player place N-1 markers to divide the goods into fair shares. ./graphic
- Give the first share to Player A ./graphic
- Remove the all the markers for the first share and Player A's markers. Repeat for Players B,...,N

Player A always gets exactly a fair share

Other players get at least a fair share

- N players bid for N-1 items
- Top bid for each item wins the item
- The item winners pay back the difference of the value of the item they won and what they consider a fair share \((\text{won item value} - \frac{\text{total item values}{N})\)
- The amount payed back can be a negative value
- the value of a loser's item is 0
- The leftover money is always positive

How do we assign the seats in Congress to populations of states?

The sum of all shares of seats must equal the total seats available.

- \(A_1,...,A_N\) - states to assign seats to
- \(P_i\) - population of each state
- \(M\) - seats in congress
- \(SD = \frac{P}{M}\) - standard divisor (people corresponding to each state)
- \(q_i = \frac{P_i}{SD}\) - standard quota (fair share of seats for a state)

**Quota Criterion**

Each state should get either \(\lfloor q_i \rfloor\) or \(\lceil q_i \rceil\) seats

- Find the fair share for each state (\(q_i\)) and give them the floor
- Assign the remaining seats to the states with the largest leftover fraction (\(q_i - \lfloor q_i \rfloor\))

A B C D E F \(\sum\) \(P_i\) 1646 6936 154 2091 685 988 12500 \(q_i\) 32.92 138.72 3.08 41.82 13.7 19.76 250 \(\lfloor q_i \rfloor\) 32 138 3 41 13 19 246

With a decrease in \(M\) (the number of seats available), it is possible for the number of seats assigned to a state to increase.

- population and \(M\) are fixed
- modify \(SD = \frac{P}{M}\) so that \[\sum \lfloor q_i \rfloor = \sum \lfloor ( \frac{P_i}{P} M ) \rfloor = M\]
- new \(SD\) ≤old \(SD\)

A B C D E F \(\sum\) new \(q_i\) 33.25 140.12 3.11 42.24 13.84 19.96 \(\lfloor q_i \rfloor\) 33 140 3 42 13 19 250

- identical to Jefferson's method, but using ceiling
- modify \(SD = \frac{P}{M}\) so that \[\sum \lceil q_i \rceil = \sum \lceil ( \frac{P_i}{P} M ) \rceil = M\]
- new \(SD\) ≥old \(SD\)

A B C D E F \(\sum\) \(\lceil q_i \rceil\) 33 137 4 42 14 20 250

- identical to Adam's and Jefferson's, but using rounding
- modify \(SD = \frac{P}{M}\) so that \[\sum \text{round} (q_i) = \sum \text{round} ( \frac{P_i}{P} M ) = M\]

A B C D E F \(\sum\) new \(q_i\) 32.85 138.44 3.07 41.74 13.67 19.72 \(\lceil q_i \rceil\) 33 138 3 42 14 20 250

similar to webster, but rounding using geometric mean

- if \(\frac{P_i}{P} * M \geq \sqrt{N(N+1)}\) use ceiling
- if \(\frac{P_i}{P} * M \leq \sqrt{N(N+1)}\) use floor

**apportionment** - how to scale congress to population of states? \[A_1 ... A_N\] - states

\(N\) - number of states

\(P_i\) - population of a state

\(M\) - seats available in congress

\(SD = \frac{P}{M}\) - standard divisor, people per seat

\(q_i = \frac{P_i}{SD}\) - fair share of seats for state

**quota rule** - every state should either get floor(\(q_i\)) or ceil(\(q_i\))

Give everyone the floor of their fair share. Assign the remaining n seats to n states with highest remainder.

State A B C D E F sum \(P_i\) 1646 6936 154 2091 685 988 12500 \(q_i\) 32.92 138.71 3.08 41.82 13.7 19.76 250 floor 32 138 3 41 13 19 246

Modify \(SD\) until the sum of the ceils of fair shares of seats is equal to the total seats available

\(\sum \lceil(q_i)\rceil = \sum \frac{P_i}{SD} \geq M\)

so \(SD\) needs to be increased until

\(\sum \lceil(q_i)\rceil = \sum \frac{P_i}{SD} = M\)

**its possible to violate the quote rule**

Same as Adam's method, but using rounding.

\(\sum \lceil(q_i)\rceil = \sum \frac{P_i}{SD} \approx M\)

so increase or decrease \(SD\) until

\(\sum \lceil(q_i)\rceil = \sum \frac{P_i}{SD} = M\)

This method is currently in use today.

Find the geometric mean of the ceiling and floor of the the fair shares for each state. If the fair share is greater than the geometric mean, use the ceiling. If the fair share is less than the geometric mean, use the floor.

If \(q_i \geq \sqrt{\lfloor q_i \rfloor \lceil q_i \rceil}\), use \(\lceil q_i \rceil\) If \(q_i \leq \sqrt{\lfloor q_i\rfloor \lceil q_i \rceil}\), use \(\lfloor q_i \rfloor\)

**euler paths** - uses each edge once

If G has an euler path, then

- all vertices must have even degree except for start and end
- start and end are either both odd or even

Proof

**euler circuit** - uses each edge once and returns to start

If G has an euler circuit, then

- it must be connected
- deg of every vertex is even

If G has an even degree, then

- it can be seen as a union of circuits

*Hierholzer Algorithm*

Start following circuit I until you reach circuit II Continue on circuit II until you reach III ... Continue on circuit m until you reach n Finish m Finish n ... Finish II Finish I

**euler circuit** ⇔ G has even degree

**fluery algorithm**

**platonic solids**

- regular polygon faces
- faces and edges all have same angles
- same number of faces and edges meet at every vertex

**semiplatonic solids**

- relax one of the rules for platonic solids

**bipartite** - elements can be grouped into two non touching groups

Given some vertices, find a path through them that is minimal. By giving each edge a weight, we can give minimal a concrete meaning.

2 Simplifications

- \(\sum w(e) = 1\)
- There are edges between all vertices

**hamilton circuit** - a path that visits every vertex exactly once **hamilton graph** - a graph with a hamilton circuit

Let n be the number of vertices If \(\text{deg}(a) + \text{deg}(b) \geq n\) for all vertices a,b then the graph is hamiltonian

**P** - any problem with \[a_nn^{b_n} + a_{n-1}n^{b_{n-1}} + ... + a_0\] steps is class P **NP hard** - finding an algorithm for these problems proves P = NP

**tree** - a connected graph with no loops

**spanning tree** - a tree which contains all vertices of a graph

**leaf** - a vertex in a graph with degree one

**Properties of Trees**

- connected and no loops
- removing any edge disconnects graph
- edges = vertices - 1

All trees must have at least one leaf

Identical to the cheapest link algorithm, but prevents circuits from forming.

- Select the cheapest edge.
- Repeat until all vertices are connecting, taking care not to create circuits.

Kruskal's Algorithm always finds an optimal solution.

**Steps to create Prüfer Sequence from tree**

- find leaf with smallest index
- delete and record index that leaf was attached to

**Steps to recreate graph from Prüfer sequence**

S = {3,3} - Prüfer sequence

L = {1,2,3,4} - list of vertices

S = {3}

L = {2,3,4}

edge 1-3

S = {}

L = {3,4}

edge 2-3

edge 3-4

Spanning trees in \(K_N\): \(n^{n-2}\)

There is a pair of rabbits. A pair of rabbits takes 1 year to mature, and another to produce offspring. What is the population at year n?

\(n\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 |

\(m_n\) | 1 | 0 | 1 | 1 | 2 | 3 | 5 |

\(m_n\) | 0 | 1 | 1 | 2 | 3 | 5 | 8 |

\(p_n\) | 1 | 1 | 2 | 3 | 5 | 8 | 13 |

where \(n\) is the year, \(y_n\) is the number of young rabbits, \(m_n\) is the number of mature rabbits, and \(p_n\) is the total population

\(p_n = \frac{1 - \lambda_1}{\lambda_2(\lambda_2 - \lambda_1)} \lambda_1^n + \frac{1 - \lambda_2}{\lambda_1(\lambda_1 - \lambda_2)} \lambda_2^n\)

where \(\lambda_1,\lambda_2 = \frac{1 + \sqrt{5}}{2},\frac{1 - \sqrt{5}}{2}\)

Derivation

If \((a)\) is a sequence with a recurrence of depth 2,

then \(a_n = C_{n-1}a_{n-1} + C_{n-2}a_{n-2}\)

with initial conditions \(a_1,a_n = A_1,A_2\)

Let \(\lambda_1,\lambda_2\) be the roots of \(\lambda^2 = C_{n-1} \lambda + C_{n-2}\)

then \(a_n = b_1 \lambda_1^n + b_2 \lambda_2^n\)

Let \(a_n = 3a_{n-1} - 2a_{n-2}\), \(a_0 = 1\), \(a_1 = 1\)

Find \(\lambda\)

\(\lambda^2 = 3 \lambda - 2\)

\(\lambda1,\lambda2 = 1,2\)

Find \(b_1,b_2\) using initial conditions

\(1 = a_0 = b_1 1^0 + b_2 2^0 = b_1 + b_2\)

\(1 = a_1 = b_1 1^1 + b_2 2^1 = b_1 + 2 b_2\)

So \(b_1 = 1, b_2 = 0\)

Let \(a_n = 6a_{n-1} - 11a_{n-2} + 6a_n - 3\), \(a_0 = 1, a_1 = 2, a_2 = 7\)

\(\lambda^n = 6\lambda^{n-1} - 11\lambda^{n-2} + 6\lambda^{n-3}\)

Divide out \(\lambda^{n-3}\)

\(\lambda^3 = 6\lambda^2 - 11\lambda + 6\)

Making guesses for roots: \(\lambda = \pm 1, \pm 2, \pm 3, \pm 6\)

our roots are \(\lambda = 1,2,3\)

so the guess for the solution is \(a_n = A1^n + B2^n + C3^n\)

Substituting our initial conditions:

\(1 = a_0 = A1^0 + B2^0 + C3^0 = A + B + C\) \(1 = a_1 = A1^1 + B2^1 + C3^1 = A + 2B + 3C\) \(7 = a_2 = A1^2 + B2^2 + C3^2 = A + 4B + 9C\)

Solving the system yields \(A = \frac{3}{2}, B = -2, C = \frac{3}{2}\)

Let \(a_n = c_{n-1}a_{n-1} + ... + c_{n-d}a_{n-d}\)

If there are \(k\) roots of \(\lambda^d - (C_{n-1}\lambda^{d-1} + C_{n-2}\lambda^{d-2} + ... + C_{n-d}\lambda^{0}\), let the multiplicities be \(e_1,...,e_k\)

so \(f(\lambda) = (\lambda - \lambda_1)^{e_1} + ... (\lambda - \lambda_k)^{e_k}\)

\[ \begin{aligned} a_n & = \lambda_1^n(b_{1,0} + b_{1,1}n + ... + b_{1,e_1 - 1} n^{e_1 - 1}) \\ & + \lambda_2^n(b_{2,0} + b_{2,1}n + ... + b_{2,e_2 - 1} n^{e_2 - 1}) \\ & + ... \\ & + \lambda_k^n(b_{k,0} + b_{k,1}n + ... + b_{k,e_k - 1} n^{e_k - 1}) \end{aligned} \]

#+begin definition **Fibonacci sequence** \(F_N = F_{N-1} + F_{N-2}\)

\(F_1 = 1, F_2 = 1\) - seed numbers

#+end_{definition}

The golden ratio \(\phi\) is defined as an irrational number where

\(\phi^2 = \phi + 1\)

\(\phi = \frac{1 + \sqrt{5}}{2}\)

The golden ratio can be found in many places in nature, from population modelling to the number of chambers in a nautilus shell.

An interesting property of the golden ratio is that the ratio of two consecutive fibonacci numbers approaches \(\phi\) as \(N\) gets large.

\(\lim_{n \to \infty} \frac{F_N}{F_{N-1}} = \phi\)

If \(f\) is a polynomial with integer coefficients and leading coefficient 1, then

- all rational roots are integers
- all integer roots divide the constant term of f

Let \(a_n = 6a_{n-1} - 11a_{n-2} + 6a_{n-3}\)

\(\lambda^3 - 6\lambda^2 + 11\lambda - 6 = 0\)

Divisors of 6 as possible roots: -6, -3, -2, -1,

**1**,**2**,**3**, 6\(a_n = b_11^n + b_22^n + b_33^n\)

Let \(a_n = 8a_{n-2} - 16a_{n-4}\)

$f(

*λ*) =*λ*^{4}- 8*λ*^{2}+ 16

& = (*λ*^{2}- 4)^{2}\end{align*} \[ $\lambda_1,\lambda_2 = -2_{x2},2_{x2}$ \] \begin{align*} a_{n}= 2^{n}(b_{1,0}+ b_{1,1}n)

& + (-2)^{n}(b_{2,0}+ b_{2,1}n) \end{align*} $$\(F_1(n) = 1\) \(t = 0, m = 1, s = 1\)

\(F_2(n) = 2^n\) \(t = 0, m = 0, s = 2\)

**Simple Interest**

\(F_s = P(1 + rt)\)

*Compounded Interest

\(F_c = P * (1 + \frac{r}{n})^{tn}\)

\(\lim_{n \to \infty} F_c = P * e^{rt}\)

Let \(t \geq 1\)

then \(F_c = P (1^n + 1^{n-1}r(\frac{t}{1}) + ... \geq F_s = P (1 + rt)\)

- Month 1 - spend 876
- Month 2 - spend 288

Bill 1

- pay 876
- pay $20 min charge
- pay $20<$400<$876

Bill 2

- nothing, owe 288
- owe $1165 = $876 - $20 + $288 + $21
- owe $777.64 = $876 - $400 + $288 + $13.64 not paying off bill increases interest for this month's balance by \(\frac{1}{2} \frac{\text{APR}}{12}\) times what was spent this month Over the course of a year this compounds to more than \((\frac{1}{2} APR) * \text{spent over year}\)

**Fixed annuity**

Sequence of equal payments at regular time intervals

**Deferred**

Making regular payments and collecting at some point in the future (investment)

**Installment loan**

Receive loan up front and pay it back in regular payments

**Motion**

Let \(v \in \mathbb{R}^n\)

Let \(A \in M_{m \times n}, B \in \mathbb{R}^m\)

Then the mapping \((A,B): \mathbb{R}^n \to \mathbb{R}^n\) such that \((A,B) \overrightarrow{v} = A\overrightarrow{v} + b\)

is called a motion

- motions have an inverse and an identity, which makes all motions a
**group** - motions are associative and have an inverse

We can find the size of a motion in various dimensions

In dimension 1, \(A^TA = 1\), so \(A = 1\) and \(A\) has 0 degrees of freedom + 2 degrees of freedom for \(B\)

In dimension 2, \(A^TA = 1\), so \(A\) has 1 degree of freedom + 2 degrees of freedom for \(B\)

If a motion is a rotation about the origin, it has the form \[A = \left( \begin{bmatrix} \cos(\alpha) & -\sin(\alpha) \\ \sin(\alpha) & \cos(alpha) \end{bmatrix} \right)\]

If \(\overrightarrow{v}\) and \((A,B)\overrightarrow{v}\) are given, there is a line of possible points for the center of rotation

A motion is proper if \(\det(A) = 1\).

ie. A motion rotates the input, but does not flip

If \(\det(A) = -1\), then the motion is called improper and flips the system as well as rotates

**If a pair of points are reflected and shifted by the same amount, how can we find the axis of reflection and the shift?**

**Symmetry group**

Let \(G\) be the set of motions such that the system \(X\) looks the same before and after

\(G\) is called a symmetry group

- symmetry groups are not commutative (ex. rotating an object, then flipping is not the same as flipping then rotating)

**Dihedral group**

The set of motions which preserve the look of a regular polygon is called a dihedral group

We can classify various line patterns based on their symmetries

Type name convention: **xy**

**x** can be m or 1

- m - reflection, vertical axis
- 1- no reflection

*y* can be m, g, 2, or 1

- m - reflection, horizontal axis
- g - glide reflection
- 2 - \(180^{\circ}\) rotation
- 1 - no reflection

**Glide reflection**

Flip a pattern over the horizontal axis, then translate it left or right:

Pattern | Type | Symmetry groups |
---|---|---|

--T--T--T--T-- | m1 | translations by \(\mathbb{Z}\) and vertical reflections at \(\mathbb{Z}\) or \(\mathbb{Z} + .5\) |

->-T->-T->-T->- | 11 | translations by \(\mathbb{Z}\) |

->-I->-I->-I->- | 1m | translations by \(\mathbb{Z}\) and horizontal reflection |

--I--I--I-- | mm | translations by \(\mathbb{Z}\) and horizontal/vertical reflections |

--Z--Z--Z-- | 12 | translations by \(\mathbb{Z}\) and rotations by \(180^{\circ}\) |

--b--p--b-- | 1g | translation by \(2\mathbb{Z}\) and glide reflection |

--^--v--^-- | mg | translation by \(2\mathbb{Z}\) and glide reflection |

\(\text{Area} = \frac{3}{4}^n\)

\(\text{Perimeter} = \frac{3}{2}^n\)

$Area = ∑

**pascal's triangle modulo 6**

The Mandelbrot set is named after Benoit Mandelbrot, a mathematician at Yale University who developed his fractal theories while working for IBM.

**Mandelbrot Sequence**

\(a_{n} = a_{n - 1}^2 + s\)

$a_{0} = s

where \(s\) is called the seed

Mandelbrot sequences can either be escaping, attracting, or periodic, depending on their behavior at infinity.

**Periodic**Let \(s = -1\)

\(a_1\) -1 \(a_2\) 0 \(a_3\) -1 ... ... **Escaping**Let \(s = 1\)

\(a_1\) 1 \(a_2\) 2 \(a_3\) 5 ... ... **Attracting**Let \(s = \frac{-3}{4}\)

\(a_1\) \(\frac{-3}{4}\) \(a_2\) \(\frac{-3}{16}\) ... ... \(a_n\) \(\frac{-1}{2}\)

To generate an image from the Mandelbrot set, we evaluate the behavior of all seeds in the complex plane and assign a color based on the speed that the seed escapes or attracts.

- if a live square has less than 2 or more than 3 neighbors, it dies
- if a dead square has 3 neighbors, it comes to life

Various shapes we are familiar with can be assigned a dimension. For example, a line, a square, and a cube have dimensions 1, 2, and 3, respectively.

Since these shapes are self similiar (they can be constructed from smaller versions of themselves) we can define a formula for calculating dimension.

Let \(N\) be the number of self similar children, \(S\) be the scaling ratio of a child to parent, and \(D\) be the dimension of the shape we are studying.

Then \(N = S^D\)

Assume a straight line made of 4 equal line segments.

We know \(N = 4\), \(S = 4\),

so \(D = 1\)Assume a square made of 16 equal squares

We know \(N = 16\), \(S = 4\),

so \(D = 2\)Assume a cube made of 64 equal cubes.

We know \(N = 64\), \(S = 4\)

so \(D = 3\)Assume a Sierpinsky gasket

**incomplete**Since a sierpinsky gasket is made of 3 half-size versions of itself

we know \(N = 3\), \(S = 2\)

\(3 = 2^D\)

\[D = \dfrac{\log (3)}{\log (2)}\]

Assume a sponge (3D carpet)

**incomplete**Since X is the union of 20 third-size copies of itself,

we know \(N = 20\), \(S = 3\)

\(20 = 3^D\)

\(D = \frac{\log{20}}{\log{3}}\)

Start with \(X \in \mathbb{N}\)

- if X is divisible by 2, divide it by 2
- otherwise, multiply by 3 and add 1

You will always reach 1.

This conjecture remains unproven.

**statistic** - the result drawn from a sample

**parameter** - the actual value that the statistic attempts to estimate

**target population** - set to evaluate

**sample population** - sampled subset

**sampling frame** - where lists of the sample population are obtained (eg, magazine subscription lists, club membership). Adds selection bias to the polls

Used to determine total populations. Assumes population exhibits Brownian (random) motion.

- Capture n indivudals from the population
- Tag each individual and release them again
- Allow the tagged individuals to mix with the population
- Capture m individuals from the population.
- If there are t tagged individuals in the m captured individuals, the population is approximately \[N = \frac{n}{\frac{t}{m}}\]

In theory, random sampling is simply randomly sampling N individuals that all have an equal chance of being sampled.

This is difficult to implement in practice, as **sampling bias** leads to skewed results. Alternative sampling methods are an attempt to correct this sampling bias.

**Quota Sampling**

- Using prior knowledge about the sampling population, create profiles based on characteristics of individuals (eg. white males, asian females, etc.)
- Determine the percentage of individuals that make up each profile
- When conducting the study, ensure that a proportionate number of individuals matching each profile is sampled

Quota sampling requires that you know enough about the population beforehand to generate a comprehensive list of profiles. This is often not the case.

Despite the potential for reducing sample bias between profiles, quota sampling is still flawed in that it assumes individuals within each profile have a similar opinion.

In 1916-1932, the Literary Digest journal conducted voting polls that were "scientifically reliable".

25% of all voters were sampled

In the 1936 election - Landon (R-Kansas), Roosevelt (D):

prediction: 57% Landon results: 38% Roosevelt

At the same time, George Gallup asked 50,000 people and predicted the result within 1%. He also predicted what the Literary Digest would predict with a sample size of 3,000 people.

Gallup focused on eliminating bias by sampling in person and prescribing quotas for certain profiles.

eg. 7 white males over 40, 5 black males under 40, etc.

Stratified random sampling is similar to quota sampling, but an attempt is made to randomly select individuals within each profile.

**Independence**

Events \(E_1\) and \(E_2\) are independent iff

\(P(E_1 \cap E_2) = P(E_1) * P(E_2)\)

**Conditional Probability**

\(P(E_1 | E_2) = \frac{P(E_1 \cap E_2)}{P(E_2)}\)

if \(E_1\) and \(E_2\) are independent, then \(P(E_1 | E_2) = P(E_1)\)

Let the sample space be \(S = {2,...,12}\) (rolling 2 fair dice)

Let \(E\) - even sum, \(F\) - sum \(\geq\) 9

1 2 3 4 5 6 / < 1 2 3 4 5 6 7 2 3 4 5 6 7 8 3 4 5 6 7 8 9 4 5 6 7 8 9 10 5 6 7 8 9 10 11 6 7 8 9 10 11 12 \(P(E) = .5\)

\(P(F) = \frac{10}{36}\)

\(P(E|F) = \frac{P(E \cap F)}{P(F)} = \frac{4}{10}\)

- full house - AAABB - \(13 \left( \frac{4}{3} \right) 12 \left( \frac{4}{2} \right)\)
- choose suit for A, pick A cards, choose suit for B, pick B cards

- 2 pair - AABBC - \[\frac{13 \left( \frac{4}{2} \right) 12 \left( \frac{4}{2} \right) 11 \left( \frac{4}{1} \right)}{2}\]
- choose suit for A, pick A cards, choose suit for B, pick B cards, pick C cards, remove A-B permutation

Find the average number of inversions of all permutations in \(S_n\)

Let \(X: S_n \to \mathbb{R}\)

\(E(x) = \sum_{\sigma \in S_n} p(\sigma)X(\sigma)\)

Let $X_{i,j}=

\[ X = \sum X_{i,j} = \sum \begin{cases} 1 & \text{i,j are inverted} \\ 0 & \text{i,j are not inverted} \end{cases} \]

- fibonacci sequence
- linear recurrence
- general form
- explicity solution

- golden ratio

- 20% increase then decrease
- simple interest
- compound interest \(F = P(1 + \frac{R}{n})^{nt}\)
- APY vs APR
- geometric series \(P(\frac{c^N - 1}{c - 1}) = \sum_{n = 0}^{n - 1} P * c^n\)
- deferred annuities -
- installment (amortization) formula \(P = f*q * \frac{q^T - 1}{q - 1}\)

- rigid motion in \(\mathbb{R}^2, \mathbb{R}^3\)
- translation, rotation, reflection, glide
- proper/improper (reflection)
- regular polygons - dihedral groups
- border patterns

- koch snowflake, sierpinski gasket
- iteration leads to self similarity
- chaos game
- twisted fractals
- mandelbrot set - seed, attracted, period, escaping, asymptotic

- N-value, population
- sampling frame, convenience sampling, quota sampling, random sampling, stratified sampling
- sample bias
- capture recapture

- sample space
- probability function
- expected value
- linearity

- discrete vs continuous distributions
- fair vs loaded experiment (uniformity)
- independence
- conditional probability