\documentstyle[11pt]{article}

\setlength{\parindent}{0pt}

\addtolength{\textwidth}{2.5 in}
\addtolength{\oddsidemargin}{-1.25 in}
\addtolength{\evensidemargin}{-1.25 in}
\addtolength{\parskip}{-0.1 in}
\addtolength{\topmargin}{-1.5 in}
\addtolength{\textheight}{3 in}


%% fix parskip eventually

\begin{document}\
\hspace*{\fill}{\large{\bf 6.041}}\hspace*{\fill}
\par
\footnotesize

\paragraph{Seven Axioms of the Algebra of Events}  $A+B=B+A$;
$A+(B+C)=(A+B)+C$; $A(B+C)=AB+AC$; $(A^\prime)^\prime==A$;
$(AB)^\prime=A^\prime+B^\prime$; $AA^\prime=\phi$; $AU=A$.

\paragraph{Three Axioms of Probability Measure}  (1) For any event $A$,
$P(A) \geq 0$; (2) $P(U)=1$; (3) If $AB=\phi$, then $P(A+B)=P(A)+P(B)$.

\paragraph{Conditional Probability}  $P(A \mid B) = \frac{P(AB)}{P(B)}$
defined only for $P(B) \neq 0$; $P(AB) = P(A) P(B \mid A) = P(B) P(A \mid
B)$.  For random variables, $p_{x,y}(x_0,y_0) = p_x(x_0)p_{y \mid
x}(y_0 \mid x_0) = p_y(y_0)p_{x \mid y}(x_0 \mid y_0)$.

\paragraph{Independence} Two events are Independent if and only if
$P(A \mid B) = P(A)$.  For {\em random variables} $x$ and $y$, they
are independent if and only if $p_{y \mid x}(y_0 \mid x_0) = p_y(y_0)$
for all possible values of $x_0$ and $y_0$.  If two random variables
$x$ and $y$ are independent, $E(xy) = E(x)E(y)$.  Two random variables
$x$ and $y$ are {\em linearly independent} (but not necessarilly
independent) if $E(xy) = E(x)E(y)$.  Two PDF's are ({\em
statistically}) independent if and only if $f_{x \mid y}(x_0 \mid y_0)
= f_x(x_0)$ for all possible $x_0, y_0$.

\paragraph{Bayes' Theorem}  $P(A_i \mid B) = \frac{P(A_i)P(B \mid
A_i)}{\Sigma_{i=1}^N P(A_i)P(B \mid A_i)}$ with $P(B) \neq 0$ and $A_1,
A_2, \ldots, A_N$ an event space.

\paragraph{Expected Value} $E[g(x)] \equiv \sum_{x_0} g(x_0)p_x(x_0)
\equiv \overline{g(x)}$ 

\paragraph{Moments} First: $E(x) = \sum_{x_0} x_0 p_x(x_0)$; $n^{th}$:
$\overline{x^n} = E(x^n) = \sum_{x_0}x_0^np_x(x_0)$.

\paragraph{Central Moments} Second ({\em variance}): $\sigma_x^2 = E \{ [x
- E(x)]^2 \} =  E(x^2) - [E(x)]^2$ ($\sigma_x$ is {\em standard
deviation}); $n^{th}$: $E \{ [x - E(x)]^n \} = \sum_{x_0}[x_0 -
E(x)]^np_x(x_0) = \overline{(x - \overline{x})^n}$.  ($c$ is a constant) $\sigma_c^2 = 0$; $\sigma_{cx}^2=c^2\sigma_x^2$; if $x$ and $y$ are independent, $\sigma_{x+y}^2 = \sigma_x^2 + \sigma_y^2$.

\paragraph{PDF} ${\normalsize Prob}(a < x \leq b) = \int_a^b
f_x(x_0)dx_0$. ${\normalsize Prob}(x_0 < x \leq x_0 + dx_0) =
f_x(x_0)$.

