Summary Foundations of Stochastic Modeling - 2010 Lecture Notes

Foundations of Stochastic Modeling Page 1



FOUNDATIONS OF STOCHASTIC
MODELING

LECTURE 1 – 19th January 2010




Probability Preliminaries
 Set operations
o When we talk of a probability space, we quote a triple (W,  ,  ) , where

 W is the space of outcomes
  is a s -field – the space of “admissible sets/events”. The sets we will
be talking about henceforth reside in  .
  is a probability distribution/measure based on which statements are
made about the probability of various events.  :   [0,1] . In particular,
for A Î  , (A) =  (w Î W : w Î A) .

o Note the following basic property of unions and intersections of sets
c
é ù
êë n An úû =  n An
c



Or equivalently:
c
 Ac = éêën An ùúû
n n

o When we say an event A holds “almost surely”, we mean that
 (A) = 1
 A Î  (in other words, A is measurable). We will assume this always
hold throughout this course and omit this condition.
o Proposition: Let {A }
n
be a sequence of (measurable) events such that

(An ) = 1 for all n. Then  ( n An ) = 1 .

Proof: First consider that




Transcribed by Daniel Guetta from
lectures by Assaf Zeevi, Spring 2011

,Foundations of Stochastic Modeling Page 2


c
é ù
êë n An úû =  n An
c



Then consider that, using the union bound

 ( n ) ( )
Anc £ å n  Anc
= å n 1 -  (An )
= ån 0
=0
The union bound, used in the first line, simply states that if we add the
probability of events without subtracting their intersections, the result will be
greater than when considering the union (which leaves out intersections). 
o Definition (limsup and liminf): Let {an } be a real-value sequence. Then we

write
lim supn an := infm supn ³m an

This is the least upper bound on that sequence. Similarly
lim infn an := supm infn ³m an

Graphically (source: Wikipedia):
an

lim supn ¥ an

lim infn ¥ an
n
Note that these limits need not be finite.
Remarks:
 If lim supn an < a , then an < a eventually (ie: for sufficiently large n). If
lim supn an > a , then an > a infinitely often – in other words, there are
infinitely many elements in the sequence above a.
 Similarly, lim infn an > a  an > a ev. and lim inf an < a  an < a i.o.
We now attempt to extend this definition to sets.
o Definition (limsup and liminf for sets): Let {A }
n
be a sequence of

measurable sets. Then




Transcribed by Daniel Guetta from
lectures by Assaf Zeevi, Spring 2011

,Foundations of Stochastic Modeling Page 3


lim supn An := m n ³m An = limm ¥ n ³m An
lim infn An := m n ³m An = limm ¥ n ³m An

We can interpret these as follows. The lim sup of An is the set of events that are
contained in infinitely many of the An (but not necessarily in all the An past a
point – the event could “bounce in and out” of the An)

{lim sup n
An } = {w Î W : w Î An i.o.}

Similarly, the lim inf of An is the set of events that eventually appear in an An
and then in all An past that point.

{lim inf n
An } = {w Î W : w Î An ev.}

Clearly, if an event is in the lim inf, it also appears infinitely often (because it
appears in all the An past a point, and so lim infn An Í lim supn An .
Remark: Take {An , ev.} = {lim infn An } . Then
c
{A , ev.} = éêm n ³m An ùú
c
n ë û
= m {( A
n ³m n )}
c



= m n ³m Anc
= lim infn Anc
{
= Anc , i.o. }
o Proposition: Let {An } be a sequence of measurable sets, then

  (lim infn An ) £ lim infn  (An )

  (lim supn An ) ³ lim supn  (An )

(The first statement can be thought of as a generalization of Fatou’s Lemma for
probabilities).
Proof of (i): Let us define Bm =  n ³m An . Then we know that

 Í Bm Í Bm +1 Í  . In other words, the sets Bm increase monotonically to

B =  m Bm =  m n ³m
An = lim infn An

Since the events are increasing, a simple form of monotone convergence gives us
that  (Bn )   (B ) . But we also have that

 (Bm ) £  (An ) n ³m




Transcribed by Daniel Guetta from
lectures by Assaf Zeevi, Spring 2011

, Foundations of Stochastic Modeling Page 4


because Bm is the intersection of all events from Am onwards, so its probability is
less than or equal to the probability of any single event. Thus

 (Bm ) £ infn ³m  (An )
supm  (Bm ) £ supm infn ³m  (An )
 (B ) £ lim infn  (An )

And given how we have defined B:
 (lim infn An ) £ lim infn  (An )

As required. 

 Borel-Cantelli Lemmas & Independence
o Proposition (First Borel-Cantelli Lemma) Let {A } be a sequence of
n


measurable events such that å n
(An ) < ¥ . Then  (A i.o.) = 0 . In other
n


words,  (lim supn An ) = 0 .1 We offer two proofs – the first is somewhat

mechanical, the second is more intuitive.

Proof (version 1): Consider that
lim supn An =  m n ³m
An

As such

 (lim supn An ) £  ( n ³m
An )
£ å n ³m  (An )
0
As required. 

The second proof will require a lemma:
Lemma (Fubini’s): If {Xn } is a sequence of real-valued random variables with

X n ³ 0 , then  ( å n Xn ) = å n  (Xn ) (which could be infinite). This is




1
It might not be clear that the statements  (An i.o.) = 0 and  (lim supn An ) = 0 are equivalent. To see
this more clearly, note that the first statement is simply a shorthand for  (w Î W : w Î An i.o.) = 0 . This
is clearly identical, by definition, to  (lim supn An ) = 0 .




Transcribed by Daniel Guetta from
lectures by Assaf Zeevi, Spring 2011