Technical Program

Paper Detail

Paper Title Sequential Change Detection Based on Universal Compression for Markov Sources
Paper IdentifierTH3.R6.1
Authors Ashwin Verma, University of California, San Diego, United States; Rakesh K. Bansal, Indian Institute of Technology, Kanpur, India
Session Quickest Change Detection I
Location Sorbonne, Level 5
Session Time Thursday, 11 July, 14:30 - 16:10
Presentation Time Thursday, 11 July, 14:30 - 14:50
Manuscript  Click here to download the manuscript
Abstract A universal compression code can act as an estimator for the distribution of a finite alphabet finite-order Markov source. This property of universal codes was exploited by Jacob and Bansal in 2008 to propose a modification of the CUSUM test in order to solve the change detection problem when the post-change distribution is not known. The performance of this test was proven to be asymptotically optimal for a memoryless sources and class of sources with memory under Lorden's minimax formulation. This study was further extended in 2018 where performance of the modified CUSUM for an i.i.d. setting under Lai's criterion involving a constraint on the probability of false alarm within a window (PFAW) was analyzed. In this paper, we introduce a modified version of the window limited CUSUM (WL-CUSUM) test by incorporating strongly universal code. We closely follow the work of Lai (1998) in order to prove the asymptotic optimality for the test under the PFAW criterion. We further prove the asymptotic optimality of the modified WL-CUSUM test in the Bayesian setting.