\documentclass{article}
\title{Isabelle Hurbain's Exam Formular}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{fullpage}
\usepackage{rotating}
\usepackage{graphicx}
\newcommand\Esp{\mathbf E}
\newcommand\Var{\text{Var}}
\begin{document}
\maketitle
Most recent version and some context available on:

http://www.pasithee.fr/articles/examformular.html
\section{Logs and stuff}
$$\log(xy) = \log(x) + \log(y)$$
$$\log(x^p) = p \log(x)$$
$$\log(1/x) = -\log(x)$$
$$\log_b(x) = \frac{\log_k(x)}{log_k(b)}$$
$$x^{i+j} = x^i \cdot x^j$$
$$(x^i)^j = x^{ij}$$
$$b^x = e^{x\ln b}$$
$$e^x = \sum_{n=0}^\infty \frac{x^n}{n!} = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots$$
\section{Binomial coefficients}
$$\binom n k = \frac{n!}{k!(n-k)!}$$
$$\binom n {k_1, k_2, ..., k_m} = \frac{n!}{k_1!k_2!...k_m!} \text{ (where} \sum_{i=1}^m{k_i} = n)$$
$$(x+y)^n = \sum_{k=0}^n \binom n k x^{n-k}y^k$$
$$\binom n k = \binom{n-1}{k-1} + \binom{n-1}{k}$$
$$\binom n k = \frac n k \binom{n-1}{k-1}$$
$$\sum_{k=0}^n \binom n k = 2^n$$
$$\sum_{k=0}^n k\binom n k = n2^{n-1}$$
$$\left(\frac n k\right)^k \leq \binom n k \leq \frac{n^k}{k!} \leq \left(\frac{ne}{k}\right)^k$$
$$\binom{2n}{n} \stackrel{Stirling}{\sim} \frac{4^n}{\sqrt{\pi n}}$$
$$\binom n 2 = \frac{n(n-1)}{2}$$
$$\binom n 3 = \frac{n(n-1)(n-2)}{6}$$
$$\binom n 4 = \frac{n(n-1)(n-2)(n-3)}{24}$$
$$\binom n 5 = \frac{n(n-1)(n-2)(n-3)(n-4)}{120}$$
\section{Distributions}
\subsection{Binomial distribution}
Number of successes in a sequence of $n$ independent yes/no experiments, each of which yields success with probability $p$.
$$\Pr[X = k] = \binom n k p^k (1-p)^{n-k}$$
$$\Esp[X] = np$$
$$\Var[X] = np(1-p)$$
\subsection{Geometric distribution}
Probability distribution of the number $X$ of Bernoulli trials needed to get one success.

$$\Pr[X=k] = (1-p)^{k-1}p$$
$$\Esp[X] = \frac 1 p$$
$$\Var[X] = \frac{1-p}{p^2}$$
\section{Usual limits}
$$\lim_{x\rightarrow +\infty} \left(1+\frac k x\right)^{mx} = e^{mk}$$
$$\lim_{x\rightarrow +\infty} \left(1-\frac 1 x\right)^{x} = \frac 1 e$$
$$\lim_{x\rightarrow +\infty} x^\alpha = \begin{cases}+\infty,& \alpha > 0\\0,&\alpha<0\end{cases}$$
\section{Approximations and bounds}
\begin{itemize}
\item $\forall x \in \mathbb R, 1-x \leq e^{-x}$
\item Around 0, $1+x \sim e^x$
\item $\ln n \leq H_n \leq \ln n+1$
\item $\binom n k \leq 2^n$
\item $\binom n k \leq \frac{n^k}{k!}$
\item $\left(\frac n k\right)^k \leq \binom n k \leq \left(\frac{ne}{k}\right)^k$
\item $n! \sim \sqrt{2\pi n}\left(\frac n e\right)^n$
\item For $0 \leq x \leq 1$, $(1-x)^n \geq 1 - xn$
\item For $0 \leq x \leq 1/2, (1 - x) \geq e^{-x-x^2}$
\end{itemize}
\section{Numerical values}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$n$ &1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
\hline
$n!$ & 1 & 2 & 6 & 24 & 120 & 720 & 5040 & 40320 & 362880 \\
\hline
$n^3$ & 1 & 8 & 27 & 64 & 125 & 216 & 343 & 512 & 729 \\
\hline
$n^4$ & 1 & 16 & 81 & 256 & 625 & 1296 & 2401 & 4096 & 6561 \\
\hline
$2^n$ & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 512 \\
\hline 
$e^x$ & 2.718 & 7.389 & 20.086 & 54.698 & 148.413 & 403.428 & 1096.63 & 2980.96 & 8103.08 \\
\hline
$\ln x$ & 0 & 0.693 & 1.098 & 1.386 & 1.609 & 1.791 & 1.946 & 2.079 & 2.197\\
\hline
$\log_2 x$ & 0 & 1 & 1.584 & 2 & 2.321 & 2.585 & 2.807 & 3 & 2.170 \\
\hline
$\sqrt x$ & 1 & 1.414 & 1.732 & 2 & 2.236 & 2.449 & 2.646 & 2.828 & 3 \\
\hline
\end{tabular}

\section{Series}
$$\sum_{k=1}^m k = \frac{m(m+1)}{2}$$
$$\sum_{k=1}^n \frac 1 k = H_n$$
$$\sum_{k=1}^\infty \frac{1}{k^2} = \frac{\pi^2}{6}$$
$$\sum_{k=1}^n z^k = z \frac{1-z^n}{1-z}$$
$$\sum_{k=1}^\infty z^k = \frac{z}{1-z}$$
$$\sum_{k=1}^\infty kz^k = \frac{z}{(1-z)^2}$$
$$\sum_{k=0}^\infty \frac{z^k}{k!} = e^z$$
$$\sum_{k=0}^\infty \binom n k = 2^n$$
$$\sum_{k=0}^n k\binom n k = n2^{n-1}$$

\section{Randomized algorithms tools\protect\footnote{Formulation of theorems from Pr A. Steger awesome Randomized Algorithm Lecture notes, version of September 21st 2011. Typos are my own ;)}}
\subsection{Markov}
Let $X$ be a non-negative random variable. For all $t>0$, we have
$$\Pr[X \geq t] \leq \frac{\Esp[X]} t$$
\subsection{Chebyshev}
Let $X$ be a random variable. For all $t > 0$, we have
$$\Pr[|X - \Esp[X] \geq t] \leq \frac{\Var[X]}{t^2}$$
\subsection{First and second moment method}
Let $(X_n)_{n \in \mathbb N}$ be a sequence of random variables which take non-negative integer values. Then
$$\Esp[X_n] = o(1) \text{ implies } \Pr[X_n = 0] = 1 - o(1)$$

