On the simultaneous construction of sample paths

Sensitivity analysis and optimization within stochastic discrete event simulation require the ability to rapidly estimate performance measures under different parameter values. One technique, termed “rapid learning”, aims at enumerating all possible sample paths under different parameter values of the model based on the observed sample path under the nominal parameter value. There are two necessary conditions for this capability: observability, which asserts that every state observed in the nominal path is always richer in terms of feasible events than the states observed in the constructed paths, and constructability, which, in addition to observability, requires that the lifetime of an event has the same distribution as its residual life. This paper asserts that the verification of the observability condition is an NP-hard search problem. This result, in turn, implies that it is algorithmically not possible to find parameter values satisfying observability; hence, it encourages the development of heuristic procedures. Further implications are also discussed