Nonparametric Random Variate Generation Using a Piecewise-Linear Cumulative Distribution Function

Abstract

The standard approach to solving the interpolation problem for a trace-driven simulation involving a continuous random variable is to construct a piecewise-linear cdf that fills in the gaps between the data values. Some probabilistic properties of this estimator are derived, and three extensions to the standard approach (matching moments, weighted values, and right-censored data) are presented, along with associated random variate generation algorithms. The algorithm is a nonparametric blackbox variate generator requiring only observed data from the user.