\paragraph{CDF} $F_x(x_0) = p_{x \leq x_0}(x_0) = {\normalsize
Prob}(x \leq x_0) = \int_{-\infty}^{x_0} f_x(x_0)dx_0$.  $f_x(x_0) =
\frac{dF_x(x_0)}{dx_0}$.  ${\normalsize Prob}(a < x \leq b) = F_x(b) -
F_x(a)$.

\paragraph{Conditional PDF} $f_{x,y \mid A}(x_0,y_0 \mid A) =
\frac{f_{x,y}(x_0,y_0)\cdot(x_0,y_0 \in A)}{P(A)}$. 

\paragraph{Derived PDF's} {\sc first step:} Determine probability of
event $g \leq g_0$ for all values of $g_0$.  {\sc second step:}
Differentiate this quantity with respect to $g_0$ to obtain
$f_g(g_0)$.


\paragraph{S Transform} $f_x^T(s) \equiv E(e^{-sx}) =
\int^{\infty}_{-\infty}e{-sx}f_x(x_0)dx_0$; $\frac{d^nf_x^T(s)}{ds^n} =
\int_{x_0 = -\infty}^{\infty}(-x_0)^ne^{-sx_0}f_x(x_0)dx_0$ \\
$[f_x^T(s)]_{s=0} = 1$ \hspace{1 cm} 
$E(x) = - [ \frac{df_x^T(s)}{ds}]_{s=0}$ \hspace{1 cm}
$E(x^2) = [ \frac{d^2f_x^T(s)}{ds^2}]_{s=0}$ \\
$\sigma_x^2 = E(x^2) - [E(x)]^2 =
\{\frac{d^2f_x^T(s)}{ds^2}-[\frac{df_x^T(s)]^2}{ds} \}_{s=0}$  

\paragraph{Z Transform} $p_x^T(z) \equiv E(z^x) =
\Sigma_{x_0=0}^{\infty}z^{x_0}p_x(x_0)$ \\
$\frac{d^np_x^T(z)}{dz^n} =
\Sigma_{x_0=0}^{\infty}x_0(x_0-1)(x_0-2)\cdots(x_0-n+1)z^{x_0-n}p_x(x_0)$
\\
$[p_x^T(z)]_{z=1} = 1$ \hspace{1 cm} 
$E(x) = [ \frac{dp_x^T(z)}{dz}]_{z=1}$ \hspace{1 cm}
$E(x^2) = [ \frac{d^2p_x^T(z)}{dz^2} + \frac{dp_x^T(z)}{dz} ]_{z=1}$  \\ 
$\sigma_x^2 = [[ \frac{d^2p_x^T(z)}{dz^2} + \frac{dp_x^T(z)}{dz} ]_{z=1} -
[\frac{dp_x^T(z)}{dz}]^2 ]_{z=1} $  

\paragraph{Sum of Random variables} ($w = x+y$, $x,y$ independent)
$f_x(w_0) = \int_{x_0=-\infty}^{\infty}dx_0f_x(x_0)f_y(w_0-x_0)$.
Equivalently, in transform world: $f_x^T(s) = f_x^T(s)f_y^T(s)$ and
$p_x^T(z) = p_x^T(z)p_y^T(z)$ . For any random variables $x$ and $y$,
$E(x+y) = E(x) + E(y)$. $\sigma_w^2 = \sigma_x^2 + \sigma_y^2$ if $x,y$ are
linearly independent.

\paragraph{Random number of iid random variables} $(r=x_0+x_+\cdots x_n)$ \\
$f_r^T(s) = p_n^T[f_x^T(s)]$. \hspace{1 cm} $E(r) = E(n)E(r)$.
\hspace{1 cm} $\sigma_r^2 =  E(n)\sigma_x^2 + [E(x)]^2\sigma_n^2$.

\paragraph{Infinite Sums} $\Sigma_{x=0}^{\infty}a^{k-1}k=\frac{1}{(1-a)^2}$
\hspace{1 cm}
$\sum_{k=1}^{\infty} \frac{(-1)^{k+1}x^{k}}{k} = \ln(1+x)$
\hspace{1 cm}
$n! = \sqrt{2\pi}e^{-n}n^{(n+0.5)}$


\paragraph{Bernoulli} Trial: \\
\[ p_x(x_0) = \left\{ \begin{array}{ll}
                         1-P & x_0 = 0 \mbox{(a ``failure'')} \\
                         P   & x_0 = 1 \mbox{(a ``success'')} \\
                      \end{array}
               \right. \] 
$p_x^T(z) = 1-P+zP$ \hspace{1 cm} $E(x) = P$ \hspace{1 cm} 
$\sigma_x^2=P(1-P)$ \\

Process: $k$ is sum of $n$ independent Bernoulli random variables. (Binomial)\\
$p_k(k_0) = \left( \begin{array}{l} n \\ k_0 \end{array} \right)
P^{k_0}(1-P)^{n-k_0}$ \hspace{1 cm} $k_0 = 1, 2, \ldots, n$
\\
$p_k^T(z) = (1 - P + zP)^n$ \hspace{1 cm} $E(k) = nP$ \hspace{1 cm}
$\sigma_k^2 = nP(1-P)$ \\

Interarrival Times: (Geometric, Pascal) \\
$P_{l_1}(l) = P(1-P)^{l-1}$ \hspace{1 cm} $l = 1,2,\ldots$ 
\hspace{1 cm} $p_{l_1}^T(z) = \frac{zP}{1-z(1-P)}$ \hspace{1 cm}
$E(l_1) = \frac{1}{P}$ \hspace{1 cm}
$\sigma_{l_1}^2 = \frac{1-P}{P^2}$ \\
$P_{l_r}(l) = \left( \begin{array}{l} l-1 \\ r-1 \end{array}\right)
P^r(1-P)^{l-r}$ \hspace{1 cm} $l = r,r+1,r+2,\ldots$; $r=1,2,\ldots$ \\ 
$p_{l_r}^T(z) = [\frac{zP}{1-z(1-P)}]^r$ \hspace{1 cm} $E(l_r) =
\frac{r}{P}$ \hspace{1 cm} $\sigma_{l_r}^2 = \frac{r(1-P)}{P^2}$ \\


\paragraph{Poisson Process} First-order interarrival times are independent
identically distributed exponential random variables.  $k$ is the number of
arrivals in an interval of duration $t$. \\
$p_k(k_0) = \frac{(\lambda t)^{k_0}e^{-\lambda t}}{k_0!}$ \hspace{1 cm}
$t\geq 0$; $k_0 = 0, 1, 2, \ldots$ \hspace{1 cm}
$p_k^T(z) = e^{\lambda t(z-1)}$ \hspace{1 cm} $E(k) = \lambda t$ \hspace{1 cm}
$\sigma_k^2 = \lambda t$ \\

Interarrival Times: (Erlang)\\

$f_{l_1}(l) = \lambda e^{-\lambda l}$ \hspace{1 cm} $l \geq 0$ \hspace{1 cm}
$f_{l_1}^T(s) = \frac{\lambda}{\lambda + s}$ \hspace{1 cm}
$E(l_1) = \frac{1}{\lambda} $ \hspace{1 cm} 
$\sigma_{l_1}^2 = \frac{1}{\lambda^2}$ \\
$f_{l_r}(l) = \frac{\lambda^rl^{r-1} e^{-\lambda l}}{(r-1)!}$ \hspace{1 cm} $l \geq 0$;
$r=1, 2, \ldots $ \hspace{1 cm}
$f_{l_r}^T(s) = (\frac{\lambda}{\lambda + s})^r$ \hspace{1 cm}
$E(l_r) = \frac{r}{\lambda} $ \hspace{1 cm} 
$\sigma_{l_r}^2 = \frac{r}{\lambda^2}$ \\

\paragraph{Combined Poisson Processes} $\lambda_a$ and $\lambda_b$ are
average interarrival time for two independent, simultaneous poisson
processes. \\
Prob(next event type A) = $\frac{\lambda_a}{\lambda_a + \lambda_b}$\\
$N$ is total number of events while waiting for $R$ events of type A. \\
$P_N(N_0) = \left( \begin{array}{l} N_0-1 \\ R-1 \end{array}\right) 
\left(\frac{\lambda_a}{\lambda_a + \lambda_b}\right)^R
\left(\frac{\lambda_b}{\lambda_a + \lambda_b}\right)^{N_0-R}$;  $N_0 = R, R+1,
\ldots$; $R = 1, 2, 3, \ldots$ \\

\paragraph{Renewal Process} First-order interarrival times are mutually
independent and described by the same PDF.

\paragraph{Random Incidence} $x$ 1st order interarrival time; $y$ remaining
gap length; $w$ incident gap length: \\
$p_w(w_0) = \frac{w_0p_x(w_0)}{E(x)}$ \hspace{1 cm}
$f_w(w_0) = \frac{w_0f_x(w_0)}{E(x)}$ \hspace{1 cm} 
$f_{y \mid w}(y_0 \mid w_0) = \frac{1}{w_0}$ \hspace{ 0.5 cm} 
$0 \leq y_0 \leq w_0$ \hspace{1 cm} $E(w) = \frac{E(x^2)}{x}$\\
$f_{y,w}(y_0,w_0) = \frac{f_x(w_0)}{E(x)}$ \hspace{ 0.5 cm} 
$0 \leq y_0 \leq w_0 \leq \infty$ \hspace{ 1 cm} 
$ f_y(y_0) = \int_{y_0}^{\infty}\frac{f_x(w_0) dw_0}{E(x)} =
\frac{1-F_x(y_0)}{E(x)}$ \hspace{1 cm}
$E(y) = \frac{E(x)}{2}$ \\

\paragraph{Linear Algebra} Eigenvalues: $\det(A-\lambda I) = 0$;
Eigenvectors: all $\vec{x}$ satisfying $(A-\lambda I)\vec{x} = \vec{0}$;
For Markov Matrix probabilities to converge, it must be neutral stable.
Neutral stable: for all eigenvalues, $\lambda$, $\lambda \leq 1$, and for
one eigenvalue, $\lambda=1$.  For Markov Matrix, set up probability matrix
so columns sum to 1 (as opposed to rows as done in text/class -- take the
transpose of the matrix if it comes from class/text).  Then as $n \rightarrow
\infty$ for $A^n$, $p_{j,1}\ldots p_{j,m}$ all converge to $P_j$.
Alternately, solve for the eigenvector for $\lambda=1$ and normalize so
the values sum to 1 and you get the corresponding probability vector
$\vec{P}$. 

\paragraph{Book Markov} {\em Ergodic Theorem} says should be recurrent,
nonperiodic, and finite number of states.  Limiting state probabilities:
$P_j = \sum^m_{i=1}(P_i)(p_{ij})$;$\sum^m_{i=1}P_i = 1$.  {\bf Birth and
Death Processes} $P_{i+1} = \left( \frac{b_i}{d_{i+1}} \right) P_i$.  Then
normalize so probabilities sum to one.

\paragraph{Chebyshev Inequality} Prob $[|x-E(x)| \geq t] \leq 
\left( \frac{\sigma_x}{t} \right)^2$

\paragraph{Stochastic Convergence} Sequence $\{y_n\} = y_1,y_2,$\ldots, is
stochastically convergent to $C$ if, for every $\epsilon > 0$,
$\lim_{n\rightarrow\infty}$ Prob $(|y_n - C| > \epsilon) = 0$.

\paragraph{Weak Law for Large Numbers} 
\begin{equation}
\lim_{n\rightarrow\infty} \mbox{Prob} \left[ \left| \frac{1}{n}
\sum^n_{i=1}y_i - E(y) \right| \geq \epsilon \right] = 0
\end{equation}

\paragraph{Gausian} $f_x(x_0) =
\frac{1}{\sqrt{2\pi}\sigma_x}e^{-[x_0-E(x)]^2/2\sigma_x^2}$ \hspace{1 cm}
$-\infty \leq x_0 \leq \infty$ \hspace{1 cm} $f_x^T(s) =
e^{(s^2\sigma_x^2/2) - sE(x)}$.\\
PDf for sum of independent Gaussians random variables is a Gaussian PDF.

\paragraph{Unit Gausian} $f_y(y_0) = \frac{1}{\sqrt{2\pi}}e^{-y_0^2/2}$
\hspace{1 cm} $-\infty \leq x_0 \leq \infty$,  \hspace{1 cm} $E(y) = 0$, 
\hspace{1 cm} $\sigma_y=1$. \\
Normalize arbitrary Gaussian: $y =
\frac{x-E(x)}{\sigma_x}$.  CDF for unit Gaussian: $\Phi(y_0) \equiv
F_y(y_0)$. \\
CDF for arbitrary Gaussian: $F_x(x_0) = \Phi\left[ \frac{x_0 -
E(x)}{\sigma_x}\right]$.  $\Phi(-y_0) = 1-\Phi(y_0)$.  

\paragraph{Centeral Limit Theorem}
As $n\rightarrow\infty$, the CDF of any sum of random variables
approaches that of a Gaussian.  \\
$\lim_{n\rightarrow\infty}F_r(r_0) = \Phi\left[ \frac{r_0 -
E(r)}{\sigma_r}\right]$ \hspace{1 cm} $E(r) = nE(x)$ \hspace{1 cm}
$\sigma_r = \sqrt{n}\sigma_x$ 

\paragraph{Binomial PMF} When using the Central Limit Theorem to
approximate the binomial PMF (P close to 0.5): \\
$\mbox{Prob}(a \leq k\leq b) \approx 
\Phi\left[ \frac{b+\frac{1}{2}-nP}{\sqrt{nP(1-P)}} \right]
- \Phi\left[ \frac{a-\frac{1}{2}-nP}{\sqrt{nP(1-P)}} \right]$ \\
For P or (1-P) small and $n$ large, use Poisson approximation: 
$\lim_{n\rightarrow\infty} p_k(k_0)=\frac{(nP)^{k_0}e^{-(nP)}}{k_0!}$


\paragraph{Significance Tests} Let $\alpha$ be level of significance.
Select ``unlikely'' range for variable.  Select unlikely range such that:
Prob(value in unlikely range) = $\alpha$.  Run test/experiment.  If value
in unlikely range, reject; otherwise, accept.

\paragraph{Hypothesis Testing} $\alpha$ = probability of false rejection of
$H_0$ given $H_0$ is true; $\beta$ = condictional probability of false
accpetance of $H_0$ given $H_0$ is false (i.e.\  $H_1$ is true). [n.b. if
$H_0$ centered to left, $\beta$ is left tail of $H_1$.]

\paragraph{Cost Analysis} $E(\mbox{cost}) = 
\mbox{Cost(false acceptance of }H_0\mbox{)}(1 - P(H_0))\beta + 
\mbox{Cost(false rejection of }H_0\mbox{)}P(H_0)\alpha + $\\
$\mbox{Cost(valid acceptance of}H_0\mbox{)}P(H_0)(1-\alpha) + 
\mbox{Cost(valid rejection of }H_0\mbox{)}(1 - P(H_0))(1-\beta)$.

\paragraph{Estimators} $Q$ sequence is consistent if:
$\lim_{n\rightarrow\infty} \mbox{Prob} \left( \left| Q_n - Q \right| 
 > \epsilon \right) = 0$ \hspace{ 0.5 cm} for any $\epsilon > 0$. \\ 
$Q_n$ is an unbiased estimator of $Q$ if: $E(Q_n)=Q$ for $n$ = 1,2,\ldots
\\ 
$Q_n$ is an asymptotically unbiased estimator of $Q$ if: 
$\lim_{n\rightarrow\infty} E(Q_n)=Q$

\paragraph{Maximal Likelihood Estimator} Express {\it a priori} probability
of obtaining Experimental result as a function of the parameter of
interest.  $Q^*$ is the parameter $Q$ which maximizes this {\it a priori}
probability ({\it i.e.\ } differentiate the probability expression with
respects to $Q$, solve for 0 of the derivative to maximize expression, will
get expression for $Q^*$ in terms of the experimental results).











\end{document}

