MATH 5763  Stochastic Processes, Section 990  Fall 2015
Tue 1:30–4:20 p.m., Classroom Building 3104
Instructor:
Nikola Petrov, 802 PHSC, (405)3254316, npetrov AT math.ou.edu
First day handout
Prerequisite:
Basic calculusbased probability theory (including axioms of probability, random variables,
expectation, probability distributions, independence, conditional probability).
The class will also require knowledge of elementary analysis (including sequences, series, continuity),
linear algebra (including linear spaces, eigenvalues, eigenvectors), and ordinary differential equations.
Course description:
The theory of stochastic processes studies systems that evolve
randomly in time;
it can be regarded as the "dynamical" part of probability theory.
It has many important practical applications,
as well as in other branches
in mathematics such as partial differential equations.
This course is a graduatelevel
introduction to stochastic processes,
and should be of interest to students of mathematics,
statistics, physics, engineering, and economics.
The emphasis will be on the fundamental concepts,
but we will avoid using the theory of Lebesgue measure
and integration in any essential way.
Many examples of stochastic phenomena in applications
and some modeling issues will also be discussed in class
and given as homework problems.
Texts (all available free for OU students from the
OU Library):

[L]
M. Lefebvre, Applied Stochastic Processes,
1st edition, Springer, 2007, through the

[BZ]
Z. Brzezniak, T. Zastawniak. Basic Stochastic Processes. Springer, 1999

[P]
E. Parzen. Stochastic Proceses. SIAM, 1999

[D]
R. Durrett. Essentials of Stochastic Processes. 2nd ed., Springer, 2012

[R]
S. Ross. Introduction to Probability Models.
8th ed., Elsevier, 2003
Main topics (a tentative list):

a brief review of probability theory;

discrete Markov chains: ChapmanKolmogorov equations,
persistence and transience, generating functions,
stationary distributions, reducibility, limit theorems, ergodicity;

continuous Markov processes:
Poisson process, birthdeath and branching processes,
embedding of a discretetime Markov chain
in a continuoustime Markov processes;

conditional expectation, martingales;

stationary processes (autocorrelation function,
spectral representation);

renewal processes, queues;

diffusion processes, Wiener processes (Brownian motion);

introduction to stochastic differential equations, Itô calculus;

FokkerPlanck equation, OrnsteinUhlenbeck process.
Homework:

Homework 1,
due by 4:30 p.m. on Wednesday, September 2, in Mrs. Wagenblatt's office.

Homework 2,
due by 4:30 p.m. on Wednesday, September 9, in Mrs. Wagenblatt's office.

Homework 3,
due by 1:30 p.m. on Tuesday, September 15, in class.

Homework 4,
due by 4:30 p.m. on Wednesday, September 23, in Ms. Arnett's office.

Homework 5,
due on Tuesday, October 6, in class.

Homework 6,
due by 4:30 p.m. on Wednesday, October 21, in Mrs. Wagenblatt's office.

Homework 7,
due by 12:00 p.m. on Friday, October 30, in Mrs. Wagenblatt's office.

Homework 8,
due by 12:00 p.m. on Thursday, November 12, in Mrs. Wagenblatt's office.

Homework 9,
due by 12:00 p.m. on Tuesday, November 24, in Mrs. Wagenblatt's office.
Content of the lectures:

Lecture 1 (Tue, Aug 25):
Review of probability:
sample space Ω, events as subsets of the sample space,
elementary events as elements of the sample space,
operations with events (complement, union,
intersection, difference, symmetric difference,
subset, impossible event);
σalgebra (σfield), examples;
De Morgan's laws, disjoint events,
distributivity properties of intersection and union;
probability (probability measure) P,
probability space,
elementary properties of probability measures
(including the inclusionexclusion formula);
conditional probability P(AB),
properties of conditional probability,
partitions of the sample space,
law of total probability, Bayes' formula,
independent events, independent family of events,
pairwise independent family of events;
an example of using conditioning
[pages 13, 58 of Sec. 1.1 of [L]]
Random variables:
random variables (RVs),
(cumulative) distribution function (c.d.f.) F_{X}(x)
of a RV X,
properties of c.d.f.s;
discrete RVs, probability mass function (p.m.f.)
p_{X}(x) of a discrete RV,
important discrete RVs (Bernoulli, binomial, Poisson, geometric)
[pages 8, 9, 11, 12 of Sec. 1.2 of [L]]

