MA279 - Modern Mathematics in Society

# Voting

ballot - ordering of candidates

method - way of counting ballots

criterion - requirements on the result of a method

## Criteria

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

## Methods

### Plurality Method

• the candidate with the most 1st place votes wins
• fails condorcet criterion
1. 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

### Plurality Method with instant drop off

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

### Borda count method

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

### Pairwise compare method (Copeland's method)

• 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
1. 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 > C 16 A > D 13 A > E 18 B > C 10 B > D 11 B > E 14 C > D 12 D > E 18 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 > D 13 A > E 18 B > D 11 B > E 14 D > E 18

B wins

A lost even though votes were changed in this candidate's favor

## Counting Methods and Criterion Violations

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

## Ranking and Extended Voting Methods

### Recursive

• use voting method, remove winner and repeat process

### Extended Methods

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

## Weighted Voting

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]

### Banzhaf Power Index

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)

1. [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}$

# Division

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.

## Continuous Division

### Divider-Chooser

• 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

### Lone Divider

• 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

1. 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$$
2. 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$$

### Lone Chooser

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

### Last Diminisher

1. Player 1 takes a fair share of the booty and passes it to Player 2.
2. Player 2 either cuts down the share to what he thinks is fair, or doesn't change it and passes it down
3. 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.

## Discrete Division

### Markers

1. Put all goods in a line and have each player place N-1 markers to divide the goods into fair shares. ./graphic
2. Give the first share to Player A ./graphic
3. 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

### Sealed Bids

• 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

# Apportionment

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

## Hamilton's Method

1. Find the fair share for each state ($$q_i$$) and give them the floor
2. Assign the remaining seats to the states with the largest leftover fraction ($$q_i - \lfloor q_i \rfloor$$)
1. 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
Give 4 remaining seats to $$A, D, F, B$$

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

## Jefferson's Method

• 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$$
1. 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
2 extra seats for $$B$$ violates quota criterion

• 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$$
1. A B C D E F $$\sum$$
$$\lceil q_i \rceil$$ 33 137 4 42 14 20 250

## Webster's Method

• 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$
1. 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

## Huntington-Hill

• 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

## Apportionment Definition

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$$)

## Apportionment methods

### Hamilton's Method

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

1. 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
So remaining for seats are assigned to A,B,D,F

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

### Webster's Method

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$$

### Hunting-Hill Method

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$$

# Graphs

## Euler Paths

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

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 Graphs

bipartite - elements can be grouped into two non touching groups

## Traveling Salesman

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 Graphs

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 vs NP

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

## Trees

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

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

All trees must have at least one leaf

### Kruskal's Algorithm

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

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

Kruskal's Algorithm always finds an optimal solution.

### Prüfer Sequence

Steps to create Prüfer Sequence from tree

1. find leaf with smallest index
2. delete and record index that leaf was attached to

sequence: {4,4}

sequence {2,3}

Steps to recreate graph from Prüfer sequence

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

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

1. S = {3}

L = {2,3,4}

edge 1-3

2. S = {}

L = {3,4}

edge 2-3

3. edge 3-4

Spanning trees in $$K_N$$: $$n^{n-2}$$

# Exponential Growth

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$$

1. 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$$

2. 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}

## Fibonacci Sequence

#+begin definition Fibonacci sequence $$F_N = F_{N-1} + F_{N-2}$$

$$F_1 = 1, F_2 = 1$$ - seed numbers

#+enddefinition

## Golden Ratio

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$$

## Solving Higher Order Polynomials

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
1. 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$$

2. 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*} an = 2n (b1,0 + b1,1n) & + (-2)n (b2,0 + b2,1n) \end{align*}$$$F_1(n) = 1$$ $$t = 0, m = 1, s = 1$$ $$F_2(n) = 2^n$$ $$t = 0, m = 0, s = 2$$ # Ginomons # Mathematics of Money 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)$$ ## Credit Cards • 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}$$ ## Annuities 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 # Motions 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$$ ## Rotation 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)$ ## Finding a motion for some input and output If $$\overrightarrow{v}$$ and $$(A,B)\overrightarrow{v}$$ are given, there is a line of possible points for the center of rotation ## Proper motions 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 groups 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 ## Frieze patterns (Border Patterns) 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 # Fractals ## Sierpinsky gasket $$\text{Area} = \frac{3}{4}^n$$ $$\text{Perimeter} = \frac{3}{2}^n$$ ## Snowflake$Area = ∑

pascal's triangle modulo 6

## Mandelbrot Set

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$$

$a0 = s where $$s$$ is called the seed Mandelbrot sequences can either be escaping, attracting, or periodic, depending on their behavior at infinity. 1. Periodic Let $$s = -1$$  $$a_1$$ -1 $$a_2$$ 0 $$a_3$$ -1 ... ... 2. Escaping Let $$s = 1$$  $$a_1$$ 1 $$a_2$$ 2 $$a_3$$ 5 ... ... 3. 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. ## Game of life ### Rules • 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 ## Fractal Dimension 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$$ 1. Assume a straight line made of 4 equal line segments. We know $$N = 4$$, $$S = 4$$, so $$D = 1$$ 2. Assume a square made of 16 equal squares We know $$N = 16$$, $$S = 4$$, so $$D = 2$$ 3. Assume a cube made of 64 equal cubes. We know $$N = 64$$, $$S = 4$$ so $$D = 3$$ 4. 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)}$ 5. 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}}$$ ## Collatz conjecture 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. # Sampling 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 ## Capture-Recapture Method Used to determine total populations. Assumes population exhibits Brownian (random) motion. 1. Capture n indivudals from the population 2. Tag each individual and release them again 3. Allow the tagged individuals to mix with the population 4. Capture m individuals from the population. 5. If there are t tagged individuals in the m captured individuals, the population is approximately $N = \frac{n}{\frac{t}{m}}$ ## Random Sampling 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 Quota Sampling 1. Using prior knowledge about the sampling population, create profiles based on characteristics of individuals (eg. white males, asian females, etc.) 2. Determine the percentage of individuals that make up each profile 3. 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. 1. 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 Stratified random sampling is similar to quota sampling, but an attempt is made to randomly select individuals within each profile. # Statistics and Probability 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)$$ 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}$$ ## Poker Hands • 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 ## Permutations 1. 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$Xi,j =

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

# Final Review

## Exponential Growth

• fibonacci sequence
• linear recurrence
• general form
• explicity solution
• golden ratio

## Mathematics of Money

• 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}$$

## Symmetries

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

## Fractals

• iteration leads to self similarity
• chaos game
• twisted fractals
• mandelbrot set - seed, attracted, period, escaping, asymptotic

## Censuses and Surveys

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

## Probability

• sample space
• probability function
• expected value
• linearity
• discrete vs continuous distributions
• fair vs loaded experiment (uniformity)
• independence
• conditional probability