\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} \begin{center} \Large{\textbf{Stat 455 Cheat Sheet}} \\ \end{center} %************************************************* %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 (?). \\ % \verb!slides! & Large sans-serif font. % \end{tabular} % $E[X]= \sum{xp(x)}$ \\ % $P_{X|Y}(x|y) = \frac{p(x,y)}{p_{y}(y)}$\\ %************************************************* \section{Chapter 3} \subsection{Conditionals} discrete pmf $P(X=x)$ \\ continuous pdf $f_X(x) = P(x \le X \le x+dx)$\\ $E[X] = \int_{-\infty}^{\infty}xf_X(x)dx = \sum_{x \in S} xP(X=x)$\\ $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)$\\ conditional pmf: $p_{X|Y}(x,y) = P(X=x|Y=y)=\frac{P(X=x,Y=y)}{P(Y=y)}$\\ $E[X|Y=y] = \sum_{x}xP(X=x|Y=y)=\sum_{x}xp_{X|Y}(x|y)$\\ $E[X] = \sum_{y}E[X|Y=y]P(Y=y)$ \\ $~~~~~~~=\int_{-\infty}^{\infty}E[X|Y=y]f_{Y}(y)dy$ \\ \section{Chapter 4} \subsection{Discrete Time Markov Chains} Markov Property\\ $P(X_{n+1}=j|X_{n}=i_{n}, X_{n-1}=i_{n-1},\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)$\\ Transition Probabilities\\ $P_{ij}=P(X_{n+1} = j|X_{n}=i)=P(X_{1} = j|X_{0}=i_{})$\\ $P_{ij}^{k}=P(X_{n+k} = j|X_{n}=i)=P(X_{k} = j|X_{0}=i_{})$\\ State J is \emph{accessible} from I if $P_{ij}^{n}=(P(X_{n}=j|X_{0}=i)>0$,some $n>0$\\ 2 states \emph{communicate} $(i\leftrightarrow j)$if they 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. \\ If $N(i)$ is the number of times we visit state i, we say a state is \emph{recurrent} if it is visited infinitely often, ie:\\ $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$\\ $f_i = P (\text{enter state i } | \text{ in state i} )$\\ If a state is not recurrent then it is \emph{transient}, $f_i < 1, ie:$\\ $\lim_{k \to \infty}P(N(i)\ge k|X_0=i)=0 \Rightarrow P(N(i)=\infty|X_0=i)=0$\\ state i recurrent $\iff \sum_{n=1}^{\infty}P_{ii}^{n}=\infty$\\ state i transient $\iff \sum_{n=1}^{\infty}P_{ii}^{n} < \infty$\\ recurrence is a \emph{class property}, a class property is one such that if state i has the property and $i \leftrightarrow j$ then j has the property too.\\ 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$\\ \emph{period} of a state,d,=\\ $d=gcd(n \ge 1 : 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.\\ A MC is \emph{ergodic} if it is positive recurrent and aperiodic.\\ For an irreducible and ergodic MC $lim_{n\to \infty} P_{ij}^{n} = \pi_j$ is independent of i.\\ $\pi_j$ is the solution of $\pi_j = \sum_{i=0}^{\infty}\pi_i P_{ij}$\\ note $\sum_{j=0}^{\infty}\pi_j=1$\\ $\pi_i$ are the \emph{limiting probabilities}. Put them in a vector $(\pi_1,\ldots,\pi_j)$ and that is your \emph{stationary distribution}.\\ A MC is \emph{reversible} wrt $\{\pi=i\}_{i\in S} \iff \pi_i P_{ij}=\pi_j P_{ji} $ this is the \emph{local balance equation}\\ For $X_n$ a Markov Chain, $Y_n = X_{-n}$ is the \emph{reverse process}.\\ Define the \emph{mean return time} to be $m_{jj} = inf\{n \ge 1|X_n =j\}$\\ $\pi_j m_{jj} = 1$ and $\pi_j = \frac{1}{\mathcal{C}_j}$\\ \emph{Kolmogorov Equations}\\ ${\bf P}(n+m)={\bf P}(n){\bf P}(m)$\\ $P_{ij}^{n+m}=\sum_{k=0}^{\infty}P_{ik}^{n}P_{kj}^{m}$\\ $P_{ij}^{n+1}=P(X_{n+1}=j|X_0=i)=$\\ ~~~~~~$\sum_sP(X_{n+1}=j|X_1=s,X_0=i)P(X_1=s|X_0=i)$\\ \section{Chapter 5} \subsection{Exponential Distribution} %\bf{exponential distribution} $f(x) = \lambda e ^ {-\lambda x} , x > 0$\\ $F(x) = \int_{-\infty}^{x}{f(x)dx}=1-e^{-\lambda x}$ \\ $E[X] = 1/\lambda$\\ $E[X^2]=2/\lambda^2$\\ \subsection{Memoryless RV} $P\{X > s + t | X > t\}=P\{X > s\}=e^{-\lambda 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 0$ \item $N(t)$ is integer valued \item If $s < t$ then $N(s) \le N(t)$ \item For $s t) = P ( N(t)=0)=e^{-\lambda t}$\\ $P(T_n > t) = e^{-\lambda t}$\\ \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}$ \item $q_{i,i+1} = \lambda_i$ \item $q_{i,i-i} = \mu_i $ \item $q_{ii}=0$ \item Knowing q's can give us P, but knowing P can't give us q's \end{itemize} \subsection{Transition Probability Function} Move from state i to state j in a time t later. \\ $P_{ij} = P(X(t)=j|X(0)=i) $ a continuous function. \\ \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} }}$\\ $T_i$ is the holding time in state i $\sim exp(-v_i)$\\ $P(T_i > h) = e^{v_i h}$\\ \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$ In the \emph{discrete} case $\pi$ may exists but limiting probabilities may not (if discrete chain is not aperiodic)\\ In the \emph{continuous} case there is no similar problem, if $\pi$ exists it is unique a and the above limit holds. \subsection{Embeded Chains} $\{X(t)\}_{t \ge 0}$ a CTMC\\ $\pi$ - stationary distribution of X\\ $\psi$ - stationary distribution of the embedded discrete time MC\\ $\psi_j=\frac{\pi_j v_j}{\sum_{i \in S}\pi_i v_i} , \pi_j=\frac{\psi_j/v_j}{\sum_{i \in S}\psi_i/v_i}$\\ $\psi_j$ - long run proportoin of transitions that CTMC makes into state j\\ $1/v_J$ - average time it stays in state j\\ $\psi_j/v_j$ - long run proportion of time the CTMC spends in state j\\ Note: $\psi$ may exist and $\pi$ may not! \\ \subsection{Local Balance Equation for CTMC} $\pi_iq_{ij}=\pi_j q_{ji}$ means rate of flow from i to j = rate of flow from j to i\\ \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}$ \\ $X \sim \text{Bernoulli}(p)$ means that you have an even with probability of success p. \\ $X \sim \text{geometric}(p)$ means X is the number of Bernoulli trials until success.\\ ~~~~$p(n) = p\{X=n\}=(1-o)^{n-1}p$\\ $X \sim \text{binomial}(n,p)$ X is the number of successes in n trials.\\ ~~~~$p(i)= \binom{n}{i}p^{i}(1-p)^{n-i}$\\ $\binom{n}{i} = \frac{n ! }{(n-i) ! i ! }$\\ $\sum_{i=0}^{N}\binom{N}{i}=(1+1)^N=2^N $\\ $\sum_{i=1}^{k}m^i = \frac{m(1-m^k)}{1-m}$\\ \section{Infitesimal Generator: G} $g_{ij}=q_{ij}, i \ne j$\\ $g_{ii}=-v_i$ (note: on last 2 lines, entries not probabilities\\ $[P\prime (t)]_{ij}=[GP(t)]_{ij}$\\ $P\prime(t)=GP(t)$(K's backwards eqn)\\ $P\prime(t)=P(t)G$ (K's forward eqn)\\ $P(t)=e^{tg} = \sum_{n=0}^{\infty}\frac{(tG)^n}{n!}$\\ $a$\\ \section{Stationary Distribution for a CTMC} $\pi = \pi P(t)$\\ $\sum\pi = 1$\\ If the initial distribution of $X(0)$ is $\pi$ then the distribution of $X(t)$ will also be $\pi, t > 0$. $(P(X(t)=j)=\pi_j \forall j \in S, t > 0$\\ $\sum_{i \in S}p_{ij}(t)\pi_i=\pi_j$\\ \section{Global balance equation for CTMC} $0=\pi G$\\ $v_j\pi_j=\sum_{i\ne j}q_{ij}\pi_i$ this is the jth row of the matrix \\ $\Rightarrow$ long run rate out of j = long run rate into state i\\ $\pi_i$ long run proportion of time that process in in state j.\\ $v_j$ rate of leaving state j\\ $\pi_j v_j $ long run rate of leaving j\\ $\pi_i q_{ij} $ long run rate of going from state i to j\\ \newpage \begin{itemize} \item \item \item \end{itemize} \end{multicols} %\end{landscape} \end{document}