Transcript variance reduction

VARIANCE
REDUCTION
CALCULATIONS ON
VARIANCES: SOME BASICS
Let X and Y be random variables
1)VAR[ X ]  E[ X ]  ( E[ X ])
2
2
2)VAR[ X  Y ]  VAR[ X ]  VAR[Y ]  2COV [ X , Y ]
3)COV [ X , Y ]  E[ XY ]  E[ X ]E[Y ]
4)VAR[cX ]  c VAR[ X ]
2
5)VAR[ X  Y ]  VAR[ X ]  VAR[Y ]  2COV [ X , Y ]
COV=0 if X and Y are independent.
COMMON RANDOM NUMBERS
Built for distinguishing among two systems
di = yi – xi
Variance reduced by COV(X, Y)
Streaming induces MORE Covariance
STREAMING
Segregate the random number generation
task into streams connected to
phenomena
seed1
Zi=aZi-1 mod m
seed2
Inter-arrival
times
Service
times
1. Change features of the service.
2. Use exact same arrival stream for
comparing each service setting.
ANTITHETIC VARIATES
Use Uniforms U1, U2, ... to generate a sample
Use Uniforms 1-U1, 1-U2, ... to generate a
second sample
Combine the samples
Extreme values get canceled out
Depends on...

effective streaming

straightforward F-1(U) method of variate generation
spreadsheet...
CONTROL VARIATES
X is your output variable

You seek the Expected Value of X
Y is a random variable


Y is one of the variables that we are generating
We know the Expected Value of Y
Example


X is the total waiting time of a customer
Y is the inter-arrival time before he entered service
...more CONTROL VARIATES
Xc is a random variable with less Variance and
the same Expected Value
pick b to minimize VAR(Xc)
Xc  X  b (Y  E[Y ])
OPTIMAL CONTROL
Xc  X  b (Y  E[Y ])
VAR( Xc)  VAR( X )  b VAR(Y )  2bCOV ( X , Y )
2
VAR( Xc)
 2bVAR(Y )  2COV ( X , Y )  0
b
COV ( X , Y )
b* 
VAR(Y )
IMPORTANT
CALCULATIONS
Fusing many results in statistics
2
 COV ( X , Y )
 COV ( X , Y ) 
 VAR(Y )  2
VAR( Xc)  VAR( X )  
 VAR(Y ) 
 VAR(Y )
COV ( X , Y ) 2
 VAR( X ) 
VAR(Y )

COV ( X , Y ) 2 

 VAR( X )1 
 VAR( X )VAR(Y ) 
 VAR( X )(1   XY )
2

COV ( X , Y )

ALSO KNOWN AS...
We are regressing X vs. Y
b* is the parameter that a regression
package would calculate
 = SQRT[COV(X,Y)2/VAR(X)VAR(Y)]
is the correlation coefficient of X and Y
 =1 or -1 implies


Y completely explains X and
VAR(Xc)=0