Search

This paper investigates change point detection in state space models, in which the pre-change distribution $f^{\theta_0}$ is given, while the poster distribution $f^{\theta}$ after change is unknown. The problem is to raise an alarm as soon as possible after the distribution changes from $f^{\theta_0}$ to $f^{\theta}$, under a restriction on the false alarms. We investigate theoretical properties of a weighted Shiryayev-Roberts-Pollak (SRP) change point detection rule in state space models. By making use of a Markov chain representation for the likelihood function, exponential embedding of the induced Markovian transition operator, nonlinear Markov renewal theory, and sequential hypothesis testing theory for Markov random walks, we show that the weighted SRP procedure is second-order asymptotically optimal. To this end, we derive an asymptotic approximation for the expected stopping time of such a stopping scheme when the change time $\omega = 1$. To illustrate our method we apply the results to two types of state space models: general state Markov chains and linear state space models., Comment: 17 pages. arXiv admin note: text overlap with arXiv:1801.04756 by other authors

This work considers the cooperative sequential hypothesis testing problem in a distributed network with quantized communication channels. The sensors observe independent sequences of samples and in the meantime, exchange their local information in the form of quantized statistics at every sampling interval. The communication links are represented as an undirected graph. In this distributed setup, every sensor performs its own sequential test based on the local samples and the messages from the neighbour sensors. Our goal is to devise the distributed sequential test that comprises the quantization scheme, the message-exchange protocol and the test procedure such that every sensor in the network fully exploits the network diversity and achieves the (asymptotically) optimal performance in terms of the stopping time. In particular, two distributed sequential tests are proposed based on different quantization schemes and a quantized message-exchange protocol that satisfies certain conditions. The first quantization scheme uniformly quantizes the local statistic at each sensor and at every sampling interval; the second one hinges on a modified level-triggered quantization technique, and resembles the Lebesgue sampling of the running local statistic. Our analyses show that the uniform quantization based distributed sequential test yields sub-optimal performance, while the one based on level-triggered quantization achieves the order-2 asymptotically optimal performance at every sensor for any fixed quantization step-size. Furthermore, we generalize the proposed sequential tests to the cluster-based network. Numerical results are provided to corroborate our analyses and demonstrate the effectiveness of the proposed sequential tests.

Opportunistic detection rules (ODRs) are variants of fixed-sample-size detection rules in which the statistician is allowed to make an early decision on the alternative hypothesis opportunistically based on the sequentially observed samples. From a sequential decision perspective, ODRs are also mixtures of one-sided and truncated sequential detection rules. Several results regarding ODRs are established in this paper. In the finite regime, the maximum sample size is modeled either as a fixed finite number, or a geometric random variable with a fixed finite mean. For both cases, the corresponding Bayesian formulations are investigated. The former case is a slight variation of the well-known finite-length sequential hypothesis testing procedure in the literature, whereas the latter case is new, for which the Bayesian optimal ODR is shown to be a sequence of likelihood ratio threshold tests with two different thresholds. A running threshold, which is determined by solving a stationary state equation, is used when future samples are still available, and a terminal threshold (simply the ratio between the priors scaled by costs) is used when the statistician reaches the final sample and, thus, has to make a decision immediately. In the asymptotic regime, the tradeoff among the exponents of the (false alarm and miss) error probabilities and the normalized expected stopping time under the alternative hypothesis is completely characterized and proved to be tight, via an information-theoretic argument. Within the tradeoff region, one noteworthy fact is that the performance of the Stein-Chernoff lemma is attainable by ODRs.

With a finite number of samples drawn from one of two possible distributions sequentially revealed, an opportunistic detection rule is proposed, which possibly makes an early decision in favor of the alternative hypothesis, while always deferring the decision of the null hypothesis until collecting all the samples. Properties of this opportunistic detection rule are discussed and its key asymptotic behavior in the large sample size limit is established. Specifically, a Chernoff-Stein lemma type of characterization of the exponential decay rate of the miss probability under the Neyman-Pearson criterion is established, and consequently, a performance metric of asymptotic exponential efficiency loss is proposed and discussed, which is exactly the ratio between the Kullback-Leibler distance and the Chernoff information of the two hypotheses. Analytical results are corroborated by numerical experiments.

