\documentclass[10pt,landscape]{article}
\usepackage{multicol}
\usepackage{calc}
%\usepackage{amssymb} 
\usepackage{amssymb,amsmath} 
%\usepackage{lscape}

\usepackage[left=2cm,top=2cm,right=2cm, bottom=2cm]{geometry}

% 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}}
                                {\normalfont\normalsize\bfseries}}
\renewcommand{\subsection}{\@startsection{subsection}{2}{0mm}%
                                {-1explus -.5ex minus -.2ex}%
                                {0.5ex plus .2ex}%
                                {\normalfont\small\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}
%\begin{landscape}
\raggedright
\footnotesize
\begin{multicols}{3}
\tiny

% 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}
%*************************************************
%for a 2 column table

% \begin{tabular}{@{}ll@{}}
% \verb!book!    & Default is two-sided. \\
% \verb!report!  & No \verb!\part! divisions. \\
% \verb!article! & No \verb!\part! or \verb!\chapter! divisions. \\
% \verb!letter!  & Letter (?). \\

% \end{tabular}

% $E[X]= \sum{xp(x)}$ \\
% $P_{X|Y}(x|y) = \frac{p(x,y)}{p_{y}(y)}$\\

%*************************************************

\section{Chapter 3}
X - discrete RV:\\
pmf - $P(X=x) = f_X(X)$\\
$E[X]=\sum_{x \in S} {xP(X=x)}$\\
$E[X^{n}] = $nth moment\\
$Var[X]=E[(X-E[X])^2]$\\
\vspace{0.1cm}
X - continuous RV:\\
pdf - $f_X(x) = P(x \le X \le x+dx)$\\
$E[X] = \int_{-\infty}^{\infty}{xf_X(x)dx}$\\
$E[X^n] = \int{-\infty}^{\infty}x^n f_X(x)dx$\\
\vspace{0.1cm}
Relationships:\\
$P(A|B) = \frac{P(A \cap B)}{P(B)}$ \\
Bayes: $P(A)=P(A|B)P(B)+P(A|B^C)P(B^C)$\\
discrete - $P_{X|Y}(x,y) = P(X=x|Y=y)=\frac{P(X=x,Y=y)}{P(Y=y)}$\\
continuous - $F_{X|Y}(x,y) = P(X \le x|Y=y) = \sum_{a \le X} {P_{X|Y} (x|y)}$\\
$E[X|Y=y] = \sum_{x}xP(X=x|Y=y)=\sum_{x}x P_{X|Y}(x|y)$\\
expectation gives RV - $E[X|Y] = g(Y)$\\
\vspace{0.1cm}
X $\perp$ Y:\\
$P_{X|Y}(x|y) = P_{X}(x)$\\
$F_{X|Y}(x|y) = F_{X}(x)$\\
$E[X|Y=y]=E[X] ~~ \forall y$\\
\vspace{0.1cm}
X,Y continuous, $f_{X}(x), f_{Y}(y)$, joint $f_{XY}(x,y)$: \\
$f_{X|Y}(X|Y) = \frac{f_{XY}(x,y)}{f_{Y}(Y)}$\\
$E[X|Y=y]=\int {x f_{X|Y} (x,y) dx}$\\
\vspace{0.1cm}
Law of Total Expectation:\\
discrete - $E[X] = \sum_{y}E[X|Y=y]P(Y=y)$ \\
continuous - $E[X] = \int {E[X|Y=y]f_{Y}(y)dy}$\\
general - $P(A) = \sum_{y} {P(A|Y=y)}$\\
law - $E[E[X|Y]] = E[X]$