Let $(X_n)_{n \in \mathbb N}$ be a sequence of random variables. Then
$$\Esp[X_n] \neq 0 \text{ (for $n$ large enough) and } \Var[X_n] = o(\Esp[X_n]^2) \text{ implies } \Pr[X_n = 0] = o(1)$$

\subsection{"Weak" Chernoff}
Let $X_1, ..., X_n$ be independent (or, weaker, negatively associated) Bernouilli-distributed variables with $\Pr[X_i = 1] = p_i$ and $\Pr[X_i = 0] = 1 - p_i$. Then the following inequalities hold for $X = \sum_{i = 1}^n X_i$ and $\mu = \Esp[X] = \sum_{i=1}^n p_i$:
$$\Pr[X \geq (1+\delta)\mu] \leq e^{-\mu \delta^2/3} \text{ for all } 0 < \delta \leq 1$$
$$\Pr[X \leq (1-\delta)\mu] \leq e^{-\mu \delta^2/2} \text{ for all } 0 < \delta \leq 1$$
$$\Pr[|X - \mu| \geq \delta \mu] \leq 2e^{-\mu \delta^2/3} \text{ for all } 0 < \delta \leq 1$$$$\Pr[X \geq t] \leq 2^{-t} \text{ for } t \geq 2e\mu$$

\subsection{Azuma}
Let $(\Omega, \Pr)$ be the product of $N$ discrete probability spaces $(\Omega_1, \Pr_1), ..., (\Omega, \Pr_N)$, and let $X : \Omega \rightarrow \mathbb R$ be a random variable with the property that the effect of the $i$-th coordinate is at most $c_i$. Then for all $t\geq 0$ we have
$$\Pr[X \geq \Esp[X] + t] \leq e^{-\frac{t^2}{2\sum_{i=1}^N c_i^2}}$$
$$\Pr[X \leq \Esp[X] - t] \leq e^{-\frac{t^2}{2\sum_{i=1}^N c_i^2}}$$

\subsection{Janson}
Let $(\Omega, \Pr)$ be the product of $N$ discrete probability spaces $(\Omega_1, \Pr_1), ..., (\Omega, \Pr_N)$ and let $X_1, ..., X_m$ be indicator variables and $I_1, ..., I_m$ sets of coordinates such that for all $1 \leq i \leq m$ we have: $X_i$ depends only on coordinates in $I_i$. Furthermore, let $X := \sum_{i=1}^mX_i$. Then we have, with
$$\lambda := \Esp[X] = \sum_{i=1}^m \Pr[X_i = 1]$$
$$\Delta := \sum_{i\neq j, I_1 \cap I_j \neq \emptyset} \Pr[X_i = 1 \wedge X_j = 1]$$
for all $0 \leq t \leq \Esp[X]$ that
$$\Pr[X \leq \Esp[X] - t] \leq e^{\frac{-t^2}{2(\lambda + \Delta)}}$$
In particular:
$$\Pr[X = 0] \leq e^{-\frac{\lambda^2}{2\lambda +\delta)}} \leq e^{-\min\{\lambda, \lambda^2/\Delta\}/4}$$