Lecture 2 (Tue, Sep 1):
Random variables (cont.):
continuous RVs; p.d.f. ƒ_{X}(x) of a continuous RV;
important continuous RVs (uniform, exponential, normal/Gaussian, standard normal);
p.d.f. ƒ_{Y}(y) of a function Y=g(X) of the RV X;
conditional c.d.f. F_{X}(xA)
of a RV X conditioned on an event A;
conditional p.m.f. p_{X}(xA)
or p.d.f. ƒ_{X}(xA) of a RV X conditioned on an event A;
expectation E[X] of a RV X;
expectation E[g(X)] of a function of a RV X;
rth moment E[X^{r}] of a RV X
for r=0,1,2,...;
variance Var X and standard deviation
σ_{X}=(Var X)^{1/2}
of a RV X; properties of E[X] and Var X;
conditional expectation E[XA],
conditional moments E[X^{r}A]
and conditional variance and Var(XA)
of a RV X given an event A; example;
characteristic function C_{X}(ω)
and momentgenerating function M_{X}(t)
of a RV X, expressing the E[X^{r}]
as a derivative of M_{X}(t)
[pages 10, 11, 1320 of Sec. 1.2 of [L]]
Random vectors:
definition; (joint) c.d.f. F_{X,Y}(x,y)
of a random vector X=(X,Y); properties of F_{X,Y}(x,y);
marginal c.d.f.s F_{X}(x)=F_{X,Y}(x,∞)
and F_{Y}(y)=F_{X,Y}(∞,y);
marginal p.m.f.s p_{X}(x) and p_{Y}(y),
respectively p.d.f.s ƒ_{X}(x) and ƒ_{Y}(y),
of a random vector (X,Y);
independence of the components of a random vector;
proof that if the RVs X and Y are independent, then
M_{X+Y}(t)=M_{X}(t)M_{Y}(t);
conditional c.d.f. F_{XY}(xY=y_{m})
and conditional p.m.f.
p_{XY}(x_{k}Y=y_{m})
of the discrete RV X conditioned on the discrete RV Y;
conditional c.d.f. F_{XY}(xy)
and conditional p.m.f.
ƒ_{XY}(xy)
of the continuous RV X conditioned on the continuous RV Y;
conditional expectation E[XY=y] of the RV X
conditioned on the RV Y;
the conditional expectation E[XY=y]
depends only on y (but not on X), so it can be considered as a function of Y,
therefore we can think of the conditional expectation E[XY]
as a new random variable which is a function of the RV Y: namely,
E[XY]:Ω→R is defined as
the value of E[XY](ω) is defined as E[XY=y],
where y=Y(ω);
tower rule E[E[XY]]=E[X]
[pages 2127 of Sec. 1.3 of [L]]

Lecture 3 (Tue, Sep 8):
Stochastic processes:
definition of a stochastic process (random process);
classification of random processes:
discretetime or continuoustime,
discretestate space or continousstate space
[pages 4748 of Sec 2.1 of [L]]
Markov chains  introduction:
Markov property; Markov chain (MC);
example: simple 1dimensional random walk (RW), symmetric simple 1dim RW;
the future of a MC depends only on the most recent available information (Prop. 3.1.1);
more examples: 2dimensional, and ddimensional RWs, Ehrenfests' urn model,
birthdeath processes
[pages 7375 of Sec. 3.1 of [L]]
Discretetime Markov chains  definitions and notations:
timehomogeneous discretetime discretestate space MCs;
stationary (timehomogeneous) MCs;
onestep and nstep transition probabilities;
onestep transition probability matrix P of a MC;
stochastic and doublystochastic matrices;
nstep transition probability matrices P^{(n)};
ChapmanKolmogorov in matrix form
(P^{(m+n)}=P^{(m)}P^{(n)})
and in components;
corollary: P^{(n)}=P^{n};
an example of a MC with 2 states;
probability ρ_{ij}^{(n)}
of visiting state j for the first time
in n steps starting from state i;
probability ρ_{ii}^{(n)}
of first return to state i in n steps;
representation of p_{ij}^{(n)}
as a sum over k from 1 to n of
ρ_{ij}^{(k)}p_{jj}^{(n−k)};
examples of direct computation ρ_{ij}^{(n)} for a simple MC;
initial distribution (p.m.f.) a=(a_{0},a_{1},a_{2},...),
a_{i}=P(X_{0}=i), of a MC;
distribution (p.m.f.)
a^{(n)}=(a_{0}^{(n)},a_{1}^{(n)},a_{2}^{(n)},...),
a_{i}^{(n)}=P(X_{n}=i), of a MC at time n;
formula for evolution of the probability distribution:
a^{(n)}=aP^{n};
examples: simple 1dim random walk on Z,
simple 1dim random walk on Z_{+} with reflecting
and absorbing boundary condition at 0,
a Markov chain coming from sums of i.i.d. random variables (read Example 2 on page 85)
[Sec. 3.2.1 of [L]]
Properties of Markov chains:
accessibility of state j from state i, i→j;
communicating states i↔j;
properties of the relation ↔
(reflexivity, symmetry, transitivity),
↔ as an equivalence relation,
equivalence classes with respect of ↔,
closed sets of the state space (Def. 3.2.7)
[pages 8586 of Sec. 3.2.2 of [L]]

Lecture 4 (Tue, Sep 15):
Properties of Markov chains (cont.):
irreducible MCs; irreducibility criteria; examples;
absorbing states;
probability ƒ_{ij}
of eventual visit of state j starting from state i;
probability ƒ_{ii}
of eventual return to state i;
expressing ƒ_{ij}
as a sum of the first visit probabilities
ρ_{ij}^{(n)};
recurrent (persistent) and transient states;
Decomposition Theorem;
an example of identifying closed irreducible sets of recurrent states
and sets of transient states, and structure of the stochastic
matrix; a necessary and sufficient criterion of recurrence
of state i in terms of the expected value E[N_{i}]
of the number N_{i} of returns to this state (Prop. 3.2.3);
a necessary and sufficient criterion of recurrence of state i
in terms of a sum of the (ii)th matrix element of
P^{(n)} over n (Prop. 3.2.4);
recurrence is a class property (Prop 3.2.5);
average number μ_{i} of transitions for first
return to state i;
positive recurrent and nullrecurrent states;
criterion for nullrecurrence;
type of recurrence (positive or null) is a class property;
recurrent states of a finite MC are positive recurrent;
periodic and aperiodic states; remarks about periodicity; examples;
simple random walk on Z: computing the number of itineraries
by using combinatorial arguments, Stirling's formula,
recurrence in the symmetric case (p=1/2)
and transience otherwise
[pages 8693 of Sec. 3.2.2 of [L]]
Limiting probabilities:
limiting probabilities π_{i},
limiting probability distribution
π=(π_{0},π_{1},π_{1},...),
ergodic states,
Ergodic Theorem (giving conditions for existence and uniqueness
of a limiting probability distribution,
relation between π_{i} and
μ_{i},
and an algorithm for computing π)
[pages 9495 of Sec. 3.2.3 of [L]]
Mathematical digression:
computing high powers of a matrix by diagonalizing it first;
general methods for solving linear recurrence relations.