\section{Chapter 4}
\subsection{Discrete Time Markov Chains}
Markov Property:\\
$P(X_{n+1}=j|X_{n}=i_{n}, \ldots,X_{0}=i_{0})=P(X_{n+1} = j|X_{n}=i_{n})$\\
Markov Property V2:\\
$P(X_{n+m} = j|X_{n}=i,\ldots,X_{0}=i_{0})=P(X_{n+m} = j|X_{n}=i)$\\
Time Homogeneous:\\
$P(X_{n+m}=j|X_m = i) = P(X_{n+m+k} = j | X_{m+k} = i)$\\
Transition Probabilities:\\
$P_{ij}=P(X_{n+1} = j|X_{n}=i)=P(X_{1} = j|X_{0}=i_{n})$\\
k-step - $P_{ij}^{k}=P(X_{n+k} = j|X_{n}=i)=P(X_{k} = j|X_{0}=i_{n})$\\
\vspace{0.2cm}
Chapman-Kolmogorov:\\
$P(n+m) = P(n)P(m)$\\
$P(n) = P(1)^n$\\
$\therefore P_{ij} = P(X_{n+1}=j|X_0 = i) = \sum_{s}{P_{sj}^n P_{is}}=$\\
$~~~~~~~ = (i,j)^{th} ~ entry ~ of ~ P(1)P(n)$\\
* the transition prob matrix is stochastic - $\sum_{j \in S} {P_{ij} = 1 } ~~ \forall i \in S$\\
\vspace{0.1cm}
Classification of States:\\
j is \emph{accessible} from i if $P_{ij}^{n}=(P(X_{n}=i|X_{0}=j)>0$, for $n>0$\\
2 states \emph{communicate} $(i\leftrightarrow j)$if they can access each other \\
If 2 states communicate they are in the same \emph{class}. \\
Any 2 classes are identical or disjoint. \\
A MC is \emph{irreducible} if it has only one class. \\
\vspace{0.1cm}
Recurrence/Transience: \\
Define $N(i)$ to be the number of times we visit state i\\
Define $f_i$ to be the probability of entering i, given we start in i\\
State i is: ~~~~~ recurrent: if $f_i = 1$ ($N(i)=\infty$)\\
~~~~~~~~~~~~~~~~~~~ transient: if $f_i < 1$\\
Recurrence and transience are \emph{class properties}\\
At least one state \emph{must} be recurrent.\\
A finite state-space irreducible MC is recurrent.\\

recurrent:\\
$P(N(i) \ge k | X_0 = i ) = (f_i)^k = 1 \iff \lim_{k \to \infty} P(N(i) \ge k|X_0 = 1) $\\
$\Rightarrow P(N(i) = \infty | X_0 = i ) = 1$\\
$\iff \sum_{n=1}^{\infty}P_{ii}^{n}=\infty$\\
transient:\\
$\lim_{k \to \infty}P(N(i)\ge k|X_0=i)=0 \Rightarrow P(N(i)=\infty|X_0=i)=0$\\
$\iff \sum_{n=1}^{\infty}P_{ii}^{n} < \infty$\\

A state is \emph{positive recurrent} if for $\mathcal{C}=min\{n \ge 1 | X_n = j\}, E[\mathcal{C}_j|X_0=j]<\infty$\\
A state is \emph{null recurrent} if $E[\mathcal{C}_j|X_0=j] =\infty$\\
For finite state-space MC, recurrent $\Rightarrow$ positive recurrent\\
\vspace{0.1cm}
Period:\\
\emph{Period} of a state $d=gcd(n | P_{ii}^{n}>0)$\\
$P_{ii}^{n}>0 \iff d | n $\\
$P_{ii}^{n}=0 \iff d \nmid n $\\
A state is \emph{aperiodic} if its period is 1.\\
Period is a class property\\
A MC is \emph{ergodic} if it is positive recurrent and aperiodic.\\
\vspace{0.1cm}
Stationary Distbn / Generating Fns:\\
$\{X_n\}_{n \ge 0}$ - positive-recurrent MC, with stationary distbn $\{\pi_{ij} \}_{j \in S}$\\
$T_{j}= inf \{ n \ge 1 | X_n = j\}$ ~~~~~~ $m_{ij} = E[T_j|X_0 = j] \Rightarrow m_{jj}\pi_{j}=1$\\
Recurrent MC with stationary distbn is actually \emph{positive-recurrent}\\
$\pi_j m_{jj} = 1 \Rightarrow \pi_j \neq 0 \Rightarrow m_{jj} = \frac {1}{\pi_{j}} < \infty$\\
A MC is \emph{reversible} wrt a distribution $\{ \pi_{i}\}_{i \in S} \iff \pi_i P_{ij} = \pi_j P_{ji}$\\
If a MC is irreducible, aperiodic, and has a stationary distbn $\{ \pi_{i} \}_{i \in S}$ then:
$lim_{n\to \infty} P_{ij}^{n} = \pi_j \forall j \in S$\\
Note: $\sum_{j=0}^{\infty}\pi_j=1$\\
\vspace{0.1cm}
Reversibility:
Take $\{ X_n \}_{n \ge 0}$ a MC w. stationary distbn\\
$\{ \pi_i \}_{i \in S}$ - long-run proportion of transitions \emph{out} of state i\\
$P_{ij}$ - probability of going from i to j\\
$\pi_i P_{ij} $ - long-run proportion of transitions from i to j\\
$\pi_j = \sum_{i \in S} \pi_i P_{ij}$ - \emph{Global Balance Equation}\\
$\pi_j P_{ji} = \pi_i P_{ij}$ - \emph{Local Balance Equation}\\
\vspace{0.1cm}
Reversible MC:\\
A MC is \emph{reversible} wrt a stationary distbn if the Local Balance Eqn holds.\\
If a MC is reversible wrt $\{ \pi_i \}_{i \in S}$ then $\{ \pi_i \}_{i \in S}$ is a stationary distbn.\\
If $\{ X_n \}_{n \in \mathbb{Z}} = \{ \dots, X_{-n}, X_{-n+1}, \dots, X_0, \dots, X_n, \dots\}$ is a MC then 
$\{ Y_n \}~with~Y_n = X_{-n}$ is a MC, and is called the \emph{reversed process}\\

\section{Chapter 5}
\subsection{Exponential Distribution}
%\bf{exponential distribution} 
$f(x) = \lambda e ^ {-\lambda x}$\\
$F(x) = \int_{-\infty}^{x}{f(x)dx}=1-e^{-\lambda x}$

\subsection{Memoryless RV}
$P\{X > s + t | X > t\}=P\{X > s\}$

\subsection{Gamma Distribution}
$X_i$ drawn idd $\sim exp(\lambda) \Rightarrow X_1+\ldots+X_n $is gamma$(n,\lambda) f(t)=\lambda e^{-\lambda t}\frac{(\lambda t )^{n-1}}{(n-1)!}$

\subsection{Comparing Exponentials}
$P\{X_1 < X_2\} = \int_0^\infty{P\{X_1 < X_2|X_1=x\}\lambda_1 e^{-\lambda_1 x}dx}=\int_0^\infty{P\{x<X_2\}\lambda_1e^{-\lambda_1 x}dx}=\frac{\lambda_1}{\lambda_1+\lambda_2}$

\subsection{Counting Process}

  $\{N(t), t \ge 0\}$ is a counting process if:
  
  \begin{itemize}
    \item $N(t) > 0$
    \item $N(t)$ is integer valued
    \item If $s < t$ then $N(s) \le N(t)$
    \item For $s<t, N(t)-N(s)$ equals the number of events that occur in the interval $(s,t]$
  \end{itemize}
  
\subsection{Independent Increments}
If the numbers of events that occur in the disjoint time intervals are independent 

\subsection{Poisson Process}
A counting process $\{N(t), t \ge 0\}$ is a Poisson process with rate $\lambda$ if:
  \begin{itemize}
    \item $N(0)=0$
    \item $N(t)$ has independent increments
    \item Number of evens in a time interval of length t is Poisson with $\lambda$:\\
    $P\{N(t+s)-N(s)=n\}=e^{-\lambda t}\frac{(\lambda t)^n)}{n!}, n=0,1,\ldots$
  \end{itemize}

