# 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