Active Sampling for the Quickest Detection of Markov Networks

Ali Tajer, Javad Heydari, H. Vincent Poor

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


Consider n random variables forming a Markov random field (MRF). The true model of the MRF is unknown, and it is assumed to belong to a binary set. The objective is to sequentially sample the random variables (one-at-a-time) such that the true MRF model can be detected with the fewest number of samples, while in parallel, the decision reliability is controlled. The core element of an optimal decision process is a rule for selecting and sampling the random variables over time. Such a process, at every time instant and adaptively to the collected data, selects the random variable that is expected to be most informative about the model, rendering an overall minimized number of samples required for reaching a reliable decision. The existing studies on detecting MRF structures generally sample the entire network at the same time and focus on designing optimal detection rules without regard to the data-acquisition process. This paper characterizes the sampling process for general MRFs, which is shown to be optimal in the asymptote of large $n$. The critical insight in designing the sampling process is devising an information measure that captures the decisions' inherent statistical dependence over time. Furthermore, when the MRFs can be modeled by acyclic probabilistic graphical models, the sampling rule is shown to take a computationally simple form. Performance analysis for the general case is provided, and the results are interpreted in several special cases: Gaussian MRFs, non-asymptotic regimes, Chernoff's rule for controlled (active) sensing, and the problem of cluster detection.

Original languageEnglish (US)
Pages (from-to)2479-2508
Number of pages30
JournalIEEE Transactions on Information Theory
Issue number4
StatePublished - Apr 1 2022
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


  • Active sampling
  • Markov network
  • controlled sensing
  • correlation detection
  • quickest detection


Dive into the research topics of 'Active Sampling for the Quickest Detection of Markov Networks'. Together they form a unique fingerprint.

Cite this