\subsection{$o(h)$ Functions}
A function $f(\dot)$ is $o(h)$ if\\
$\lim_{h\to\infty}\frac{f(h)}{h}=0$

\subsection{Poisson Process 2}
	\begin{itemize}
   		\item $N(0)=0$
		\item The process has stationary and independent increments
		\item $P\{N(h)=1\}=\lambda h + o(h)$
		\item $P\{N(h) \ge 2\} = o(h)$
	\end{itemize}
	
\subsection{Interarrival Time}
$T_n$is the time between the $(n-1)$st and  $n$th events. $\{T_n\}$ is the {\bf sequence of internarrival times} with $T_n \sim $ exp$(\lambda)$

\subsection{Waiting Time}
$S_n = \sum_{i=1}^{n}{T_i} \sim $gamma(n,$\lambda$)

\section{Chapter 6}

\subsection{Continuous Time Markkov Chain}
$\{X(t), t \ge 0\} \forall s,t \ge 0$, non-neg ints $i,j,x(u),0 \le u < s$  
has 
$P\{X(t+s)=j|X(s)=i,X(u)=x(u),0\le u \le s\} $\\
$=P\{X(t+s)=j|X(s)=i\}$

\subsection{Stationary Transition Probabilities}
A CTMC has these if $P\{X(t+s)=j|X(s)=i\}$

\subsection{CTMC Alternate Definition}
A stochastic process having these properties each time it enters state i:
\begin{itemize}
	\item The amount of time it spends in that state before make a transition into a different state $\sim exp(\lambda)$ with mean $1/v_i$
	\item when the process leaves state i, it enters state j with some probability $P_{ij}$ and \\
		$P_{ii} = 0$ all i\\
		$\sum_{j}{P_{ij}}=1$, all i
\end{itemize} 



