{
  "id": "2207.14088",
  "version": "v1",
  "published": "2022-07-28T13:52:09.000Z",
  "updated": "2022-07-28T13:52:09.000Z",
  "title": "On the Sequential Probability Ratio Test in Hidden Markov Models",
  "authors": [
    "Oscar Darwin",
    "Stefan Kiefer"
  ],
  "comment": "28 pages, 10 figures, submitted to CONCUR 2022",
  "categories": [
    "math.PR",
    "cs.LO",
    "math.ST",
    "stat.TH"
  ],
  "abstract": "We consider the Sequential Probability Ratio Test applied to Hidden Markov Models. Given two Hidden Markov Models and a sequence of observations generated by one of them, the Sequential Probability Ratio Test attempts to decide which model produced the sequence. We show relationships between the execution time of such an algorithm and Lyapunov exponents of random matrix systems. Further, we give complexity results about the execution time taken by the Sequential Probability Ratio Test.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-07-28T13:52:09.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "F.0",
      "G.3"
    ],
    "keywords": [
      "hidden markov models",
      "sequential probability ratio test attempts",
      "random matrix systems",
      "execution time taken"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 28,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}