Transcript Document

Conditionality and stopping
times in probability
Mark Osegard, Ben Speidel, Megan
Silberhorn, and Dickens Nyabuti
Conditional Expectation
Conditional Probability
Discrete: Conditional Probability Mass Function
PX  x | Y  y  PX  x, Y  y
PY  y
Continuous: Conditional Probability Density Function
f ( x, y )
fX | Y ( x | y ) :
fX ( y )
Conditional Expectation
Discrete:
EX | Y  y   xPX  x | Y  y
x

Continuous:
EX | Y  y   xfX | Y ( x, y)dx

Note:
y  E X | Y  y 
of y. We write this as
i.e.
is a function
E X | Y 
EX | Y  y   EX | Y  y
(Conditional Expectation Function)
Theorem:
EX   EEX | Y 
Clearly, when Y is discrete,
  EX | Y  yPY  y
y
When Y is continuous,

  EX | Y  y fY  y dy

Proof: Continuous Case
Recall, if X,Y are jointly continuous with
joint pdf f x, y 
Define:
f  x, y 
fX | Y  X | Y  
fY  y 

and
EX | Y  y   xfX | Y  X | Y dx

Note:




E
X
|
Y

y
f
Y  y dy 

 xfX

 

| Y  x | y dx  fY  y dy


 

  xf x | y  f  y dxdy
X | Y
Y

 f x, y 
   x
fY  y dxdy

fY  y  
 
 
Continuous Case Cont.

 
 


  xf x, y dxdy    xf x, y dydx
(Fubini’s Theorem)

 

 



x
f
x
,
y
dydx

 
 f x, y dy
So,

xf
X  x dx  E  X 


Therefore, concluding
EX   EEX | Y 
Summary:
When Y is discrete,
  EX | Y  yPY  y
y
When Y is continuous,

  EX | Y  y fY  y dy

Conditional Variance
Definition

Var ( X | Y )  E  X  EX | Y  | Y

2


 E X | Y  EX | Y 
2
2
Var X   EVar X | Y   VarEX | Y 
Proof
using
EX   EEX | Y 
since


Var  X | Y   E X | Y  E X | Y 
taking expectations of both sides
2
2
 
 E E X | Y  E E X | Y  
 E X  E E  X | Y  
E Var  X | Y   E E X | Y  E X | Y 
2
2
2
2
2
2

Note as well …


VarEX | Y   E EX | Y   EEX | Y 

2
2

 E EX | Y   EX 
2
2
…adding
 
E Var  X | Y   Var E X | Y   E X  E X 
2
2
 Var  X 
Thus we've shown that
Var  X   E Var  X | Y   Var E X | Y 
g
Stopping times
Stopping Times



Definition
Application to Probability
Applications of Stopping Times to other
formulas
Stopping Times

Basic Definition:
A Stopping Time for a process does exactly
that, it tells the process when to stop.
Ex) while ( x != 4 )
{ … }
The stopping time for this code fragment
would be the instance where x does equal 4.
Stopping times in Sequences

Define:
Suppose we have a sequence of Random
Variables (all independent of each other)
Our sequence then would be:
X1 , X 2 , X 3 ,...
Stopping Times: A Discrete Case

From our previous slide we have the
sequence:
X1 , X 2 , X 3 ,...

A discrete Random Variable N is a stopping
time for this sequence if :
{N=n}
Where n is independent of all following items
in the sequence
X n1, X n2 ,...
Independence
Summarizing the idea of stopping times with
Random Variables we see that the decision
made to stop the sequence at Random
Variable N depends solely on the values of
the sequence
X1 , X 2 ,..., X n
Because of this, we then can see that N is
independent of all remaining values
Xm, m  n
Applications of Stopping Times
Does Stopping Times affect expectation?
No!
Consider this statement:
N
S   Xi
i 1
E[S ]  E[ N ]E[ X ]
This formula, the formula used for Conditional
Expectation does remain unchanged
Applying Stopping Times
For an example of how to use stopping times
to solve a problem, we will now introduce to
you Wald’s Equation…
N
E[ X i ]  E[ N ]E[ X ]
i 1
Wald’s Equation
Proposition
If {X1, X2, X3, …} are independent identically distributed
(iid) random variables having a finite expectation E[X], and
N is a stopping time for the sequence having finite
expectation E[N], then:


E  X i   E[ N ]E[ X ]
 i 1 
