On computing the total variation distance of hidden Markov models
We prove results on the decidability and complexity of computing the total variation distance (equivalently, the L1-distance) of hidden Markov models (equivalently, labelled Markov chains). This distance measures the difference between the distributions on words that two hidden Markov models induce....
| Main Author: | |
|---|---|
| Format: | Conference item |
| Published: |
Schloss Dagstuhl
2018
|
| Summary: | We prove results on the decidability and complexity of computing the total variation distance (equivalently, the L1-distance) of hidden Markov models (equivalently, labelled Markov chains). This distance measures the difference between the distributions on words that two hidden Markov models induce. The main results are: (1) it is undecidable whether the distance is greater than a given threshold; (2) approximation is #P-hard and in PSPACE. |
|---|