The embedding problem of Markov chains revisited : necessary eigenvalue conditions for embeddability.
- Author
- Marie-Anne Guerry and Philippe Carette (UGent)
- Organization
- Abstract
- This paper addresses the question whether a discrete-time Markov chain can be embedded in a continuous-time or in a discrete-time Markov chain. Two variants of the embedding problem are studied: (1) a continuous-time version, introduced by Elfving in 1937, asking whether a transition matrix P can be expressed as P = exp(Q) for some Markov generator matrix Q, and (2) a discrete-time version, first studied by Singer and Spilerman (1973-1974), investigating whether P has a stochastic matrix root A, i.e. A^k=P for some integer k > 1. The ability to determine whether a stochastic matrix is embeddable is valuable, as it allows for the estimation of transition probabilities over intervals shorter than one time step. The embedding problem is a hard problem. Therefore, this paper provides easily verifiable necessary conditions for discrete-time embeddability, focusing on the spectrum of P and using known spectral properties of nonnegative and stochastic matrices. Various types of conditions are explored, including those based on individual eigenvalues and the full spectrum. The embedding conditions are derived from the Nonnegative Inverse Eigenvalue Problem (NIEP), the Johnson-Loewy-London inequalities (JLL), and properties of powers of the Karpelevich region. Detailed results are presented for 3 × 3 stochastic matrices with both real and nonreal spectra. As a by-product, the paper also recovers the necessary spectral condition for continuous-time embeddability, as found by Runnenburg in 1962.
- Keywords
- Markov chain, embedding problem
Downloads
-
(...).pdf
- full text (Published version)
- |
- UGent only
- |
- |
- 228.75 KB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU-01JXFCQ1QG8CF95AXRDZAQZ9ZS
- MLA
- Guerry, Marie-Anne, and Philippe Carette. “The Embedding Problem of Markov Chains Revisited : Necessary Eigenvalue Conditions for Embeddability.” 21st Applied Stochastic Models and Data Analysis International Conference, Book of Abstracts, edited by Christos Skiadas, International Society for the Advancement of Science and Technology, 2025.
- APA
- Guerry, M.-A., & Carette, P. (2025). The embedding problem of Markov chains revisited : necessary eigenvalue conditions for embeddability. In C. Skiadas (Ed.), 21st Applied Stochastic Models and Data Analysis International Conference, Book of Abstracts. International Society for the Advancement of Science and Technology.
- Chicago author-date
- Guerry, Marie-Anne, and Philippe Carette. 2025. “The Embedding Problem of Markov Chains Revisited : Necessary Eigenvalue Conditions for Embeddability.” In 21st Applied Stochastic Models and Data Analysis International Conference, Book of Abstracts, edited by Christos Skiadas. International Society for the Advancement of Science and Technology.
- Chicago author-date (all authors)
- Guerry, Marie-Anne, and Philippe Carette. 2025. “The Embedding Problem of Markov Chains Revisited : Necessary Eigenvalue Conditions for Embeddability.” In 21st Applied Stochastic Models and Data Analysis International Conference, Book of Abstracts, ed by. Christos Skiadas. International Society for the Advancement of Science and Technology.
- Vancouver
- 1.Guerry M-A, Carette P. The embedding problem of Markov chains revisited : necessary eigenvalue conditions for embeddability. In: Skiadas C, editor. 21st Applied Stochastic Models and Data Analysis International Conference, Book of Abstracts. International Society for the Advancement of Science and Technology; 2025.
- IEEE
- [1]M.-A. Guerry and P. Carette, “The embedding problem of Markov chains revisited : necessary eigenvalue conditions for embeddability.,” in 21st Applied Stochastic Models and Data Analysis International Conference, Book of Abstracts, Piraeus, Greece, 2025.
@inproceedings{01JXFCQ1QG8CF95AXRDZAQZ9ZS,
abstract = {{This paper addresses the question whether a discrete-time Markov chain can be embedded in a continuous-time or in a discrete-time Markov chain. Two variants of the embedding problem are studied: (1) a continuous-time version, introduced by Elfving in 1937, asking whether a transition matrix P can be expressed as P = exp(Q) for some Markov generator matrix Q, and (2) a discrete-time version, first studied by Singer and Spilerman (1973-1974), investigating whether P has a stochastic matrix root A, i.e. A^k=P for some integer k > 1. The ability to determine whether a stochastic matrix is embeddable is valuable, as it allows for the estimation of transition probabilities over intervals shorter than one time step.
The embedding problem is a hard problem. Therefore, this paper provides easily verifiable necessary conditions for discrete-time embeddability, focusing on the spectrum of P and using known spectral properties of nonnegative and stochastic matrices. Various types of conditions are explored, including those based on individual eigenvalues and the full spectrum. The embedding conditions are derived from the Nonnegative Inverse Eigenvalue Problem (NIEP), the Johnson-Loewy-London inequalities (JLL), and properties of powers of the Karpelevich region. Detailed results are presented for 3 × 3 stochastic matrices with both real and nonreal spectra. As a by-product, the paper also recovers the necessary spectral condition for continuous-time embeddability, as found by Runnenburg in 1962.}},
author = {{Guerry, Marie-Anne and Carette, Philippe}},
booktitle = {{21st Applied Stochastic Models and Data Analysis International Conference, Book of Abstracts}},
editor = {{Skiadas, Christos}},
keywords = {{Markov chain,embedding problem}},
language = {{eng}},
location = {{Piraeus, Greece}},
pages = {{2}},
publisher = {{International Society for the Advancement of Science and Technology}},
title = {{The embedding problem of Markov chains revisited : necessary eigenvalue conditions for embeddability.}},
year = {{2025}},
}