On the Sequential Test and Distributed Detection

I. INTRODUCTION

• Because error probability decreases with sample size, the motivating objective is to find the fewest observations needed to keep error at or below a tolerated ε.Source: §I · p. 1
• The approach treats stopping time as a random variable determined by a sequence of ternary decisions, making expected stopping time primarily a property of the decision strategy.The expected number of observations is minimized while the desired accuracy is maintained throughout the decision process.Source: §I · p. 2
• Sample-by-sample rules yield upper bounds on optimal stopping time that illuminate its qualitative dependence on observation quality and desired accuracy.The bounds ignore previous observations, using the current observation and previous decisions.Source: §I · p. 2

II. GENERAL DECISION PROCEDURE

• The general decision procedure covers isolated or centralized sensors and distributed networks, with a single sensor making multiple decisions representable as a network of single-decision sensors.The basic single-sensor rule is a one-step decision based on the observation alone.Source: §II · pp. 2–3

A. Single sensor rules (for one-step decisions)

• For the illustrated single-sensor Bayesian objective, the optimal rule is deterministic and is selected by comparing derivatives of the objective with respect to decision probabilities.The setup assigns nonnegative costs to decisions under hypotheses and uses their prior probabilities and observation likelihoods.Source: A. Single sensor rules (for one-step… · p. 3

B. Sensor network rules

• Each sensor bases its decision on its own observation and the decisions forwarded to it; with the stated conditions, each optimal rule is deterministic.The deterministic-rule result follows from the affine objective and continuously distributed observations.Source: B. Sensor network rules · pp. 3–4
• For conditionally independent, continuously distributed observations in an acyclic sensor network, the decision rules and optimal Bayes-function value are given by (8), (9), (11), and (12).The network’s sensors are nodes and decision transmissions are arrows.Source: B. Sensor network rules · p. 4

III. THE CENTRALIZED SEQUENTIAL TEST

• The centralized test minimizes expected sample count subject to false-alarm and missed-detection probabilities bounded by α and β.The constraints are p(u_n = 1|H0) ≤ α and p(u_n = 0|H1) ≤ β.Source: §III · p. 5
• Wald’s SPRT minimizes expected stopping time when its thresholds depend on sample number, under the stated conditional-independence assumption.The theorem’s objective is the Lagrangian in (19).Source: §III · p. 5
• The optimal objective Sopt converges when observations are conditionally independent and the likelihood ratio depends nontrivially on data.Source: §III · p. 6
• The one-sensor stopping-time-bound figure varies standard deviation and missed-detection level β; reported graph shapes and values are independent of prior probability π.Source: §III · p. 7, Figure 1 · p. 7

A. Savings in number of observations

• The savings are defined as Δn = N(α, β) − Sopt, where N(α, β) is a static-test sample count and Sopt is the optimal sequential sample count.Source: A. Savings in number of observations · p. 7
• At σ = 1, the static test’s excess sample count is approximately 1, based on the upper bound and an approximation of sequential thresholds by a static threshold.The numerical computation is noted as not presented.Source: A. Savings in number of observations · p. 8
• About 50% sampling time can be saved by using the SLRT, consistent with the observation in.Source: A. Savings in number of observations · p. 8

B. Centralized version of the two-sensor distributed SLRT

• The two-sensor centralized sequential test is a centralized version of the distributed test for the network in Fig. 3.The sensor observations are available at the same location.Source: B. Centralized version of the… · p. 8
• The relevant probabilities are expressed in terms of Q-functions using the joint-observation likelihood ratio l(x, y) = p1(x, y)/p0(x, y).Source: B. Centralized version of the… · p. 8
• The numerical-results figure plots stopping-time-bound dependence on standard deviation at Y and missed-detection level β.Source: Figure 2 · p. 8, B. Centralized version of the… · p. 8

IV. THE DISTRIBUTED SEQUENTIAL TEST: TWO SENSORS

• The tandem network is the simplest nontrivial distributed case and retains essential features of tests for acyclic directed graphs.Source: §IV · p. 8
• X forwards its decision to Y, which begins sampling after receiving it and makes the final decision.Source: §IV · p. 8
• The objective minimizes expected sample count subject to false-alarm level α and missed-detection level β constraints.Source: §IV · p. 9
• Under conditional independence, the two-sensor test has optimal decision rules at X and fusion center Y.Source: §IV · p. 10
• Without conditional independence, the two-threshold likelihood rules are suboptimal in general.Source: §IV · p. 10
• Unlike in the centralized test, error constraints alone do not determine the optimal stopping time, so thresholds require constrained minimization.Source: §IV · p. 11

A. Upper bound of the sample number

• The distributed convergence result extends Theorem III.2, and the sample-by-sample test has a decision rule at X.Source: A. Upper bound of the sample number · p. 11
• The distributed sample-by-sample test has an upper bound on stopping time.Source: A. Upper bound of the sample number · p. 11
• The numerical bound is minimized over eight threshold parameters subject to the sample-by-sample constraints, with results shown in Fig. 4.Source: A. Upper bound of the sample number · p. 12, Figure 4 · p. 13
• With σ1 = 3 and α = β = 0.2, distributed processing is most beneficial when observations have low quality.Source: Figure 5 · p. 13, A. Upper bound of the sample number · p. 13
• The optimal stopping time has a finite upper bound whose behavior matches expectations and may be qualitatively similar to the optimum for simple networks.Source: A. Upper bound of the sample number · p. 13

V. GENERALIZATION: ACYCLIC DIRECTED GRAPHS

• The extension covers detection networks in the form of acyclic directed graphs.Source: §V · p. 13
• The section first establishes the usual binary decision rules for static detection over these networks.Source: §V · p. 13
• It then discusses sequential testing for acyclic-graph networks.Source: §V · p. 13

A. Binary decision rules for static detection over acyclic graphs

• For simplicity, each sensor is assumed to send the same message to all its offspring.Source: A. Binary decision rules for static… · p. 13
• Theorem V.1 gives the optimal binary decision rule for the network objective when observations are conditionally independent.Source: A. Binary decision rules for static… · p. 13
• The proof identifies the rule as Theorem II.1 simplified for binary decisions.Source: A. Binary decision rules for static… · p. 13

• Each sensor begins sampling only after receiving its parents’ decisions, and the timing constraints require its stopping time to be no earlier than its parents’ stopping times.Source: B. The sequential test for acyclic… · pp. 14–15
• The fusion-center objective is to minimize expected sample count subject to false-alarm and missed-detection constraints.Source: B. The sequential test for acyclic… · p. 14
• The section presents the acyclic-graph result as a straightforward extension of Theorem IV.1.Source: B. The sequential test for acyclic… · p. 15
• The graph result gives an optimal decision strategy under conditional independence; without that assumption, two-threshold likelihood rules are generally suboptimal.Source: B. The sequential test for acyclic… · p. 15

• The sample-by-sample test yields an upper bound on sample number.Source: C. Upper bound of the sample number · pp. 15–16
• The analysis assumes the prior and error levels are independent of sample number; time-dependent signals in time-dependent noise may require them to vary with sample number.Source: C. Upper bound of the sample number · p. 16
• The tests have an infinite horizon with no stopping-time limit, although finite-horizon versions can be considered with adjustments.Source: C. Upper bound of the sample number · p. 16

• Wald’s classical sequential probability ratio test is obtained as a byproduct of the optimal decision rule when stopping time is the objective.Source: §VI · p. 16
• Sample-by-sample processing yields upper bounds used to study how stopping time depends qualitatively on observation quality and desired accuracy.Source: §VI · p. 16
• The distributed sequential test for a two-sensor tandem network extends to acyclic directed sensor networks, using binary decision rules for static detection.Source: §VI · p. 16

APPENDIX A PROOF OF THEOREM III.1

• The proof of Theorem III.1 derives the decision regions and final thresholds from derivatives, with a step requiring the theorem’s conditional-independence assumption.Source: Appendix A · pp. 16–17

APPENDIX B PROOF OF THEOREM IV.1

• The proof of Theorem IV.1 derives decision rules for both X and Y, then obtains their decision regions after applying constraints.Source: Appendix B · pp. 17–18
• Theorem IV.1’s derivation uses conditional-independence assumptions when evaluating probabilities for the decision regions at Y.Source: Appendix B · p. 17