N
Wald’s Proof
Let N1 = N represent the stopping time for the sequence
{X1, X2, …, XN }
1
Let N2 = the stopping time for the sequence
{X(N +1) , X(N +2), …, X(N +N )}
1
1
1
2
Let N3 = the stopping time for the sequence
{X(N +N +1) , X(N +N +2), …, X(N +N +N ) }
1
2
1
2
1
2
3
Wald’s Proof ...
We can now define the sequence of stopping times as
{N i } i  1
where {Ni} clearly represents,
N1, N2 , N3 , ...
and see the sequence is iid
Wald’s Proof…
If we define a sequence {Si} as,
where,
S i   S1S 2.....S m 
N1  N 2 ... N m
N1
N1  N 2


{Si }  S1   X i , S 2   X i , ... , Sm 
Xi 

i 1
i  N1 1
i  N1  N 2 ... N m1 

Note: {Si} are iid
Wald’s Proof…
S i   S1S 2.....S m  will consist of
{N1+ N2+ ... + Nm}
which are iid because the Xi’s are.
with common mean E[Xi ] = E[X]
Wald’s Proof…
By the Strong Law of Large Numbers,
lim
m 
{S1+ S2 + ... + Sm }
E [X]
=
{N1+ N2 + ... + Nm }
Wald’s Proof…
EX 
Also
S 1 S 2..... S m  N 1 N 2..... N m 
m

ES 
m
let m  

E N 
Concluding
So as we let
m 
EX   ES  EN 
Which can be manipulated into our preposition:


E[S ]  E  X i   E[ N ]E[ X ]
 i 1 
N
Miners Problem
Sample Conditional and Stopping times
in probability problem
The problem
A miner is trapped in a room containing three
doors. Door one leads to a tunnel that returns
to the same room after 4 days; door two
leads to a tunnel that returns to the same
room after 7 days; door three leads to
freedom after a 3 day journey. If the miner is
at all times equally likely to choose any of the
doors, find the expected value and the
variance of the time it takes the miner to
become free
Expected Value
Using Wald’s Equation:
X i  4,7,3
N  the stopping time
N  mini | X i  3
Continue ….
N is a geometricdistribution with a
1
Probability , selecting door 3 denotes
3
successonce this event occurs,its trial
Number will be set to N to denote the
stopping time.
Continue ….
Recall:
The expectedvalue of a Geometric
1
distribution is
p
1
 E N    3
1
3
Expected value Conclusion
Substituting using Wald' s Equation,
E X   E N E X i 
we get
14
E X   3   14 days
3
Thus on average,the miner is
expectedto attain freedom
in 14 days
Variance
using the equation
Var ( X )  E Var  X | N   Var E X | N 
Solution :


E  X | N  n   E  X i | N  n 
 i 1

n
n
  E X i | N  n
i 1
Continue…..
EX i | N  n   xPX i  x | N  n
 4 PX i  4 | N  n 7 PX i  7 | N  n
 3PX i  3 | N  n
 112
 E  X i | N  n  
3
in
i n
Continue…..
n 1
n
 EX
i 1
i
| N  n   E X i | N  n  E X i | N  n
i 1
11
 n  1  3
2
11
5
 n
2
2
11
5
 EX | N   N 
2
2
Continue…..
using
Var aX  b   a 2Var ( x )
then
5
 11
Var E  X | N   Var 
N 
2
 2
121

Var  N 
4
1
1
1 P
3 6
Var  N  

2
P2
1
 
 
3
Thus far
Var( X )  EVar X | N   VarEX | N 
||
||
?
363
2
Continue…..
 n

Var  X | N   Var  X i | N  n 
 i 1

n
 Var  X i | N  n 
i 1


Var  X i | N  n   E X | N  n  EX i | N  n


2
i
E X i2 | N  n   x 2 PX i  x | N  n
2
Continue…..
 4 2 PX i  4 | N  n 7 2 PX i  7 | N  n
 32 PX i  3 | N  n
 65
in

2
E Xi | N  n   2
9 i  n
 65 121 9

in
 
Var  X i | N  n    2
4
4
9  9  0
in


Continue…..
n 1
Var  X | N  n    Var  X i | N  n   Var  X n | N  n 
i 1
9
  N  1
4
9

E Var  X | N   E   N  1
4

9
9
9
 E N   E 1  3  1 
4
4
2
In conclusion
Var( X )  EVar X | N   VarEX | N 
||
||
9
2
363
2
Hence
9 363 372
Var  X   

 186
2
2
2
Thanks to:
Dr. Steve Deckelman
Dr. Ayub Hossain
Who helped make this a success!!!!!!!!!!!!!!!!!!!!!!!