We consider how local and global decision policies interact in stopping time problems such as quickest time change detection. Individual agents make myopic local decisions via social learning, that is, each agent records a private observation of a noisy underlying state process, selfishly optimizes its local utility and then broadcasts its local decision. Given these local decisions, how can a global decision maker achieve quickest time change detection when the underlying state changes according to a phase-type distribution? This paper presents four results. First, using Blackwell dominance of measures, it is shown that the optimal cost incurred in social-learning-based quickest detection is always larger than that of classical quickest detection. Second, it is shown that in general the optimal decision policy for social-learning-based quickest detection is characterized by multiple thresholds within the space of Bayesian distributions. Third, using lattice programming and stochastic dominance, sufficient conditions are given for the optimal decision policy to consist of a single linear hyperplane, or, more generally, a threshold curve. Estimation of the optimal linear approximation to this threshold curve is formulated as a simulation-based stochastic optimization problem. Finally, this paper shows that in multiagent sensor management with quickest detection, where each agent views the world according to its prior, the optimal policy has a similar structure to social learning.

A random walk (or a Wiener process), possibly with drift, is observed in a noisy or delayed fashion. The problem considered in this paper is to estimate the first time \tau the random walk reaches a given level. Specifically, the p-moment (p\geq 1) optimization problem \inf_\eta \ex|\eta-\tau|^p is investigated where the infimum is taken over the set of stopping times that are defined on the observation process. When there is no drift, optimal stopping rules are characterized for both types of observations. When there is a drift, upper and lower bounds on \inf_\eta \ex|\eta-\tau|^p are established for both types of observations. The bounds are tight in the large-level regime for noisy observations and in the large-level-large-delay regime for delayed observations. Noteworthy, for noisy observations there exists an asymptotically optimal stopping rule that is a function of a single observation. Simulation results are provided that corroborate the validity of the results for non-asymptotic settings., Comment: To appear in the IEEE Transactions on Information Theory

We show that the optimal decision policy for several types of Bayesian sequential detection problems has a threshold switching curve structure on the space of posterior distributions. This is established by using lattice programming and stochastic orders in a partially observed Markov decision process (POMDP) framework. A stochastic gradient algorithm is presented to estimate the optimal linear approximation to this threshold curve. We illustrate these results by first considering quickest time detection with phase-type distributed change time and a variance stopping penalty. Then it is proved that the threshold switching curve also arises in several other Bayesian decision problems such as quickest transient detection, exponential delay (risk-sensitive) penalties, stopping time problems in social learning, and multi-agent scheduling in a changing world. Using Blackwell dominance, it is shown that for dynamic decision making problems, the optimal decision policy is lower bounded by a myopic policy. Finally, it is shown how the achievable cost of the optimal decision policy varies with change time distribution by imposing a partial order on transition matrices.

Let {Xn}n=0 ? be a stationary real-valued Gaussian time series. We estimate the conditional expectation E(Xn+1|X0, ...,Xn) from a growing number of observations X0,..., Xn in a pointwise consistent way along a sequence of stopping times.

A variable-to-fixed length encoder partitions the source string into variable-length phrases that belong to a given and fixed dictionary. Tunstall, and independently Khodak, designed variable-to-fixed length codes for memoryless sources that are optimal under certain constraints. In this paper, we study the Tunstall and Khodak codes using variety of techniques ranging from stopping times for sums of independent random variables to Tauberian theorems and Mellin transform. After proposing an algebraic characterization of the Tunstall and Khodak codes, we present new results on the variance and a central limit theorem for dictionary phrase lengths. This analysis also provides a new argument for obtaining asymptotic results about the mean dictionary phrase length and average redundancy rates.

