Optimal detection and error exponents for hidden semi-Markov models

Dragana Bajović, Kanghang He, Lina Stanković, Dejan Vukobratović, Vladimir Stanković

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)
30 Downloads (Pure)


We study detection of random signals corrupted by noise that over time switch their values (states) between a finite set of possible values, where the switchings occur at unknown points in time. We model such signals as hidden semi-Markov signals (HSMS), which generalize classical Markov chains by introducing explicit (possibly non-geometric) distribution for the time spent in each state. Assuming two possible signal states and Gaussian noise, we derive optimal likelihood ratio test and show that it has a computationally tractable form of a matrix product, with the number of matrices involved in the product being the number of process observations. The product matrices are independent and identically distributed, constructed by a simple measurement modulation of the sparse semi-Markov model transition matrix that we define in the paper. Using this result, we show that the Neyman-Pearson error exponent is equal to the top Lyapunov exponent for the corresponding random matrices. Using theory of large deviations, we derive a lower bound on the error exponent. Finally, we show that this bound is tight by means of numerical simulations.
Original languageEnglish
Pages (from-to)1077-1092
Number of pages16
JournalIEEE Journal on Selected Topics in Signal Processing
Issue number5
Early online date29 Jun 2018
Publication statusPublished - 31 Oct 2018


  • multi-state processes
  • hidden semi Markov models
  • explicit random duration
  • hypothesis testing
  • error exponent
  • large deviations principle
  • threshold effect
  • Lyapunov exponent


Dive into the research topics of 'Optimal detection and error exponents for hidden semi-Markov models'. Together they form a unique fingerprint.

Cite this