$E (Y) = i = 1 \sum n E (Y ∣ A_{i}) P (A_{i}) if A_{i} is partition of outcome space \Rightarrow average conditional probability P (B) = i = 1 \sum n P (B ∣ A_{i}) P (A_{i})$

rule of average conditional expectation

$E (Y) = x \sum E (Y ∣ X = x) P (X = x)$ aka the formula for $E (Y)$ by conditioning on $X$

conditional expectation of $Y$ given $X$

$E (Y ∣ X)$ is a function $g (x)$ of $x$ $E (Y) = x \sum E (Y ∣ X = x) P (X = x) = x \sum g (x) P (X = x) = E (g (x)) \Rightarrow E (Y) = E [E (Y ∣ X)]$

to find a function, find its value first and replace the parameter with variable

$E . g . E (X = x) = f (x) \Rightarrow E (X) = f (X)$

conditioning: continuous case

$f_{X ∣ Y} (X ∣ Y = y) = \frac{f ( x , y )}{\int _{R} f ( x , y ) d x} = \frac{f ( x , y )}{f _{Y} ( y )}$ if $f_{Y} (y) > 0$ $\Rightarrow f (x, y) = f_{X ∣ Y} (x ∣ Y = y) f_{Y} (y)$

probability over a region

$P (x \in D ∣ Y = y) = \int_{D} f_{X ∣ Y} (x ∣ Y = y) d x$

infinitesimal conditioning formula

$P (A ∣ X = x) = \frac{P ( A , X \in d x )}{P ( X \in d x )}$ $X \in d x X$ fall in small interval near $x$

conditional density of $Y$ given $X = x$

$f_{Y} (y ∣ X = x) = \frac{f ( x , y )}{f _{X} ( x )}$ $\Rightarrow \int f_{Y} (y ∣ X = x) d y = 1$

multiplication rule for density

$f (x, y) = f_{X} (x) f_{Y} (y ∣ X = x)$

averaging conditional probability

integral conditioning formula

$P (A) = \int P (A ∣ X = x) f_{X} (x) d x$

conditional expectation

$E [g (Y) ∣ X = x] = \int g (y) f_{Y} (y ∣ X = x) d y E [g (Y)] = \int E [g (Y) ∣ X = x] f_{X} (x) d x$

conditional variance

$v a r (X ∣ Y) \equiv E [(X - E [X ∣ Y])^{2} ∣ Y] = E [X^{2} ∣ Y] - (E [X ∣ Y])^{2}$

! another way to calculate variance

$Va r (X) = E [Va r (X ∣ Y)] + Va r (E [X ∣ Y])$

! for $X_{i}$ i.i.d. with number $N > 0$ independent to $X_{i}$

$E [i = 1 \sum N X_{i}] = E [X] E [N] Va r (i = 1 \sum N X_{i}) = E [N] Va r (X) + (E [X])^{2} Va r (N)$

Bayesian estimation

take the wanted parameter $θ$ as a random variable with distribution prior distribution take a sample and use it to update the posterior distribution

