Week 5 Flashcards
Typical Discrete-Time Output Performance Measures
Di = delay of the ith customer in queue
Average delay: Đ(N) = ΣDi/N
Maximum delay: D*(N) = maxDi
Proportion of customers that have waited more than 3 minutes: P3(N) = Σ I(3,∞)(Di)/N
-> where I(3,∞)(Di) = 1 if Di > 3, 0 else
Typical Continuous-Time Output Performance Measures
Time-average length of queue: Q̄(T) = ∫Q(t)dt)/T (integral from 0 to T)
Maximum length of queue: Q*(T) = max Q(t)
Proportion of time that there was more than 2 people in queue: P2(T) = ∫I(2,∞)(Q(t))dt/T
Server utilization: U(T) = ∫B(t)dt/T, where B(t) is busy function = 1 if server busy at time t
Holding cost in inventory: H(T) = h∫S(t)dt/T, where S(t) = # of stocks at time t
Terminating vs. Non-Terminating Simulation
Terminating simulation: there is a natural event that specifies the end of each replication
Non-terminating simulation: there is no natural event that specifies the end of a replication
Steady-State Parameter
A performance measure that is a characteristic of the steady-state distribution
- Theoretically, it does not depend on initial conditions
- Practically, we must ensure that run is long enough so that the impact of initial-condition is minimized
Not all non-terminating systems are steady-state: there could be a periodic “cycle” in the long run, giving rise to steady-state cycle parameters
When is steady-state relevant?
24 hours/day, manufacturing companies
Recursive Computation of Mean and Variance
- Initialize Xbar 0 = 0, S1^2 = 0
- Update mean: Xbar k+1 = Xbar k + (X k+1 - Xbar k)/(k+1)
- Update variance: Sk+1^2 = (1 - 1/k)Sk^2 + (k+1)(Xbar k+1 - Xbar k)^2
Mean Square Error (MSE)
E[ (Xbar - θ)^2 ] = σ^2/n
We can stop generating data when σ/sqrt(n) small
LOLN: at least 100 draws
Empirical Distribution Function
X1, …, Xn with CDF F
Consider a realization x1, …, xn of these r.v.s
Fe(x) = 1/n Σ I{xi ≤ x}, I{xi ≤ x} = 1 if xi ≤ x
Bootstrapping Purpose
To calculate the MSE of the empirical distribution
Impossible to compute analytically when n is large
Bootstrapping
- For r = 1, …, R
- Draw x1^r, … xn^r from Fe, that is drawn from the data:
- Let s be a draw from U[0,1]
- Set j = floor(ns)
- Return xj
- Compute Mr = [θ^*(x1^r, … xn^r) - θ(Fe)]^2
- Estimate of MSE(Fe) and, therefore of MSE(F):
1/R Σ Mr
-Typical value for R: 100
Bootstrapping Understanding
Take θ(Fe) from empirical distribution
Find θ^ for each sample
Find MSE for each sample: [θ^ - θ(Fe)]^2
Take average of MSEs to find bootstrap approximation
Confidence Interval Formula
Xbar (n) ± t(n-1, 1-α/2)sqrt(S^2(n)/n)
Idea of Specified Precision
Make the half-width of the CI small enough
δ(α, n) = t(n-1, 1-α/2)sqrt(S^2(n)/n)
Absolute Precision
Specify β > 0, want n big enough s.t. δ(α, n) < β
Requires at least some knowledge of context to set meaningful β
Relative Precision
Card not working - delta/xbar < gamma; don’t need to know much to set meaningful
Sequential Approach
Idea: Increase n until δ(α, n) is small enough
Algorithm:
- Choose a confidence level and an acceptable value β for CI length
- Generate at least 100 data values
- Continue to generate additional data, stopping when δ(α, n*) < β
- The estimate is given by Xbar(n) = 1/n ΣXi
Two-Stage Approach
Idea: One quick way to estimate n* is to use fixed estimates of S(n) based on a small # of replications
1. Use a pilot sample (small number of trial runs e.g. n1 replications) to get estimates of sample variance
2. Substitute these in the formulas for the required sample sizes
n* = min{i≥n1 : t(i-1, 1-α/2)*sqrt(Sn1^2/i) < β)
Using Normal Distribution instead of t-student
n* = Sn1^2* (Z(α/2)/β)^2
Replication/Deletion Approaches Disadvantages
No completely reliable method to identify an appropriate warm-up period
Too long -> wasteful of data
Too short -> point-estimator bias, which can have serious consequences
Reason to Use Bootstrap
Have a small but significant sample of an unknown distribution and want to construct e.g. confidence intervals
