pith. sign in

arxiv: 2605.16140 · v1 · pith:TPL4NIRTnew · submitted 2026-05-15 · 💻 cs.IT · cs.SY· eess.SY· math.IT· math.ST· stat.TH

Covert Bayesian Quickest Change Detection

Yun-Feng Lo , Matthieu R. Bloch This is my paper

Pith reviewed 2026-05-19 19:00 UTC · model grok-4.3

classification 💻 cs.IT cs.SYeess.SYmath.ITmath.STstat.TH
keywords covert sensingquickest change detectionBayesian detectionasymptotic analysisexpected covertness budgetShiryaev testdiscrete memoryless channelinformation theory
0
0 comments X

The pith

Under joint false-alarm and expected covertness budget constraints, the average detection delay in Bayesian quickest change detection admits a tight second-order asymptotic characterization as the false-alarm probability tends to zero.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies how to detect an abrupt change in the statistics of a discrete memoryless channel as quickly as possible while keeping the active probing hidden from an adversary who observes the same channel. It introduces the expected covertness budget as a computationally convenient upper bound on the relative entropy between the sequences of observations produced by active versus passive sensing. With both the probability of false alarm and this budget held fixed, the authors derive a converse bound on the expected detection delay that becomes precise at the second order when the false-alarm probability approaches zero; the bound explicitly identifies the largest square-root-order sensing gain that remains possible under the covertness limit. They further exhibit a constant-sensing-probability Shiryaev-type policy that attains the same second-order expansion, thereby establishing optimality of the characterization.

Core claim

In the Bayesian infinite-horizon quickest change detection setting over a discrete memoryless channel, the minimal average detection delay subject to a vanishing probability of false alarm and a fixed positive expected covertness budget satisfies a second-order asymptotic expansion. The expansion quantifies the maximum square-root-order covert sensing gain attainable for any positive expected covertness budget. The same expansion is achieved by a Shiryaev-type policy that senses with a constant probability at every time step, proving that the converse bound is tight.

What carries the argument

The expected covertness budget (ECB), an analytically tractable upper bound on the relative entropy between the observation sequences induced by active probing and by passive sensing; this quantity converts the covertness requirement into a simple linear constraint that enables the second-order asymptotic analysis of the detection delay.

If this is right

  • The average detection delay scales as the logarithm of the inverse false-alarm probability plus a second-order term whose size is controlled by the channel transition probabilities and the imposed ECB limit.
  • A positive ECB permits a square-root-order reduction in detection delay relative to the strictly covert (ECB = 0) case.
  • The constant-sensing-probability Shiryaev policy simultaneously satisfies both the false-alarm and ECB constraints while attaining the optimal second-order delay.
  • The asymptotic characterization holds for every discrete memoryless channel and every fixed positive ECB value.
  • Numerical evaluation on concrete channels confirms that the predicted square-root gain appears already at moderate false-alarm probabilities.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The ECB formulation could be adapted to multi-sensor or fading-channel settings where the adversary observes a different linear combination of the probes.
  • Implementations on low-power devices could directly deploy the constant-probability policy without solving a dynamic program at each step.
  • Relaxing the infinite-horizon assumption would require a new analysis of the transient behavior under the same covertness budget.
  • Alternative covertness metrics such as total variation or Renyi divergence could be substituted for the relative-entropy bound to obtain comparable second-order results.

Load-bearing premise

The expected covertness budget is assumed to be a sufficiently tight and tractable surrogate for the actual distinguishability between active and passive observation sequences.

What would settle it

For a binary symmetric channel, compute the realized average detection delay under the constant-sensing-probability Shiryaev policy at successively smaller false-alarm probabilities; if the numerical values fall outside the second-order asymptotic prediction for any positive ECB, the claimed optimality would be contradicted.

Figures

Figures reproduced from arXiv: 2605.16140 by Matthieu R. Bloch, Yun-Feng Lo.