A novel quickest detection setting is proposed which is a generalization of the well-known Bayesian change-point detection model. Suppose \{(X_i,Y_i)\}_{i\geq 1} is a sequence of pairs of random variables, and that S is a stopping time with respect to \{X_i\}_{i\geq 1}. The problem is to find a stopping time T with respect to \{Y_i\}_{i\geq 1} that optimally tracks S, in the sense that T minimizes the expected reaction delay E(T-S)^+, while keeping the false-alarm probability P(T, Comment: 19 pages, 4 figures, to appear in IEEE Transactions on Information Theory

For pt. I see ibid. vol.45, p.2448-61, 1999. We proved in pt.I that two specific constructions of multihypothesis sequential tests, which we refer to as multihypothesis sequential probability ratio tests (MSPRTs), are asymptotically optimal as the decision risks (or error probabilities) go to zero. The MSPRTs asymptotically minimize not only the expected sample size but also any positive moment of the stopping time distribution, under very general statistical models for the observations. In this paper, based on nonlinear renewal theory we find accurate asymptotic approximations (up to a vanishing term) for the expected sample size that take into account the "overshoot" over the boundaries of decision statistics. The approximations are derived for the scenario where the hypotheses are simple, the observations are independent and identically distributed (i.i.d.) according to one of the underlying distributions, and the decision risks go to zero. Simulation results for practical examples show that these approximations are fairly accurate not only for large but also for moderate sample sizes. The asymptotic results given here complete the analysis initiated by Baum and Veeravalli (1994), where first-order asymptotics were obtained for the expected sample size under a specific restriction on the Kullback-Leibler distances between the hypotheses.

A sequential multihypothesis test known as the M-ary sequential probability ratio test (MSPRT) is generalized to account for nonuniform decision costs. Bounds on error probabilities and asymptotic expressions for the stopping time and error probabilities are given. A key result of this correspondence is a proof that the generalized MSPRT is asymptotically efficient.

The sequential testing of more than two hypotheses has important applications in direct-sequence spread spectrum signal acquisition, multiple-resolution-element radar, and other areas. A useful sequential test which we term the MSPRT is studied in this paper. The test is shown to be a generalization of the sequential probability ratio test. Under Bayesian assumptions, it is argued that the MSPRT approximates the much more complicated optimal test when error probabilities are small and expected stopping times are large. Bounds on error probabilities are derived, and asymptotic expressions for the stopping time and error probabilities are given. A design procedure is presented for determining the parameters of the MSPRT. Two examples involving Gaussian densities are included, and comparisons are made between simulation results and asymptotic expressions. Comparisons with Bayesian fixed sample size tests are also made, and it is found that the MSPRT requires two to three times fewer samples on average. >

A Wald-like equation is proved for the entropy of a randomly stopped sequence of independent identically distributed discrete random variables X/sub 1/, X/sub 2/. . ., with a nonanticipating stopping time N. The authors first define a general stopping time and the associated stopped sequence, and then present the two main theorems for the entropy of a stopped sequence. The formal proofs of the lemmas necessary for the proof of the theorems are given. The randomness in the stopped sequence X/sup N/ is the expected number of calls for X times the entropy per call plus the residual randomness in the stopping time conditioned on the unstopped sequence X/sup infinity /. >

In this correspondence the problem of sequential estimation is considered when the observation delays are, in general, costly. General theorems determining the "optimal" stopping time in this case are stated, and specific cases are worked out.

This paper exhibits an optimum strategy for the sequential estimation of, or search for, the location of the maximum M of a unimodal function, when M is initially uniformly distributed over some interval. The explicit search strategy which is found is valid for a variety of expected cost functions that add the expected cost of observation to the expected cost of terminal decision. The search problem possesses some of the features of problems in the areas of sequential analysis and stochastic approximation. The search stopping time can be determined as the search proceeds as in problems of sequential analysis. However, unlike many sequential analysis problems, the observational outcomes are somewhat within our control by a choice of observation or trial points. In common with problems of stochastic approximation, we attempt to determine the maximum of an unknown regression function. Contrary to many problems in stochastic approximation, though, the observations are noiseless, and the regression function is not required to be smooth or regular in the neighborhood of M . The main result is that the strategy minimizing the expected cost, drawn from the class of randomized, optional stopping strategies, is nonrandomized and of a size that can be fixed in advance of observation.