3.9. math basics#

3.9.1. misc#

  • \(\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

3.9.2. functions#

  • 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

3.9.3. stochastic processes#

  • Stochastic - random process evolving with time

  • Markov: \(P(X_t=x\|X_{t-1})=P(X_t=x\|X_{t-1}...X_1)\)

  • Martingale: \(E[X_t]=X_{t-1}\)

3.9.4. abstract algebra#

  • Group: set of elements endowed with operation satisfying 4 properties:

  1. closed 2. identity 3. associative 4. inverses

  • Equivalence Relation;

  1. reflexive 2. transitive 3. symmetric

3.9.5. 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 \(\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 \(\|\) a and d \(\|\) b

  • Proof Techniques

    • Proof by Induction

    • Direct Proof

    • Proof by Contradiction - assume p \(\land\) -q, show contradiction

    • Proof by Contrapositive - show -q \(\to\) -p

3.9.6. identities#

  • \(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)\)

3.9.7. imaginary numbers#

  • 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 = |z| e^{i \theta}\)

    • makes multiplication / division simpler

  • absolute value / modules of imaginary numbers: \(|a + ib| = \sqrt{a^2 + b^2}\)

3.9.8. 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