ON EFFICIENT PERFORMANCE EVALUATION OF THE GENERALIZED SHIRYAEV–ROBERTS DETECTION PROCEDURE 

Quickest change-point detection is a branch of statistics concerned with the design and analysis of reliable statistical machinery for rapid anomaly detection in “live” monitored random processes. The subject’s current state-of-the-art detection procedure is the recently proposed Generalized Shiryaev–Roberts (GSR) procedure (it was proposed in 2008, but the paper was published only in 2011). Notwithstanding its “young age”, the GSR procedure has already been shown to have strong optimality properties not exhibited by such mainstream procedures as the Cumulative Sum (CUSUM) “inspection scheme” and the Exponentially Weighted Moving Average (EWMA) chart. To foster and facilitate further research on the GSR procedure we propose a numerical method to evaluate the performance of the GSR procedure in a “minimax-ish” multi-cyclic setup where the procedure of choice is applied repetitively (cyclically) and the change is assumed to take place at an unknown time moment in a distant-future stationary regime. Specifically, the proposed method is based on the integral-equations approach and uses the collocation technique with the basis functions chosen so as to exploit a certain change-of-measure identity and the GSR detection statistic’s unique martingale property. As a result, the method’s accuracy and robustness improve, as does its efficiency since the use of the change-of-measure identity allows the Average Run Length (ARL) to false alarm and the Stationary Average Detection Delay (STADD) to be computed simultaneously. We show that the method’s rate of convergence is quadratic and supply a tight upperbound on its error. We conclude with a case study and confirm experimentally that the proposed method’s accuracy and rate of convergence are robust with respect to three factors: (a) partition fineness (coarse vs. fine), (b) change magnitude (faint vs. contrast), and (c) the level of the ARL to false alarm (low vs. high). Since the method is designed not restricted to a particular data distribution or to a specific value of the GSR detection statistic’s headstart, this work may help gain greater insight into the characteristics of the GSR procedure and aid a practitioner to design the GSR procedure as needed while fully utilizing its potential. 
This is joint work with Grigory Sokolov (Department of Mathematical Sciences, SUNY Binghamton) and Wenyu Du (Department of Mathematical Sciences, SUNY Binghamton).

Анализ длинного временного ряда (в режиме off-line) следует начинать с проверки гипотезы о его «однородности», а именно, надо проверить, не изменялся ли механизм генерации ряда в процессе сбора данных. Если эта гипотеза отвергается, и ряд «склеен» из достаточно длинных кусков, каждый из которых сгенерирован своим собственным механизмом, то для проведения дальнейшего анализа надо найти точки «склейки», т.е., те моменты времени, когда механизм генерации ряда менялся. Без осуществления такой процедуры результаты анализа ряда не могут быть адекватны. В том случае, когда ряд генерируется вероятностными механизмами, описанная задача есть известная задача о «разладке» (в режиме off-line). Однако, далеко не всегда ряд генерируется вероятностными механизмами. Но даже если это так, то найти точки «разладки» без априорной информации о модели ряда весьма сложно. Возникает вопрос: нельзя ли найти такую «внутреннюю» характеристику ряда, которая бы не зависела от механизма его генерации и дала бы возможность его сегментации на «однородные» участки? Мы полагаем, что такой характеристикой может служить введенное нами новое понятие – эпсилон-сложность индивидуальной непрерывной функции. Это понятие согласуется с общей идеей А.Н.Колмогорова о том, что такое «сложный» объект. Устанавливается, что для «почти любой» функции, удовлетворяющей условию Гёльдера, эпсилон-сложность допускает простую характеризацию в виде пары действительных чисел (мы их называем коэффициенты сложности). Это обстоятельство позволяет предложить принципиально новую методологию сегментации временных рядов произвольной природы (стохастических, детерминированных или смешанных) без использования какой-либо априорной информации о механизмах генерации. Ключевая гипотеза этой методологии состоит в том, что изменение механизма генерации влечет за собой изменение средних значений коэффициентов сложности, и поэтому нахождение моментов «склейки» сводится к задаче обнаружения «разладок» в среднем значении коэффициентов сложности. Приводятся результаты вычислительных экспериментов, подтверждающие работоспособность предлагаемой методологии.