\documentclass[10pt,english,landscape]{article} \usepackage{multicol} \usepackage{calc} \usepackage[landscape]{geometry} \usepackage{color,graphicx,overpic} \usepackage[T1]{fontenc} \usepackage[bitstream-charter]{mathdesign} \usepackage[utf8]{inputenc} \usepackage{url} \usepackage{amsfonts} \usepackage{amsmath} \usepackage{array,booktabs} \usepackage{textcomp} \usepackage[usenames,dvipsnames,table]{xcolor} \usepackage[most]{tcolorbox} \usepackage{tabularx} \usepackage{multirow} \usepackage{colortbl} \usepackage{tikz} \usepackage{environ} \usepackage{booktabs} \usepackage{tabularx} \usepackage{blindtext} \usepackage{anyfontsize} \usepackage{wrapfig} \usepackage{rotating} \usepackage{changepage} \usepackage{enumitem} %\usepackage{showframe} \usetikzlibrary{calc} \pgfdeclarelayer{background} \pgfdeclarelayer{foreground} \pgfsetlayers{background,main,foreground} \geometry{top=-0.5cm,left=1cm,right=1cm,bottom=1cm} \def\tabularxcolumn#1{m{#1}} %centre vertically \newcolumntype{s}{>{\hsize=2\hsize}X} \pagestyle{empty} % Turn off header and footer % Redefine section commands to use less space \makeatletter \renewcommand{\section}{\@startsection{section}{1}{0mm}% {-1ex plus -.5ex minus -.2ex}% {0.5ex plus .2ex}%x {\normalfont\large\bfseries}} \renewcommand{\subsection}{\@startsection{subsection}{2}{0mm}% {-1explus -.5ex minus -.2ex}% {0.5ex plus .2ex}% {\normalfont\normalsize\bfseries}} \renewcommand{\subsubsection}{\@startsection{subsubsection}{3}{0mm}% {-1ex plus -.5ex minus -.2ex}% {1ex plus .2ex}% {\normalfont\small\bfseries}} \makeatother \renewcommand{\baselinestretch}{1.0} \setcounter{secnumdepth}{0} % Don't print section numbers \setlength{\parindent}{0pt} \setlength{\parskip}{0pt plus 0.5ex} \definecolor{TableHead}{gray}{0.25} \definecolor{TableRow}{gray}{0.885} \NewEnviron{defns}[1]{ % \begin{center} \smallskip \begin{tikzpicture} \rowcolors{1}{}{TableRow} \centering \node (tbl) [inner sep=0pt] { \begin{tabular}{m{2.28cm}m{5.26cm}} \rowcolor{TableHead} \multicolumn{2}{l}{\normalsize\textbf{\color{white}{#1}}}\parbox{0pt}{\rule{0pt}{0.3ex+\baselineskip}}\\ \BODY \arrayrulecolor{TableHead}\specialrule{.17em}{0em}{.2em} \end{tabular}}; \begin{pgfonlayer}{background} \draw[rounded corners=2pt,top color=TableHead,bottom color=TableHead, draw=white] ($(tbl.north west)-(0,-0.05)$) rectangle ($(tbl.north east)-(0.0,0.15)$); \draw[rounded corners=2pt,top color=TableHead,bottom color=TableHead, draw=white] ($(tbl.south west)-(0.0,-0.11)$) rectangle ($(tbl.south east)-(-0.0,-0.02)$); \end{pgfonlayer} \end{tikzpicture} % \end{center} } \NewEnviron{defns1}[1]{ % \begin{center} \smallskip \begin{tikzpicture} \rowcolors{1}{}{TableRow} \centering \node (tbl) [inner sep=0pt] { \begin{tabular}{m{7.8cm}} \rowcolor{TableHead} \multicolumn{1}{l}{\normalsize\textbf{\color{white}{#1}}}\parbox{0pt}{\rule{0pt}{0.3ex+\baselineskip}}\\ \BODY \arrayrulecolor{TableHead}\specialrule{.17em}{0em}{.2em} \end{tabular}}; \begin{pgfonlayer}{background} \draw[rounded corners=2pt,top color=TableHead,bottom color=TableHead, draw=white] ($(tbl.north west)-(0,-0.05)$) rectangle ($(tbl.north east)-(0.0,0.15)$); \draw[rounded corners=2pt,top color=TableHead,bottom color=TableHead, draw=white] ($(tbl.south west)-(0.0,-0.11)$) rectangle ($(tbl.south east)-(-0.0,-0.02)$); \end{pgfonlayer} \end{tikzpicture} % \end{center} } \def\checkmark{\tikz[green]\fill[scale=0.4](0,.35) -- (.25,0) -- (1,.7) -- (.25,.15) -- cycle;} \newcommand{\Cross}{$\mathbin{\tikz [x=1.4ex,y=1.4ex,line width=.2ex, red] \draw (0,0) -- (1,1) (0,1) -- (1,0);}$}% \newenvironment{tight_enumerate}{ \begin{enumerate}[nosep, partopsep=0pt] \setlength{\itemsep}{0pt} \setlength{\parskip}{0pt} }{\end{enumerate}} \setlist{nolistsep} \newcolumntype{L}[1]{>{\raggedright\let\newline\\\arraybackslash\hspace{0pt}}m{#1}} \newcommand{\rom}[1]{\uppercase\expandafter{\romannumeral #1\relax}} \begin{document} \raggedright\ \begin{center} \Large{\underline{PwA Cheatsheet}} \end{center} \footnotesize \centering\section{Common Distributions} \begin{tabular}{|L{2.94cm}|l|L{2.9cm}|l|l|} \hline \multicolumn{5}{|c|}{\textbf{Discrete}} \\ \hline \textbf{Name} & \textbf{pmf} & \textbf{cdf} & \textbf{mean} & \textbf{variance}\\ \hline Binomial(n,p) & $ \binom nk p^k (1-p)^{n-k} $ & $F(k;n,p) = \Pr(X \le k) = \sum_{i=0}^{\lfloor k \rfloor} {n\choose i}p^i(1-p)^{n-i}$ & $np$ & $np(1-p)$ \\ \hline Neg. Binomial(r,p) & $ \binom{i-1}{r-1} p^r (1-p)^{i-r} $ & - & $\frac{r}{p}$ & $r\frac{1-p}{p^2}$ \\ \hline Bernoulli(p) & {$\begin{cases} q=(1-p) & \text{for }k=0 \\ p & \text{for }k=1 \end{cases}$} & {$ \begin{cases} 0 & \text{for }k<0 \\ 1 - p & \text{for }0\leq k<1 \\ 1 & \text{for }k\geq 1 \end{cases}$} &$p$ & $p(1-p)$ \\ \hline Uniform(a,b) & $ \frac{1}{n}, n=b-a+1 $ & $ \frac{\lfloor k \rfloor -a+1}{n} $ & $ \frac{a+b}{2} $ & $ \frac{(b-a+1)^2-1}{12}$\\ \hline Geometric(p) & $ p(1-p)^{i-1} $ & $ 1-(1-p)^i $ & $\frac{1}{p}$ & $\frac{1-p}{p^2}$ \\ \hline Hypergeometric(N,K,n) {\fontsize{6}{6}\selectfont "k successes $\subset$ N, K suc $\in$ N"} & ${{{K \choose k} {{N-K} \choose {n-k}}}\over {N \choose n}}$ & - & $n {K\over N}$ & $n{K\over N}{(N-K)\over N}{N-n\over N-1}$ \\ \hline Poisson($\lambda$) & $ \frac{\lambda^k e^{-\lambda}}{k!} $ & $e^{-\lambda} \sum_{i=0}^{\lfloor k\rfloor} \frac{\lambda^i}{i!}$ & $\lambda$ & $\lambda$ \\ \hline \end{tabular} \begin{tabular}{|l|l|l|l|l|} \hline \multicolumn{5}{|c|}{\textbf{Continuous}} \\ \hline \textbf{Name} & \textbf{pdf} & \textbf{cdf} & \textbf{mean} & \textbf{variance}\\ \hline Uniform(a,b) & $ \begin{cases} \frac{1}{b - a} & \text{for } x \in [a,b] \\ 0 & \text{otherwise}\end{cases}$ & $ \begin{cases} 0 & \text{for } x < a \\ \frac{x-a}{b-a} & \text{for } x \in [a,b) \\ 1 & \text{for } x \ge b \end{cases} $& $\frac{a+b}{2}$ & $\frac{(b-a)^2}{12}$ \\ \hline Normal$(\mu,\omega^2)$ & $ \frac{1}{\sqrt{2\sigma^2\pi}}\, e^{-\frac{(x - \mu)^2}{2 \sigma^2}}$ & $ \frac12\left[1 + \operatorname{erf}\left( \frac{x-\mu}{\sigma\sqrt{2}}\right)\right] $ & $\mu$ & $ \sigma^2$ \\ \hline Exponential($\lambda$) & $ \lambda e^{-\lambda x} $ & $ 1 - e^{-\lambda x} $ & $1 / \lambda$ & $1 / \lambda^2$ \\ \hline \multicolumn{5}{|c|}{\textbf{Hazard/Failure Rate Functions}} \\ \hline \textbf{Survival} & \textbf{Hazard} & \textbf{Distribution} & \textbf{Rate} & \textbf{Book}\\ \hline $\bar{F}(t) = 1- F(t)$ & $\lambda (t) = \frac{f(t)}{\bar{F}(t)} $ & $F(t) = 1-exp \{- \int_{0}^{t} \lambda(t)dt \}$ & $\lambda$ & p217 \\ \hline \end{tabular} \begin{multicols}{3} \begin{defns}{Events} Sample Space & $ S=\{all \: possible \: outcomes\} $ \\ Event & $ E \subset S $ \\ Union (either or both) & $ E \cup F $ \\ Intersection (both) & $ E \cap F $ or $EF$ \\ Complement & $ E^C = S \backslash E \Rightarrow P(E^C) = 1-P(E)$ \\ Inclusion-Exclusion & $ \hookrightarrow P(A \cup B) = P(A) + P(B) - P(A \cap B)$ \\ DeMorgan's Law & {\begin{tight_enumerate} \item $(E_1 \cup \ldots \cup E_n)^C = E_1^C \cap \ldots \cap E_n^C$ \item $(E_1 \cap \ldots \cap E_n)^C = E_1^C \cup \ldots \cup E_n^C$ \end{tight_enumerate} \vspace*{-\baselineskip}\leavevmode }\\ Axioms & {\begin{tight_enumerate} \item $ 0 \leq P(E) \leq 1 $ \item $ P(S) \eq 1 $ \item For mutually excl. events $A_i, i \geq 1$: $ P(\cup_{i=1}^{\infty} A_i ) = \sum_{i=1}^{\infty} P(A_i) $ \end{tight_enumerate} \vspace*{-\baselineskip}\leavevmode }\\ {\fontsize{6}{6}\selectfont Finite S, Equal Probability for all point sets:} & $ P(A) = \mid A \mid \div \mid S \mid$ \\ Odds of Event & $\alpha = \frac{P(A)}{P(A^C)} = \frac{P(A)}{1-P(A)}$\\ \end{defns} \begin{defns}{Conditional Probability and Independence \rom{1}} Conditional Probability & $ P(F \mid E) = \frac{P(F \cap E )}{P(E)} $ \\ Independence if & $ P(F \cap E ) = P(F)P(E)$ \\ Multiplication Rule & $ P(E_1 E_2 \cdots E_n) = P(E_1)P(E_2 \mid E_1) \cdots P(E_n \mid E_1 \cdots E_{n-1}) $ \\ Bayes Formula (simple) & $ P(A\mid B) = \frac{P(B \mid A)\, P(A)}{P(B)}\cdot \, $ \\ Bayes Formula (full) & $ P(A_i\mid B) = \frac{P(B\mid A_i)\,P(A_i)}{\sum_j P(B\mid A_j)\,P(A_j)}\cdot $ \\\hline Conditional pmf (discrete) & $ p_{X\mid Y}(x\mid y) = \frac{p(x,y)}{p_Y(y)} $ \\ Conditional pdf (discrete) & $ F_{X\mid Y}(x\mid y) = \sum_{a \leq x} p_{X\mid Y}(a\mid y) $ \\ Conditional Density (continuous) & $ f_{X \mid Y}(x \mid y) = \frac{f(x,y)}{f_Y(y)} $ \\ Conditional Probabilities (continuous) & $ P\{ X \in A \mid Y = y \} = \int_A f_{X \mid Y}(x \mid y) dx $ \\ \end{defns} \begin{defns}{Random Variables (Discrete)} Distribution Function & $ F(x) = P \{ X \leq x\} $ \\ Probability Mass Function & $ p(x) = P{X = x} $ \\ Joint Probability Mass Function & $ \begin{aligned}& \mathrm{P}(X=x\ \mathrm{and}\ Y=y) \\& = \mathrm{P}(Y=y \mid X=x) \cdot \mathrm{P}(X=x) \\& = \mathrm{P}(X=x \mid Y=y) \cdot \mathrm{P}(Y=y) \end{aligned} $ \\ Expectation & $ E[X] = \sum_{x:p(x)>0} xp(x) $ \\ $\hookrightarrow note:$ & $ E[g(X)] = \sum_{x:p(x)>0} g(x)p(x) $ \\ Variance & $\begin{aligned} Var(X) &= E[(X - E[X])^2] \\ &= E[X^2] - (E[X])^2 \end{aligned}$\\ Standard Derivation & $ \sigma = \sqrt{Var(X)} $ \\ Covariance & {$\begin{aligned} Cov(X,Y) &= E[(X-E[X])(Y-E[Y])] \\ &= E[XY] - E[X]E[Y] \end{aligned}$} \\ {\fontsize{6}{6}\selectfont Moment Gener. Function } & $ M(t) = E[e^{tX}] $ (same for continuous RVs) \\ \end{defns} \begin{defns}{Random Variables (Continuous) \rom{1}} Probability Density Function & $f$ such that $ P\{X \in B \} = \int_B f(x)dx $ \\ Distribution Function & $F$ such that $ \frac{d}{dx}F(x) = f(x) $ \\ Expectation & $ E[X] = \int_{-\infty}^{\infty} xf(x)dx $ \\ $\hookrightarrow note:$ & $ E[g(X)] = \int_{-\infty}^{\infty} g(x)f(x)dx $ \\ Variance & $\begin{aligned} Var(X) &= E[(X - E[X])^2] \\ &= E[X^2] - (E[X])^2\end{aligned}$\\ Standard Derivation & $ \sigma = \sqrt{Var(X)} $ \\ Covariance & {$\begin{aligned} Cov(X,Y) &= E[(X-E[X])(Y-E[Y])] \\ &= E[XY] - E[X]E[Y] \end{aligned}$} \\ Joint Probability Mass Function & $ \begin{aligned} P\{(X,Y) \in C\} &= \iint_{(x,y)\in C} f(x,y) dxdy \\ P\{X \in A, Y \in B\} &= \int_{B}\int_A f(x,y) dxdy \end{aligned} $ \\ \end{defns} \begin{defns}{Random Variables (Continuous) \rom{2}} Marginal pmfs & $ \begin{aligned} f_X (x) &= \int_{-\infty}^{\infty} f(x,y) dy \\ f_Y (y) &= \int_{-\infty}^{\infty} f(x,y) dx \end{aligned} $ \\ \end{defns} \begin{defns1}{More on Expectation, Variance, ..} $ E[X+Y] = E[X] + E[Y] $ \\ $ E[\alpha X] = \alpha E[X] $ \\ $ Var(X+a) = Var(X) $ \\ $ Var(aX+b) = a^2 Var(X) $ \\ $ \begin{aligned} Var(X+Y) &= E[(X+Y)^2] - (E[X+Y])^2 \\ &= E[X^2 + 2XY + Y^2] - (E[X] + E[Y])^2 \\ &= E[X^2] + 2E[XY] + E[Y^2] - \\ & \qquad (E[X])^2 -2E[X]E[Y] - (E[Y])^2 \\ &= Var(X) + Var(Y) + 2 ( E[XY] - E[x]E[Y]) \\ &= Var(X) + Var(Y) + 2 ( Cov(X,Y) )\end{aligned} $ \\ Independence $ \begin{aligned} &\Rightarrow E[f(X)g(Y)] = E[f(X)]E[g(Y)] \\ &\Rightarrow E[XY] = E[X]E[Y] \\ &\Rightarrow Cov(X,Y) = 0 \\ &\Rightarrow Var(X + Y) = Var(X) + Var(Y) \end{aligned}$ \\ Correlation $ corr (X,Y) = \rho (X,Y) = \frac{Cov(X,Y)}{\sqrt{Var(X)Var(Y)}}$ \\ \begin{tight_enumerate} \item $ -1 \leq \rho (X,Y) \leq 1 $ \item Independence $ \Rightarrow \rho (X,Y) = 0$ \item $ \begin{aligned} & Y=mX+cm,\, m \neq 0 \; and \; c: \\ & m > 0 \Rightarrow \rho (X,Y) = 1 \\ & m < 0 \Rightarrow \rho (X,Y) = -1 \end{aligned} $ \end{tight_enumerate} \\ $E[X] = E[E[X \mid Y]] $ \\ Disc.: $E[X] = \sum_y E[X \mid Y=y] P\{Y=y\} $ \\ Cont.: $E[X] = \int_{-\infty}^{\infty} E[X \mid Y=y] f_y(y)dy $ \\ \end{defns1} \end{multicols} \newpage \newgeometry{top=0.35cm,left=1cm,right=1cm,bottom=1cm} \begin{multicols}{3} \centering\section{Combinatorial Analysis} \centering{\begin{tabular}{|l|l|} \hline Order matters and k = n & Permutation \\ \hline Order does matter and k $ < $ n & Variation \\ \hline Order does not matter and k $ < $ n & Combination \\ \hline \end{tabular}} \begin{defns}{Counting} Basic Counting Principle & Experiments $E_1, E_2, .. E_r$ with $n_1, n_2, .. n_r$ possible outcomes. Total outcomes: $\prod_i^r n_i$ \\ Permutations (without Repeats) & $ n! = n \cdot (n-1) \cdot \ldots \cdot 1 $ \\ Permutations \newline (with Repeats) & $ \frac{n!}{k!} = n \cdot (n-1) \cdot \ldots \cdot (k+1) $ \\ Variations \newline (without Repeats) & $n\cdot (n-1) \cdot \ldots \cdot (n-k+1) = \frac{n!}{(n-k)!}$\\ Variations \newline (with Repeats) & $ \underbrace{n \cdot \dotsc \cdot n}_{k\text{-times}} = n^k $ \\ Combinations \newline (without Repeats) \newline {\fontsize{6.5}{6}\selectfont "Binomial Coefficient"} & $ \frac{n!}{(n-k)! \, k!} = \frac{n (n-1)(n-2) \ldots (n-k+1)}{k!} = \binom{n}{n-k} = \binom{n}{k} $ \\ Multinominal Coefficient & $ \frac{n!}{n_1!n_2!\ldots n_r!} =$ $n! \choose n_1,n_2,...,n_r $ \newline {\fontsize{6}{6}\selectfont "divide n into r non-overlapping subgroups of sizes n1,n2,.."}\\ Combinations (with Repeats) & $ \frac{(n+k-1)!}{(n-1)! \, k!} = {n+k-1 \choose k} = {n+k-1 \choose n-1} $ \\ \end{defns} \begin{defns}{Limit Theorems} Central Limit Theorem & $\begin{aligned} Z_n &= \frac{((X_1 + X_2 + \ldots + X_n) - n\mu)}{\sigma \sqrt{n}} \\ \text{Then as } & n \rightarrow \infty \\ P(Z_n \leq x) &\rightarrow \int_{-\infty}^{\infty} \frac{1}{\sqrt{2 \pi}} exp (-\frac{1}{2} u^2)du \\ i.e. P(Z_n \leq x) & \rightarrow P(Y \leq X) \text{ where } Y \sim N(0,1) \end{aligned}$ \\ Weak Law of Large Numbers & $\begin{aligned} E[X_i] = \mu \quad Var(X_i) = \sigma^2 \\s_n = \frac{1}{n}(X_1+\ldots+X_n)\\ \text{then for any } \epsilon > 0 \\ \lim_{n \rightarrow \infty} P(\mid s_n - \mu \mid > \epsilon) = 0 \end{aligned}$\\ Strong Law of Large Numbers & $\begin{aligned} P\{ lim_{n \rightarrow \infty} (X_1 + X_2 + \ldots + X_n) \div n = \mu \} = 1 \end{aligned}$\\ Markov's Inequality & $ p\{ x \geq a \} \leq \frac{E[X]}{a}$ \\ Chebyshev's Inequality & $\begin{aligned} E[Y^2] < \infty,\, \forall a > 0. \\ P(\mid Y \mid \geq \frac{1}{a^2}E[Y^2] ) \end{aligned}$\\ $\hookrightarrow$ & $\begin{aligned} P\{ \mid X - \mu \mid \geq a \} \leq \frac{\sigma^2}{a^2} \end{aligned}$\\ One-sided Chebyshev (mean 0) & $\begin{aligned} P\{ X \geq a \} \leq \frac{\sigma^2}{\sigma^2 + a^2} \end{aligned}$\\ Chernoff Bounds & $\begin{aligned} P\{ X \geq a \} &\leq e^{-ta}M(t) \quad t > 0 \\ P\{ X \leq a \} &\leq e^{-ta}M(t) \quad t < 0 \end{aligned}$\\ \end{defns} \vspace{4cm} \centering\section{Markov Chains} \subsection{Discrete} $$ P_{i,j} = P(\text{system is in state }j\text{ at time }n + 1 \mid \text{system in state }i\text{ at time }n) $$ Transition Matrix: $ P = \begin{pmatrix} p_{1,1} & p_{1,2} & \cdots & p_{1,n} \\ p_{2,1} & p_{2,2} & \cdots & p_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ p_{n,1} & p_{n,2} & \cdots & p_{n,n} \end{pmatrix} $ \\ Probability vector $\pi ^{(n)}$: Probabilities that we are in state i at n. $$ \begin{aligned} \pi^{(n+1)} &= \pi^{(n)}P \\ \pi^{(n)} &= \pi^{(0)}P^n \end{aligned} $$ \textbf{A Markov Chain is ergodic}(aperiodic and irreducible) iff there exists $n \in \mathbb{N}^+$ such that $P^n$ has no zero entries. It then has a Steady State Probability vector $ \pi = lim_{n \rightarrow \infty} \pi^{(n)} $ independent of $\pi^{(0)}$. \begin{tight_enumerate} \item $\pi_0 + \pi_1 + \ldots + \pi_N-1 = 1$ \item $ \pi = \pi P$ \end{tight_enumerate} \subsection{Continuous} \subsubsection{Poisson} $$ P(\widetilde{N}(t)=k) = \frac{(\lambda t)^k}{k!}e^{-\lambda t} \text{ if}$$ \begin{tight_enumerate} \item For any fixed $t,\, \widetilde{N}(t)$ is a discrete RV \item $\widetilde{N}(0)=0$ \item \# of events in disjoint intervals are independent \item $\widetilde{N}(t+h) - \widetilde{N}(t) = \#$ of events in $[t,t+h]$ for $h \rightarrow 0$ \item $ P(\widetilde{N}(h) = 1) = P(\text{event occurs in } [t, t+h]) = \lambda h + E(h)$ ($E(h)/h \rightarrow 0,\,\text{as } h \rightarrow 0$) \item $\frac{1}{h} P(\widetilde{N}(h) \geq 2) \rightarrow 0, \text{ as } h \rightarrow 0$ \end{tight_enumerate} \subsubsection{Birth-Death} \textbf{ Birth Rates } $\lambda_{i,i+1} = b_i$ \\ \textbf{ Death Rates } $\lambda_{i,i-1} = d_i$ \\ $\lambda_{i,j} = 0$, otherwise \\ $ \rightarrow$ Have steady state prob. vector if $b_i$s and $d_i$s are non-zero and we have a finite number of states. \begin{tight_enumerate} \item $\pi_0 + \pi_1 + \ldots + \pi_N-1 = 1$ \item $\pi_j = \frac{b_0\cdots b_{j-1}}{d_0\cdots d_{j-1}}\pi_0$ \end{tight_enumerate} \subsubsection{M/M/S Queue} Customers arrive with Poisson Process rate $\lambda$, S servers, Service time exponentially distributed with mean $\frac{1}{\mu}$. State j = j customers in queue, $b_j = \lambda$, $d_j = \begin{cases} j \mu, \qquad & j = 1,2,\ldots,S \\ S\mu, \qquad & j \geq S \end{cases}$ \\ $ \rightarrow$ Has steady state prob. vector if $\lambda < S\mu$. \subsubsection{M/M/1 Queue} $\pi_j = (1-\frac{\lambda}{\mu})(\frac{\lambda}{\mu})^j$, Mean Queue Length $E[J] = \frac{\lambda}{\mu-\lambda}$ \begin{defns}{Surprise, Uncertainty \& Entropy} Entropy & $\begin{aligned} H(X) & := -\textstyle\sum_k p_x(x_k)log_2p_x(x_k) \\ ( 0log_2(0) & := 0 ) \end{aligned}$ \\ Surprise & $S(X = x_k) = -log_2p_x(x_k)$ \\ $\hookrightarrow$ Properties & \begin{tight_enumerate} \item $ S(1) = 0 \neq S(0)$ (which is undefined) \item S decreases: $p < q \Rightarrow S(q) < S(p)$ \item $S(pq) = S(p) + S(q)$ \end{tight_enumerate} If S is continuous and these are satisfied, $\exists \mathscr{C} > 0.\forall p\in [0,1], \; S(p) = - \mathscr{C} log(p)$ \\ Average Uncertainty & $H(X,Y) := - \sum_j \sum_k p_{X,Y}(x_j,y_k)log_2p_{X,Y}(x_j,y_k) $\\ Uncertainty of X given Y & $\begin{aligned} & H_{Y=y_k}(X) := \\ &- \sum_j p_{X\mid (Y = y_k)}(x_j)log_2p_{X\mid (Y = y_k)}(x_j)\end{aligned} $ \\ Conditional Entropy & $H_{Y}(X) := \sum_k H_{Y=y_k}(X)p_Y(y_k) $ \\ \end{defns} \begin{defns}{Coding Theory} Code $\mathfrak{C}$ & A map from $ \{x_k\} \subset \mathbb{R} $ into sequences of 0's and 1's. Sequences are called code words. \\ Code Word length & $x_k \mapsto 0111 \quad \Rightarrow n+k = $ \\ Expected Length of Code $\mathfrak{C}$ & $E[\mathfrak{C}] = \sum_kn_kp_k = \sum_kn_kP(X=x_k)$ \\ Acceptable Code & No code word extends another one: {\begin{tabular}{|c|c|} \hline \Cross & \checkmark \\ \hline $ x_1 \mapsto 0$ & $ x_1 \mapsto 0$ \\ \hline $ x_2 \mapsto 00$ & $ x_2 \mapsto 10$ \\ \hline \end{tabular}} \\ Noiseless Coding Theorem & For any acceptable code assigning $n_k$ bits to $x_k$ the following holds: $$ E[\mathfrak{C}] = \sum_k n_kp_k \geq H(X) = -\sum_k p_k log_2 p_k $$ Where $p_k = P(X = x_k)$ and $n_k$ length of a codeword associated with $x_k$\\ $\hookrightarrow$ Thrm & For any discrete RV X there exists an acceptable code with the expected length $E[\mathfrak{C}] = L $ such that $$ H(X) \leq L < H(X) +1 $$ \\ \end{defns} Algorithm for finding an acceptable code with expected length $H(X) \leq E[\mathfrak{C}] = L < H(X) +1 $ for discrete RV X: \begin{tight_enumerate} \item Let $n_j$ be the integer satisfying $-log_2p_j \geq n_j < -log_2p_j+1$ \item Find any acceptable code assigning $n_j$ bits to $x_j$ \end{tight_enumerate} There is no unique nearly-optimal code in general. Optimal or nearly-optimal coding depends on the pmg of X. \begin{defns}{Common Moment Generating Functions M(t)} Binomial & $ (pe^t + 1-p)^n $\\ Neg. Binomial & $ [(pe^t) \div (1-(1-p)e^t)]^r $\\ Poisson & $ exp(\lambda(e^t-1)) $\\ Uniform & $ (e^{tb} - e^{ta}) \div (t(b-a)) $\\ Exponential & $ \lambda \div (\lambda - t) $\\ Normal & $ exp( \mu t + ( (\sigma^2t^2)\div2 ) $\\ \end{defns} \end{multicols} \end{document}