The Eigenvalue Region of a Family of Markov Chains with Randomness Confined to Two States
Abstract
We determine the complete eigenvalue region of the following Markov chains on 2q states, for q≥2. The states are A0,…,Aq−1 and B0,…,Bq−1. Each transition Aj→ Aj+1 and Bj→ Bj+1, for 0≤ j<q−1, has probability one. From Aq−1, the chain moves to A0 with probability a and to B0 with probability 1−a. From Bq−1, it moves to B0 with probability b and to Aj with probability (1−b)pj. Here a,b∈[0,1] and pj≥0 with ∑j=0q−1pj=1; these parameters vary over all permitted values. Every segment from zero to an attainable eigenvalue lies in the region. Its unit-circle points are exactly the roots of unity of order at most 2q, as for unrestricted stochastic matrices of the same order, yet the full region is strictly smaller. It excludes 0<|Argλ|<π/q. For odd q, the final nonreal boundary arc ends at a negative real point inside the unit disk; the remaining interval to −1 is also boundary. Every transition matrix has the same characteristic polynomial as one with a=b. Among q+1 fixed matrices in this balanced family, convex combinations of at most three realize every attainable eigenvalue, and two suffice on the boundary. Both bounds are sharp within this set. Consecutive reduced fractions in $[1/(2q),1/2]$ with denominators at most 2q select the upper nonreal boundary constructions. Each boundary radius is the unique solution of an equation whose left-hand side increases strictly with the radius.
Related
- How the eigenvalue region of standardized Laplacians leaves the 2005 polygon
- Regret in the Newsvendor Model with Demand and Yield Randomness
- How far is Kolmogorov-Loveland randomness from Martin-Löf randomness?
- A Randomness Test Formalism for Neutral Measures and Beyond
- Common Randomness: A Key Enabler of Trustworthy 6G Communication Systems
BibTeX
@misc{verbeken2026eigenvalue,
title = {{The Eigenvalue Region of a Family of Markov Chains with Randomness Confined to Two States}},
author = {Brecht F. Verbeken and Vincent Ginis},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.31768},
eprint = {2609.31768},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.31768},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Eigenvalue Region of a Family of Markov Chains with Randomness Confined to Two States
AU - Brecht F. Verbeken
AU - Vincent Ginis
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2609.31768
UR - https://arxiv.org/abs/2609.31768
AB - We determine the complete eigenvalue region of the following Markov chains on 2q states, for q≥2. The states are A_0,…,A_q−1 and B_0,…,B_q−1. Each transition A_j→ A_j+1 and B_j→ B_j+1, for 0≤ j<q−1, has probability one. From A_q−1, the chain moves to A_0 with probability a and to B_0 with probability 1−a. From B_q−1, it moves to B_0 with probability b and to A_j with probability (1−b)p_j. Here a,b∈[0,1] and p_j≥0 with ∑_j=0^q−1p_j=1; these parameters vary over all permitted values. Every segment from zero to an attainable eigenvalue lies in the region. Its unit-circle points are exactly the roots of unity of order at most 2q, as for unrestricted stochastic matrices of the same order, yet the full region is strictly smaller. It excludes 0<|Argλ|<π/q. For odd q, the final nonreal boundary arc ends at a negative real point inside the unit disk; the remaining interval to −1 is also boundary. Every transition matrix has the same characteristic polynomial as one with a=b. Among q+1 fixed matrices in this balanced family, convex combinations of at most three realize every attainable eigenvalue, and two suffice on the boundary. Both bounds are sharp within this set. Consecutive reduced fractions in $[1/(2q),1/2]$ with denominators at most 2q select the upper nonreal boundary constructions. Each boundary radius is the unique solution of an equation whose left-hand side increases strictly with the radius.
ER -