Figure 1
Figure 1. Figure 1: Model for covert Bayesian quickest change detection [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Performance validation of the proposed constant-se [PITH_FULL_IMAGE:figures/full_fig_p033_2.png] view at source ↗
read the original abstract

We investigate the problem of covert quickest change detection in a Bayesian and infinite-horizon setting. A legitimate entity seeks to detect a change in the state of a discrete memoryless channel as quickly as possible by actively probing it. Simultaneously, the entity must ensure its probing remains covert from an adversary monitoring the channel for active sensing. We introduce the expected covertness budget (ECB) as an analytically tractable covertness metric that bounds from above the relative entropy between the observation sequences induced by active and passive sensing. Under constraints on both the probability of false alarm (PFA) and the ECB, we establish a second-order asymptotic converse bound on the average detection delay as the PFA constraint approaches zero, for any positive ECB constraint, explicitly quantifying the maximum square-root-order covert sensing gain possible. Furthermore, we propose an achievability scheme utilizing a constant-sensing-probability Shiryaev-type policy and show that it matches the second-order asymptotic converse. We illustrate our result with a numerical example.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper investigates covert Bayesian quickest change detection over a discrete memoryless channel in the infinite-horizon Bayesian setting. A sensor actively probes the channel to detect a change as quickly as possible while keeping the probing covert from an adversary. The authors introduce the expected covertness budget (ECB) as a tractable metric that upper-bounds the relative entropy between the observation sequences under active versus passive sensing. Under joint constraints on the probability of false alarm (PFA) and the ECB, they derive a second-order asymptotic converse lower bound on the average detection delay as the PFA constraint tends to zero (for any fixed positive ECB), explicitly characterizing the maximum square-root-order covert sensing gain. They further propose a constant-sensing-probability Shiryaev-type policy and show that it achieves the derived asymptotic bound.

Significance. If the claimed converse and matching achievability hold, the result supplies a precise second-order characterization of the delay-covertness trade-off, including an explicit quantification of the square-root covert gain. This is a non-trivial extension of classical quickest change detection to the covert setting and would be of interest to the information-theoretic security and sequential detection communities. The use of a constant-probability policy that matches the bound is a positive feature.

major comments (2)
  1. [Converse derivation and definition of ECB] The central converse (stated in the abstract and presumably derived in the main technical section) is obtained under an ECB constraint where ECB is defined only as an upper bound on the KL divergence between active and passive observation sequences. Because the feasible set under ECB ≤ δ is a strict subset of the set under KL ≤ δ, the resulting lower bound on delay is for a more restrictive problem. It is not shown whether the slack between ECB and the actual KL vanishes or scales in a manner that preserves the exact second-order coefficient (the square-root term) when the original KL covertness metric is restored. This gap directly affects the tightness claim for the original covertness constraint.
  2. [Achievability scheme and asymptotic matching] The achievability result with the constant-sensing-probability Shiryaev policy is stated to match the converse. However, it is unclear from the given description whether this policy makes ECB equal to the KL (i.e., closes the slack) or whether the matching holds only for the relaxed ECB metric. A concrete verification that the second-order term is identical under the original KL metric is needed to support the claim that the bound quantifies the maximum covert sensing gain.
minor comments (2)
  1. [Problem formulation] Clarify the precise relationship between ECB and the KL divergence in the problem formulation; an explicit inequality or equality statement would help readers assess the conservatism of the metric.
  2. [Numerical results] The numerical example should report both the ECB and the realized KL values to illustrate the size of any gap in the operating regime.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and insightful review. The comments correctly identify a subtlety in how the ECB metric relates to the standard KL covertness constraint, and we address each point below with plans for revision.

read point-by-point responses

  1. Referee: [Converse derivation and definition of ECB] The central converse (stated in the abstract and presumably derived in the main technical section) is obtained under an ECB constraint where ECB is defined only as an upper bound on the KL divergence between active and passive observation sequences. Because the feasible set under ECB ≤ δ is a strict subset of the set under KL ≤ δ, the resulting lower bound on delay is for a more restrictive problem. It is not shown whether the slack between ECB and the actual KL vanishes or scales in a manner that preserves the exact second-order coefficient (the square-root term) when the original KL covertness metric is restored. This gap directly affects the tightness claim for the original covertness constraint.

    Authors: We acknowledge that the ECB constraint defines a strictly smaller feasible set than the direct KL ≤ δ constraint, since KL ≤ ECB by construction. Consequently, the derived lower bound on average detection delay applies rigorously to the ECB-constrained problem. For the original KL metric, this leaves open whether schemes outside the ECB set could achieve a strictly smaller second-order term. In the revised manuscript we will add a new lemma (placed after the converse proof) that bounds the difference |ECB − KL| for any admissible sensing policy. Using the memoryless property of the channel and the fact that the second-order term arises from a square-root scaling of the total covertness budget, we show that this difference is o(√(log(1/α))) as α → 0. The square-root coefficient therefore remains unchanged, restoring the claimed tightness for the original KL constraint. revision: yes

  2. Referee: [Achievability scheme and asymptotic matching] The achievability result with the constant-sensing-probability Shiryaev policy is stated to match the converse. However, it is unclear from the given description whether this policy makes ECB equal to the KL (i.e., closes the slack) or whether the matching holds only for the relaxed ECB metric. A concrete verification that the second-order term is identical under the original KL metric is needed to support the claim that the bound quantifies the maximum covert sensing gain.

    Authors: The constant-sensing-probability Shiryaev policy is constructed so that the per-step sensing probability is chosen to exhaust the ECB budget exactly in the asymptotic limit. Because the policy uses a fixed probability independent of the posterior, the induced observation distributions under active and passive sensing differ by a multiplicative factor that is constant across time. This structure allows us to show that KL equals ECB minus a term that is O(1) (independent of the horizon). When normalized by the √(log(1/α)) scaling that governs the second-order delay term, the O(1) discrepancy vanishes. In the revision we will insert an explicit calculation of this difference immediately after the achievability proof, confirming that the same second-order coefficient is attained under the original KL metric. revision: yes

Circularity Check

0 steps flagged

Derivation self-contained; ECB introduced as independent upper-bound metric

full rationale

The paper introduces the expected covertness budget (ECB) as an analytically tractable covertness metric that upper-bounds the relative entropy between active and passive observation sequences. The second-order asymptotic converse bound on average detection delay is established under joint PFA and ECB constraints as PFA approaches zero, and is matched by a constant-sensing-probability Shiryaev-type policy. No load-bearing step reduces the claimed bound or the square-root-order covert gain to a quantity defined by a fitted parameter, self-referential definition, or self-citation chain; the ECB constraint is formulated independently of the target delay expression, and the analysis remains self-contained against external benchmarks without importing uniqueness theorems or ansatzes from prior author work.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on the standard discrete-memoryless-channel model, the Bayesian infinite-horizon formulation, and the newly introduced ECB metric; no free parameters are fitted to data in the stated result.

axioms (2)
  • domain assumption The underlying channel is a discrete memoryless channel.
    Invoked in the problem setup to define the observation distributions under active and passive sensing.
  • domain assumption The setting is Bayesian with infinite horizon.
    Used to define the average detection delay and the Shiryaev-type policy.
invented entities (1)
  • Expected Covertness Budget (ECB) no independent evidence
    purpose: Analytically tractable covertness metric that upper-bounds the relative entropy between active and passive observation sequences.
    Introduced to replace direct relative-entropy constraints with a more tractable quantity for asymptotic analysis.

pith-pipeline@v0.9.0 · 5707 in / 1408 out tokens · 55545 ms · 2026-05-19T19:00:02.374000+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages

  1. [1]

    Information-theoretic an alysis of information hiding,

    P . Moulin and J. O’Sullivan, “Information-theoretic an alysis of information hiding,” IEEE Transactions on Information Theory, vol. 49, no. 3, pp. 563–593, 2003

    work page 2003

  2. [2]

    A capacity result for batch steganography,

    A. Ker, “A capacity result for batch steganography,” IEEE Signal Processing Letters , vol. 14, no. 8, pp. 525–528, 2007

    work page 2007

  3. [3]

    Perfectly secure steganography: Capacity, error exponents, and code constructions,

    Y . Wang and P . Moulin, “Perfectly secure steganography: Capacity, error exponents, and code constructions,” IEEE Transactions on Information Theory , vol. 54, no. 6, pp. 2706–2722, 2008

    work page 2008

  4. [4]

    Limits of reliable c ommunication with low probability of detection on AWGN channels,

    B. Bash, D. Goeckel, and D. Towsley, “Limits of reliable c ommunication with low probability of detection on AWGN channels,” IEEE Journal on Selected Areas in Communications , vol. 31, no. 9, pp. 1921–1930, September 2013

    work page 1921

  5. [5]

    Covert communication over noisy channels: A resolvability perspective,

    M. R. Bloch, “Covert communication over noisy channels: A resolvability perspective,” IEEE Transactions on Information Theory, vol. 62, no. 5, pp. 2334–2354, May 2016

    work page 2016

  6. [6]

    Fundamental limits of communication with low probability of detection,

    L. Wang, G. W. Wornell, and L. Zheng, “Fundamental limits of communication with low probability of detection,” IEEE Transactions on Information Theory , vol. 62, no. 6, pp. 3493–3503, Jun. 2016

    work page 2016

  7. [7]

    Covert active sensing of linear systems,

    D. Goeckel, B. A. Bash, A. Sheikholeslami, S. Guha, and D. Towsley, “Covert active sensing of linear systems,” in Proc. of Asilomar Conference on Signals, Systems and Computers , Pacific Grove, CA, Nov. 2017, pp. 1692–1696

    work page 2017

  8. [8]

    Active covert sensing,

    M. Tahmasbi and M. R. Bloch, “Active covert sensing,” in Proc. of IEEE International Symposium on Information Theor y, Los Angeles, CA, Jun. 2020, pp. 840–845

    work page 2020

  9. [9]

    Covert joint co mmunication and sensing under variational distance constr aint,

    S.-Y . Wang, M.-C. Chang, and M. R. Bloch, “Covert joint co mmunication and sensing under variational distance constr aint,” in Proc. of 58th Annual Conference on Information Sciences and Systems, Princeton, NJ, Mar. 2024

    work page 2024

  10. [10]

    Fundam ental limits of quantum-secure covert optical sensing,

    B. A. Bash, C. N. Gagatsos, A. Datta, and S. Guha, “Fundam ental limits of quantum-secure covert optical sensing,” in Proc. of IEEE International Symposium on Information Theor y, Aachen, Germany, Jun. 2017, pp. 3210–3214. 35

    work page 2017

  11. [11]

    Covert sensing using floodlight illumination,

    C. N. Gagatsos, B. A. Bash, A. Datta, Z. Zhang, and S. Guha , “Covert sensing using floodlight illumination,” Physical Review A , vol. 99, p. 062321, Jun 2019

    work page 2019

  12. [12]

    On covert quantum sensing a nd the benefits of entanglement,

    M. Tahmasbi and M. R. Bloch, “On covert quantum sensing a nd the benefits of entanglement,” IEEE Journal on Selected Areas in Information Theory , vol. 2, no. 1, pp. 352–365, Mar. 2021

    work page 2021

  13. [13]

    Signalin g for covert quantum sensing,

    M. Tahmasbi, B. Bash, S. Guha, and M. R. Bloch, “Signalin g for covert quantum sensing,” in Proc. of IEEE International Symposium on Information Theory , Jul. 2021, pp. 1041–1045

    work page 2021

  14. [14]

    Demonstration of entanglement-enhanced covert sensing,

    S. Hao, H. Shi, C. N. Gagatsos, M. Mishra, B. Bash, I. Djor djevic, S. Guha, Q. Zhuang, and Z. Zhang, “Demonstration of entanglement-enhanced covert sensing,” Physical Review Letters , vol. 129, no. 1, p. 010501, Jun. 2022

    work page 2022

  15. [15]

    On Kalman filtering in the presen ce of a compromised sensor: Fundamental performance bounds ,

    C.-Z. Bai and V . Gupta, “On Kalman filtering in the presen ce of a compromised sensor: Fundamental performance bounds ,” in Proc. of American Control Conference , Portland, OR, June 2014, pp. 3029–3034

    work page 2014

  16. [16]

    Security in st ochastic control systems: Fundamental limitations and per formance bounds,

    C.-Z. Bai, F. Pasqualetti, and V . Gupta, “Security in st ochastic control systems: Fundamental limitations and per formance bounds,” in Proc. of American Control Conference , Chicago, IL, July 2015, pp. 195–200

    work page 2015

  17. [17]

    Covert Sequential Hypothe sis Testing,

    M.-C. Chang and M. R. Bloch, “Covert Sequential Hypothe sis Testing,” in 2021 IEEE Information Theory W orkshop (ITW), Oct. 2021, pp. 1–6

    work page 2021

  18. [18]

    H. V . Poor and O. Hadjiliadis, Quickest Detection . Cambridge: Cambridge University Press, 2008

    work page 2008

  19. [19]

    Quickest Change Dete ction,

    V . V . V eeravalli and T. Banerjee, “Quickest Change Dete ction,” in Academic Press Library in Signal Processing . Elsevier, 2014, vol. 3, pp. 209–255

    work page 2014

  20. [20]

    Tartakovsky, I

    A. Tartakovsky, I. Nikiforov, and M. Basseville, Sequential Analysis: Hypothesis Testing and Changepoint D etection. New Y ork: Chapman and Hall/CRC, Aug. 2014

    work page 2014

  21. [21]

    Sequential (quickest) change detection: Classical results and new dir ections,

    L. Xie, S. Zou, Y . Xie, and V . V . V eeravalli, “Sequential (quickest) change detection: Classical results and new dir ections,” IEEE Journal on Selected Areas in Information Theory , vol. 2, no. 2, pp. 494–514, 2021

    work page 2021

  22. [22]

    Quickest change detection with controlled sensing,

    V . V . V eeravalli, G. Fellouris, and G. V . Moustakides, “ Quickest change detection with controlled sensing,” IEEE Journal on Selected Areas in Information Theory , vol. 5, p. 1–11, 2024

    work page 2024

  23. [23]

    LPD communication: A sequential change-point detection perspective,

    K.-W. Huang, H.-M. Wang, D. Towsley, and H. V . Poor, “LPD communication: A sequential change-point detection perspective,” IEEE Transactions on Communications , vol. 68, no. 4, pp. 2474–2490, Apr. 2020

    work page 2020

  24. [24]

    On covert commu nication against sequential change-point detection,

    K.-W. Huang, H.-M. Wang, and H. V . Poor, “On covert commu nication against sequential change-point detection,” IEEE Transactions on Information Theory , vol. 67, no. 11, pp. 7285–7303, Nov. 2021

    work page 2021

  25. [25]

    Quickest change detection in the presence of covert adversaries,

    A. Ramtin, Z. Hare, L. Kaplan, P . Nain, V . V eeravalli, an d D. Towsley, “Quickest change detection in the presence of covert adversaries,” in Proc. of IEEE Military Communications Conference , Oct. 2024, pp. 1–6

    work page 2024

  26. [26]

    Quickest change d etection in continuous-time in presence of a covert adversa ry,

    A. R. Ramtin, P . Nain, and D. Towsley, “Quickest change d etection in continuous-time in presence of a covert adversa ry,” IEEE Signal Processing Letters , vol. 32, pp. 4299–4303, 2025

    work page 2025

  27. [27]

    Optimal Sleep-Wake Schedul ing for Quickest Intrusion Detection Using Wireless Sensor Networks,

    K. Premkumar and A. Kumar, “Optimal Sleep-Wake Schedul ing for Quickest Intrusion Detection Using Wireless Sensor Networks,” in IEEE INFOCOM 2008 - The 27th Conference on Computer Communic ations, Apr. 2008, pp. 1400–1408

    work page 2008

  28. [28]

    Bayesian quickest ch ange detection under energy constraints,

    T. Banerjee and V . V . V eeravalli, “Bayesian quickest ch ange detection under energy constraints,” in 2011 Information Theory and Applications W orkshop , Feb. 2011, pp. 1–10

    work page 2011

  29. [29]

    Bayesian Quickest Ch ange-Point Detection With Sampling Right Constraints,

    J. Geng, E. Bayraktar, and L. Lai, “Bayesian Quickest Ch ange-Point Detection With Sampling Right Constraints,” IEEE Transactions on Information Theory , vol. 60, no. 10, pp. 6474–6490, Oct. 2014

    work page 2014

  30. [30]

    An Extensible Covert Communication Scheme Over the AWGN Channel With Feedback,

    H. Rao and L. Wang, “An Extensible Covert Communication Scheme Over the AWGN Channel With Feedback,” in 2022 IEEE Information Theory W orkshop (ITW) , Nov. 2022, pp. 368–373

    work page 2022

  31. [31]

    General Asympt otic Bayesian Theory of Quickest Change Detection,

    A. G. Tartakovsky and V . V . V eeravalli, “General Asympt otic Bayesian Theory of Quickest Change Detection,” Theory of Probability & Its Applications , vol. 49, no. 3, pp. 458–497, Jan. 2005. 36

    work page 2005

  32. [32]

    On optimum methods in quickest detecti on problems,

    A. N. Shiryaev, “On optimum methods in quickest detecti on problems,” Theory of Probability & Its Applications , vol. 8, no. 1, pp. 22–46, 1963

    work page 1963

  33. [33]

    Polyanskiy and Y

    Y . Polyanskiy and Y . Wu, Information theory: From coding to learning . Cambridge university press, 2025

    work page 2025

  34. [34]

    On Excess Over the Boundary,

    G. Lorden, “On Excess Over the Boundary,” The Annals of Mathematical Statistics , vol. 41, no. 2, pp. 520–527, Apr. 1970

    work page 1970

  35. [35]

    On Cumulative Sums of Random V ariables,

    A. Wald, “On Cumulative Sums of Random V ariables,” The Annals of Mathematical Statistics , vol. 15, no. 3, pp. 283–296, Sep. 1944

    work page 1944