Math basics#
Assorted math basics - functions, discrete math, proofs, identities, and complex numbers.
About this chapter
A grab bag of facts that the other math chapters use without stating. It starts with a few bounds, such as Stirling’s formula for \(n!\), and a short list of named functions (gamma, sigmoid, softmax). Then come one-line definitions from stochastic processes, abstract algebra and discrete math, and a list of proof techniques.
The last sections are reference material: log and trig identities, partial fractions, and complex numbers. Polar form \(z = |z| e^{i\theta}\) is the one idea worth slowing down for, since it is what makes multiplying complex numbers easy and it comes back in the Fourier transform.
Chapter outline: 9 sections
- MiscBounds that come up when counting and when analyzing algorithms.
- FunctionsNamed functions that show up in later chapters.
- Stochastic processesA stochastic process is a random variable evolving in time.
- Abstract algebra
- Discrete mathDefinitions for sets and propositional logic, then the standard ways to prove an implication p \to q: directly, by contradiction, by the contrapositive, or by induction.
- ProofsNotes on what proofs can and can't do: induction checks a formula you already have but doesn't explain it, and a non-existence proof has to rule out every case.
- IdentitiesLog rules, change of base, partial fractions and the angle-sum formulas for sine and cosine.
- Imaginary numbers1 interactiveEuler's formula turns a complex number into a magnitude times a phase.
- Spaces
Misc#
Bounds that come up when counting and when analyzing algorithms. Stirling’s formula says \(n!\) grows like \((n/e)^n\), so \(\log(n!)\) is \(O(n \log n)\).
\(\left( \frac{n}{k} \right) < \left( \frac{ne}{k} \right)^k\)
Stirling’s formula: \( n! ~= (\frac{n}{e})^n \)
corollary: log(n!) = 0(n log n)
gives us a bound on sorting
\(\left( \frac{n}{e} \right)^n < n!\)
\((1-x)^N \leq e^{-Nx}\)
Poisson pmf approximates binomial when N large, p small
Functions#
Named functions that show up in later chapters. The gamma function extends the factorial, \(\Gamma(n) = (n-1)!\), and the sigmoid and softmax turn real numbers into probabilities.
Gamma: \(\Gamma(n)=(n-1)!=\int_0^\infty x^{n-1}e^{-x}dx\)
Zeta: \(\zeta(x) = \sum_1^\infty \frac{1}{x^2} \)
Sigmoid (logistic): \(f(x) = \frac{1}{1+e^{-x}} = \frac{e^x}{e^x+1}\)
Softmax: \(f(x) = \frac{e^{x_i}}{\sum_i e^{x_i}}\)
spline: piecewise polynomial
Stochastic processes#
A stochastic process is a random variable evolving in time. The Markov property says the next value depends on the past only through the current value.
Stochastic - random process evolving with time
Markov: \(P(X_t=x\vert X_{t-1})=P(X_t=x\vert X_{t-1}...X_1)\)
Martingale: \(E[X_t]=X_{t-1}\)
Abstract algebra#
Group: set of elements endowed with operation satisfying 4 properties:
closed 2. identity 3. associative 4. inverses
Equivalence Relation;
reflexive 2. transitive 3. symmetric
Discrete math#
Definitions for sets and propositional logic, then the standard ways to prove an implication \(p \to q\): directly, by contradiction, by the contrapositive, or by induction.
Goldbach’s strong conjecture: Every even integer greater than 2 can be expressed as the sum of two primes (He considered one a prime).
Goldbach’s weak conjecture: All odd numbers greater than 7 are the sum of three primes.
Set - An unordered collection of items without replication
Proper subset - subset with cardinality less than the set
A U A = A Idempotent law
Disjoint: A and B = empty set
Partition: mutually disjoint, union fills space
powerset \(\mathcal{P}\)(A) = set of all subsets
Converse: \(q\to p\) (same as inverse: \(-p \to -q\))
\(p_1 \to p_2 \iff - p_1 \lor p_2 \)
The greatest common divisor of two integers a and b is the largest integer d such that d \(\vert\) a and d \(\vert\) b
Proof Techniques
Proof by Induction
Direct Proof
Proof by Contradiction - assume p \(\land\) -q, show contradiction
Proof by Contrapositive - show -q \(\to\) -p
Proofs#
Notes on what proofs can and can’t do: induction checks a formula you already have but doesn’t explain it, and a non-existence proof has to rule out every case. The subsection lists famous results and puzzles, with a worked pigeonhole argument.
induction
must already know formula
doesn’t give intuition
there are uncomputable functions e.g. Halting Problem, 3x+1 problem
non-existence proofs
must cover all possible scenarios, harder than existence
Interesting#
http://acko.net/blog/how-to-fold-a-julia-fractal/
Biggest primes, the twins
Infinite twin primes – guy working at subway
Different infinites – people driven crazy
Four-Color problem – Computer aided proof in 1977, basically checks cases
Bruower’s Fixed Point Theorem
Fermat’s Last Theorem – Pythagorean thm untrue for anything bigger than squared
Pf in 1995
Godel’s Thm: there are unprovable statements
Pigeonhole Principle
Claim: Consider a 10 foot by 10 foot square room. Let every point on the floor of the room be colored either red or blue. Then there exists somewhere on the floor two points of the same color that are exactly one foot apart.
Proof: Consider an equilateral triangle on the floor of the room with side lengths equal to one foot. As every point is either red or blue, two vertices of the triangle must have the same color, satisfying the claim.
There must be 2 people in London with the same amount of hairs on their head
Identities#
Log rules, change of base, partial fractions and the angle-sum formulas for sine and cosine. Change of base is why logs in different bases differ only by a constant factor.
\(e^{-2lnx}= \frac{1}{e^{2lnx}} = \frac{1}{e^{lnx}e^{lnx}} = \frac{1}{x^2}\)
\(\ln(xy) = \ln(x)+\ln(y)\)
\(\ln x * \ln y = \ln(x^{\ln y})\)
difference between log 10n and log 2n is always a constant (about 3.322)
\(\log_b (x) = \log_d (x) / \log_d (b)\)
partial fractions: \(\frac{3x+11}{(x-3)(x+2)} = \frac{A}{x-3} + \frac{B}{x+2}\)
\((ax+b)^k = \frac{A_1}{ax+b}+\frac{A_2}{(ax+b)^2}+...\)
\((ax^2+bx+c)^k = \frac{A_1x+B_1}{ax^2+bx+c}+...\)
\(\cos(a\pm b) = \cos(a)\cos(b)\mp \sin(a)\sin(b)\)
\(\sin(a \pm b) = \sin(a)\cos(b) \pm \sin(b)\cos(a)\)
Imaginary numbers#
Euler’s formula turns a complex number into a magnitude times a phase. In that form, multiplying two numbers multiplies their magnitudes and adds their angles.
complex conjugate of z=x+iy is \(z^*\) = x - iy
Euler’s formula \(e^{i \theta} = \cos (\theta) + i \sin (\theta)\)
sometimes we write imaginary numbers in polar form: \(z = \cblue{\vert z\vert} \corange{e^{i \theta}}\)
magnitude times phase
makes multiplication / division simpler
absolute value / modules of imaginary numbers: \(\vert a + ib\vert = \sqrt{a^2 + b^2}\)
Spaces#
hilbert space - requires an inner product (useful in analyzing kernels) - more general than an inner product space
reproducing kernel hilbert space with extra property
Key ideas
Stirling’s formula is \(n!\approx (n/e)^n\), which gives \(\log(n!) = O(n \log n)\), the bound behind sorting.
The Poisson pmf approximates the binomial when \(N\) is large and \(p\) is small.
An implication \(p \to q\) can be proved directly, by contradiction, by the contrapositive \(\neg q \to \neg p\), or by induction.
Logs in different bases differ by a constant factor, \(\log_b x = \log_d x / \log_d b\).
In polar form \(z = |z| e^{i\theta}\), multiplying complex numbers multiplies magnitudes and adds angles.