Precision of sequential change point detection

Aleksandra Ochman-Gozdek¹ ; Wojciech Sarnowski² ; Krzysztof Szajowski³

¹ Objectivity Bespoke Software Specialists Ltd. Strzegomska 142a 54-429 Wrocław, Poland
² Business Intelligence Team at Krajowy Rejestr Długów Armii Ludowej 21 51-214 Wrocław, Poland
³ Faculty of Pure and Applied Mathematics Wrocław University of Science and Technology Wybrzeże Wyspiańskiego 27 50-370 Wrocław, Poland

Applicationes Mathematicae, Tome 44 (2017) no. 2, pp. 267-280.

Résumé

A random sequence having two segments that are homogeneous Markov processes is registered. Each segment has its own transition probability law, and the length of the segment is unknown and random. The transition probabilities of each of the processes are known and the a priori distribution of the disorder time is given. The decision maker’s aim is to detect the time when the transition probabilities change. The detection of the disorder is rarely precise. The decision maker accepts some deviation in estimation of the disorder time. In the model we consider the aim is to indicate the change point with fixed, bounded error with maximal probability. The precision differs for over and under estimation of this point. The case when the disorder does not appear with positive probability is also included. The results extend significantly the range of applications, explain the structure of optimal detector in various circumstances and show new details of the solution construction. The motivation for this investigation is the modelling of attacks in a node of networks. The objective is to detect one of the attacks immediately or in very short time before or after its appearance with the highest probability. The problem is reformulated as optimal stopping of the observed sequences. The detailed analysis of the problem is presented to show the form of the optimal decision function.

Détail

DOI : 10.4064/am2278-5-2017

Keywords: random sequence having segments homogeneous markov processes registered each segment has its own transition probability law length segment unknown random transition probabilities each processes known priori distribution disorder time given decision maker detect time transition probabilities change detection disorder rarely precise decision maker accepts deviation estimation disorder time model consider indicate change point fixed bounded error maximal probability precision differs under estimation point disorder does appear positive probability included results extend significantly range applications explain structure optimal detector various circumstances details solution construction motivation investigation modelling attacks node networks objective detect attacks immediately short time before after its appearance highest probability problem reformulated optimal stopping observed sequences detailed analysis problem presented form optimal decision function