Lecture 5 (Tue, Sep 22):
a recap of the Ergodic Theorem, examples showing
the importance of the aperiodicity (otherwise
the limit of p_{ij}^{(n)}
as n→∞ may not exist),
the irreducibility (otherwise the stationary distribution
may not be unique), and the recurrence
(otherwise the average number μ_{j}
of transitions for first return to state i will be infinite,
so that the relation π_{j}=1/μ_{j}
will not make sense); an example of identifying the closed irreducible sets
of recurrent states and of the sets of transient states of a MC,
and structure of the stochastic matrix of a MC;
stationary distribution of a doubly stochastic irreducible aperiodic MC
with a finite state space (Prop. 3.2.6);
simple RW on {0,1,2,...} with a partially reflecting boundary
 obtaining the stationary distribution π
when the probability of moving to the right is smaller 1/2,
and showing that a stationary distribution does not exist
when the probability of moving to the right is greater than 1/2
(exercise: study this MC when the probability of moving to the right is equal to 1/2)
[pages 95100 of Sec. 3.2.3 of [L]]
Absorption problems:
definition of the probability
r_{i}^{(n)}(C)
of absorption by the closed subset C of the state space S
after exactly n steps (starting from state i);
definition of the probability r_{i}(C)
of eventual absorption by the closed subset C of the state space S
(starting from state i);
a theorem giving r_{i}(C)
in terms of the (p_{ij}) (Theorem 3.2.2.);
an example: the gambler's ruin problem;
martingales
[Sec. 3.2.4 of [L]]
Continuoustime discretestate space MCs:
definition of a continuoustime discretestate state MCs;
Markov property;
transition functions
p_{ij}(s,t)=P(X_{t}=jX_{s}=i) for t>s;
stationary (timehomogeneous) MCs  for which
p_{ij}(s,t)=p_{ij}(0,t−s),
notation:
p_{ij}(t)=p_{ij}(0,t)=P(X_{t}=jX_{0}=i) for t>0;
a discretetime MC {Y_{n}}_{n∈{0,1,2,...}}
embedded in the continuoustime MC {X_{t}}_{t≥0};
irreducibility; analogue of the condition of being
a stochastic matrix for p_{ij}(t)
(the sum over j is 1);
evolution of the occupation probabilities
p_{j}(t)=P(X_{t}=j)
expressed in terms of the initial occupation probabilities
p_{i}(0) and the transition probabilities p_{ij}(t);
ChapmanKolmogorov equations;
discussion of the meaning of the memorylessness properties of the geometric
and the exponential random variables (Prop. 3.3.1)
[pages 121123 of Sec. 3.3.2 and pages 109110 of Sec. 3.3.1 of [L]]

Lecture 6 (Tue, Sep 29):
Continuoustime discretestate space MCs (cont.):
exponential random variable: definition,
proof that it is memoryless, momentgenerating function,
other properties (Prop. 3.3.4 and the remarks after it, Prop. 3.3.5)
[pages 109111, 112114 of Sec. 3.3.1 of [L]]
Poisson process:
counting process;
"little o(h)" notation, examples;
definition of a Poisson process N as a nondecreasing process with N(0)=0,
certain shorttime transition probabilities
p_{ij}(h) (for small h),
and independence of events occurring at a later time interval
from the events occurring at a nonoverlapping earlier time interval;
derivation of the distribution of N(t)
for a Poisson process N by deriving an initialvalue problem
for an infinite system of ODEs for p_{ij}(t)
and solving the system by induction and by the method of generating functions;
an "elementary" way of deriving that N(t)∼Poisson(λt)
by dividing the interval [0,t] into a large number n of short intervals
of length t/n and applying the binomial distribution
to the distribution of the events k events in the n short intervals
[loosely following pages 231, 232, 236 of Sec. 5.1 of [L]]
Poisson process and distribution of interarrival times:
independence and exponential distribution of the interarrival times τ_{j}
of a Poisson process (Prop. 5.1.3);
arrival times T_{j} as sums of interarrival times;
basic properties of the Γ(α,λ) random variables;
the sum of n i.i.d. Exp(λ) random variables is a Γ(n,λ)
random variable (Prop. 3.3.6);
reconstructing a Poisson process from the interarrival times τ_{j}
[pages 237240 of Sec. 5.1, pages 115119 of Sec. 3.3.1 of [L]]
Miscellaneous facts about Poisson processes (optional):
a sum of independent Poisson processes is a Poisson process (Prop. 5.5.1);
decomposition of Poisson processes (Prop. 5.5.2);
distribution of T_{1} given that N(t)=1 (Prop. 5.1.5);
generating a Poisson process by using a generator of uniform random variables (Example 5.1.2);
first occurrence of two or more independent Poisson processes (∼Prop. 3.3.4, Prop. 3.3.5)
[pages 234236, 239, 240 of Sec. 5.1, pages 113, 114 of Sec. 3.3.1 of [L]]