\subsection{Birth and Death Processes}
A system with n people with
\begin{itemize}
	\item $\{\lambda_n\}_{n=0}^{\infty}$ the arrival/birth rate
	\item $\{\mu_n\}_{n=0}^{\infty}$ the departure/death rate
	\item	 $v_0=\lambda_0$
	\item	 $v_i=\lambda_i+\mu_i$
	\item	 $P_{01} = 1$
	\item	 $P_{i,i+1} = \frac{\lambda_i}{\lambda_i+\mu_i}$
	\item	 $P_{i,i-1} = \frac{\mu_i}{\lambda_i+\mu_i}$
\end{itemize}

\subsection{Transition Probability Function}
Move from state i to state j in a time t later

\subsection{Instantaneous Transition Rates}
$P_{ij}(t)=P\{X(t+s)=j|X(s)=i\}$\\
$q_{ij}=v_i P_{ij}$ is the rate, when in state i, at which the process makes a transition into state j.	\\
$v_i=\sum_j{v_i P_{ij}} = \sum_j{q_{ij}}$ \\
$P_{ij} = \frac{q_{ij}}{v_i} = \frac{q_{ij}}{\sum_j{q_{ij} }}$

\subsection{Chapman-Kolmogorov Equations}
$ P_{ij}(t+s) = \sum_{k=0}^{\infty}{P_{ik}(t) P_{kj}(s)} , \forall s,t \ge 0 $

