422 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 55, NO. 1, JANUARY 2009Tracking Stopping TimesThrough Noisy ObservationsUrs Niesen, Student Member, IEEE, and Aslan TchamkertenAbstract—A novel quickest detection setting is proposed, gen-eralizing the well-known Bayesian change-point detection model.Supposef(Xi;Yi)gi1is a sequence of pairs of random variables,and thatSis a stopping time with respect tofXigi1. The problemis to find a stopping timeTwith respect tofYigi1that optimallytracksS, in the sense thatTminimizes the expected reaction delay(T0S)+, while keeping the false-alarm probability(T<S)below a given threshold2[0;1]. This problem formulation ap-plies in several areas, such as in communication, detection, fore-casting, and quality control.Our results relate to the situation where theXi’s andYi’s takevalues in finite alphabets and whereSis bounded by some positiveinteger. By using elementary methods based on the analysis ofthe tree structure of stopping times, we exhibit an algorithm thatcomputes the optimal average reaction delays for all2[0;1], andconstructs the associated optimal stopping timesT. Under certainconditions onf(Xi;Yi)gi1andS, the algorithm running time ispolynomial in.Index Terms—Algorithms, decision theory, feedback communi-cation, forecasting, monitoring, optimal stopping, quickest detec-tion problem, sequential analysis, synchronization, tree analysis.I. PROBLEM STATEMENTTHE tracking stopping time (TST) problem is definedas follows. Letbe a sequence of pairs ofrandom variables. Alice observesand chooses astopping time (s.t.)with respect to that sequence.1Knowingthe distribution ofand the stopping rule ,but having access only to the’s, Bob wishes to find a s.t.that gets as close as possible to Alice’s. Specifically, Bobaims to find a s.t.minimizing the expected reaction delay, while keeping the false-alarmprobabilitybelow a certain threshold .Manuscript received February 06, 2008. Current version published De-cember 24, 2008. This work was supported in part by the NSF under GrantCCF-0515122, by DoD MURI under Grant N00014-07-1-0738, and by aUniversity IR&D Grant from Draper Laboratory. The material in this paper waspresented in part at the IEEE International Symposium on Information Theory,Nice, France, June 2007. This work was carried out while A. Tchamkerten wasat MIT as a Postdoctoral Associate.U. Niesen is with the Department of Electrical Engineering and ComputerScience, Massachusetts Institute of Technology (MIT), Cambridge, MA 02139USA (e-mail: [email protected]).A. Tchamkerten is with the Department of Communications and Electronics,TELECOM ParisTech, 75634 Paris Cedex 13, France (e-mail: [email protected]).Communicated by H. Bölcskei, Associate Editor for Detection and Estima-tion.Digital Object Identifier 10.1109/TIT.2008.20081151Recall that a s.t. with respect to a sequence of random variablesfXgis arandom variableStaking values in the positive integers such that the eventfS=ng, conditioned onfXg, is independent offXgfor alln 1.Ans.t.Sis nonrandomized if(S=njX=x)2f0;1gfor allx2Yandn 1. An s.t.Sis randomized if(S=njX=x)2[0;1]for allx2Xandn 1.Example 1. Monitoring: Let be the distance of an objectfrom a barrier at time, and let be the first time the object hitsthe barrier, i.e.,. Assume we haveaccess toonly through a noisy measurement , and that wewant to raise an alarm as soon as the object hits the barrier. Thisproblem can be formulated as the one of finding a s.t.withrespect to the’s that minimizes the expected reaction delay, while keeping the false-alarm probabilitysmall enough.Another situation where the TST problem applies is in thecontext of communication over channels with feedback. Mostof the studies related to feedback communication assume per-fect feedback, i.e., the transmitter is fully aware of the outputof the channel as observed by the receiver. Without this as-sumption—i.e., if the feedback link is noisy—a synchroniza-tion problem may arise between the transmitter and the receiverwhich can be formulated as a TST problem, as shown in the fol-lowing example.Example 2. Communication: It is well known that the pres-ence of a noiseless feedback link allows to dramatically increasethe reliability for a given communication delay (see, e.g., [12]).However, to take advantage of feedback, variable-length codesare often necessary.2This can be observed by looking at a non-perfect binary erasure channel. In this case, any block codingstrategy yields a strictly positive error probability. In contrast,consider the variable-length strategy where the encoder keepssending the bit it wishes to convey until it is successfully re-ceived. This simple strategy achieves error-free communicationat a rate equal to the capacity of the channel in question. Can westill use this coding strategy if the feedback channel is (some-what) noisy? Because of the noisy feedback link, a synchroniza-tion problem between the decoder and the encoder arises: if thefirst nonerased output symbol occurs at time, what should besent at time? This agreement problem occurs because theencoder observes now only a noisy version of the symbols re-ceived by the decoder (see Fig. 1). In particular, the first non-erased output symbol may not be recognized as such by theencoder.3Instead of treating the synchronization issue that re-sults from the use of variable-length codes over channels withnoisy feedback, let us consider the simpler problem of findingthe minimum delay needed by the encoder to realize that the de-2The reliability function associated with block coding schemes is lower thanthe one associated with variable length coding. For symmetric channels, for in-stance, the reliability function associated with block coding schemes is limitedby the sphere packing bound, which is lower than the best optimal error expo-nent attainable with variable length coding ([5], [10]).3For fixed-length coding strategies over channels with noisy feedback werefer the reader to [13], [6].0018-9448/$25.00 © 2009 IEEEAuthorized licensed use limited to: University of Houston. Downloaded on October 24, 2009 at 15:15 from IEEE Xplore. Restrictions apply.NIESEN AND TCHAMKERTEN: TRACKING STOPPING TIMES THROUGH NOISY OBSERVATIONS 423Fig. 1. The decoding timeSdepends on the output of the forward channel.The encoder decides to stop transmission at timeTbased on the output of thefeedback channel. If the feedback channel is noisy,SandTneed not coincide.coder has made a