On the ARL of CUSUM in multinomial models

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

References

1. [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. [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. [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. [4] D. Brook and D.A. Evans, An approach to the probability distribution of CUSUM run length, Biometrika. 59, 539-549, 1972.
5. [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. [6] Y.S. Chow, H. Robbins and D. Siegmund, The Theory of Optimal Stopping, Houghton Miffin Co., 1971.
7. [7] R.B. Crosier, Multivariate generalization of cumulative sum quality-control schemes, Technometrics. 30, 291-303, 1988.
8. [8] M. DeGroot, Optimal Statistical Decisions, McGraw-Hill Book Co., 1970.

9. [9] D.S. van Dobben de Bruyn, Cumulative Sum Tests, Griffin Publishers, London, UK, 1968.
10. [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. [11] J.D. Healy, A note on multivariate CUSUM procedures, Technometrics. 29 (4), 409- 412, 1987.
12. [12] A. van Holt and C.Y. Huang, 802.11 Wireless Networks: Security and Analysis, Springer, London UK, 2010.
13. [13] R.A. Johnson and M. Bagshaw, The effect of serial correlation on the performance of CUSUM tests, Technometrics. 16, 103-112, 1974.
14. [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. [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. [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. [17] D.P. Kennedy, Some martingales related to cumulative sum tests and single-server queues, Stoch. Process. Their Appl. 4, 261-269, 1976.
18. [18] R.A. Khan, A note on Page’s two-sided cumulative sum procedure, Biometrika. 68, 717-719, 1981.
19. [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. [20] R.A. Khan, Detecting changes in probabilities of a multi-component process, Seq. Anal. 14, 375-388, 1995.
21. [21] G. Lorden, Procedures for reacting to a change in distribution, Ann. Math. Statist. 42, 1897-1908, 1971.
22. [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. [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. [24] G.V. Moustakides, Optimal stopping times for detecting changes in distributions, Ann. Stat. 14, 1379-1387, 1986.
25. [25] G.V. Moustakides, Quickest detection of abrupt changes for a class of random processes, IEEE Trans. Inform. Theory. 44, 1965-1968, 1998.
26. [26] G.V. Moustakides, Optimality of the CUSUM procedure in continuous time, Ann. Stat. 32, 302-315, 2004.
27. [27] A.G Munford, A control chart based on cumulative scores, Appl. Stat. 29, 252-258, 1980.
28. [28] E.S. Page, Continuous inspection schemes, Biometrika. 41, 100-115, 1954.
29. [29] J.J. Pignatiello and G.C. Runger, Comparisons of multivariate CUSUM charts, J. Qual. Technol. 22, 173-186, 1990.
30. [30] H.V. Poor and O. Hadjiliadis, Quickest Detection, Cambridge University Press, 2009.
31. [31] N.U. Prabhu, Stochastic Storage Systems: queues, insurance risk, dams, and data communication, 2nd ed. Springer, New York, 2012.
32. [32] P. Qiu and D. Hawkins, A rank based multivariate CUSUM procedure, Technometrics. 43, 120-132, 2001.
33. [33] M.R. Reynolds, Approximations to the average run length in cumulative sum control charts, Technometrics. 17, 65-71, 1975.
34. [34] Y. Ritov, Decision theoretic optimality of the CUSUM procedure, Ann. Statist. 18 (3), 1464-1469, 1990.
35. [35] G.C. Runger and M. Testik, Multivariate extensions to cumulative sum control charts, Qual. Reliab. Engng. Int. 20, 587-606, 2004.
36. [36] A.N. Shiryaev, Optimal Stopping Rules, Springer, Berlin, 2007.
37. [37] D. Siegmund, Sequential Analysis: Tests and Confidence Intervals. Springer-Verlag, New York, 1985.
38. [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. [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. [40] A. Wald, Sequential Analysis, John Wiley, New York, 1947.
41. [41] W.H. Woodall, On the Markov chain approach to the two-sided CUSUM procedure, Technometrics. 26, 41-46, 1984.
42. [42] W.H. Woodall and M.M. Ncube, Multivariate CUSUM quality-control procedures, Technometrics. 27 (3), 285-292, 1985.
43. [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. [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. [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.