Lecture 7 (Tue, Oct 6):
Continuoustime discretestate space MCs (cont.):
stochastic semigroup {P_{t}}_{t≥0};
standard semigroups;
generator
G=(ν_{ij}):=(dP_{t}/dt)_{t=0}
of a stochastic semigroup;
properties of G
(the sum of the elements ν_{ij} in each row of G is zero);
holding time U_{i} of the ith state;
proof that U_{i} is an Exp(−ν_{ii}) random variable;
discussion of the meaning of ν_{ij}
expressed in terms of the rates ν_{i}
(such that the probability of leaving state i in a time interval of length h
is ν_{i}h+o(h))
and the matrix elements γ_{ij} of the 1step transition
probability matrix of the jump chain {Y_{n}}_{n≥0};
obtaining the 1step transition probability matrix (γ_{ij})
of the jump chain from the generator G;
obtaining P_{t} from G:
Kolmogorov forward and backward equations
P_{t}'=P_{t}G,
resp.
P_{t}'=GP_{t},
initial condition
P_{t}_{t=0}=I;
definition of exponential of a matrix e^{A};
main properties of e^{A}:
e^{A}e^{A}=e^{AB},
de^{tA}/dt=Ae^{tA};
computing e^{A} by simplifying A by a similarity
transformation, e.g., A=C^{−1}DC
for a diagonal matrix D,
and using that A^{n}=C^{−1}D^{n}C
to show that e^{A}=C^{−1}e^{D}C;
expressing the solution of the initial value problem
x'(t)=Ax(t), x(0)=x^{(0)}
(for a constant matrix A) as
x(t)=e^{tA}x^{(0)};
expressing the stochastic semigroup P_{t}
through the generator G: P_{t}=e^{tG};
computing P_{t} for a continuoustime, twostate MC;
remarks on the Laplace transform and its usage to solve initialvalue problems for ODEs;
birth process; computing the expectation of the time T_{n}
for a birth process starting at X_{0}=1 to reach
X_{t}=n for the first time;
solving the Kolmogorov forward equations for the birth process by using generating functions
G_{i}(ξ,t);
using the generating function G_{i}(ξ,t)
to prove that the birth process is honest (G_{i}(1,t)=1),
to compute the conditional average of the birth process given that X(0)=k
as E[X(t)X(0)=k]=(∂G_{k}(ξ,t)/∂ξ)_{ξ=1}
and the conditional variance Var(X(t)X(0)=k);
another way of computing the conditional expectation E[X(t)X(0)=k]
[roughly following Sec. 3.3.3, and pages 129133 of Sec. 3.3.4 of [L]]

