On the ARL of CUSUM in multinomial models

Year 2024, , 1484 - 1496, 15.10.2024

Shangchen Yao , Mohammad Khan

https://doi.org/10.15672/hujms.1428934

Abstract

There is no known closed form expression for the average sample number, also known as average run length, of a multivariate CUSUM procedure $N = \min\{ M_1, M_2,\cdots, M_m\}$ for $m\geq 3$, where $M_i$ are univariate CUSUM procedures. The problem is generally considered to be hopelessly complicated for any model. In this paper, for the multinomial model we show, however, that there is a rather simple closed form expression for the average run length of $N$ with an elementary proof. A bit surprisingly, we further show that the average run length of $N$ is related to the average run lengths of $M_i$ the same way as the capacitance of a series network of capacitors is related to the capacitances of its own components.

Keywords

Average run length, multivariate CUSUM, Markov chain, sequential change point detection

Thanks

Thank you for considering our article for publication in Hacettepe Journal of Mathematics and Statistics.

References

• [1] V. Abramov, M.K. Khan and R.A. Khan, A probablistic analysis of trading the line strategy, Quant. Finance. 8, 499-512, 2008.
• [2] M. Bagshaw and R.A. Johnson, The effect of serial correlation on the performance of CUSUM tests II, Technometrics. 17, 73-80, 1975.
• [3] M. Beibel, A note on Ritov’s Bayes approach to the minimax property of the CUSUM procedure, Ann. Statist. 24 (4), 1804-1812, 1996.
• [4] D. Brook and D.A. Evans, An approach to the probability distribution of CUSUM run length, Biometrika. 59, 539-549, 1972.
• [5] A. Cardenas, S. Radosavac and S. Baras, Performance comparison of detection schemes for MAC layer misbehavior, Infocom, 2007, 26th IEEE International Conference on Computer Communications, IEEE, Anchorage, AK, 1496-1504, 2007.
• [6] Y.S. Chow, H. Robbins and D. Siegmund, The Theory of Optimal Stopping, Houghton Miffin Co., 1971.
• [7] R.B. Crosier, Multivariate generalization of cumulative sum quality-control schemes, Technometrics. 30, 291-303, 1988.
• [8] M. DeGroot, Optimal Statistical Decisions, McGraw-Hill Book Co., 1970.
• [9] D.S. van Dobben de Bruyn, Cumulative Sum Tests, Griffin Publishers, London, UK, 1968.
• [10] De Leval, M.R., Francois, K., Bull, C., Brawn, W.B., Spiegelhalter, D., Analysis of a cluster of surgical failures: Application to a series of neonatal arterial switch operations, J. Thorac. Cardiovasc. Surg. 107, 914-924, 1994.
• [11] J.D. Healy, A note on multivariate CUSUM procedures, Technometrics. 29 (4), 409- 412, 1987.
• [12] A. van Holt and C.Y. Huang, 802.11 Wireless Networks: Security and Analysis, Springer, London UK, 2010.
• [13] R.A. Johnson and M. Bagshaw, The effect of serial correlation on the performance of CUSUM tests, Technometrics. 16, 103-112, 1974.
• [14] E. Kaufmann and W.M. Koolen, Mixture martingales revisited with applications to sequential tests and confidence intervals, J. Mach. Learn. Res. 22 (246), 1-44, 2021.
• [15] K. Kemp, Formulae for calculating the operating characteristics and the Average Sample Number of some sequential tests, J. R. Stat. Soc., B: Stat. Methodol. 20, 379-386, 1958.
• [16] K. Kemp The average run length of the cumulative sum chart when a V-mask is used, J. R. Stat. Soc., B: Stat. Methodol. 23, 149-153, 1961.
• [17] D.P. Kennedy, Some martingales related to cumulative sum tests and single-server queues, Stoch. Process. Their Appl. 4, 261-269, 1976.
• [18] R.A. Khan, A note on Page’s two-sided cumulative sum procedure, Biometrika. 68, 717-719, 1981.
• [19] R.A. Khan, On cumulative sum procedures and the SPRT with applications, J. R. Stat. Soc., B: Stat. Methodol. 46, 79-85, 1984.
• [20] R.A. Khan, Detecting changes in probabilities of a multi-component process, Seq. Anal. 14, 375-388, 1995.
• [21] G. Lorden, Procedures for reacting to a change in distribution, Ann. Math. Statist. 42, 1897-1908, 1971.
• [22] J.M. Lucas and R.B. Crosier, Fast initial response for CUSUM quality control schemes: give your CUSUM a head start, Technometrics. 24, 199-205, 1982.
• [23] A.F. Martinez and R.H. Mena, On a nonparametric change point detection model in Markovian regimes, Bayesian Anal. 9, 823-858, 2014.
• [24] G.V. Moustakides, Optimal stopping times for detecting changes in distributions, Ann. Stat. 14, 1379-1387, 1986.
• [25] G.V. Moustakides, Quickest detection of abrupt changes for a class of random processes, IEEE Trans. Inform. Theory. 44, 1965-1968, 1998.
• [26] G.V. Moustakides, Optimality of the CUSUM procedure in continuous time, Ann. Stat. 32, 302-315, 2004.
• [27] A.G Munford, A control chart based on cumulative scores, Appl. Stat. 29, 252-258, 1980.
• [28] E.S. Page, Continuous inspection schemes, Biometrika. 41, 100-115, 1954.
• [29] J.J. Pignatiello and G.C. Runger, Comparisons of multivariate CUSUM charts, J. Qual. Technol. 22, 173-186, 1990.
• [30] H.V. Poor and O. Hadjiliadis, Quickest Detection, Cambridge University Press, 2009.
• [31] N.U. Prabhu, Stochastic Storage Systems: queues, insurance risk, dams, and data communication, 2nd ed. Springer, New York, 2012.
• [32] P. Qiu and D. Hawkins, A rank based multivariate CUSUM procedure, Technometrics. 43, 120-132, 2001.
• [33] M.R. Reynolds, Approximations to the average run length in cumulative sum control charts, Technometrics. 17, 65-71, 1975.
• [34] Y. Ritov, Decision theoretic optimality of the CUSUM procedure, Ann. Statist. 18 (3), 1464-1469, 1990.
• [35] G.C. Runger and M. Testik, Multivariate extensions to cumulative sum control charts, Qual. Reliab. Engng. Int. 20, 587-606, 2004.
• [36] A.N. Shiryaev, Optimal Stopping Rules, Springer, Berlin, 2007.
• [37] D. Siegmund, Sequential Analysis: Tests and Confidence Intervals. Springer-Verlag, New York, 1985.
• [38] S.H. Steiner, R.J. Cook and V.T. Farewell, Monitoring paired binary surgical outcomes using cumulative sum charts, Statist. Med. 18, 69-86, 1999.
• [39] S.H. Steiner, P.L. Geyer and G.O. Wesolowsky, Grouped data-sequential probability ratio tests and cumulative sum control charts, Technometrics. 38, 230-237, 1996.
• [40] A. Wald, Sequential Analysis, John Wiley, New York, 1947.
• [41] W.H. Woodall, On the Markov chain approach to the two-sided CUSUM procedure, Technometrics. 26, 41-46, 1984.
• [42] W.H. Woodall and M.M. Ncube, Multivariate CUSUM quality-control procedures, Technometrics. 27 (3), 285-292, 1985.
• [43] L. Xie, S. Zou, Y. Xie and V.V. Veeravalli, Sequential (quickest) change detection: Classical results and new directions, IEEE J. Selected Areas in Information Theory. 2 2, 494-514, 2021.
• [44] S. Zacks, The probability distribution and the expected value of a stopping variable associated with one-sided CUSUM procedures for non-negative integer valued random variables, Commun. Stat. - Theory Methods A10, 2245-2258, 1981.
• [45] S. Zacks, Detection and change-point problems, In: B. K. Ghosh, and P. K. Sen, (Eds), Handbook of Sequential Analysis. Marcel Dekker, New York, 531-562, 1991.