The embedding problem of Markov chains revisited : necessary eigenvalue conditions for embeddability.

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.