Math Basics view markdown
misc
- (nk)<(nek)k
- Stirling’s formula: n! =(ne)n
- corollary: log(n!) = 0(n log n)
- gives us a bound on sorting
- (ne)n<n!
- (1−x)N≤e−Nx
- Poisson pmf approximates binomial when N large, p small
functions
- Gamma: Γ(n)=(n−1)!=∫∞0xn−1e−xdx
- Zeta: ζ(x)=∑∞11x2
- Sigmoid (logistic): f(x)=11+e−x=exex+1
- Softmax: f(x)=exi∑iexi
- spline: piecewise polynomial
stochastic processes
- Stochastic - random process evolving with time
- Markov: P(Xt=x|Xt−1)=P(Xt=x|Xt−1…X1)
- Martingale: E[Xt]=Xt−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
- 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 P(A) = set of all subsets
- Converse: q→p (same as inverse: −p→−q)
- p1→p2⟺−p1∨p2
- The greatest common divisor of two integers a and b is the largest integer d such that d | a and d | b
- Proof Techniques
- Proof by Induction
- Direct Proof
- Proof by Contradiction - assume p ∧ -q, show contradiction
- Proof by Contrapositive - show -q → -p
identities
- e−2lnx=1e2lnx=1elnxelnx=1x2
- ln(xy)=ln(x)+ln(y)
- lnx∗lny=ln(xlny)
- difference between log 10n and log 2n is always a constant (about 3.322)
- logb(x)=logd(x)/logd(b)
- partial fractions: 3x+11(x−3)(x+2)=Ax−3+Bx+2
- (ax+b)k=A1ax+b+A2(ax+b)2+…
- (ax2+bx+c)k=A1x+B1ax2+bx+c+…
- cos(a±b)=cos(a)cos(b)∓sin(a)sin(b)
- sin(a±b)=sin(a)cos(b)±sin(b)cos(a)
imaginary numbers
- complex conjugate of z=x+iy is z∗ = x - iy
- Euler’s formula eiθ=cos(θ)+isin(θ)
-
sometimes we write imaginary numbers in polar form: $z = z e^{i \theta}$ - makes multiplication / division simpler
-
absolute value / modules of imaginary numbers: $ a + ib = \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