\subsection{Kolmogorov's Backward Equations}
$P_{ij}^{\prime}(t)=\sum_{k\ne i}{q_{ik}P_{kj}(t)-v_i P_{ij}(t)}$

\subsection{Kolmogorov's Forward Equations}
$P_{ij}^\prime(t) = \sum_{k \ne j}q_{kj}{P_{ik}(t)-v_jP_{ij}(t)}$

\subsection{Limiting Probabilities}
$P_j \equiv \lim_{t \to \infty} {P_{ij}(t)}$
The limiting probs will exist if
\begin{itemize}
	\item all states communicate
	\item the chain is positive recurrent
\end{itemize}
Use that to get: \\
$v_j P_i = \sum_{k \ne j}{q_{kj}P_k}$, all states j \\
(leaving = entering)\\
$\sum_j{P_j}=1$

\subsection{Embeded Chains}
A ergodic CTMC has an embeded discrete-time ergodic MC with $P_{ij}$ and limiting probabilities $\pi_i$.\\
$P_i = \frac{\pi_i / v_i}{\sum_j \pi_j / v_j}$\\
$\pi_i = \sum_j \pi_j P_{ji}$

\subsection{Time Reversability}
For a long running MC, the amount of time the process spends in state $i$ is also exponentially distributed with rate $v_i$. We have the discrete time reversed chain:\\
$Q_{ij} = \frac{\pi_j P_{ji} }{\pi_i}$ and then\\
$\pi_i P_{ij} = \pi_j P_{ji} \forall i,j$ \\
$P_i q_{ij}=P_j q_{ji} \forall i,j$ 

\subsection{Computing the Transition Probabilities}
 need this?

\section{Chapter 8}
\subsection{Definitions}

\begin{tabular}{@{}ll@{}}
	$L$  		& average \# of customers in system \\ 
	$L_Q$	& average \# of customers waiting in queue \\
	$W$		& average amount of time a customer spends in system \\
	$W_Q$	& average amount of time a customer spends in queue \\
	$E[S]$	& average amount of time customer spends in service\\
	$N(t)$	& number of customer arrivals by time t\\
	
	$P_n$	& number of customers in system at time t \\
			&$ =\lim_{t \to \infty}P\{X(t)=n\}$ \\ 
			& $\bullet$ aka limiting/longrun/steady state probability that \\
			& ~~n customers are in the system\\
			& $\bullet$ also long run proportion of time that the system\\
			& ~~contains n customers\\
	$\lambda_a $ & average arrival rate of customers\\ 
			&$= \lim_{t \to \infty} \frac{N(t)}{t}$  \\

	$a_n$	& proportion of custs that find n in the system when arriving\\
	$d_n$	& proportion of custs that find n in the system when leaving\\
	
	
\end{tabular}

\subsection{Littile's Formula}
$L=\lambda_a W$
$L_Q=\lambda_a W_Q$

\subsection{Poisson Model}
Poisson arrivals see time averages. ie $P_n=a_n$. 

\subsection{M/M/1}
Customers arrive according to a Poisson process with rate $\lambda$. The time between successive
arrivals are independent rv with mean $1/\lambda$. If server free, cust goes in, else into queue. Service times are $\sim$exp$(\mu)$.\\ 

%this might be rather big for the cheat sheet, but it's oh so pretty
%\begin{align*}
		Balance Equations:\\
	$ \lambda P_0 				 = \mu P_1$\\
	$ (\lambda+\mu)P_n 		 = \lambda P_{n-1}+\mu P_{n+1} $\\
	$ P_1 					 = \frac{\lambda}{\mu}P_0$ \\
 	$ P_{n+1}	= \frac{\lambda}{\mu}P_n + ( P_n -  \frac{\lambda}{\mu}P_{n-1})  = \left(\frac{\lambda}{\mu}\right)^{n+1}P_{0}$\\
	$1=\sum_{n=0}^{\infty}P_n=\sum_{n=0}^{\infty}\left(\frac{\lambda}{\mu}\right)^n P_0 = \frac{P_o}{1-\lambda/\mu}$ or \\
	$\Rightarrow P_0 = 1 - \frac{\lambda}{\mu} , P_n= \left( \frac{\lambda}{\mu} \right) ^n (1-\frac{\lambda}{\mu})$\\
	$L=\sum_{n=0}^{\infty}nP_n=\frac{\lambda}{\mu-\lambda}$ \\
	$W=\frac{L}{\lambda}=\frac{1}{\mu-\lambda}$ \\
	$W_Q=W-E[S]=W-1/\mu=\frac{\lambda}{\mu(\mu-\lambda)}$\\
	$L_Q=\lambda W_Q  = \frac{\lambda^2}{\mu(\mu-\lambda)}$\\
%\end{align*}

\subsection{M/M/1 - Finite Capacity}
Now we have the limitation that $n \le N$.\\
		Balance Equations:\\
	$ \lambda P_0 			 = \mu P_1$\\
	$ (\lambda+\mu)P_n 		 = \lambda P_{n-1}+\mu P_{n+1} , 1 \le n \le N-1$\\
	$ \mu P_n 			= \lambda P_{n-1} $ , for state N \\
	$ P_1 					 = \frac{\lambda}{\mu}P_0$ \\
 	$ P_{n+1}	= \frac{\lambda}{\mu}P_n + ( P_n -  \frac{\lambda}{\mu}P_{n-1}) , 1 \le n \le N-1  $
	$ P_N= \frac{\lambda}{\mu}P_{N-1} \ldots = \left(\frac{\lambda}{\mu} \right)^N P_0 $\\ 
	$1=\sum_{n=0}^{\infty}P_n=P_0\sum_{n=0}^{\infty}\left(\frac{\lambda}{\mu}\right)^n  = P_0\frac{1-(\lambda/\mu)^{N+1)} }{1-\lambda/\mu}$ or \\
	$\Rightarrow P_0 = \frac{1-\lambda/\mu}{1- (\lambda/\mu)^{N+1}} , P_n=  \frac{(\lambda/\mu)^n(1-\lambda/\mu)}{1-(\lambda/\mu)^{N+1}}, n=0,\ldots,N$\\
	$L=\sum_{n=0}^{N}nP_n=\frac{(1-\lambda/\mu)}{1-(\lambda/\mu)^{N+1}}\sum_{n=0}^{N}n\left(\frac{\lambda}{\mu}\right)^n = $ \\
	$= \frac
		{
			\lambda[1+N(\lambda/\mu)^{N+1}-(N+1)(\lambda/\mu)^N]
		}
		{
			( \mu - \lambda ) (1 -(\lambda/\mu)^{N+1} )
		} $\\
	To find W we consider 2 cases.\\
	$\lambda_a=\lambda$ if ``customers in system'' includes those who never get in\\
	$\lambda_a=\lambda(1-P_N)$ if it does not. Either way we get:\\
	$W=\frac{L}{\lambda_a}$\\

\subsection{PASTA}
Poisson Arrivals See Time Averages\\
Let $\left\{X_i\right\}_{t \ge 0}$ a continuous-time Markov chain with stationary distribution $\pi$. Let $T_i$ be the arrival time of the $i^{th}$ element. These elements arrive
according to a Poisson process. \\
Then $\left\{X(T_n)\right\}_{t \ge 0}$ has $\pi$ as a stationary distribution.\\
$a_j = \pi_j$\\

\section{Other useful stuff}
$\sum_{n=0}^{\infty}nx^n=\frac{x}{(1-x)^2}$



\newpage





\begin{itemize}
	\item
	\item
	\item
\end{itemize}

\end{multicols}
%\end{landscape}
\end{document}