Transcript ulimit

Monte Carlo Approximations – Introduction
• Suppose X1, X2,… is a sequence of independent and identically
distributed random variables with unknown mean µ.
• Let M n 
1
n
 X1    X n .
• The laws of large numbers indicate that for large n, Mn ≈ µ.
• Therefore, it is possible to use Mn as an estimator or approximation
of µ.
• Estimators like Mn can also be used to estimate purely mathematical
quantities that are too difficult to compute directly.
• Such estimators are called Monte Carlo approximations.
STA347 - week 12
1
Example
• Suppose we wish to evaluate the integral

 
I   25 x 2 cos x 2 e  25 x dx.
0
• This integral cannot easily be solved exactly, but it can be computed
approximately using a Monte Carlo approximation.
• We first note that, I = E(X 2 cos(X 2)) where X ~ Exponential(25).
• Hence, for large n the integral I is approximately equal to ,
M n  1n T1    Tn  where , Ti  X i2 cosX i2  with X1, X2,…i.i.d
Exponential(25).
• Further, in the example on slide 10, we established a method to
simulate X ~ Exponential(25).
STA347 - week 12
22
• Putting things together we obtain the following algorithm for
approximating the integral I.
Step 1: Select a large positive integer n.
Step 2: Obtain Ui ~ Uniform[0, 1], independently for i = 1, …, n.
1
Step 3: Set , X i   25
ln 1  U i  for i = 1, …, n.
 
Step 4: Set , Ti  X i2 cos X i2 for i = 1, …, n.
Step 5: Estimate I by M n 
1
n
T1    Tn 
• For large n this algorithm will provide a good estimate of the
integral I.
STA347 - week 12
3
Example Using R
• The following is the R code for approximating the integral I in the
example above.
> U
> X
> T
> I
> I
[1]
=
=
=
=
runif(100000)
-(1/25)*log((1-U), base = exp(1))
X^2*cos(X^2)
mean(T)
0.00318922
STA347 - week 12
4
Assessing Error of MC Approximations
• Any time we approximate or estimate a quantity, we must also
indicate how much error there is in the estimate.
• However, we cannot say what the error is exactly since we are
approximating an unknown quantity.
• Nevertheless, the central limit theorem provide a natural approach to
assessing this error, using three times the standard error of the
estimate.
• Thus, we can approximate an unknown quantity such as the integral
I in the example above by quoting Mn and the interval
M
n
 3S
n , Mn  3S
n

STA347 - week 12
5
Assessing Error Using R
• The following is the R code for assessing the error in the
approximation of the integral I.
> llimit = I - 3*sd(T)/sqrt(100000)
> llimit
[1] 0.003121188
> ulimit = I + 3*sd(T)/sqrt(100000)
> ulimit
[1] 0.003257252
• Conclusion: the value of I is approximately 0.003189 and the true
value is almost certainly in the interval (0.003121, 0.003257).
STA347 - week 12
6
Conditional Probability on a joint discrete distribution
• Given the joint pmf of X and Y, we want to find
P X  x | Y  y  
P X  x and Y  y 
PY  y 
PY  y | X  x  
P X  x and Y  y 
P X  x 
and
• These are the base for defining conditional distributions…
STA347 - week 12
7
Definition
• For X, Y discrete random variables with joint pmf pX,Y(x,y) and marginal mass
function pX(x) and pY(y). If x is a number such that pX(x) > 0, then the
conditional pmf of Y given X = x is
pY | X  y | x   pY | X  y | X  x  
• Is this a valid pmf?
p X ,Y x, y 
p X x 
• Similarly, the conditional pmf of X given Y = y is
p X |Y x | y   p X |Y x | Y  y  
p X ,Y x, y 
pY  y 
• Note, from the above conditional pmf we get
p X ,Y x, y   p X |Y x | y  pY  y 
Summing both sides over all possible values of Y we get
p X x    p X ,Y x, y    p X |Y x | y  pY  y 
y
y
This is an extremely useful application of the law of total probability.
• Note: If X, Y are independent random variables then PX|Y(x|y) = PX(x).
STA347 - week 12
8
Example
• Suppose we roll a fair die; whatever number comes up we toss a coin that
many times. What is the distribution of the number of heads?
Let X = number of heads, Y = number on die.
We know that
1
pY  y  
, y  1, 2, 3, 4, 5, 6
6
Want to find pX(x).
• The conditional probability function of X given Y = y is given by
 y  1 
p X |Y x | y     
 x  2 
2
for
• By the Law of Total Probability we have
x = 0, 1, …, y.
 y  1  1
p X x    p X |Y x | y  pY  y       
6
y
y  x  x  2 
6
y
Possible values of x: 0,1,2,…,6.
STA347 - week 12
9
Conditional densities
• If X, Y jointly distributed continuous random variables, the conditional
density function of Y | X is defined to be
fY | X  y | x  
f X ,Y x, y 
f X x 
if fX(x) > 0 and 0 otherwise.
• If X, Y are independent then f Y | X  y | x   f Y  y  .
• Also,
f X ,Y x, y   f Y | X  y | x  f X x 
Integrating both sides over x we get

fY  y    fY | X  y | x  f X x dx

• This is a useful application of the law of total probability for the continuous
case.
STA347 - week 12
10
Example
• Consider the joint density
2 e y
f X ,Y x, y   
 0
0 x y
otherwise
• Find the conditional density of X given Y and the conditional density of Y
given X.
STA347 - week 12
11
Conditional Expectation
• For X, Y discrete random variables, the conditional expectation of Y given
X = x is
E Y | X  x    y  pY | X  y | x 
y
and the conditional variance of Y given X = x is
V Y | X  x     y  E Y | X  x   pY | X  y | x 
2
y


 E Y 2 | X  x  E Y | X  x 
2
where these are defined only if the sums converges absolutely.
• In general,
E hY  | X  x    h y   pY | X  y | x 
y
STA347 - week 12
12
• For X, Y continuous random variables, the conditional expectation of
Y given X = x is

EY | X  x    y  fY | X  y | x dy

and the conditional variance of Y given X = x is
 y  E Y | X

V Y | X  x   


 x   f Y | X  y | x dy
2

 E Y 2 | X  x  E Y | X  x 
• In general,
2
E hY  | X  x    h y   f Y | X  y | x dy
y
STA347 - week 12
13
Example
• Suppose X, Y are continuous random variables with joint density function
e  y
f X ,Y x, y   
0
y  0, 0  x  1
otherwise
• Find E(X | Y = 2).
STA347 - week 12
14
More on Conditional Expectation
• Assume that E(Y | X = x) exists for every x in the range of X. Then,
E(Y | X ) is a random variable. The expectation of this random variable is
E [E(Y | X )]
• Theorem
E [E(Y | X )] = E(Y)
This is called the “Law of Total Expectation”.
Proof:
STA347 - week 12
15
Example
• Suppose we roll a fair die; whatever number comes up we toss a coin that
many times. What is the expected number of heads?
STA347 - week 12
16
Theorem
• For random variables X, Y
V(Y) = V [E(Y|X)] + E[V(Y|X)]
Proof:
STA347 - week 12
17
Example
• Let X ~ Geometric(p).
Given X = x, let Y have conditionally the Binomial(x, p) distribution.
• Scenario: doing Bernoulli trails with success probability p until 1st success
so X : number of trails. Then do x more trails and count the number of
success which is Y.
• Find, E(Y), V(Y).
STA347 - week 12
18