Lecture 8 (Tue, Oct 13):
Limiting probabilities and balance equations:
stationary distribution π
of a stochastic semigroup P_{t};
reason for the term "stationary distribution":
if P(X(0)=i)=π_{i}
where π is a stationary distribution,
then
P(X(t)=j)=π_{j}
for all j∈S and all t≥0;
recurrence time T_{ii},
mean recurrence time μ_{ii}=E[T_{ii}];
recurrent and transient states,
positive recurrent and null recurrent states of a continuoustime Markov chain;
irreducible Markov chains;
Ergodic Theorem for continuoustime Markov process, remarks;
relation between the stationary distribution π_{j},
the rate ν_{j} of leaving state j
(where the holding time for state j is U_{j}∼Exp(ν_{j})),
and the mean recurrence time μ_{ii}=E[T_{ii}];
finding stationary distributions from the generator:
πG=0;
balance equations and their interpretation
[pages 138140 of Sec. 3.3.5 of [L]]
Birth and death processes:
birthdeathimmigrationdisaster process;
detailed derivation of the shorttime transition probabilities p_{ij}(h)
(hence, the generatorν_{ij}) of a deathimmigration process;
proving that the stationary distribution of a deathimmigration process
is Poisson(ρ/μ), i.e.,
π_{j}=e^{−ρ/μ}(ρ/μ)^{j}/j!
[roughly following pages 135, 136 of Sec. 3.3.4 of [L]]
Nonhomogeneous Poisson processes:
nonhomogeneous Poisson process with intensity function λ(t);
the number of arrivals N(s+t)−N(s)
of a nonhomogeneous Poisson process with intensity function λ(t)
is Poisson(m(s+t)−m(s)),
where m(t) is the mean value function of the process
(m(0)=0, m'(t)=λ(t))
[pages 250, 252 of Sec. 5.2 of [L]]
Reading assignment (mandatory):
distribution of the p.d.f. of the first arrival time T_{1}
of a nonhomogeneous Poisson process {N(t)}_{t≥0}
given that N(t_{1})=1 (for some fixed t_{1}>0)
(Prop. 5.5.2) [pages 21, 22 of the lecture notes from Lecture 8, page 253 of [L]]

Lecture 9 (Tue, Oct 20):
Nonhomogeneous Poisson processes (cont.):
"homogenizing" a nonhomogeneous Poisson process N(t)
(with a strictly positive rate function λt>0)
by rescaling the time:
M(t)=N(m^{−1}(t))
is a Poisson process with rate 1
[pages 253, 254 of Sec. 5.2 of [L]]
Compound Poisson processes:
compound random variable;
derivation of the mean, variance, and moment generating function
of a compound random variable (Prop. 5.3.1);
definition of a compound Poisson process;
mean, variance, and moment generating function
of a compound Poisson process;
approximating the distribution of a compound Poisson process
for large times by using the Central Limit Theorem (Prop. 5.3.2);
the sum of two independent compound Poisson processes
Y_{1}(t) and Y_{2}(t)
corresponding to Poisson processes
N_{1}(t) and N_{2}(t)
with rates λ_{1} and λ_{2}
is a compound Poisson process
corresponding to a Poisson process with rate
λ_{1}+λ_{2}
[Sec. 5.3]
Doubly stochastic Poisson processes:
definition of a conditional (or "mixed") Poisson process
(whose rate is a random variable, independent of time);
proof that a conditional Poisson process
has stationary, but not independent increments (Prop. 5.4.1);
best estimator of the rate of a Poisson process;
definition of a doubly stochastic Poisson process ("Cox process")
[pages 258260, 262 of Sec. 5.4 of [L]]
Renewal processes:
definition of a renewal process;
modified ("delayed") renewal process
(when the distribution of τ_{0}
differs from the distributions of
τ_{1}, τ_{2},...);
relations between the process N(t),
the times of the events T_{n},
and the interevent times τ_{n};
expression for the p.m.f. of N(t)
in terms of the c.d.f. of T_{n} (Prop. 5.6.1);
renewal function m(t)=E[N(t)];
expression for the renewal function m(t)
in terms of the c.d.f.'s of T_{n} (Prop. 5.6.2)
[pages 267269 of Sec. 5.6 of [L]]
Mathematical digression:
definition of Riemann integral;
definition of the RiemannStieltjes integral;
particular cases of the RiemannStieltjes integral
when g(t) is differentiable and nondecreasing,
and when g(t) is piecewise constant;
applications to computing expected values of discrete
and continuous random variables.

Lecture 10 (Tue, Oct 27):
Mathematical digression (cont.):
expected value of an Nvalued random variable X
as a sum (over n from 1 to infinity)
of probabilites of X to be greater or equal to n;
expected value of a nonnegative continuous random variable
X as an integral of
[1−F_{X}(x)],
geometric meaning.
Renewal processes (cont.):
recursive formula for the c.d.f.'s of the arrival times T_{n}
in terms of the p.d.f. F_{τ} of the interarrival
times τ_{j} through RiemannStieltjes integrals;
derivation of an integral equation for the renewal function
m(t)=E[N_{t}];
solving renewaltype equations by using Laplace transform;
another derivation of the formula for the renewal function
m(t) by performing Laplace transformation on the formula
representing m(t)
as a sum of the c.d.f.s of all the T_{n}'s;
computing the renewal function m(t)
for a Poisson process in three ways:
(1) by using the fact that N(t) is a Poisson(λt) random variable,
(2) by expressing it as a sum of the c.d.f.'s of T_{n} (Prop. 5.6.2),
(3) by solving the integral equation for m(t) using Laplace transform;
the momentgenerating function M_{X}
of a (0,∞)valued random variable X:Ω→(0,∞)
is equal to the LaplaceStieltjes transform of the c.d.f. F_{X}
of X and, if the random variable X is continuous,
equal to the Laplace transform of the p.d.f. ƒ_{X} of X.
Queues:
setup of the problem, examples of queues
(queues with baulking, multiple servers, airline checkin, FIFO, LIFO,
group servise, "student discipline", "continental queueing");
A/S/s/c/p/D classification of the queues,
where A and S are deterministic (D),
Markovian
(M  with exponentially distributed interrarival/service times),
Γ (or Erlang), or general (G) distributions,
s is the number of servers, c is the capacity of the system,
p is the size of the population, D is the discipline (i.e., service policy);
stability of a queue;
a detailed solution of the M(λ)/M(μ)/1 queue:
obtaining the stationary distribution π
(and the condition for existence of a stationary distribution),
computing the probability that the waiting time W will be zero,
the conditional average of W given that there are j customers
in the queue, and the average E[W]
(both averages for large t so that the stationary distribution
has been reached);
M(λ)/G/1 queue  constructing of a discretetime Markov
chain embedded in the queueing process
and derivation of the transition probability matrix of this Markov chain.

Lecture 11 (Tue, Nov 3):
General properties of stochastic processes:
cumulative distribution function
F(x_{1},...,x_{k};t_{1},...,t_{k})=F_{X(t1),...,X(tk)}(x_{1},...,x_{k}),
probability mass function
p(x_{1},...,x_{k};t_{1},...,t_{k})=p_{X(t1),...,X(tk)}(x_{1},...,x_{k}),
and probability density function
ƒ(x_{1},...,x_{k};t_{1},...,t_{k})=ƒ_{X(t1),...,X(tk)}(x_{1},...,x_{k})
of order k of a stochastic process
X={X_{t}:t∈[0,∞)};
mean
m_{X}(t)=E[X_{t}],
autocorrelation function
R_{X}(t_{1},t_{2})=E[X_{t1}X_{t2}],
autocovariance function
C_{X}(t_{1},t_{2})=R_{X}(t_{1},t_{2})−m_{X}(t_{1})m_{X}(t_{2}),
variance
var X(t)=C_{X}(t,t),
and autocorrelation coefficient
ρ_{X}(t_{1},t_{2})
of a stochastic process X;
processes with indepent increments;
processes with stationary increments;
strictsense stationary (SSS, strongly stationary) processes;
widesense stationary (WSS, weakly stationary) processes;
an example of a WSS stochastic process that is not SSS;
average power E[X_{t}^{2}] of a stochastic process;
E[X_{t}^{2}] of a WSS stochastic process
does not depend on t;
spectral density S_{X}(ω) of a WSS process;
properties of S_{X}(ω)
[Sec. 2.1 and 2.2 of [L]]
Gaussian and Markov processes:
multinormal distribution of a random vector
X=(X_{1},...,X_{n})∼N(m,K),
vector of the means m, covariance matrix
K=(cov(X_{i},X_{j}));
characteristic function φ_{X}(ω)=E[exp(iωX)]
of a random variable X,
(joint) characteristic function
φ_{X}(ω)=E[exp(iω⋅X)]
of a multinormal random variable X
(Prop. 2.4.1);
if two components of
X=(X_{1},...,X_{n})∼N(m,K)
are uncorrelated, then they are independent;
Gaussian process {X_{t}}
 a continuoustime stochastic process with
(X_{t1},...,X_{tn})
being multinormal for any n and times
t_{1},...t_{n};
if {X_{t}} is a Gaussian process
such that its mean m_{X}(t)
does not depend on t
and its autocovariance function
C_{X}(t_{1},t_{2})
depends only on t_{2}−t_{1},
then the process is SSS (Prop. 2.4.2);
definition of a Markov (or Markovian) processes, examples
(random walk, Poisson process);
(firstorder) density function
ƒ(x;t)=ƒ_{X(t)}(x);
conditional transition density function
p(x,x_{0};t,t_{0})=ƒ_{X(t)X(t0)}(xx_{0});
integrals of ƒ(x;t)
and
p(x,x_{0};t,t_{0})
over x are equal to 1;
expressing ƒ(x;t)
as in integral of
ƒ(x_{0};t_{0})p(x,x_{0};t,t_{0})
over x_{0};
more on the meaning of the p.d.f. of a continuous RV:
P(X∈(x,x+Δx])≈ƒ_{X}(x)Δx,
generalization for jointly continuous random vectors
P(X∈A)≈ƒ_{X}(x)vol(A)
where A is a small domain in R^{k}
containing x;
application to kth order p.d.f.'s of a random process:
P(X_{t1}∈(x_{1},x_{1}+Δx_{1}],...,X_{tk}∈(x_{k},x_{k}+Δx_{k}])≈ƒ_{(Xt1,...,Xtk)}(x_{1},...,x_{k})Δx_{1}...Δx_{k};
ChapmanKolmogorov equations for the
conditional transition density function
p(x,x_{0};t,t_{0})=ƒ_{XtXt0}(xx_{0})
[pages 5863 of Sec. 2.4 of [L]]
A digression on generalized functions (distributions):
test functions (infinitely smooth compactly supported functions);
Dirac δfunction δ_{a}
defined by δ_{a}(ƒ):=ƒ(a);
derivatives of generalized functions  defined by applying integration by parts,
treating the generalized function as a regular function
and using that for a test function ƒ
lim_{x→∞}ƒ(x)=0
and
lim_{x→−∞}ƒ(x)=0
(because ƒ has compact support):
this gives us
that integral of ƒ times the kth derivative
ξ^{(k)} of a generalized function ξ
is equal to (−1)^{k} times
integral of ξ times ƒ^{(k)},
which symbolically can be written as
ξ^{(k)}(ƒ):=(−1)^{k}ξ(ƒ^{(k)});
following this recipe, the derivatives of δ_{a}
defined by δ_{a}'(ƒ):=−ƒ'(a),
δ_{a}''(ƒ):=(−1)^{2}ƒ''(a),
and in general
δ_{a}^{(k)}(ƒ):=(−1)^{k}ƒ^{(k)}(a);
example: generalized derivative
of the Heaviside (unit step) function:
H_{a}'=δ_{a}.

Lecture 12 (Tue, Nov 10):
A digression on generalized functions (distributions) (cont.):
interpretation of generalized functions as a "rough" signal,
and of the test function as a "smoothing" function
corresponding to the "smearing" due to the experimental device.
The Wiener process (Brownian motion):
normal (Gaussian) random variables N(μ,σ^{2})
 p.d.f., mean, variance, characteristic function,
standard normal random variable Z∼N(0,1)
which can be obtained from Z∼N(μ,σ^{2})
as Z=(X−EX)/σ_{X};
computing the characteristic function of a symmetric simple random walk
on the state space ηZ={...,−2η,−η,0,η,2η,...},
with jumps (of size η) occurring as a Poisson process with rate λ/2,
proof that in the limit η→0, λ→∞, λη^{2}=1
X_{t}∼N(0,t);
definition of Brownian motion/Wiener process
W_{t}∼N(0,σ^{2}t)
and a standard Wiener process
B_{t}∼N(0,t);
the Wiener process as a limit of simple random walk;
historical remarks (Robert Brown, Albert Einstein,
Marian Smoluchowski, Norbert Wiener, Andrey Kolmogorov);
p.d.f. of order k of a Wiener process;
moments of W_{t}:
mean E[W_{t}]=0,
autocovariance function
C_{W}(t,s)=E[W_{t}W_{s}]=σ^{2}min(t,s),
autocorrelation function
R_{W}(t,s)=E[W_{t}W_{s}]=σ^{2}min(t,s);
proof that tW_{1/t}
is a Brownian motion (Example 4.1.2)
[pages 173179 of Sec. 4.1]

Lecture 13 (Tue, Nov 17):
σalgebras and probability measures:
sample space Ω; outcome (elementary event) ω  an element of Ω;
σalgebra F of subsets of Ω;
event  an element of F; examples;
Borel σalgebra B(R) of subsets of R;
subσalgebra G⊆F
of F;
σalgebra σ(A_{1},A_{2},...)
generated by a collection A_{1}, A_{2},... of subsets of Ω;
examples;
probabiliy measure P:F→[0,1] on (Ω,F);
Lebesgue measure L:B([0,1])→[0,1] on [0,1] defined by
L((a,b))=b−a;
probability space (Ω,F,P);
Fmeasurable functions
X:Ω→R  for which
{X∈B}∈F for all
B∈B(R);
random variable on (Ω,F)
 an Fmeasurable function X:Ω→R;
an example: a σ(∅)measurable function is a constant function;
more examples;
σalgebra σ(X) generated by a random variable X;
σalgebra σ(F_{1},...,F_{n})
generated by a by a collection of σalgebras;
σalgebra σ(X_{1},...,X_{n})
generated by a family of random variables
X_{1},...,X_{n};
filtration
F_{1}⊆F_{2}⊆F_{3}⊆... of σalgebras generated by a sequence
X_{1},X_{2},X_{3},...
of functions X_{k}:Ω→R,
where F_{k}=σ(X_{1},...,X_{k});
example: filtration of σalgebras generated by a sequence of coin tosses;
distribution (cumulative distribution function, c.d.f.)
F_{X}(x)=P(X≤x)=P({ω∈Ω:X(ω)≤x}) of a random variable X;
expectation E[X] of a random variable X as an integral over R
of x dF_{X}(x)
or, equivalently, as an integral over Ω of X(ω) P(dω);
integrable (L^{1}) random variables (for which E[X]<∞).
Conditional expectation and martingales:
conditional expectation E[XA]
of a random variable X conditioned on an event A;
conditional expectation E[XF]
of a random variable X conditioned on a σalgebra F;
conditional expectation E[XY]
of a random variable X conditioned on another random variable Y;
discussion of the meaning of the filtration
F_{1}⊆F_{2}⊆F_{3}⊆...
with
F_{n}=σ(X_{1},...,X_{n})
in the context of "coin tossing" (where X_{n} is the result of the nth toss)
 F_{n} represents our knowledge at time n;
a sequence Y_{1},Y_{2},... of random variables
adapted to the filtration
F_{1}⊆F_{2}⊆F_{3}⊆...
 each Y_{n} is
F_{n}measurable
(i.e., can be determined from the values of the random variables
X_{1},...,X_{n}
generating the σalgebra
F_{n}=σ(X_{1},...,X_{n}));
an example  the running averages S_{n};
martingale M_{1},M_{2},...
with respect to a filtration F_{1}⊆F_{2}⊆F_{3}⊆...
 a sequence of L^{1}random variables adapted to the filtration
and such that E[M_{n+1}F_{n}]=M_{n};
an example of a martingale  the positions
Y_{1},Y_{2},... of a particle in a simple symmetric random walk;
a continuoustime example of a martingale  for a Poisson process {N_{t}}_{t≥0}
with intensity λ,
M_{t}=N_{t}−λt is a martingale.

Lecture 14 (Tue, Nov 24):
Conditional expectation and martingales (cont.):
example  exponential martingale
exp(αB_{t}−α^{2}t/2),
obtaining a family of polynomial martingales from the Taylor
expansion of the exponential martingale with respect to α around α=0:
exp(αB_{t}−α^{2}t/2)=1+B_{t}α+(1/2)(B_{t}^{2}−t)α^{2}+(1/6)(B_{t}^{3}−3tB_{t})α^{3}+(1/24)(B_{t}^{4}−6tB_{t}^{2}+3t^{2})α^{4}+(1/120)(B_{t}^{5}−10tB_{t}^{3}+15t^{2}B_{t})α^{5}+...
The Wiener process (Brownian motion) (cont.):
a brief review  definition of W_{t} and B_{t},
increments, moments
(E[W_{t}^{odd power}]=0,
Var W_{t}=E[W_{t}^{2}]=σ^{2}t,
E[W_{t}^{4}]=3σ^{4}t^{2},
E[W_{t}^{6}]=15σ^{6}t^{3},...),
autocorrelation and autocovariance functions,
probability density function
ƒ(x_{1},...,x_{k};t_{1},...,t_{k})=ƒ_{W(t1),...,W(tk)}(x_{1},...,x_{k})
of order k expressed as product of the p.d.f.
ƒ(x_{1};t_{1})=ƒ_{W(t1)}(x_{1})
and the conditional p.d.f.'s
ƒ_{W(tj)W(tj−1)}(x_{j}x_{j−1}) for j=2,...,k,
explicit expressions for all p.d.f.'s;
shorttime behavior: for Δt>0 and
ΔB_{t}:=B_{t+Δt}−B_{t},
computing
E[ΔB_{t}^{odd power}]=0 and
E[(ΔB_{t})^{2}]=1/Δt→∞
as Δt→0^{+},
nondifferentiability of the Brownian motion;
Gaussian white noise ξ_{t}:=dB_{t}/dt;
making sense of the derivative dB_{t}/dt
as a (random) generalized function acting on a test function φ,
definition of a functional Ξ(φ) as an integral of ξ_{t}φ(t)
over t from 0 to ∞
(meaning; a measurement "smeared by φ"),
and a proof that E[Ξ(φ)]=0 and that E[Ξ(φ)^{2}]
equals integral of φ(t)^{2} over t from 0 to ∞,
interpreting these facts as
E[ξ_{t}]=0 and that E[ξ_{t}ξ_{s}]=δ(t−s).
Stochastic differential equations (SDEs):
the standard Brownian motion can be considered as the solution
of the initial value problem
dB_{t}/dt=ξ_{t}, B_{0}=0
for the unknown function B_{t} whose evolution
is driven by Gaussian white noise ξ_{t};
on meaning of an SDE  computing the transition probability density
ƒ_{BtBs}(xy)=ƒ(x,yt,s)
for 0≤s<t
as a solution of an initialvalue problem for a partial differential equation,
e.g., ∂_{t}ƒ(x,yt,s)=(1/2)∂_{xx}ƒ(x,yt,s),
limit of ƒ(x,yt,s) as t→s^{+} equals δ(x−y);
a generalization:
dX_{t}/dt=ƒ(t,X_{t})+g(t,X_{t})ξ_{t};
discretization by using the values at the left end:
ΔX_{t}≈ƒ(t,X_{t})Δt+g(t,X_{t})ΔB_{t},
X_{t+Δt}=X_{t}+ΔX_{t}
(similar to the Euler method for integration of ODEs),
main reason for using this discretization  the increment ΔB_{t}
is independent of the value of X_{t} and B_{t};
Itô integrals as a limit (in some sense) of left Riemann sums.

Lecture 15 (Tue, Dec 1):
Stochastic differerential equations and Itô integrals:
using left Riemann sums to approximate the solution of the SDE
dX_{t}=ƒ(t,X_{t})dt+g(t,X_{t})dB_{t};
definition and examples of of L^{1}limit
and m.s.limit (meansquare limit, L^{2}limit) of series of functions;
definition of Itô integral as a m.s.limit of the left Riemann sums
∑_{i} g(t_{i},X_{i}) ΔB_{i};
useful facts for calculations:
E[(ΔB_{i}^{odd power})]=0,
E[(ΔB_{i})^{2}]=Δt_{i},
E[(ΔB_{i})^{4}]=3(Δt_{i})^{2},
E[g(t_{i},B_{i})ΔB_{i}]=0,
E[g(t_{i},B_{i})(ΔB_{i})^{2}]=E[g(t_{i},B_{i})]Δt_{i},
E[(ΔB_{i})^{k}(ΔB_{j})^{m}]=E[(ΔB_{i})^{k}]E[(ΔB_{j})^{m}] for i≠j;
computing the Itô integral from t_{0} to t of B_{s}dB_{s};
writing the result about the integral in the form
d(B_{t}^{2})=2B_{t}dB_{t}+dt; similar result for
d(B_{t}^{k}) for k=3,4,5,...;
Itô formula for dΨ(t,X_{t})
where Ψ(t,x) is a function of two variables
and X_{t} satisfies the SDE
dX_{t}=ƒ(t,X_{t})dt+g(t,X_{t})dB_{t}, mnemonic rules for deriving the formula;
remarks on the meaning of the solution X_{t} of a SDE;
nonanticipating functions and expectation of Itô integrals;
properties of Itô integrals; correlation formula; Itô isometry;
example  simple population growth at a noisy rate:
dX_{t}/dt=(r+αξ_{t})X_{t}
or, equivalently,
dX_{t}=rX_{t}dt+αX_{t}dB_{t}, obtaining the solution X_{t}=X_{0}e^{(r−α2/2)t+αBt} by using Itô formula, computing the average
E[X_{t}]=E[X_{0}]e^{rt},
discussion of the behavior of the solutions for
r>α^{2}/2 and for r<α^{2}/2,
remarks about the interpretation of the numerical simulations of the SDE.

Lecture 16 (Tue, Dec 8):
Stochastic differerential equations and Itô integrals (cont.):
using the exponential martingale to analyze the average of the population
in the problem of simple population growth at a noisy rate
("geometric Brownian motion"), computing the variance of the population at time t;
example: linear growth with noise that is proportional to the population:
dX_{t}=dt+X_{t}dB_{t},
solving the problem by "integration by parts" in stochastic calculus,
d(X_{t}Y_{t})=X_{t}dY_{t}+Y_{t}dX_{t}+(dX_{t})(dy_{t}),
computing the mean and the variance of the solution;
meaning and derivation of the FokkerPlanck equation for the conditional transition
density function p(x,x_{0};t,t_{0});
solution of the FokkerPlanck equation for the standard Brownian motion,
physical interpretation of the solution;
solution of the FokkerPlanck equation for the geometric Brownian motion
(lognormal distribution);
idea of Stratonovich integral.
Grading:
Your grade will be determined by your performance
on the following coursework:
Homework (lowest grade dropped) 
50% 
Takehome midterm exam 
20% 
Takehome final exam 
30% 
Homework:
Homework assignments will be given
regularly throughout the semester and will be posted on this website.
The homework will be due at the start of class on the due date.
Each homework will consist of several problems,
of which some pseudorandomly chosen problems will be graded.
Your lowest homework grade will be dropped.
All homework should be written on a 8.5"×11" paper
with your name clearly written, and should be stapled.
No late homework will be accepted!
You are encouraged to discuss the homework problems
with other students.
However, you have to write your solutions clearly
and in your own words  this is the only way to
achieve real understanding!
It is advisable that you first write a draft
of the solutions and then copy them neatly.
Please write the problems in the same order
in which they are given in the assignment.
There is no need to type the homework, but please use your best handwriting!
Exams:
There will be one takehome midterm and a comprehensive takehome final.
All tests must be taken at the scheduled times, except in extraordinary circumstances.
Please do not arrange travel plans that will prevent you
from taking any of the exams at the scheduled time.
Good to know: