隨著科技發展的進步，生活中的問題也越來越複雜，當問題難以使用數學模式分析時，利用系統模擬的技術則能夠放寬許多不合理假設。排序與選擇程序即為該領域中幫助決策者選擇最佳系統的方法，然而當系統的變異數較大時，容易面臨抽樣過多及運算時間長等問題。該領域中的變異縮減技術則可改善此問題，以變異數較小的估計量取代原本的估計量，並增進程序的效率。過往文獻中，分位數的選擇程序多為兩階段的選擇程序，且皆是透過順序統計量進行分位數的計算，容易在估計極端分位數時，造成估計量偏誤大與計算時間長等問題，因此本研究欲透過隨機近似法 (Stochastic Approximation; SA) 與漸進變異數的使用，以增進程序的效率。

本研究將分位數視為一求根問題，將 SA 方法導入於分位數的估計當中，使其在更新的過程僅需儲存最新的樣本，接著搭配分位數漸進性質發展一適應性選擇程序；在極端分位數的估計當中，本研究則導入重要性取樣法，限制兩分配為相同的母數家族，同樣利用 SA 方法最小化漸進變異數以取得最佳的取樣密度，最後將其與適應性選擇程序結合，幫助程序在抽樣的同時，進行參數的更新，使之能夠得到更為精準的估計量，以提升程序的效率。

本研究在實驗後發現，ASPQ-SA 雖然需要使用到較多的平均抽樣數，但在合適的步長函數下，程序的執行時間與系統的正確選擇機率上皆優於其他程序，表示 SA 方法有助於程序效率的提升。在極端分位數的情況下，ASPQ-SAIS 由於變異減免技術的使用，能夠以較少的樣本數進行系統的篩選，使程序的效率有所提升。在實例當中，對於抽樣時間的影響較大，因此也展現 IS 技術對於抽樣效率的影響，使 ASPQ-SAIS 能夠以較佳的效率進行系統的篩選。

In past studies, Ranking and Selection Procedures (R&S) usually use order statistic to compute quantile estimator or use the mean of a group of quantile and variance as the comparison measure. These procedures may not be efficient since quantile estimator is accompanied by high variance and significant data storage, especially when computing extreme quantiles. We develop an Adaptive Sequential Procedure for Quantile Selection (ASPQ) algorithm with Stochastic Approximation (SA) and asymptotic variance of the quantile estimator, which has a low storage and bias. Moreover, we provide a ASPQ with Importance Sampling (IS) that makes us to get more observations from important region under the appropriate IS parameter. To find the best parameter, we also use SA to minimize the asymptotic variance. The numerical experiments demonstrate that the probability of correct selection (PCS) can meet the desired confidence level, and the effectiveness of variance reduction is significant since the average number of samples (ANS) is less than other procedures. Furthermore, our procedure may has a better CPU time due to the less storage in different cases.

蔡承濂 (2017). 以更有效率之方式結合控制變量於完全連續選擇程序. 成功大學工業與資訊管理學系碩士學位論文.

葉韋呈 (2019). 使用非線性控制變量之完全連續選擇程序. 成功大學工業與資訊管理學系碩士學位論文.

吳泓寛 (2020). 導入重要性取樣法於分位數估計之完全連續選擇程序. 成功大學工業與資訊管理學系碩士學位論文.

Ahamed, T. P., Borkar, V. S., & Juneja, S. (2006). Adaptive importance sampling technique for Markov chains using stochastic approximation. Operations Research, 54(3), 489–504.

Bahadur, R. R. (1966). A note on quantiles in large samples. The Annals of Mathematical Statistics, 37(3), 577–580.

Batur, D., & Choobineh, F. (2010). A quantile-based approach to system selection. European Journal of Operational Research, 202(3), 764–772.

Batur, D., & Choobineh, F. (2012). Stochastic dominance based comparison for system selection. European Journal of Operational Research, 220(3), 661–672.

Bechhofer, R. E. (1954). A single-sample multiple decision procedure for ranking means of normal populations with known variances. The Annals of Mathematical Statistics, 25(1), 16–39.

Bechhofer, R. E., Santner, T. J., & Goldsman, D. M. (1995). Design and analysis of experiments for statistical selection, screening, and multiple comparisons. New York: John Wiley & Sons.

Bekki, J. M., Fowler, J. W., Mackulak, G. T., & Nelson, B. L. (2007). Using quantiles in ranking and selection procedures. In Proceedings - Winter Simulation Conference, (pp. 1722–1728). WSC.

Chen, E. J., & Kelton, W. D. (2006). Quantile and tolerance-interval estimation in simulation. European Journal of Operational Research, 168(2), 520–540.

Chen, F., Lambert, D., & Pinheiro, J. C. (2000). Incremental quantile estimation for massive tracking. In Proceedings of the sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (pp. 516–522).

Chu, F., & Nakayama, M. K. (2010). Confidence intervals for quantiles and value-at-risk when applying importance sampling. In Proceedings - Winter Simulation Conference, (pp. 2751–2761).

Chu, F., & Nakayama, M. K. (2012). Confidence intervals for quantiles when applying variance-reduction techniques. ACM Transactions on Modeling and Computer Simulation, 22(2), 1–25.

David, H. A., & Nagaraja, H. N. (2003). Order statistics. Wiley Series in Probability and Statistics. Hoboken, NJ, USA: John Wiley & Sons, Inc.

Egloff, D., & Leippold, M. (2010). Quantile estimation with adaptive importance sampling. Annals of Statistics, 38(2), 1244–1278.

Feng, M., & Staum, J. (2017). Green simulation: Reusing the output of repeated experiments. ACM Transactions on Modeling and Computer Simulation, 27(4), 1–28.

Fu, M. C., et al. (2015). Handbook of simulation optimization, vol. 216. Springer.

Ghosh, J. K. (1971). A new proof of the Bahadur representation of quantiles and an application. The Annals of Mathematical Statistics, 42(6), 1957–1961.

Ghosh, S., & Pasupathy, R. (2013). Low-storage online estimators for quantiles and densities. In 2013 Winter Simulations Conference (WSC), (pp. 778–789). IEEE.

Glasserman, P. (2013). Monte Carlo methods in financial engineering, vol. 53. Springer Science & Business Media.

Glasserman, P., Heidelberger, P., & Shahabuddin, P. (2000). Variance reduction techniques for estimating value-at-risk. Management Science, 46(10), 1349–1364.

Glynn, P. W. (1996). Importance sampling for Monte Carlo estimation of quantiles. In Proceedings of the Second International Workshop on Mathematical Methods in Stochastic Simulation and Experimental Design, (pp. 180–185). Mathematical methods in stochastic simulation and experimental design: proceedings of the 2nd St.Petersburg Workshop on Simulation, St. Petersburg, June 18 - 21, 1996.

Goldsman, D., Nelson, B., & Schmeiser, B. (1991). Methods for selecting the best system (for simulation). In B. Nelson, W. Kelton, & G. Clark (Eds.) Proceedings - Winter Simulation Conference, (pp. 177–186). Institute of Electrical and Electronics Engineers (IEEE).

Greenwald, M., & Khanna, S. (2001). Space-efficient online computation of quantile summaries. ACM SIGMOD Record, 30(2), 58–66.

Gupta, S. S. (1956). On a decision rule for a problem in ranking means. Ph.d. dissertation, University of North Carolina, Chapel Hill, NC.

He, S., Jiang, G., Lam, H., & Fu, M. C. (2021). Adaptive importance sampling for efficient stochastic root finding and quantile estimation. arXiv preprint arXiv:2102.10631.

Heidelberger, P. (1995). Fast simulation of rare events in queueing and reliability models. ACM Transactions on Modeling and Computer Simulation (TOMACS), 5(1), 43–85.

Jain, R., & Chlamtac, I. (1985). The p2 algorithm for dynamic calculation of quantiles and histograms without storing observations. Communications of the ACM, 28(10), 1076–1085.

Joseph, A. G., & Bhatnagar, S. (2015). A stochastic approximation algorithm for quantile estimation. In International Conference on Neural Information Processing, (pp. 311–319). Springer.

Joseph, A. G., & Bhatnagar, S. (2019). An incremental algorithm for estimating extreme quantiles. In 2019 Sixth Indian Control Conference (ICC), (pp. 286–291). IEEE.

Jourdain, B., & Lelong, J. (2009). Robust adaptive importance sampling for normal random vectors. Annals of Applied Probability, 19(5), 1687–1718.

Kim, S., & Henderson, S. G. (2007). Adaptive control variates for finite-horizon simulation. Mathematics of Operations Research, 32(3), 508–527.

Kim, S. H., & Nelson, B. L. (2001). A fully sequential procedure for indifference-zone selection in simulation. ACM Transactions on Modeling and Computer Simulation, 11(3), 251–273.

Kim, S. H., & Nelson, B. L. (2006). On the asymptotic validity of fully sequential selection procedures for steady-state simulation. Operations Research, 54(3), 475–488.

Lesnevski, V., Nelson, B. L., & Staum, J. (2007). Simulation of coherent risk measures based on generalized scenarios. Management Science, 53(11), 1756–1769.

Luo, J., Hong, L.J., Nelson, B.L., &Wu, Y.(2015). Fully sequential procedures for large-scale ranking-and-selection problems in parallel computing environments. Operations Research, 63(5), 1177–1194.

Pastel, R. (2012). Estimation of rare event probabilities and extreme quantiles. Applications in the aerospace domain. Tech. rep.

Pichitlamken, J., Nelson, B. L., & Hong, L. J. (2006). A sequential procedure for neighborhood selection-of-the-best in optimization via simulation. European Journal of Operational Research, 173(1), 283–298.

Rinott, Y. (1978). On two-stage selection procedures and related probability-inequalities. Communications in Statistics - Theory and Methods, 7(8), 799–811.

Robbins, H., & Monro, S. (1951). A stochastic approximation method. The Annals of Mathematical Statistics, (pp. 400–407).

Rubino, G., & Tuffin, B. (2009). Rare event simulation using Monte Carlo methods. John Wiley & Sons Inc.

Rubinstein, R. Y. (1997). Optimization of computer simulation models with rare events. European Journal of Operational Research, 99(1), 89–112.

Sabuncuoglu, I., Fadiloglu, M. M., & C¸elik, S. (2008). Variance reduction techniques: Experimental comparison and analysis for single systems. IIE Transactions (Institute of Industrial Engineers), 40(5), 538–551.

Serfling, R. J. (1980). Approximation theorems of mathematical statistics. New York: John Wiley & Sons.

Spall, J. C. (2005). Introduction to stochastic search and optimization: estimation, simulation, and control, vol. 65. John Wiley & Sons.

Stephanou, M., Varughese, M., Macdonald, I., et al. (2017). Sequential quantiles via hermite series density estimation. Electronic Journal of Statistics, 11(1), 570–607.

Tierney, L. (1983). A space-efficient recursive procedure for estimating a quantile of an unknown distribution. SIAM Journal on Scientific and Statistical Computing, 4(4), 706–711.

Yazidi, A., & Hammer, H. (2015). Quantile estimation using the theory of stochastic learning. In Proceedings of the 2015 Conference on Research in Adaptive and Convergent Systems, (pp. 7–14).

Yazidi, A., & Hammer, H. (2017). Multiplicative update methods for incremental quantile estimation. IEEE Transactions on Cybernetics, 49(3), 746–756.