Summary Foundations of Stochastic Modeling - 2010 Lecture Notes
4 views 0 purchase
Course
Sciences
Institution
Sciences
Columbia Business School - First Year of the Doctoral Program in Decisions, Risk and Operations
• Stochastic processes
o Notes from Prof Assaf Zeevi's "Foundations of Stochastic Modelling".
o Notes from Prof David Yao's "Stochastic Processes II".
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
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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller tandhiwahyono. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $2.60. You're not tied to anything after your purchase.
