-
Notifications
You must be signed in to change notification settings - Fork 0
/
latexsheet.tex
322 lines (282 loc) · 21.2 KB
/
latexsheet.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
\documentclass[10pt,landscape]{article}
\usepackage{multicol}
\usepackage{calc}
\usepackage{ifthen}
\usepackage[landscape]{geometry}
\usepackage{hyperref}
% To make this come out properly in landscape mode, do one of the following
% 1.
% pdflatex latexsheet.tex
%
% 2.
% latex latexsheet.tex
% dvips -P pdf -t landscape latexsheet.dvi
% ps2pdf latexsheet.ps
% If you're reading this, be prepared for confusion. Making this was
% a learning experience for me, and it shows. Much of the placement
% was hacked in; if you make it better, let me know...
% 2008-04
% Changed page margin code to use the geometry package. Also added code for
% conditional page margins, depending on paper size. Thanks to Uwe Ziegenhagen
% for the suggestions.
% 2006-08
% Made changes based on suggestions from Gene Cooperman. <gene at ccs.neu.edu>
% To Do:
% \listoffigures \listoftables
% \setcounter{secnumdepth}{0}
% This sets page margins to .5 inch if using letter paper, and to 1cm
% if using A4 paper. (This probably isn't strictly necessary.)
% If using another size paper, use default 1cm margins.
\ifthenelse{\lengthtest { \paperwidth = 11in}}
{ \geometry{top=.25in,left=.25in,right=.25in,bottom=.25in} }
{\ifthenelse{ \lengthtest{ \paperwidth = 297mm}}
{\geometry{top=1cm,left=1cm,right=1cm,bottom=1cm} }
{\geometry{top=1cm,left=1cm,right=1cm,bottom=1cm} }
}
% Turn off header and footer
\pagestyle{empty}
% 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
% Define BibTeX command
\def\BibTeX{{\rm B\kern-.05em{\sc i\kern-.025em b}\kern-.08em
T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}}
% Don't print section numbers
\setcounter{secnumdepth}{0}
\setlength{\parindent}{0pt}
\setlength{\parskip}{0pt plus 0.5ex}
% -----------------------------------------------------------------------
\begin{document}
\raggedright
\footnotesize
\begin{multicols*}{3}
% multicol parameters
% These lengths are set only within the two main columns
%\setlength{\columnseprule}{0.25pt}
\setlength{\premulticols}{1pt}
\setlength{\postmulticols}{1pt}
\setlength{\multicolsep}{1pt}
\setlength{\columnsep}{2pt}
\section{Distributions}
\textbf{Discrete}
\begin{tabular}{@{}ll@{}}
\verb!Combinatorial! & Finite space, equally likely outcomes\\
\verb!! & $P(A)=card(A)/n$\\
\verb!Bernoulli! & Success probability of bent coin\\
\verb!! & $p_0=q=(1-p)$ and $p_1=p$ \\
\verb!! &$\mu=p, \sigma^2=pq$ \\
\verb!Binomial!& Probability of n heads in k tosses\\
\verb!! & $p_k={n \choose k} p^k(1-p)^{n-k}$\\
\verb!! &$\mu=np, \sigma^2=npq$\\
\verb!Geometric! & Failures before 1st success, $k\geq 0$\\
\verb!! & $p_k= (1-p)^k p$ \\
\verb!! &$\mu=\frac{q}{p}, \sigma^2=\frac{q}{p^2}$\\
\verb!Negative Binomial! & Failures before rth success $k\geq 0$\\
\verb!! & $w_r(k;p)={k+r-1 \choose k}q^kp^r$\\
\verb!! & Note the negative binomial is sum of\\
\verb!! & r \textbf{independent} geometric RVs.\\
\verb!! &$\mu=\frac{rq}{p}, \sigma^2=\frac{rq}{(p)^2}$\\
\verb!Poisson! & Characterization of rare events\\
\verb!! & $p_k = e^{-\lambda} \lambda^k / k! $\\
\verb!! &$\mu=\lambda, \sigma^2=\lambda$\\
\end{tabular}
\textbf{Continuous\\}
\begin{tabular}{@{}ll@{}}
\verb!Uniform!& Agnostic about outcome on interval \\
\verb!! & $f(x)=1/(b-a)$ on \\
\verb!! &$ a<x<b$ and $0$ $o.w.$\\
\verb!! &$\mu=\frac{1}{2}(a+b), \sigma^2=\frac{1}{12}(b-a)$\\
\verb!Gamma!& Note $\Gamma =(n-1)!$ \\
\verb!! &$g_n(t;\alpha)=\alpha \frac{(\alpha t)^{n-1}} {(n-1)!}e^{-\alpha t}$\\
\verb!! &$\mu=\frac{n}{\alpha} , \sigma^2=\frac{n}{\alpha^2}$\\
\verb!Chi-squared! & Finite $X_k ~\mathcal{N}(0,1)$; $V^2=\sum_{k=1}^{n} X_k^2$ \\
\verb!! & $g_{n/2}(t;1/2)=\frac{1}{2^{n/2}\Gamma(\frac{n}{2})}t^{\frac{n}{2} -1}e^{-\frac{t}{2}}$\\
\verb!! &$\mu=n , \sigma^2=2n$\\
\verb!Exponential! & A model for true randomness \\
\verb!! & $f(x)=\alpha e^{-\alpha x}$ for $x>0$\\
\verb!! &$\mu=\frac{1}{\alpha} , \sigma^2=\frac{1}{\alpha^2}$\\
\verb!Normal! & The one to rule them all... \\
\verb!! & $f(x) = \frac{1}{\sqrt{(2 \pi)} \sigma} e^{-(x-\mu)^{2}/2 \sigma^{2}}$ \\
\verb!! & \hspace{-75pt} Even function, strictly positive, dies monotonically...\\
\verb!! & \hspace{-75pt} Can be sometimes written as $N(\mu,\sigma^2)$...\\
\verb!Multivariate Normal! & Note that x and m are vectors \\
\verb!! & \hspace{-55pt}$f(x)=\frac{1}{2\pi^{\frac{n}{2}} det(A)^{\frac{1}{2}}}exp(-\frac{1}{2}(x-m)A^{-1}(x-m)^T)$
\end{tabular}
\textbf{Negative Binomial Trick:}
$ { r+k-1 \choose k}q^kp^r={-r \choose k}(-q)^kp^r$
\section{Properties of Distributions}
\textbf{Shifting and Scaling} \textit{If two densities come from same type: $\frac{1}{a}f(\frac{x-m}{a})$ then $\mu =a\mu +m$ $\sigma^2=a^2\sigma^2$}\\
\textbf{Convolution }\textit{The convolution of any pair of distributions must necessarily be a distribution}\\
\textbf{Stability of the Normal}
\textit{Suppose $X_1,X_2,...X_n$ are independent and for each k $X_k$ is normal with mean $\mu_k$ and variance $\sigma_k$. Then $S_n = \sum_{k=1}^{n}X_k$ is normal with mean $\sum_{k=1}^{n} \mu_k$ and variance $\sum_{k=1}^{n} \sigma_k$, or in other words normal densities are stable under convolution. Also stable under \textbf{non-degenerate} linear transformation}\\
\textbf{Translation Invariance: Uniform}\\
\textbf{Sum of Independent Poisson RVs}
\textit{For \textbf{independent} random variables drawn from Poisson distribution is Poisson and the mean is $\lambda_1 + \lambda_2$}\\
\textbf{Sum of Independent Binomials} is also binomial.\\
\textbf{Sum of Independent Gamma RVs}
\textit{Given $X_1 \sim g_{n_1}(x_1,\alpha)$ and $X_2 \sim g_{n_2}(x_2,\alpha)$ then $Z=X_1+X_2 \sim g_{n_1+n_2}(z,\alpha)$. Note the RV's must have the same mean $\frac{1}{\alpha}$}\\
\textbf{The marginals of a multivariate normal are normal }\textit{Note: a system of variables with marginal normal densities need not have a jointly normal density, and, in fact a joint density need not even exist}\\
\textbf{Sum of Exponentials} \textit{Sum of \textbf{independent} exponential random variables from a common exponential density $\alpha e^{-\alpha x}$ for $x>0$ is $S_n$, the sum $S_n= X_1+X_2+...+X_n$ has the \textbf{gamma density}}.\\
\textbf{Memoryless Property} \textit{\textbf{ONLY} the exponential and geometric distributions are memoryless. The random variable X exhibits the memoryless property if $P\{X>s+t|X>s\}=P\{X>t\}$ or recast
$P\{X>s+t | X>s\}=P\{X>t\}$ if and only if $P\{X>s+t\}=P\{X>s\}P\{X>t\}$}\\
\textbf{Rotation of Bivariate Normal} \textit{There exists a rotation of a bivariate normal st. the normal coordinates become independent}
\textbf{Max variance for Bernoulli Trial} \textit{Is $1/4$ which occurs if $p=1/2$. Bernoulli trials are assumed to be independent unless otherwise stated.}\\
\textbf{Limit of the geometric} \textit{The exponential distribution is the continuous limit of the geometric distribution. Use two integration by parts to show variance is $\frac{1}{\alpha^2}$ and the mean is $\frac{1}{\alpha}$}\\
\textbf{The Gamma Density is Closed Under Convolutions} \textit{For every fixed $\alpha>0$ the family of gamma densities $\{g_v(\dot;\alpha), v>0\}$ is closed under convolutions, that is, $(g_\mu\star g_\nu)(x)=g_{\mu+\nu}(x) \forall\mu \nu$. Restatement of earlier property.}
\section{Expectation}
\textbf{Variance} $Var(X)=E(X^2)-E(X)^2$\\
\textbf{Covariance} $Cov(X,Y)=E(XY)- E(X)E(Y)$\\
\textbf{Law of the Unconcious Statistician}
\textit{If X is a discrete r.v. and g is a function from {$R\rightarrow R$} then, $E(g(X))=\sum_{x}g(x)P(X=x)$}
\textbf{Independence} \textit{Independent variables are uncorrelated, but uncorrelated variables are not necessarily independent. However, this is a necessary and sufficient condition if we are talking about the marginals of a normal density}
\textbf{Additivity} \textit{Expectation is additive. Variance is additive if the summands are independent.}
\textbf{Conditional Expectation} \textit{$E(X_2)=E(E(X_2|X_1))$}\\
\section{Conditional Probability}
$P(A|H)=\frac{P(A \cap H)}{P(H)}$\\
$P_H: A \rightarrow P(A|H)$\\
$P(A_1 \cap A_2 \cap ... \cap A_n)= P(A_1|A_2 \cap ... \cap A_n)$\\ $\times P(A_2|A_3 \cap ... \cap A_n) \times P(A_{n-1}|P(A_n) \times P(A_n)$\\
\textbf{Bayes Rule}
$P(A_k|H)=\frac{P(H|A_k)P(A_k)}{\sum_{j \geq 1}{} P(H|A_j)P(A_j)}$
\section{Inclusion-Exclusion}
\textit{$S_k= \sum (P(A_{j_1}) \cap...\cap P(A_{j_k}))$}\\
\textit{$P(A_1 \cup ...\cup A_n)=\sum_{k=1}^{n} (-1)^{k-1}S_k$}\\
Let $P(m)$ be probability that exactly $m$ events occur \\
Then, \textit{$P(m)=\sum_{k=0}^{n-m}(-1)^{k}{m+k \choose m}S_{m+k}$}\\
\textbf{De Finneti's Theorem}\\
Let $\tau>0$ and $L_1 ,..., L_{n+1}$ are successive spacings engendered by $n$ random points in iterval $[0,\tau)$, for every choice $x_1\geq 0, ...,$
\textit{$P\{L_1>x_1,...,L_{n=1}>x_{n+1}\}=(1-\frac{x_1}{\tau}-\frac{x_2}{\tau}...-\frac{x_{n+1}}{\tau})^n_+$}\\
\textit{(Covering Problem) $n+1$ random arcs, each of length $a$, $X_0,...,X_n$ random points on circle, probability that arcs cover unit circle}
$A_j:$ event $j$th spacing $L_j$ exceeds $a$. \textit{$P(A_{j1} \cap ...\cap A_{jk})=(1-ka)^n_+$}
\textit{$S_k= \sum (P(A_{j_1}) \cap...\cap P(A_{j_k}))={n+1 \choose k} (1-ka)^n_+$}\\
\textit{$c_{n+1}=P(A_{1}^{c} \cup ...\cup A_{n}^{c})=\sum_{k=0}^{n+1}(-1)^{k}{n+1 \choose k}(1-ka)^n_+$ }
\section{Limit Laws}
\textbf{Weak Law of Large Numbers}(Khinchin)\\
If $X_1,X_2,...$ is a sequence of independent random variable with common distibution with finite mean $\mu$ and let $S_n=(X_1+...+X_n)$ for each $n$. Then $\frac{1}{n} S_n \rightarrow^{p} \mu$. Or, $P\{|\frac{1}{n} S_n - \mu | \geq \epsilon\} \rightarrow 0$ as $n \rightarrow \infty$ for every choice $\epsilon>0$\\
\textbf{Strong Law of Large Numbers}(Kolmogorov, conditions same)\\
$\frac{1}{n} S_n \rightarrow^{a.e.} \mu$. Or, $P\{|\frac{1}{n} S_n - \mu | \geq \epsilon\ i.o.\}=0$ for every $\epsilon>0$.
\textbf{Central Limit Theorem}\\
\textit{Suppose $X_1,X_2,...$ is a sequence of independent random variable drawn from a common distribution F with mean zero and variance one. For each n, let $S_n*=(X_1+...+X_n)/\sqrt{n}$. Then $S_n*$ converges in distribution to the standard normal.}\\
$P\{a<S_n*<b\}\rightarrow\Phi(b)-\Phi(a)=\frac{1}{\sqrt{2\pi}}\int_{a}^{b}e^{-x^2/2}dx$
\textit{If $E(X_k)=\mu$ and $Var(X_k)=\sigma^2$ then we can center and scale the variables such that $S_n*=(S_n - n\mu/\sqrt{n}\sigma)$ and the theorem holds for the new properly normalized $S_n*$.}
\section{Inequalities}
\textbf{Convexity} The chord lies above the curve\\
$\Psi(\alpha x +(1-\alpha)y)\leq \alpha\Psi(x)+(1-\alpha)\Psi(y)$\\
\textbf{Jensen} If $\Psi$ is convex , $X$ is integrable, and $\Psi(x)$ is integrable then:
$\Psi(E(x))\leq E(\Psi(x))$\\
\textbf{Another of Jensen} $E(X^2)\geq E(X)^2$\\
\textbf{AM-GM} $ x_1^{p_1} x_2^{p_2}...x_n^{p_n}\leq p_1 x_1 +p_2 x_2 + ... p_n x_n$\\
\textbf{Specialization of AM-GM} $x^{1/p} y^{1/q} \leq (1/p) x +(1/q) y$\\
simplifies to: $ xy \leq (1/p) x^p +(1/q) y^p$\\
\textbf{Holder's} $|E(XY)| \leq E(|XY|) \leq E(|X|^p)^{1/p} E(|Y|^q)^{1/q}$\\
\textbf{Cauchy-Schwarz} If $p=q=2$ in Holder's $\rightarrow$ $E(XY)^2 \leq E(X^2)E(Y^2)$\\
\textbf{Minkowski} $p\geq 1$ then $ ||x+y||_p \leq ||x||_p + ||y||_p$\\
$||x||_p=E(|X|^p)^{1/p}$\\
\textbf{Chebyshev} $X$ has finite second moment and $t$ is strictly positive.\\
Then, $P\{|X-E(X)|\geq t\}\leq Var(X)/t^{2}$\\
If $X_1,X-2,...$ is a sequence of independent random variable with common distibution F. For each n, let $S_n=(X_1+...+X_n)$.\\
$P\{|S_n-n\mu|\geq n\epsilon\}\leq \frac{n\sigma^2}{n^2\epsilon^2}$\\
\textbf{Chernoff} $P\{S_n\geq t\} \leq (\inf\limits_{\lambda\geq 0} e^{-\lambda t/n}M(\lambda))^n $ and\\
$P\{S_n\leq t\} \leq (\inf\limits_{\lambda\geq 0} e^{-\lambda t/n}M(-\lambda))^n $\\
Where $M(\lambda)=E(e^{\lambda X_j})=\int_{\mathcal{R}} e^{\lambda x}dF(x)$ is the moment generating function\\
\textbf{Markov}$P\{X\geq a\} \leq \frac {E(X)}{a}$\\
\textbf{Normal Tail Bound p 317} $\frac{\phi(x)}{x}(1-\frac{1}{x^2}) < 1- \Phi(x) < \frac {\phi(x)}{x} $\\
\textbf{Normal Tail Bound p 165} $\int_{t}^{\infty}\phi(x) dx \leq \frac{1}{2}e^{-t^2/2}$
\section{Logarithmic Identities}
$y = \log _b \left( x \right){\rm{ iff }}x = b^y$\\
$\log _b \left( {\frac{x}{y}} \right) = \log _b \left( x \right) - \log _b \left( y \right) $\\
$\log _b \left( x \right) = \log _b \left( c \right)\log _c \left( x \right) = \frac{{\log _c \left( x \right)}}{{\log _c \left( b \right)}} $\\
$\log _b \left( {x^n } \right) = n\log _b \left( x \right) $\\
$\log _b \left( 1 \right) = 0 $\\
$\log _b \left( b \right) = 1 $\\
$\log _b \left( {xy} \right) = \log _b \left( x \right) + \log _b \left( y \right)$\\
%\vspace{10pt}
\begin{multicols*}{3}
$log(\infty)\rightarrow \infty$\\
$log(0)\rightarrow -\infty$\\
$log(1)=0$
\end{multicols*}
\section{Exponential Identities}
\begin{multicols*}{2}
$x^a x^b = x^{\left( {a + b} \right)} $\\
$x^a y^a = \left( {xy} \right)^a$\\
$\left( {x^a } \right)^b = x^{\left( {ab} \right)}$\\
$x^{\left( {a - b} \right)} = \frac{{x^a }}{{x^b }} $\\
\end{multicols*}
\section{Common Infinite Series}
\textbf{Exponential}\\
$\sum_{k=0}^{\infty}\frac{z^k}{k!}=e^z$\\
$\sum_{k=0}^{\infty}k\frac{z^k}{k!}=ze^z$ Mean of the Poisson\\
$\sum_{k=0}^{\infty}k^2\frac{z^k}{k!}=(z+z^2)e^z$ Second moment of Poisson\\
$\sum_{k=0}^{\infty}k^3\frac{z^k}{k!}=(z+3z^2+z^3)e^z$\\
$\sum_{k=0}^{\infty}k^4\frac{z^k}{k!}=(z+7z^2+6z^3+z^4)e^z$ \\
\textbf{Binomial}\\
$\sum_{k=0}^{\infty}{\alpha \choose k}z^k=(1+z)^\alpha, |z|<1$\\
$\sum_{k=0}^{n}{n \choose k}x^{n-k}y^k=(x+y)^n$\\
\section{Integration}
\begin{multicols*}{2}
$\int x^n dx = \frac{1}{n+1}x^{n+1}, \hspace{1ex} n\neq-1$
$\int \frac{1}{x} dx = \ln |x|$
$\int u \hspace{2pt} dv = uv - \int v du$
$\int e^x dx = e^x $
$\int a^x dx = \frac{1}{\ln a} a^x$
$\int \ln x dx = x \ln x - x$
$\int \sin x dx = -\cos x$
$\int \cos x dx = \sin x$
\end{multicols*}
\section{The Bernoulli Schema}
\textbf{Theorem 1} \textit{Suppose $X_1,...,X_n$ is a sequence of Bernoulli tials with success probability p. Then the sume $S_n=X_1+...+X_n$ has a distribution $b_n(k)={n \choose k }p^kq^{n-k}$. Recall as a matter of convention the definition for real $t$ and integer $k$ that ${t \choose k} =t(t-1)(t-2)...(t-k+1)/k!$ if $k\geq 0$ and $0$ otherwise.}
\textbf{Example: Ball and Urn} \textit{Put n balls in m urns, probability that there are k balls in first r: ${n \choose k } \frac{r}{m}^k(1-\frac{r}{m})^{n-k}$}\\
\textbf{Example: Polls} \textit{Select n individuals from population, an unknown fraction p support policy. All samples are independent.$S_n=\sum_{j=1}^{n}=Z_j$ is the number of individuals in favor, $S_n \sim b_n(k;p)$. Let $\zeta \in [0,1]$ be a guess for $p$. $b(\zeta)=b_n(S_n;\zeta)={n \choose S_n}\zeta^{S_n}(1-\zeta)^{n-S_n}$, then $b(\zeta)$ is maximized at $\zeta=(S_n/n)$. The sample mean is $\arg max_{\zeta}b_n(S_n);\zeta)$ which is the mean of the empirical distribution. Thus, p estimated by this value yields the largest probability of observations consistent with the data. We say that the sample mean is the unbiased estimator of p}\\
\textbf{Error Bound on Sample Mean} \textit{Via Chebyshev $P\{|\frac{1}{n}S_n -p|\geq\epsilon\}=\sum b_n(k;p) \leq \frac{pq}{n\epsilon^2}\leq \frac{1}{4n\epsilon^2}$}\\
\textbf{Example: Random Walks} \textit{The number of paths from (a,b) to (a',b') is $N_n(k)={n \choose \frac{n+k}{2}}$ where $n=a'-a$ and $k=b'-b$. If the path goes through strictly positive values the number of such paths is $N^{+}_{n}(k)=N_{n-1}(k-1)-N_{n-1}(k+1) = {n-1 \choose \frac{n+k}{2}-1}-{n-1 \choose \frac{n+k}{2}}=\frac{k}{n}{n \choose \frac{n+k}{2}}$}\\
\textbf{Example: Returns} \textit{The probability of a return is $ P\{S_{2}=N_{2v}(0)2^{-2v}={2v \choose v}2^{-2v}$}\\
\textbf{Example: Waiting Time} \textit{The waiting time is the wait until the first succes $w(k;p)=P(W=k)=q^kp (k\geq 0)$. Now $\sum_{k}w(k;p)=p \sum_{k=0}^{\infty}q^k=p/(1-q)=1$. Thus $w(k;p)$ is called the geometric distribution. Useful manipulation: $\sum_{k}^{\infty}q^k=1/(1-q)$}\\
\textbf{Sum of Independent RVs ~ geometric}\\
\textit{Suppose $\{W_i, i\geq 1\}$ is a sequence of independent geometric random variables with common success parameter $p>0$. For each r, let $T_r=W_1+W_2+...+W_r$ and let $w_r(k;p) =P(T_r=k)$ be its distribution. Then $w_r(k;p)={r+k-1 \choose k} q^kp^r$ this is the negative binomial.}\\
\textbf{Problem of the Points} \textit{ $P_m,n(p)=\sum_{k=0}^{n-1}{-m \choose k}(-q)^kp^m$ where m is the require points to win and n is the maximum number of failures}\\
\textbf{Example: Population Size} \textit{Hypergeometric Distribution: $h(i)=h_{m,n}(i;r)=\frac{{m \choose i}{n-m \choose r-i}}{{n \choose r}}$ where $(0 \leq u \leq r)$}\\
\textbf{Vandermonde's Convolution} \textit{ $\sum_{i} {m \choose i} {n-m \choose r-i} = {n \choose r}$ can be used to show hypergeometric is a density}\\
\textbf{Another funny sum} \textit{${n \choose 0}^2 +{n \choose 1}^2 +...+ {n \choose n}^2={2n \choose n}$}\\
\section{The Essence of Randomness}
\textbf{Buffon's Needle}\\
\textbf{Gamma Function etc} \textit{Continuous version $g_v(x,\alpha)=\frac{\alpha}{\Gamma(v)}(\alpha x)^{v-1}e^{-\alpha x}$}
\section{The Coda of the Normal}
\textbf{Bivariate Normal}\\
\textit{Suppose $(X_1,X_2)$ is a random pair governed by the bivariate normal density $\phi(x_1,x_2,\rho)$ and $Y=X_1+X_2$ then $X_1$ and $X_2$ share a common marginal normal distribution with zero mean and unit variance. Moreover, $Cov(X_1,X_2)=E(X_1 X_2)=\rho$ By additivity of expectation $E(Y)= E(X_1)+E(X_2)=0$, while, $Var(Y)=E((X_1+X_2)^2)=E(X_1^2)+E(X_2^2)+2E(X_1 X_2)=2(1+\rho)$}
\section{Random}
\textbf{The Hockey Stick Identity}
\textit{$\sum_{j=k}^{n}{j \choose n} = {n+1 \choose k+1}$}
\section{Borel-Cantelli Lemma}
\textit{(Lemma 1)} If the series $\sum_{n}P(A_n)$ converges. Then $P(\lim\sup_{n}A_{n})=P\{A_{n} i.o\}=0$, or, with probability one only finitely many of the events $A_n$ occurs.\\
\textit{(Lemma 2)} If the series $\sum_{n}P(A_n)$ diverges. If the events $\{A_n, n\geq1\}$ are independent then $P(\lim\sup_{n}A_{n})=P\{A_{n} i.o\}=1$, and the events $A_n$ occur infinitely often with probability one.\\
\section{Convergence}
\textit{(Almost everywhere)A sequence of random variables $\{X_n,n\geq 1\}$ converges almost everywhere to a random variable $X$ if $P\{\omega:X_{n}(\omega) \not\rightarrow X(\omega)\}=0$}\\
\textit{(Theorem) A random sequence $\{X_n, n\geq1\}$ converges a.e.\ to a random variable $X$ iff, for every $\epsilon\geq0$, we have $P(\lim\inf_n\{|X_n-X|<\epsilon\})=1$, or $P(\lim\sup_n\{|X_n-X|\geq\epsilon\})=0$}\\
\textit{(Theorem) A random sequence $\{X_n, n\geq1\}$ converges a.e.\ iff, for every $\epsilon\geq0$, as $n\rightarrow \infty$, $P(\cup_{j\geq 1}\{|X_{n+j}-X_n|\geq\epsilon\})\rightarrow0$}\\
\textit{(In probability)A sequence of random variables $\{X_n,n\geq 1\}$ converges in probability to a random variable $X$ if $\lim_n P\{|X_n-X|\geq\epsilon\})\}=0$, for every $\epsilon>0$}
\textit{(Theorem) Convergence a.e.\ implies convergence in probability}
\textit{(From convergence in P to a.e.) Show $\sum_{n}P\{|X_n-X|\geq \epsilon <\infty\}$, then by BC Lemma $P\{|X_n-X|\geq \epsilon \,i.o. \}=0$. Hence being by showing convergence in probability then leverage BC lemma to show that convergence is in a.e}\\
\textbf{Monotonce Convergence} \textit{Suppose $\{X_n\}$ is an increasing sequence of positive random variables converging pointwise to a random variable $X$, $0\leq X_n \uparrow X$.Then $\lim E(X_n)= E(X)$}
\textit{(Theorem)Suppose X is an integrable, positive random variable. Then $\sum_{n=1}^{\infty}P\{X\geq n\}\leq E(X) < 1+ \sum_{n=1}^{\infty}$ If arithmetic, $E(X)=\sum_{n=1}^{\infty}=P\{X\geq n\}$} \\
\textbf{Fatou's Lemma} \textit{Suppose $\{X_n\}$ is an increasing sequence of positive random variables on some probability space. Then $E(\lim\inf_{n\rightarrow \infty}X_n)\leq \lim\inf_{n\leftarrow\infty}E(X_n)$}
\textbf{Dominated Convergence} \textit{Suppose $X_n \rightarrow X$ pointwise. If there exists an integrable random variable $Y$ s.t. $|X_n|\leq Y$ for each $n$ the $X$ is integrable, $E(|X|)\leq E(Y)$, and $\lim_{n\leftarrow\infty}E(X_n)=E(X)$}\\
\textbf{Levi's Theorem}\textit{Suppose $\{X_n\}$ is an increasing sequence of random variables and there exists $M$ s.t. $E(X_n) \leq M$ for each $n$. Then there exists an integrable random variable $X$ such that $X_n \rightarrow X a.e.\ $, and moreover $E(X_n) \rightarrow E(X)$}\\
\section{Lebesgue-related}
\textbf{Lebesgue Integral}$E(X)=\int_{\Omega} X(\omega)P(d\omega)=\int_{R}xdF(x)$\\
\textbf{Lebesgue Program - Simple function} $S_m(\omega)=\sum_{n=0}^{m2^m}\frac{n}{2^m}1_{A_{mn}}(\omega)$\\
\textit{(Properties)} Functions are \textit{positive}, \textit{increasing}, and \textit{converges pointwise} to $X$, $S_m(\omega)\leftarrow X(\omega)$ for each $\omega$\\
\textbf{Stirling's Formula} $n!\sim \sqrt{2\pi}n^{n+1/2}e^{-n}$ $(n \rightarrow \infty)$
\end{multicols*}
\end{document}