want $Θ$ in $X_{i} \sim d i s t r ib u t i o n (Θ)$ let $Θ \sim p r i orD i s t r ib u t i o n \Rightarrow f_{Θ} (θ)$ with observations (measurements) $X = (X_{1}, \dots, X_{n})$ know conditional distribution $f_{X ∣Θ} (x ∣ θ)$ $\Rightarrow$ posterior distribution $f_{Θ∣ X} (θ ∣ x) = \frac{f _{X ∣Θ} ( x ∣ θ ) f _{Θ} ( θ )}{f _{X} ( x )} = \frac{f _{X ∣Θ} ( x ∣ θ ) f _{Θ} ( θ )}{\int f _{X ∣Θ} ( x ∣ θ ^{'} ) f _{Θ} ( θ ^{'} ) d θ ^{'}}$ i.e. posterior = likelihood $\cdot$ prior $/$ evidence

it does not matter if the observation points are used one by one or all at once

conjugate prior

the posterior distribution is of the same type as the prior distribution

normal + normal = normal
binomial + Beta = Beta

indicator

$1_{A} (x) = {10 x \in A x \in / A \Rightarrow E [X ∣ A] = \frac{E [ X \cdot 1 _{A} ( X )]}{P ( A )}$

maximum a posteriori probability (MAP) rule

select $\hat{θ}$ so that posterior probability $f_{Θ∣ X} (θ ∣ x)$ is maximized $\Leftrightarrow$ maximize $f_{X ∣Θ} (x ∣ θ) f_{Θ} (θ)$

point estimation

select point estimate $\hat{θ}$ to represent best guess of $Θ$

estimator $\hat{Θ} = g (X)$

maximum a posteriori probability (MAP) estimator
conditional expectation estimator a.k.a. least mean squares (LMS) estimator $↓$

least mean squares (LMS) estimation

select an estimator/function with least squared error

base case

for $θ$ , want $\hat{θ}$ such that $E [(θ - \hat{θ})^{2}]$ is minimized $\Rightarrow$ choose $\hat{θ} = E [θ]$

general case

with observations $X = x$ , want $\hat{θ}$ to minimized $E [(θ - \hat{θ})^{2} ∣ X = x]$ $\Rightarrow$ choose $\hat{θ} = E [θ ∣ X = x]$

linear least mean squares estimation

the linear form of LMS

hypothesis testing

denote $H_{i}$ as event ${Θ = θ_{i}}$

MAP rule for hypothesis testing

choose $H_{i}$ iff it has a larger posterior $P (Θ = θ_{i} ∣ X = x)$ or equivalently $p_{Θ} (θ_{i}) f_{X ∣Θ} (x ∣ θ_{i})$

general case—two coins

coin 1 gets head by $p_{1}$ , coin 2 by $p_{2} > p_{1}$ toss an unknown coin, coin $θ$ , $n$ times and get $k$ heads choose $θ = 1$ iff $P (θ = 1∣ X = k) \geq P (θ = 2∣ X = k)$

critical $k^{*} \in N$ choose $θ = 1$ iff $k \leq k^{*}$
probability of getting error $P_{e} = P (θ = 1, X > k^{*}) + P (θ = 2, X \leq k^{*})$

property

$E [\hat{θ}] = E [E [θ ∣ X]] = E [X]$

$\tilde{θ} = θ - \hat{θ}$

$C o v (\hat{θ}, \tilde{θ}) = 0$
$Va r (θ) = Va r (\hat{θ}) + Va r (\tilde{θ})$

discrete Markov chain

the Markov property the past does not matter for the future, only the present does

$P (X_{n + 1} = j ∣ X_{0} = a, \dots, X_{n} = i) = P (X_{n + 1} = j ∣ X_{n} = i)$

discrete time
state space $S$ finite or countably infinite

one-step probability $P (X_{n + 1} = j ∣ X_{n} = i) = P (i, j) = p_{ij}$

does not change

transition probability matrix

$p_{11} ⋮ p_{m 1} \dots ⋱ \dots p_{1 m} ⋮ p_{mm}$

initial distribution $π_{0}$

$n$ -step transition matrix

$p_{ab}^{n} = P (X_{m + n} = b ∣ X_{m} = a)$

$p_{ij}^{n + m} = p_{ij}^{n} \cdot p_{ij}^{m} \Rightarrow P (X_{m + n} = j ∣ X_{0} = i) = k \in S \sum P (X_{m} = k ∣ X_{0} = i) P (X_{m + n} = j ∣ X_{m} = k)$ $P (X_{n} = k) = x \sum π_{0} (x) p_{x k}^{n}$

class structure

site $i$ leads to $j$ , i.e. $i ⟶ j$ $\exists n \geq 0, P (X_{n} = j ∣ X_{0} = i) > 0$ $i ⟶ j, j ⟶ i \Rightarrow i$ and $j$ are in the same class

closed class

can not go to another class

class $C (C \subseteq S)$ is closed, $i \in C, i ⟶ j \Rightarrow j \in C$

absorbing state

transient & recurrent

hitting time

let $A \subseteq S$ , hitting time of $A$ , $T_{A}$ : $T_{A} = {min {n > 0 : X_{n} \in A} \infty \exists n, X_{n} \in A \forall n, X_{n} \in / A \Rightarrow p_{x y}^{n} = m = 1 \sum n P_{x} (T_{y} = m) P_{yy}^{n - m}$

transient and recurrent state

$ρ_{x y} = P_{x} (T_{y} < \infty) = P (T_{y} < \infty∣ X_{0} = x)$ site $y$ is recurrent if $ρ_{yy} = 1$

always can get from $y$ to $y$ in finite steps

transient if $ρ_{yy} < 1$

number of times pass $y$

$N (y) = n = 1 \sum \infty 1_{y} (X_{n})$

$N (y) \geq 1$ iff $T_{y} < \infty$
$P_{x} (N (y) \geq 1) = P_{x} (T_{y} < \infty) = ρ_{x y}$ $P_{x} (N (y) \geq m) = P_{x} (T_{y} < \infty) P_{y}^{m - 1} (T_{y} < \infty) = ρ_{x y} ρ_{yy}^{m - 1}$
$\Rightarrow P_{x} (N (y) = m) = ρ_{x y} ρ_{yy}^{m - 1} (1 - ρ_{yy})$

$g (x, y) = E_{x} [N (y)] = n = 1 \sum \infty n P_{x} (N (y) = n) = n = 1 \sum \infty p_{x y}^{n}$

theorem

let $y$ be a transient state, then $P_{x} (N (y) < \infty) = 1$ and $g (x, y) = \frac{ρ _{x y}}{1 - ρ _{yy}} \forall x \in S$ which means $lim_{n \to \infty} p_{x y}^{n} = 0$
let $y$ be a recurrent state, then $P_{y} (N (y) = \infty) = 1$ and $g (y, y) = \infty$ and $P_{x} (N (y) < \infty) = ρ_{x y}$

result

$S$ is finite $\Rightarrow \exists$ at least $1$ recurrent state $y$
$y$ is recurrent, $y ⟶ z \Rightarrow z$ recurrent, $y, z \in$ the same closed class $ρ_{yy} = ρ_{yz} = ρ_{zz} = ρ_{zy} = 1$

you always get absorbed in a closed class of recurrent states after moving around

starting from $x$ , the probability to go in class ${x_{1}, \dots, x_{k}}$

$ρ_{{x_{1}, \dots, x_{k}}} (x)$

if $x \in {x_{1}, \dots, x_{k}}$ , then $ρ_{{x_{1}, \dots, x_{k}}} (x) = 1$
if $x \in$ another closed class, then $ρ_{{x_{1}, \dots, x_{k}}} (x) = 0$
if $x$ is transient, then $ρ_{{x_{1}, \dots, x_{k}}} (x) = \sum_{i} ρ_{{x_{1}, \dots, x_{k}}} (x_{i}) p_{x x_{i}}$

starting from $x$ , the expected steps to be absorbed

$μ_{x} = y \sum (1 + μ_{y}) p_{x y} = 1 + y \sum μ_{y} p_{x y}$

stationary distribution

let ${X_{n}}$ be a Markov chain with state space $S$ a distribution $π$ on $S$ is said to be stationary if $x \in S \sum p_{x y} π (x) = π (y) \forall y \in S$ $\Rightarrow$ the distribution stay the same $x \in S \sum p_{x y}^{n} π (x) = π (y) \forall y \in S, n \in N^{*}$ $\forall$ initial distribution $π_{0}$ , the distribution after infinite steps: $n \to \infty lim P (X_{n} = y) = π (y) \forall y \in S$ $\Rightarrow$ the distribution will be independent on $π_{0}$

find stationary distribution

build linear system with $⎩ ⎨ ⎧ π (1) = \sum_{x \in S} p_{x 1} π (x) π (2) = \sum_{x \in S} p_{x 2} π (x) ⋮ π (n - 1) = \sum_{x \in S} p_{x (n - 1)} π (x) \sum_{x \in S} π (x) = 1 \Rightarrow p_{11} - 1 p_{12} ⋮ p_{1 (n - 1)} 1 p_{21} p_{22} - 1 p_{2 (n - 1)} \dots \dots \dots \dots p_{n 1} p_{n 2} p_{n (n - 1)} 1 π_{1} π_{2} ⋮ π_{n} = 0 ⋮ 01$

null recurrent and positive recurrent

$n \to \infty lim p_{xx}^{n} = 0 or \neq = 0$

period of a state $d_{x}$

GCD of all $n$ such that $p_{xx}^{n} > 0$

states in the same class have the same period

$x ⟷ y \Rightarrow d_{x} = d_{y}$

a chain is irreducible if $S$ is a closed class

if every state of a Markov chain has period $1$ we say the chain is aperiodic

suppose a Markov chain is irreducible and aperiodic and has a stationary distribution $π$

$n \to \infty lim p_{x y}^{n} = π (y)$

suppose a Markov chain is irreducible and all states are recurrent

average number of visits to $y$

$N_{n} (y) = m = 1 \sum n 1_{y} (X_{n}) \frac{N _{n} ( y )}{n} \to \frac{1}{E _{y} [ T _{y} ]}$

mean return time to $y$

$m_{y} = E_{y} [T_{y}]$

suppose a Markov chain is irreducible and has a stationary distribution $π$

$π (y) = \frac{1}{E _{y} [ T _{y} ]}$ the stationary distribution is unique

and $n \to \infty lim \frac{\sum _{m = 1}^{n} p _{x y}^{n}}{n} = π (y)$

Stochastic process

branching process

consider a population of individual:

in every generation, $n = 0, 1, 2, \dots$ , each individual produce a random number of offspring in the next generation $Z, Z \in {0, 1, \dots}$ , i.i.d. with the other individual. $X_{n}, n = 0, 1, \dots$ denote the number of individual in the $n$ -th generation

$P (Z = i) = p_{i}$

question of interest

$n \to \infty lim P (X_{n} = 0) = ?$

generating function

$Φ_{X} (t) = E [t^{X}] = x \sum P (X = x) t^{x} \Rightarrow Φ_{X}^{'} (t) = x \sum x P (X = x) t^{x - 1} \Rightarrow ⎩ ⎨ ⎧ μ = E [X] = Φ_{X}^{'} (1) Φ_{X} (0) = p_{0} Φ_{X} (1) = 1$

fixed point of $ρ$

$ρ = ρ_{1, 0} = k \sum P (Z = k) ρ_{k, 0} = k \sum P (Z = k) ρ^{k} = Φ (ρ)$

analysis: study $H (t) = Φ_{X} (t) - t$
$H^{''} (t) > 0, H (0) = p_{0} > 0, H (1) = 0$

if $μ = 0$ , then $p_{0} = 1 \Rightarrow ρ = 1$ if $0 < μ \leq 1, P (t = 0) > 0$ , then $ρ = 1$ if $μ > 1$ , then $\exists 0 < ρ < 1$

birth and death process

$S = {0, 1, \dots, d} p_{x y} = ⎩ ⎨ ⎧ q_{x} r_{x} p_{x} y = x - 1 y = x y = x + 1 q_{0} = 0, q_{x} > 0 p_{d} = 0, p_{x} > 0 (0 < x < d)$

gambler’s ruin

with $0 \leq a < x < b$ , find $u (x) = P_{x} (T_{a} < T_{b})$ $γ_{x} = \frac{q _{1} q _{2} \dots q _{x}}{p _{1} p _{2} \dots p _{x}} γ (0) = 1 u (x) = q_{x} u (x - 1) + r_{x} u (x) + p_{x} u (x + 1) \Rightarrow \frac{u ( x + 1 ) - u ( x )}{γ _{x}} = \frac{u ( x ) - u ( x - 1 )}{γ _{x - 1}} \Rightarrow u (x) = \frac{\sum _{y = a}^{b - 1} γ _{y}}{\sum _{y = a}^{b - 1} γ _{x}} 1 - u (x) = \frac{\sum _{y = a}^{x - 1} γ _{y}}{\sum _{y = a}^{b - 1} γ _{y}}$

when $p_{i} = p, q_{i} = q$

$u (x) = 1 - \frac{( \frac{q}{p} ) ^{a} - ( \frac{q}{p} ) ^{x}}{( \frac{q}{p} ) ^{a} - ( \frac{q}{p} ) ^{b}}$

irreducible and stationary distribution

$P_{1} (T_{0} < \infty) = n \to \infty lim P_{1} (T_{0} < n)$ because ${T_{0} < n}$ is non-decreasing $\Rightarrow P_{1} (T_{0} < \infty) = n \to \infty lim (1 - \frac{1}{\sum _{y = 0}^{n - 1} γ _{y}})$

$\Rightarrow$ a birth and death chain is recurrent iff $\sum_{y = 0}^{\infty} γ_{y} = \infty$

if transient $ρ_{x 0} = \frac{\sum _{y = x}^{\infty} γ _{y}}{\sum _{y = 0}^{\infty} γ _{y}} \neq = 0$ if recurrent $π (k + 1) = \frac{p _{0} p _{1} \dots p _{k}}{q _{1} q _{2} \dots q _{k + 1}} π (0)$ stationary distribution exists iff $\sum_{k = 1}^{\infty} \frac{p _{0} p _{1} \dots p _{k}}{q _{1} q _{2} \dots q _{k + 1}} < \infty$ $\Rightarrow$ positive recurrent

else, null recurrent

random walk

random walk on finite graph $G$

number of vertex

$∣ V ∣$

adjacent— $u$ is adjacent to $v$ iff there is one edge connecting them
degree of a vertex $u$ —the number of edges incident to $u$

$d (u)$

uniform—the distribution of where to go is uniform, meaning that the probability of going to any adjacent vertex is the same

$P_{x y} = {\frac{1}{d ( x )} 0 y is adjacent to x otherwise$

stationary distribution $π$

$π (x) = \frac{d ( x )}{α}$ where $α = x \sum d (x)$

random walk on positive integer

birth and death process

reflective barrier
recurrent iff $p > \frac{1}{2}$
stationary distribution $π (x) = (1 - \frac{p}{1 - p})^{x} (\frac{p}{1 - p})^{x}$ iff recurrent

random walk on integer $Z^{d}$

$S$ consist of all points in $R^{d}$ with integer coordinate

Stirling’s formula

$n! \approx 2 πn n^{n} e^{- n}$ when $n$ is large

random walk on $Z^{1}$

$p_{xx}^{2 n} = (2 n n) p^{2 n} (1 - p)^{2 n} {= \infty < \infty p = \frac{1}{2} otherwise$

limit comparison test to check convergence

continuous Markov chain

continuous time
finite or countably infinite

$P (X (s + t) = j ∣ X (s) = i, X (u) = x_{u}) = P (X (s + t) = j ∣ X (s) = i) \forall u, 0 \leq u \leq s$

time-homogenous— $s$ does nothing

$P (X (s + t) = j ∣ X (s) = i) = P (X (t) = j ∣ X (0) = i) = p_{ij} (t)$

Chapman–Kolmogorov Equations

$p_{ij} (s + t) = k \in S \sum p_{ik} (s) p_{kj} (t)$

holding time at state $i$

the time $τ_{i}$ staying at state $i$ before changing $τ_{i} \sim E x p (q_{i})$

absorbing state $q_{i} = 0$ , never move
explosive $q_{i} = \infty$ , never stay
general

proof

prove $P (τ_{i} > s + t ∣ τ_{i} > s, X (0) = i) = P (τ_{i} > t ∣ X (0) = i)$ $\Rightarrow$ the holding time is memory-less

embedded discrete Markov chain

${Y_{i}}$ consisting of the state the continuous Markov chain visit $p_{ij} = P (Y_{n + 1} = j ∣ Y_{n} = i) = P (Y_{1} = j ∣ Y_{0} = i)$

another representation of $p_{ij} (t)$

before jumping from $i$ to $j$ , holding time $\sim E x p (q_{ij})$ $j \sum q_{ij} = q_{i} p_{ij} = \frac{q _{ij}}{q _{i}}$ go to the earliest state

transition matrix for the embedded Markov chain

$\tilde{p} = 0 \frac{q _{21}}{q _{2}} ⋮ \frac{q _{12}}{q _{1}} 0 ⋮ \dots \dots ⋱$ derivative at $0$ $p_{ij}^{'} (0) = {q_{ij} - q_{i} i \neq = j i = j$

Kolmogorov backward equation

$p_{ij}^{'} (t) = k \neq = i \sum q_{ik} p_{kj} (t) - q_{i} p_{ij} (t) = k \sum Q_{ik} p_{kj} (t)$

Kolmogorov forward equation

$p_{ij}^{'} (t) = k \neq = j \sum p_{ik} (t) q_{kj} - q_{j} p_{ij} (t) = k \sum p_{ik} (t) Q_{kj}$

infinitesimal generator $Q$ —transition matrix for the Markov chain itself

$Q = - q_{1} q_{21} ⋮ q_{12} - q_{2} ⋮ q_{13} q_{23} ⋮ \dots \dots ⋱ Q_{ij} = p_{ij}^{'} (0) = {q_{ij} - q_{i} i \neq = j i = j$

recover $p_{ij} (t)$ using $Q$

system of differential equation using the Kolmogorov equation (either forward or backward)

matrix exponential

square matrix $A$ $e^{t A} = n = 0 \sum \infty \frac{( t A ) ^{n}}{n !} \frac{\partial e ^{t A}}{\partial t} = A e^{t A}$

or differential equation of matrix

$p (t) = p_{11} (t) ⋮ p_{n 1} (t) \dots ⋱ \dots p_{1 n} (t) ⋮ p_{nn} (t) p^{'} (t) = Qp (t) = p (t) Q \Rightarrow p (t) = e^{tQ}$ for $Q = S D S^{- 1}, λ_{i}$ the eigenvalues $p (t) = S e^{t D} S^{- 1} (e^{t D})_{ij} = ⎩ ⎨ ⎧ e^{t λ_{i}} 0 i = j i \neq = j$

long time behavior of continuous Markov chain

stationary distribution

definition with $π = [π (1), π (2), \dots]$

$π = π p (t) \Leftrightarrow x \in S \sum p_{x y} (t) π (x) = π (y) \forall y \in S, t$

finding the stationary distribution

$π Q = 0 \Leftrightarrow i \sum π (i) Q_{ij} = 0 \forall j$

is a limiting distribution if recurrent and finite closed class

$π (y) = t \to \infty lim p_{x y} (t) \forall x$

relationship with stationary distribution of embedded chain $Φ$

let $h (j) = π (j) q_{j}$ $Φ (j) = \frac{h ( j )}{\sum _{k} h ( k )}$

irreducible

$\exists t > 0, \forall i, j, p_{ij} (t) > 0 \Leftrightarrow$ irreducible if $\exists t_{0} > 0, p_{ij} (t_{0}) > 0$ , then $\forall t > t_{0}, p_{ij} (t) > 0$

fundamental theorem

if the chain is finite or positive recurrent, if the chain is irreducible and $S$ is positive recurrent, then $\exists$ unique stationary distribution and limiting distribution $π$

continuous birth and death process

${λ_{x} = q_{x, x + 1} μ_{x} = q_{x, x - 1}$

pure birth

$μ_{x} = 0 p_{x y} (t) = λ_{y - 1} \int_{0}^{1} e^{- λ_{y} (t - s)} p_{x, y - 1} d s p_{x, x + 1} (t) = ⎩ ⎨ ⎧ \frac{λ _{x}}{λ _{x + 1} - λ _{x}} (e^{- λ_{x} t} - e^{- λ_{x + 1} t}) λ_{x} t e^{- λ_{x} t} λ_{x + 1} \neq = λ_{x} λ_{x + 1} = λ_{x}$

recurrence

$x = 1 \sum \infty \frac{μ _{1} μ _{2} \dots μ _{x}}{λ _{1} λ _{2} \dots λ _{x}} = {\infty < \infty recurrent transient$

Poisson process

continuous time Stochastic process ${N (t), t \geq 0}$ with parameter (rate) $λ > 0$ , and

$N (0) = 0$
$N (t + s) - N (s) \sim P o i sso n (t λ)$
$N (t)$ has independent increment

$N (t_{1}) - N (t_{0}), \dots, N (t_{n}) - N (t_{n - 1})$ where $t_{0} < t_{1} < \dots < t_{n}$

$\Rightarrow$ $N (t_{1} + s_{1}) - N (s_{1}) + N (t_{2} + s_{2}) - N (s_{2}) \sim E x p ((t_{1} + t_{2}) λ)$

inter arrival time $T_{i}$

the time between the occurrence of the $(i - 1)$ th event and the $i$ th $T_{i} \sim E x p (λ)$

arrival time $S_{i}$

the time of the occurrence of the $i$ th event $S_{i} = j = 1 \sum i T_{j} S_{i} \sim G amma (i, λ)$

alternative definition using exponential distribution

sum of i.i.d. $E x p (λ)$

combine independent Poisson process

$N_{1} (t) + N_{2} (t)$ is Poisson process with $λ_{1} + λ_{2}$

splitting Poisson process

$N (t) = N_{1} (t) + N_{2} (t)$ with every occurrence go to $N_{1} (t)$ with probability $p$ and go to $N_{2} (t)$ with probability $(1 - p)$ , then $N_{1} (t)$ is Poisson process with $p λ$ , $N_{2} (t)$ is Poisson process with $(1 - p) λ$ , the distribution between them is binomial

$1$ occurrence time spot

$P (S_{1} < s ∣ N (t) = 1) = \frac{s}{t} s < t$

many occurrence time spot

let $U_{i}$ be i.i.d. $\sim U (0, t)$ let $U_{(i)}$ denote them in ascending order $f (S_{1}, S_{2}, \dots, S_{n}) = \frac{n !}{t ^{n}}$

proof

let $S_{i}$ be occurrence time for $N (t)$ given $N (t) = n$ $P (s_{1} < S_{1} < s_{1} + δ, \dots ∣ N (t) = n) = \frac{P ( s _{1} < S _{1} < s _{1} + δ , \dots , N ( t ) = n )}{P ( N ( t ) = n )} = \frac{P ( N ( t - n δ ) = 0 ) [ P ( N ( δ ) = 1 ) ] ^{n}}{P ( N ( t ) = n )} = \frac{δ ^{n} n !}{t ^{n}} f (S_{1}, \dots) = δ \to 0 lim \frac{δ ^{n} n !}{δ ^{n} t ^{n}} = \frac{n !}{t ^{n}}$

definition of $o (h)$

$f (x)$ is $o (h)$ if $x \to 0 lim \frac{f ( x )}{x} = 0$

alternative definition

$N (0) = 0$
$N (t)$ has independent increment
$P (N (t + h) - N (t) = 1) = λh + o (h)$
$P (N (t + h) - N (t) \geq 2) = o (h)$

proof

take the derivative of $P (N (t) = 0)$
prove $T_{2}, \dots$ are exponential by induction
prove $S_{i}$ are gamma using $T_{i}$

property of Stochastic process

for Stochastic process $X (t), (t \geq 0)$

mean function

$μ_{X} (t) = E [X (t)]$

covariance function (auto-covariance function)

$r_{X} (t, s) = C o v (X (t), X (s))$ all the property of covariance apply to covariance function

second order stationary process

$\forall τ, Y (t) = X (t + τ), ⎩ ⎨ ⎧ μ_{Y} = μ_{X} r_{Y} (s, t) = r_{X} (s, t) \Leftrightarrow ⎩ ⎨ ⎧ E [X (t)] = E [X (t + τ)] \forall τ E [X (t) X (s)] = f (t - s)$

Gaussian process

Stochastic process $X (t), (t \geq 0)$ $a_{1} X (t_{1}) + a_{2} X (t_{2}) + \dots + a_{n} X (t_{n}) \sim N \forall 0 \leq t_{1} < t_{2} < \dots < t_{n}, a_{1}, a_{2}, \dots, a_{n} \in R, n = 1, 2, \dots \Rightarrow ((X (t_{1}), \dots)) is multivariate normal Gaussian processes with the same μ, σ, r (s, t) \Leftrightarrow X (t) = d Y (t)$

multivariate normal distribution

random variable $X_{1}, X_{2}, \dots, X_{k}$ $a_{1} X_{1} + a_{2} X_{2} + \dots \sim N or ma l \forall a_{1}, a_{2}, \dots \in R$

joint density function is determined by
- $\overset{μ}{ˉ} = (μ_{1}, μ_{2}, \dots)$
- covariance matrix $V$ $V_{ij} = C o v (X_{i}, X_{j})$

$f (X_{1}, X_{2}, \dots) = \frac{1}{( 2 π ) ^{k} ∣ det V ∣} exp {- \frac{( X ˉ - μ ˉ ) ^{T} V ^{- 1} ( X ˉ - μ ˉ )}{2}}$

covariance and independence normal random variable $X, Y$ and $C o v (X, Y) = 0 \Rightarrow$ independence

Brownian motion

standard Brownian motion

continuous time Stochastic process $W (t), (t \geq 0)$

$P (W (0) = 0) = 1$
Stationary increment $W (t + s) - W (s) \sim N (0, σ^{2} = t)$
independent increment
$P ($ function $t \mapsto W (t)$ is continuous $) = 1$

covariance function

$r_{W} (s, t) = min {s, t}$

connection between Brownian motion and discrete random walk

sum $S (n)$ of $n$ random walk $X_{1}, \dots, X_{n}$ $S (n) = ⎩ ⎨ ⎧ 0 \sum_{i = 1}^{n} X_{i} n = 0 n > 0$ is discrete, but $\overset{(t) = ⎩ ⎨ ⎧ S (t) S (⌊ t ⌋) + X_{⌊ t ⌋ + 1} (t - ⌊ t ⌋) t \in N^{*} t \in / N^{*} is continuous, can approximate Brownian motion after scaling and limiting using S_{t}^{(n)} = \frac{S ( n t )}{n} \to \dots W (t)}{S}$

relation between Gaussian process and Brownian motion

standard Brownian motion $\Leftrightarrow$ Gaussian process $X (t)$ that

$P (X (0) = 0) = 1$
$μ_{X} (t) = 0 \forall t \geq 0$
$r_{X} (t, s) = min {s, t} \forall s, t \geq 0$
continuous path $P ($ function $t \mapsto X (t)$ is continuous $) = 1$

transformation of Brownian motion

standard Brownian motion $W (t) \Rightarrow$ the following are standard Brownian motion $(t \geq 0)$

reflection $- W (t)$
new start $W (t + s) - W (s)$
scaling $\frac{W ( a t )}{a}$
Gaussian $X (t) = t \cdot W (\frac{1}{t}) (X (0) = 0)$

hitting time

first time reaching $a$ $T_{a} = min {t : W (t) = a}$

usage $P (W (t) > a ∣ T_{a} < t) = P (W (t) < a ∣ T_{a} < t) = \frac{1}{2} \Rightarrow P (T_{a} < t) = 2 P (W (t) > a) f_{T_{a}} (t) = \frac{1}{2 π t ^{3}} e x p {- \frac{a ^{2}}{2 t}} \Rightarrow t \to \infty lim P (T_{a} < t) = 1, E [T_{a}] = \infty$

some distributions

Beta random variables

$X \sim B e t a (a, b)$ $f (x) = {\frac{x ^{α - 1} ( 1 - x ) ^{β - 1}}{B ( α , β )} 0 0 < x < 1 o t h er w i se$

Beta function

$B (α, β) = \int_{0}^{1} θ^{α - 1} (1 - θ)^{β - 1} d θ = \frac{( α - 1 )! ( β - 1 )!}{( α + β - 1 )!}$

exponential random variable

$X \sim E x p (λ)$ $f_{X} (x) = f (x) = {λ e^{- λ x} 0 x > 0 \int_{0}^{\infty} λ e^{- λ x} d x = 1 P (X \geq t) = e^{- λ t} M_{X} (t) = \frac{λ}{λ - t} E [X] = M_{X}^{'} (0) = \frac{1}{λ} Va r (X) = M^{''} (0) - (M^{'} (0))^{2} = \frac{1}{λ ^{2}}$

memory-less property

$P (X > t + s ∣ X > t) = P (X > s)$

sum of $n$ i.i.d. exponential distribution is gamma distribution

$f_{S_{n}} (x) = λ e^{- λ x} \frac{( λ x ) ^{n - 1}}{( n - 1 )!}$ proved by induction

comparison between $X_{1} \sim E x p (λ_{1})$ and $X_{2} \sim E x p (λ_{2})$

$P (X_{1} < X_{2}) = \frac{λ _{1}}{λ _{1} + λ _{2}}$

comparison between $X_{1}, X_{2} \dots \sim E x p$ with parameter $λ_{1}, λ_{2}, \dots$

$P (X_{i} = min) = \frac{λ _{i}}{\sum _{i} λ _{i}}$

minimum of $n$ exponential distribution with $λ_{i}$ ’s

$V \sim E x p (i \sum λ_{i})$

Gamma distribution

$X \sim G amma (α, λ)$ $f (x) = {\frac{λ ^{α} x ^{α - 1}}{Γ ( α )} e^{- λ x} 0 x \geq 0 x < 0 E [X] = \frac{α}{λ} Va r (X) = \frac{α}{λ ^{2}}$

Poisson distribution

$X \sim P o i sso n (λ)$ $p_{X} (k) = e^{- λ} \frac{λ ^{k}}{k !} E [X] = Va r (X) = λ$

bivariate normal distribution

joint density

$μ_{x}, μ_{y}, σ_{x} > 0, σ_{y} > 0, - 1 < ρ < 1 f (x, y) = \frac{1}{2 π σ _{x} σ _{y} 1 - ρ ^{2}} e^{- \frac{1}{2 ( 1 - ρ ^{2} )} [(\frac{x - μ _{x}}{σ _{x}})^{2} + (\frac{y - μ _{y}}{σ _{y}})^{2} - 2 ρ \frac{( x - μ _{x} ) ( y - μ _{y} )}{σ _{x} σ _{y}}]}$

marginals

$X \sim N (μ_{x}, σ_{x}^{2}) Y \sim N (μ_{y}, σ_{y}^{2})$

conditionals

$(X ∣ Y = y) \sim N (μ_{x} + ρ \frac{σ _{x}}{σ _{y}} (y - μ_{y}), σ^{2} = σ_{x}^{2} (1 - ρ^{2})) (Y ∣ X = x) \sim N (μ_{y} + ρ \frac{σ _{y}}{σ _{x}} (x - μ_{x}), σ^{2} = σ_{y}^{2} (1 - ρ^{2})) ρ = C orr (X, Y) = \frac{C o v ( X , Y )}{σ _{x} σ _{y}} X, Y independent \Leftrightarrow C o v (X, Y) = 0$

Steven Hé (Sīchàng)