| For many complex stochastic systems, simulation has become the preferred, if not only, means of analysis. We study quantile estimation and stochastic dynamic programming by using sample path estimates.; The use of quantiles as primary measures of performance has gained prominence recently, especially in the financial industry, where Value at Risk (VaR) has emerged as a standard tool to measure and control the risk of trading portfolios. In terms of statistics, VaR is nothing more than a quantile of a portfolio's potential profit and loss over a given time period. For quantile estimation, we analyze the probability that a quantile estimator fails to lie in a pre-specified neighborhood of the true quantile. First, we show that this error probability converges to zero exponentially as the sample size increases for negatively dependent sampling. Then we consider stratified quantile estimators and show that the error probability for these estimators can be guaranteed to be 0 with sufficiently large, but finite, sample size. Numerical experiments on a VaR example illustrate the potential for dramatic orders of magnitude variance reduction.; For stochastic dynamic programming problems, by applying the theory of large deviations, we establish conditions under which the sample path optimal policy converges to the true optimal policy, for both finite and infinite horizon problems, at an asymptotically exponential convergence rate. This is in contrast with the usual canonical (inverse) square root rate associated with standard statistical output analysis for performance evaluation, here corresponding to estimation of the value (cost-to-go) function itself. Then, a portfolio selection problem in finance, interesting in its own right, is used to illustrate the convergence rate results. We show that the sample path solution converges to the true solution at an asymptotically convergence rate. |