\begin{sidewaystable}
\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\
\hline
\hline
1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\
\hline
2 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & 26 & 28 & 30 & 32 & 34 & 36 & 38 & 40 \\
\hline
3 & 3 & 6 & 9 & 12 & 15 & 18 & 21 & 24 & 27 & 30 & 33 & 36 & 39 & 42 & 45 & 48 & 51 & 54 & 57 & 60 \\
\hline
4 & 4 & 8 & 12 & 16 & 20 & 24 & 28 & 32 & 36 & 40 & 44 & 48 & 52 & 56 & 60 & 64 & 68 & 72 & 76 & 80 \\
\hline
5 & 5 & 10 & 15 & 20 & 25 & 30 & 35 & 40 & 45 & 50 & 55 & 60 & 65 & 70 & 75 & 80 & 85 & 90 & 95 & 100 \\
\hline
6 & 6 & 12 & 18 & 24 & 30 & 36 & 42 & 48 & 54 & 60 & 66 & 72 & 78 & 84 & 90 & 96 & 102 & 108 & 114 & 120 \\
\hline
7 & 7 & 14 & 21 & 28 & 35 & 42 & 49 & 56 & 63 & 70 & 77 & 84 & 91 & 98 & 105 & 112 & 119 & 126 & 133 & 140 \\
\hline
8 & 8 & 16 & 24 & 32 & 40 & 48 & 56 & 64 & 72 & 80 & 88 & 96 & 104 & 112 & 120 & 128 & 136 & 144 & 152 & 160 \\
\hline
9 & 9 & 18 & 27 & 36 & 45 & 54 & 63 & 72 & 81 & 90 & 99 & 108 & 117 & 126 & 135 & 144 & 153 & 162 & 171 & 180 \\
\hline
10 & 10 & 20 & 30 & 40 & 50 & 60 & 70 & 80 & 90 & 100 & 110 & 120 & 130 & 140 & 150 & 160 & 170 & 180 & 190 & 200 \\
\hline
11 & 11 & 22 & 33 & 44 & 55 & 66 & 77 & 88 & 99 & 110 & 121 & 132 & 143 & 154 & 165 & 176 & 187 & 198 & 209 & 220 \\
\hline
12 & 12 & 24 & 36 & 48 & 60 & 72 & 84 & 96 & 108 & 120 & 132 & 144 & 156 & 168 & 180 & 192 & 204 & 216 & 228 & 240 \\
\hline
13 & 13 & 26 & 39 & 52 & 65 & 78 & 91 & 104 & 117 & 130 & 143 & 156 & 169 & 182 & 195 & 208 & 221 & 234 & 247 & 260 \\
\hline
14 & 14 & 28 & 42 & 56 & 70 & 84 & 98 & 112 & 126 & 140 & 154 & 168 & 182 & 196 & 210 & 224 & 238 & 252 & 266 & 280 \\
\hline
15 & 15 & 30 & 45 & 60 & 75 & 90 & 105 & 120 & 135 & 150 & 165 & 180 & 195 & 210 & 225 & 240 & 255 & 270 & 285 & 300 \\
\hline
16 & 16 & 32 & 48 & 64 & 80 & 96 & 112 & 128 & 144 & 160 & 176 & 192 & 208 & 224 & 240 & 256 & 272 & 288 & 304 & 320 \\
\hline
17 & 17 & 34 & 51 & 68 & 85 & 102 & 119 & 136 & 153 & 170 & 187 & 204 & 221 & 238 & 255 & 272 & 289 & 306 & 323 & 340 \\
\hline
18 & 18 & 36 & 54 & 72 & 90 & 108 & 126 & 144 & 162 & 180 & 198 & 216 & 234 & 252 & 270 & 288 & 306 & 324 & 342 & 360 \\
\hline
19 & 19 & 38 & 57 & 76 & 95 & 114 & 133 & 152 & 171 & 190 & 209 & 228 & 247 & 266 & 285 & 304 & 323 & 342 & 361 & 380 \\
\hline
20 & 20 & 40 & 60 & 80 & 100 & 120 & 140 & 160 & 180 & 200 & 220 & 240 & 260 & 280 & 300 & 320 & 340 & 360 & 380 & 400 \\
\hline
\end{tabular}
\end{sidewaystable}
\end{document}