# A Finite-Sample Bound for Identifying Partially Observed Linear Switched Systems From a Single Trajectory

Dániel Rácz, Mihaly Petreczky, Bálint Daróczy

► To cite this version:

Dániel Rácz, Mihaly Petreczky, Bálint Daróczy. A Finite-Sample Bound for Identifying Partially Observed Linear Switched Systems From a Single Trajectory. IEEE Control Systems Letters, 2025, 9, pp.1790-1795. 10.1109/LCSYS.2025.3580519. hal-05389384

HAL Id: hal-05389384

https://hal.science/hal-05389384v1

Submitted on 30 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A finite-sample bound for identifying partially observed linear switched systems from a single trajectory

Dániel Rácz, Mihály Petreczky and Bálint Daróczy

**Abstract**— We derive a finite-sample probabilistic bound on the parameter estimation error of a system identification algorithm for Linear Switched Systems. The algorithm estimates Markov parameters from a single trajectory and applies a variant of the Ho-Kalman algorithm to recover the system matrices. Our bound guarantees statistical consistency under the assumption that the true system exhibits quadratic stability. The proof leverages the theory of weakly dependent processes. To the best of our knowledge, this is the first finite-sample bound for this algorithm in the single-trajectory setting.

**Index Terms**— Statistical learning, Switched systems, System Identification

## I. INTRODUCTION

In this paper we consider the problem of identifying a Linear Switched System (LSS)

$$ \Sigma \begin{cases} \mathbf{x}(t+1) = A_{\mathbf{q}(t)}\mathbf{x}(t) + B_{\mathbf{q}(t)}\mathbf{u}(t) + \mathbf{w}(t) \\ \mathbf{y}(t) = C\mathbf{x}(t) + D\mathbf{u}(t) + \mathbf{v}(t) \end{cases} \quad (1) $$

For simplicity, we consider MISO systems, i.e. the input $\mathbf{u}(t) \in \mathbb{R}^m$, the output $\mathbf{y}(t) \in \mathbb{R}$ and the state $\mathbf{x}(t) \in \mathbb{R}^n$, where $n$ is the dimension of the state space, $m$ is the dimension of the input, the switching signal $\mathbf{q}(t) \in \{1, ..., n_Q\} = Q$, which is a finite set, and $\mathbf{w}(t)$ and $\mathbf{v}(t)$ are the noise vectors. We would like to estimate the matrices $(\{A_q, B_q\}_{q \in Q}, C, D)$ (up to similarity) from a sample $S_N = \{(y_t, u_t, q_t)\}_{t=0}^N$ of $(\mathbf{y}(t), \mathbf{u}(t), \mathbf{q}(t))$ and derive finite-sample bounds on the parameter estimation error.

**Contribution.** We present a finite-sample probabilistic bound on the error between the true parameters and those returned by a particular subspace identification algorithm, described in [4], [18]. The latter algorithm relies on estimating the Markov-parameters of the LSS [13], and applying Ho-Kalman algorithm to the arising Hankel matrix. The bound on the estimation error of the system matrices is $O(1/\sqrt{N})$,

Submitted for review on March 17, 2025. "This work has been supported by the European Union project RRF-2.3.1-21-2022-00004 within the A.I. National Laboratory Program, by the C.N.R.S. E.A.I. project StabLearnDyn and the E.D.F. project 101103386 FaRADAI."

D. Rácz is with HUN-REN SZTAKI, Budapest, Hungary and ELTE, Budapest, Hungary (e-mail: racz.daniel@sztaki.hun-ren.hu)

M. Petreczky is with Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRISTAL, F-59000 Lille, France (e-mail: mihaly.petreczky@centralelille.fr).

B. Daróczy is with HUN-REN SZTAKI, Budapest, Hungary (e-mail: daroczy.balint@sztaki.hun-ren.hu).

therefore it converges to 0 as $N \to \infty$. We assume bounded, i.i.d. inputs, noises, and switching processes, as well as the stability of the true system. These simplifying assumptions ensure persistence of excitation [14]. We consider scalar outputs for simplicity, but the results can be extended to the MIMO case, see [17, Appendix B].

Similarly to bounds of this type, the bound is polynomial in the underlying system's state-space dimension, and decreases with the Lyapunov exponent of the underlying system. Unlike much of the related work, we do not assume any lower bound on the number of Markov parameters needed to be estimated for a given trajectory length. On the downside, we need the boundedness of inputs and noise. In contrast to most of the existing work, instead of concentration inequalities for sub-Gaussian random matrices, we use concentration inequalities for weakly dependent processes [1].

**Motivation.** Finding finite-sample bounds on the system matrices allows us to evaluate the performance of the estimated model in terms of their predictive power for any inputs and switching sequences, and their use for control design.

**Related work: system identification.** Identification of switched and jump-Markov systems is an active research area, see e.g. [9]. Most of the literature assumes that the switching signal is unobserved, making the learning problem more challenging and leading to the absence of consistency results. In contrast, we assume that the switching signal is observed, which is a more restrictive assumption, but still relevant for many application, and we provide a finite-sample bound which also proves consistency. Furthermore, there are consistent subspace identification algorithms, e.g. [14] for noiseless LSSs, or in [18] for noisy LSS. Both algorithms assume that the switching signal is known. To our knowledge, there are no consistency results without some knowledge about the switching signal.

LSSs can be viewed as a subclass of linear parameter-varying (LPV) systems, if the switching signal is viewed as a discrete scheduling. There is a wealth of literature on system identification for LPV systems, including subspace methods [5], [25], but there are no finite-sample bounds for the single time series setup.

**Related work: finite-sample bounds.** Probably Approximately Correct (PAC, see [22] for a general overview) bounds for sub-classes of dynamical systems exist in autoregressive [1], [10] and state-space form [6], [7]. However, the cited
papers relate the true loss with the empirical loss, and except [7] which studies only linear systems, the cited papers do not address the parameter estimation error.

Recent works on finite-sample bounds on learning algorithms for dynamical systems [26] focus on autoregressive models or full-state observation models, including switched models [10], [21], [23], [27]. A few papers propose finite-sample bounds for identifying linear dynamical systems [24] by estimating Markov parameters and applying Ho-Kalman [12]. [20] proposed a finite-sample bound for estimating Markov parameters for bilinear systems. However, all these results are not transferable to LSSs, due to differences between the system classes.

In [19] a similar problem was considered, but the training data consisted of several independently sampled time series. Another difference is that we consider a version of the Ho-Kalman algorithm with a basis selection. The latter has been used for subspace identification [4], [5], and it is computationally more efficient.

To sum it up, the main novelty of this paper is proposing a finite-sample bound for estimating Linear Switched Systems with (1) partial observations from a (2) single time series, using the theory of (3) weakly-dependent processes [1]. The paper is organized as follows. In Section II, we define our problem. Next, we state our main result in Section III, conclude our findings in Section IV followed by the proofs of the Lemmas in Section V.

## II. PROBLEM SETUP

**Notation.** For any vector $v \in \mathbb{R}^n$ we denote the i-th component of $v$ by $v[i]$, while $v[k:m]$ is the component of $v$ between the indices $k$ and $m$. A word $w = w_1...w_k$ refers to the tuple $(w_1, ..., w_k)$. The length of the word is denoted by $|w|$. For any words $v$ and $w$, $vw$ denotes their concatenation. The empty word is denoted by $\epsilon$ and $Q^*$ denotes the Kleene star of $Q$. We use boldface characters for probabilistic quantities. For any matrix $A$, $\sigma_n(A)$ denotes its smallest singular value, while $\lambda_1(A)$ and $\lambda_n(A)$ denote the eigenvalues with the largest and smallest absolute values, respectively. $I_n \in \mathbb{R}^{n \times n}$ denotes the identity matrix, 0 denotes the squared zero matrix and $|$ denotes the concatenation of matrices. We denote by $\|\cdot\|_p$ the $p$-norm $p = 1, 2, \infty$ on the Euclidean space and $\|\cdot\|_F$ denotes the Frobenius norm. All the random variables are understood over the probability space $(\Omega, \mathcal{F}, \mathbb{P})$, $\mathbb{E}$ denotes the expectation and all the stochastic processes are over the discrete time axis $\mathbb{Z}$.

**Preliminaries on switched systems.** We make the following assumptions on the LSS parameters defined in (1).

**Assumption 2.1:** We assume the following on the processes and matrices involved in the definition of (1):

a) $\mathbf{q}(t)$ is i.i.d., $\mathbb{P}(\mathbf{q}(t) = q) = p_q > 0, \forall q \in Q$,

b) $\mathbf{r}(t) = [\mathbf{u}^T(t), \mathbf{w}^T(t), \mathbf{v}^T(t)]^T$ is a zero mean i.i.d. process with $\Sigma_u = \mathbb{E}[\mathbf{u}(t)\mathbf{u}^T(t)]$ being the covariance matrix of $\mathbf{u}$, and for $t \in \mathbb{Z}$, $\|\mathbf{r}(t)\|_{\infty} \le K_u$, and $\mathbf{r}(t)$ and $\mathbf{x}(t)$ are independent, and also $\{\mathbf{w}^T(t), \mathbf{v}^T(t)\}$ and $\mathbf{u}(t)$ are independent,

c) $\{\mathbf{r}(s)\}_{s \in \mathbb{Z}}$ and $\{\mathbf{q}(s)\}_{s \in \mathbb{Z}}$ are independent,

d) the noiseless LSS, $x_{t+1} = A_{q_t}x_t + B_{q_t}u_t$, $y_t = Cx_t + Du_t$ has minimal dimension in the sense of [13], i.e. it is span-reachable from zero and observable,

e) there exists a positive definite matrix $P > 0$ and $\gamma \in (0, 1)$ such that $\forall q \in Q$, $A_q^T P A_q < \frac{\gamma^2}{n_Q^2} P$.

Assumption a) is somewhat restrictive, but reasonable when switching is treated as an external input, as it is common in LSS applications. Assumption b) requires the inputs and the noise to be i.i.d., bounded, and that the noise is independent of state/input. Independence is standard; boundedness is typical in robust control, though it is restrictive. I.i.d. inputs are common in finite-sample bounds, but restrictive for identification. Assumption c) assumes the switching to be independent of inputs/noise, realistic for external, but excludes state-dependent switching. Assumption d) ensures well-posed parameter estimation: $A_q, B_q, C$ are unique up to a coordinate change. Assumption e) implies quadratic stability, ensuring mean-square stability [3], similar to [19].

Assumption e) implies that i.i.d. $\mathbf{q}$ and $\mathbf{u}$ act as the persistence of excitation: once system matrices are identified (up to a basis change), the model is input-output equivalent to the true system for any input or switching sequence, similar to the standard principles in system identification.

Next, we recall from [4], [13], [19] the definition of Markov parameters and the covariance formula for them.

For any word $w \in Q^*$ define $A_w$ as the matrix product $A_w = A_{w_k} \cdots A_{w_1}$ if $w = w_1 \cdots w_k$, where $w_i \in Q$, $i = 1, \dots, k$, and let $A_\epsilon = I_n$. Define the Markov parameters $\{M_v\}_{v \in Q^*}$ of $\Sigma$ for any $i \in Q$ and $w \in Q^*$ as

$$M_{iw} = C A_w B_i, \quad M_{\epsilon} = D. \qquad (2)$$

It follows from realization theory of LSSs [13] that the Markov parameters $\{M_w\}_{w \in Q^*}$ determine the matrices $\{A_q, B_q\}_{q \in Q}$, $C$ up to a change of basis, due to minimality. In fact, there is a Ho-Kalman-like realization algorithm for computing the system matrices from the Markov parameters. In turn, the Markov parameters can be computed as covariances of the input and output as follows. For any vector valued, discrete-time stochastic process $\mathbf{h}$ define

$$\begin{aligned} \mathbf{z}_{w}^{\mathbf{h}}(t) &= \mathbf{h}(t-k)\chi_{w}(t-1) \\ \chi_{c}(t) &:= \begin{cases} 1 & \text{if } \mathbf{q}(t) = c \in Q \\ 0 & \text{otherwise} \end{cases} \end{aligned}$$

and $\chi_w(t) = \chi_{w_1}(t-k+1) \cdots \chi_{w_k}(t)$ for $Q^* \ni w = w_1 \cdots w_k, k > 1$, and set $\chi_\epsilon(t) = 1, \mathbf{z}_\epsilon^\mathbf{h}(t) = \mathbf{h}(t)$.

**Lemma 2.1:** Let $B'_q = [B_q | I_n | 0]$, and for all $v \in Q^*$, $M'_{qv} = C A_v B'_q$ and $M'_\epsilon = [D, 0] \in \mathbb{R}^{1 \times m+1}$, and $m' = m + n + 1$. Under Assumption 2.1 the followings hold:

a) $\exists \gamma \in (0, 1), K_M > 0$ such that $\|M'_w\|_2 < K_M \frac{\gamma^{|w|}}{n_Q^{|w|}}$.

b) There exist unique stationary state and output trajectories $\mathbf{x}$ and $\mathbf{y}$ which satisfy (1) and

$$\mathbf{x}(t) = \sum_{(v,q) \in Q^* \times Q} A_v B'_q \mathbf{z}_v^\mathbf{r}(t), \quad \mathbf{y}(t) = \sum_{v \in Q^*} M'_v \mathbf{z}_v^\mathbf{r}(t)$$

where the infinite sum converges in the mean square sense, and for all $w = w_1 \cdots w_k \in Q^*$

$$M_w = \mathbb{E}[\mathbf{y}(t)\mathbf{z}_w^\mathbf{u}(t)]^T \Sigma_u^{-1} p_w^{-1} \qquad (3)$$
where $p_{\epsilon} = 1$ and $p_w = \prod_{i=1}^{k} p_{w_i}$ for $w_i \in Q, k > 0$.

c) $y(t)$ is bounded, i.e. $|y(t)| < K_y := \frac{\sqrt{m'K_M K_u}}{1-\gamma}$.

The proof can be found in [17, Appendix A].

**Reduced basis Ho-Kalman algorithm.** An isomorphic copy of $\Sigma$ can be recovered from the Markov parameters using the reduced basis Ho-Kalman algorithm [4], [14], [15], which, unlike naive extensions of Ho-Kalman to LSSs, avoids any exponential growth of the Hankel-matrix.

Consider the sets $\alpha = \{\eta_1, \dots, \eta_n\} \subseteq Q^*$ and

$\beta = \{(\mu_1, q_1, l_1), \dots, (\mu_n, q_n, l_n)\} \subseteq Q^* \times Q \times \{1, \dots, m\}$, where $|\eta_i|, |\mu_i| \le n-1$ for $i=1, \dots, n$. These are called n-row and n-column selections, respectively. Intuitively, they represent a selection of rows and columns of the standard Hankel-matrix for LSSs [13], [19]. Thus we define the Hankel-matrix $H_{\alpha, \beta} \in \mathbb{R}^{n \times n}$ as

$$ (H_{\alpha, \beta})_{i,j} = M_{q_j \mu_j \eta_i} [l_j]. $$

**Lemma 2.2:** [2, Theorem 7]. There exists an n-row selection $\alpha$ and n-column selection $\beta$, such that $\text{rank}(H_{\alpha, \beta}) = n$.

We introduce the following matrices $H_{\alpha, q, \beta} \in \mathbb{R}^{n \times n}$, $H_{\alpha, q} \in \mathbb{R}^{n \times m}$, $H_{\beta} \in \mathbb{R}^{1 \times n}$, where

$$ (H_{\alpha, q, \beta})_{i,j} = M_{q_j \mu_j q_i} [l_j], \quad (H_{\alpha, q})_{i,j} = M_{\eta_i q} [l_j], $$

$$ (H_{\beta})_{1,j} = M_{q_j \mu_j} [l_j]. $$

The reduced basis Ho-Kalman algorithm computes $(\{\bar{A}_q, \bar{B}_q\}_{q \in Q}, \bar{C}, \bar{D})$ defined as $\bar{A}_q = H_{\alpha, \beta}^{-1} H_{\alpha, q, \beta}$, $\bar{B}_q = H_{\alpha, \beta}^{-1} H_{\alpha, q} \bar{C} = H_{\beta}$ and $\bar{D} = M_{\epsilon}$.

**Lemma 2.3:** [15, Lemma 4]. If $\text{rank}(H_{\alpha, \beta}) = n$, there exists $T \in \mathbb{R}^{n \times n}$ such that $\det(T) \neq 0$ and for all $q \in Q$ we have $\bar{A}_q = T A_q T^{-1}$, $\bar{B}_q = T B_q$, $\bar{C} = C_T^{-1}$.

By Lemma 2.3, the finite collection $\{M_w\}_{w \in W}$, with

$$ \mathcal{W} = \{ \nu_i q \mu_j q_j, \nu_i \mu_j q_j, \nu_i q, \mu_j q_j \}_{i,j=1}^n, \quad |\mathcal{W}| \le n^2(n_Q + 1) + n_Q nm + n \quad (4) $$

of Markov parameters determine all the Hankel matrices above, thus estimating the system matrices reduces to estimating $\{M_w\}_{w \in W}$. By (4) the realization algorithm above requires $O(n^2)$ Markov parameters, in contrast to the naive version [13], [19], which requires $O(n_Q^n)$. The trade-off is the need to find suitable n-selections, which takes $O(n_Q^n)$ steps, as there are $O(n_Q^n)$ choices. However, in learning, storage complexity is often more critical, than time complexity. The Markov parameters can be computed from the expectations in (3). Given $S_N = \{(y(t), u(t), q(t))\}_{t=0}^N$ a finite-sample path, we replace these expectations with their empirical counterparts. Substituting these estimates in the Ho-Kalman algorithm yields the empirical Ho-Kalman algorithm, as described in [4], [5], [14], [18].

Since we focus on the statistical properties of this algorithm, we interpret the estimated Markov parameters and system matrices as the following random variables.

**Empirical Markov parameters** are defined as

$$ \tilde{M}_w = \frac{1}{N - |w|} \sum_{t=|w|+1}^{N} \mathbf{y}(t) \mathbf{z}_w^{\mathbf{u}}(t) \Sigma_u^{-1} p_w^{-1}. \quad (5) $$

**Empirical Hankel matrices** $\tilde{H}_{\alpha, \beta}, \tilde{H}_{\alpha, q, \beta}, \tilde{H}_{\alpha, q}, \tilde{H}_{\beta}$ are constructed in the same way as $H_{\alpha, \beta}, H_{\alpha, q, \beta}, H_{\alpha, q}, H_{\beta}$ but by using $\tilde{M}_w$ instead of $M_w$.

**Estimates of the system matrices** are obtained as

$$ \hat{\mathbf{A}}_q = \hat{\mathbf{H}}_{\alpha, \beta}^{-1} \hat{\mathbf{H}}_{\alpha, q, \beta}, \quad \hat{\mathbf{B}}_q = \hat{\mathbf{H}}_{\alpha, \beta}^{-1} \hat{\mathbf{H}}_{\alpha, q}, \quad \hat{\mathbf{C}} = \hat{\mathbf{H}}_{\beta}. $$

If the training set $S_N$ corresponds to the random element $\omega \in \Omega$, i.e., $y(t) = \mathbf{y}(t)(\omega)$, $u(t) = \mathbf{u}(t)(\omega)$, $q(t) = \mathbf{q}(t)(\omega)$ for $t=0, \dots, N$, then $\tilde{M}_w(\omega)$ and $\{\hat{\mathbf{A}}_q(\omega), \hat{\mathbf{B}}_q(\omega)\}_{q \in Q}, \hat{\mathbf{C}}(\omega)$ represent the empirical estimates of the Markov parameters $M_w$, and the system matrices obtained from the empirical Ho-Kalman algorithm applied to $S_N$, respectively.

### III. MAIN RESULT

The main result of this paper is a finite-sample bound on the Frobenius norm distance between the outputs of the classical and empirical Ho-Kalman algorithms. We first bound the absolute difference between the true and empirical Markov parameters in the following Lemma.

**Lemma 3.1:** Under Assumption 2.1, if $N > 2(2n + 1)$

$$ \mathbb{P} \left[ \|M_w - \tilde{M}_w\|_F \le K(\delta, N) \right] > 1 - \delta \quad (6) $$

where $\tilde{K}(\delta, N) = K_0 \sqrt{8 \log \left( \frac{2m|\mathcal{W}|}{\delta} \right) / N}$,

$$ K_{-1} = \|\Sigma_u^{-1}\|_F / \min_{w \in W} p_w, \quad K(\delta, N) = \sqrt{m} K_{-1} \tilde{K}(\delta, N) $$

$$ K_0 = \frac{\sqrt{m'} K_u' K_M}{1 - \gamma} + K_\theta, \quad K'_u = \max\{K_u, K_u^2\} $$

$$ K_\theta = 2(m'K_u + n_Q)\sqrt{m'} K_u' K_M K_\gamma $$

$$ K_\gamma = \frac{\gamma + (2n+1)(n+2)(1-\gamma)^2 + (1-\gamma)^3}{(1-\gamma)^3} $$

Note that $|\mathcal{W}|$ can be upper bounded by (4). Additionally, if $p_* = \min_{q \in Q} p_q$ then $1/ \min_{w \in W} p_w \le 1/p_*^{2n+1}$.

**Proof:** Let us fix $\lambda > 0$, an index $l \in [1, m]$, and $w = w_1 \dots w_k$. Let $\tilde{\mathbf{M}}_w[l] = \frac{1}{N-l} \sum_{t=l+1}^{N} \mathbf{y}(t) \mathbf{z}_w^{\mathbf{u}[l]}(t)$ and $\tilde{\mathbf{M}}_w[l] = \mathbb{E}[\mathbf{y}(t) \mathbf{z}_w^{\mathbf{u}[l]}(t)]$. It is enough to show that

$$ \mathbb{P}[|\tilde{\mathbf{M}}_w[l] - \tilde{\mathbf{M}}_w[l]| > \tilde{K}(\delta, N)] \le \delta m^{-1} |\mathcal{W}|^{-1}. \quad (7) $$

The reason is that since $\|M_w - \tilde{M}_w\|_F^2 \le \|\tilde{M}_w - \tilde{\mathbf{M}}_w\|_F^2 \|\Sigma_u^{-1}\|_F^2$ and $\|\tilde{M}_w - \tilde{\mathbf{M}}_w\|_F^2 = \sum_{l=1}^m |\tilde{M}_w[l] - \tilde{\mathbf{M}}_w[l]|^2$, taking the union-bound [22, Lemma 2.2] over the set of indices $l$, and the sum, give $\mathbb{P}[\|\tilde{M}_w - \tilde{\mathbf{M}}_w\|_F > \sqrt{m} \tilde{K}(\delta, N)] \le \delta |\mathcal{W}|^{-1}$, then the union-bound over $\mathcal{W}$ and the complement rule yields the result of Lemma 3.1.

Thus, it is enough to show (7). To this end, for $\lambda > 0$, $\vartheta \in \{-1, 1\}$, the Chernoff-bound [22, Lemma B.3] leads to

$$ \mathbb{P}[\vartheta(\tilde{M}_w[l] - \tilde{\mathbf{M}}_w[l]) > K] \le \frac{\mathbb{E}[e^{\lambda \vartheta(\tilde{M}_w[l] - \tilde{\mathbf{M}}_w[l])}]}{e^{\lambda K}} = \Theta(\lambda) $$

Next, we wish to apply [1, Theorem 6.6] to the numerator.

**Theorem 3.2:** [1, Theorem 6.6] Let $\mathcal{X}$ be a Banach space with the norm $\|\cdot\|$ and let $\mathbf{Y} = \{\mathbf{Y}_t\}_{t \in \mathbb{Z}}$ be a bounded, stationary stochastic process such that $\|\mathbf{Y}_0\| < C_{\mathbf{Y}}$. Let $h: \mathcal{X}^\mathbb{Z} \to \mathbb{R}$ be a 1-Lipschitz function, i.e., $\forall \{x_t\}, \{y_t\} \in \mathcal{X}^N$ we have $|h(x_1, \dots, x_N) - h(y_1, \dots, y_N)| \le \sum_{i=1}^N \|x_i - y_i\|$.
Then, for any $\nu > 0$ we have

$$ \mathbb{E} \left[ e^{\nu \left[ \mathbb{E}[h(\mathbf{Y}_1, \dots, \mathbf{Y}_N)] - h(\mathbf{Y}_1, \dots, \mathbf{Y}_N) \right]} \right] \le e^{\frac{\nu^2 N (C_Y + \theta)^2}{2}}, $$

where $\theta$ is defined in [1, Chapter 3.1] as $\theta_{\infty,N}(1)$.

Let $h(x_1, \dots, x_N) = \sum_{t=|w|+1}^{N} x_t$, $\mathbf{X}_i = \vartheta \mathbf{y}(i) \mathbf{z}_w^{u[l]}(i)$ and $\mathcal{X} = \mathbb{R}$. It is clear that $h$ is 1-Lipschitz and $\vartheta \widehat{\mathbf{M}}_w[l] = (N - |w|)^{-1}h(\mathbf{X}_1, \dots, \mathbf{X}_N)$, and $\mathbb{E}[\widehat{\mathbf{M}}_w[l]] = \widehat{M}_w[l]$. By Lemma 2.1, $\{\mathbf{y}(t), \mathbf{u}(t), \mathbf{q}(t)\}$ is jointly stationary and bounded, and hence $\{\mathbf{X}_i\}_{i \in \mathcal{Z}}$ is a stationary bounded process with $\|\mathbf{X}_0\|_2 \le K_y K_u \le \frac{\sqrt{m'K_u'K_M}}{1-\gamma}$. Moreover, the coefficient $\theta$ from Theorem 3.2 is finite for $\{\mathbf{X}_i\}_{i \in \mathcal{Z}}$.

**Lemma 3.3:** For $K_\theta$ from Lemma 3.1 we have $\theta \le K_\theta$.

The proof is in Section V. Therefore $\{\mathbf{X}_i\}$ satisfies the conditions of Theorem 3.2, hence we can apply it with $\nu = \lambda(N - |w|)^{-1}$ to $\{\mathbf{X}_i\}$ with $K_u K_y + \theta \le K_0$, yielding

$$ \mathbb{E}[e^{\vartheta \lambda (\widetilde{M}_w[l] - \widetilde{\mathbf{M}}_w[l])}] \le e^{\frac{\lambda^2 N}{2(N-|w|)^2} K_0^2}. $$

Hence, $\Theta(\lambda) \le e^{\frac{\lambda^2 N}{2(N-|w|)^2} K_0^2 - \lambda K} =: e^{F(\lambda)}$. It follows the minimal value $F(\lambda_*)$ of $F$ is $-\frac{K^2(N-|w|)}{2N K_0^2}$ and it is achieved at $\lambda_* = (KK_0^2(N-|w|)^2)/N$, implying $\Theta(\lambda_*) \le F(\lambda_*)$. By using $N > 2(2n+1) \ge 2|w|$ and choosing $K = \tilde{K}(\delta, N)$ it follows that $F(\lambda_*) \le 0.5|W|^{-1}m^{-1}$.

As a result, $\mathbb{P}[\vartheta(\widetilde{M}_w[l] - \widetilde{\mathbf{M}}_w[l]) > \tilde{K}(\delta, N)] \le \Theta(\lambda_*)$

$\le 0.5\delta|W|^{-1}m^{-1}$. Since $|\widetilde{M}_w[l] - \widetilde{\mathbf{M}}_w[l]| < K$ is equivalent to $\forall \vartheta \in \{1, -1\}: \vartheta(\widetilde{M}_w[l] - \widetilde{\mathbf{M}}_w[l]) < K$, hence (7) follows using the union bound.

The next lemma establishes the sensitivity of the Hankel-matrices in the Ho-Kalman algorithm to perturbations of Markov-parameters. ■

Lemma 3.4: Let $n_* = \max\{n, m\}$ and $K_{-1}$ from Lemma 3.1. For any collection of $1 \times m$ matrices $\{\widetilde{M}_w\}_{w \in W}$, and any pair of matrices $(H, \hat{H}) = (H_\kappa, \hat{H}_\kappa)$, on condition that $\kappa \in \mathcal{K} = \{(\alpha, \beta)\} \cup \{\beta\} \cup \{(\alpha, q, \beta), (\alpha, q)\}_{q \in \mathcal{Q}}$, where $\hat{H}_\kappa$ is defined as $H_\kappa$ but with $M_w$ replaced by $\widetilde{M}_w$:

$$ \|H\|_F \le n_* K_{-1} K_y K_u \quad \text{and} \quad \|\hat{H}^{-1}\|_F \le \frac{2}{\sigma_n(H)}, \quad (8) $$

$$ \|\hat{H} - H\|_F \le \sqrt{\sum_{w \in W} \|M_w - \hat{M}_w\|_F^2} \quad (9) $$

If $\forall w \in W: \|M_w - \hat{M}_w\|_F < \frac{\sigma_n(H)}{2|W|} \sqrt{n}$, then

$$ \|\hat{H}^{-1} - H^{-1}\|_F \le \frac{4\sqrt{2}}{\sigma_n^2(H)} \sqrt{\sum_{w \in W} \|M_w - \hat{M}_w\|_F^2} \quad (10) $$

The proof is in Section V. By using the fact that the matrices returned by the Ho-Kalman algorithms are obtained by arithmetic operations from the Hankel matrices, Lemma 3.1 and Lemma 3.4, we obtain the following Theorem.

**Theorem 3.5 (Main result):** Under Assumption 2.1, if $K(\delta, N)$, $K_{-1}$ as in Lemma 3.1, $n_*$ as in Lemma 3.4, $K_y, K_u$ from Lemma 2.1 and Assumption 2.1, and $N$ large enough for $N > 2(2n+1)$ and $K(\delta, N) \le \frac{\sigma_n(H_{\alpha, \beta})}{2|W|} \sqrt{n}$, then

$$ \text{EstErr} = \max_{q \in Q} \{ \|\hat{\mathbf{A}}_q - \bar{A}_q\|_F, \|\hat{\mathbf{B}}_q - \bar{B}_q\|_F, \|\hat{\mathbf{C}} - \bar{C}\|_F \} $$

$$ \mathbb{P}[\text{EstErr} < K_2 K(\delta, N)] > 1 - \delta \quad (11) $$

$$ K_2 = \sqrt{|W|} \max \left\{ 1, \frac{2\sigma_n(H_{\alpha,\beta}) + n_* K_{-1} K_y K_u 4\sqrt{2}}{\sigma_n^2(H_{\alpha,\beta})} \right\} $$

*Proof:* The existence of $N$ is guaranteed by Lemma 3.1 and that $K(\delta, N)$ is strictly decreasing in $N$.

First we prove (11) for $A_q$. For a fixed $\alpha, \beta$ and $q \in Q$ let $H_1 = H_{\alpha, \beta}$, $H_2 = H_{\alpha, q, \beta}$, $\hat{H}_1 = \hat{H}_{\alpha, \beta}$ and $\hat{H}_2 = \hat{H}_{\alpha, q, \beta}$. Due to the definitions and Lemma 3.4, for $\zeta = \sigma_n(H_1)$

$$ \begin{aligned} \|\hat{\mathbf{A}}_q - \bar{A}_q\|_F &= \|\hat{\mathbf{H}}_1^{-1} \hat{\mathbf{H}}_2 - H_1^{-1} H_2\|_F \\ &\le \|\hat{\mathbf{H}}_1^{-1}\|_F \|\hat{\mathbf{H}}_2 - H_2\|_F + \|H_2\|_F \|\hat{\mathbf{H}}_1^{-1} - H_1^{-1}\|_F \\ &\le K_2 \sqrt{\sum_{w \in W} \|M_w - \hat{M}_w\|_F^2} \end{aligned} $$

Therefore by Lemma 3.1 and basic properties of probability,

$$ \begin{aligned} \mathbb{P}[\|\hat{\mathbf{A}}_q - \bar{A}_q\|_F < K_2 K(\delta, N)] \\ \ge \mathbb{P}[\|M_w - \hat{M}_w\|_F < K(\delta, N)] > 1 - \delta \end{aligned} $$

For $B_q$ it is the same proof with $H_2 = H_{\alpha, q}$. For $C$ we have $\|\hat{\mathbf{C}} - \bar{C}\|_F^2 = \|\hat{\mathbf{H}}_\beta - H_\beta\|_F^2 \le \sum_{w \in W} \|M_w - \hat{M}_w\|_F^2$ which is due to Lemma 3.4. ■

**Discussion.** The term $K_2 K(\delta, N)$ is $O(\sqrt{\log(1/\delta)/N})$, since $K_2$ is independent of $N$, matching standard PAC bounds [1], [22]. Thus, as $N \to \infty$, the estimation error vanishes with probability $1 - \delta$, ensuring statistical consistency. The constant $K_0$ in $K(\delta, N)$ is $O((1 - \gamma)^{-3})$, due to $K_\theta$ being $O((1 - \gamma)^{-3})$, therefore higher degree of stability (smaller $\gamma$) yields smaller estimation error of Markov parameters. The term $K_\theta$ upper bounds a mixing coefficient. The bound is inversely proportional to the input covariance, which is consistent with persistence of excitation. Moreover, as $K(\delta, N) = O(p_*^{-2(2n+1)}N^{-1/2})$, for fixed $N$, small $p_*$ both inflates the bound and means too few samples visit the mode $q_*$ (as $\mathbb{P}(q(t) = q_*) = p_*$), so no algorithm can learn the system reliably. Allowing $N$ to grow arbitrarily large compensates for any small $p_*$, ensuring Ho-Kalman succeeds once enough visits to $q_*$ are collected.

Finally, $K_2$ and $K_0$ increase polynomially in the number of states, discrete modes, and bounds on the input noise. The condition $K(\delta, N) < \frac{\sigma_n(H_{\alpha, \beta})}{\sqrt{n}|W|}$ ensures the estimated Hankel matrix $\hat{H}_{\alpha, \beta}$ is invertible with high probability, enabling the Ho-Kalman algorithm, and it holds if $N = \Omega(n^5\sigma_n^{-1}(H_{\alpha, \beta}))$. In summary, the bound exhibits expected behavior: increasing input variance, stability, and choosing good $\alpha$ and $\beta$ reduce sample complexity, while larger model size increases it. Numerical experiments confirm the above discussion about the behavior of the estimation error, see [17, Appendix C].

**Comparison with related results.** Our bound aligns with [19], for bounded inputs/noises, but we use a single time series with bounded signals and known system order. In contrast, [19] does not assume system order knowledge, relying on $M$ independent time series and exponentially large Hankel matrices; their bound is $O(1/\sqrt{M})$. Our bound is stronger than [7], as it depends on $\log(1/\delta)$ rather than $1/\delta$.

When applied to LTI systems ($n_Q = 1$), our results yield a $O(1/\sqrt{N})$ bound, consistent with existing literature. Unlike
prior work, we do not require a stability dependent a lower bound on the number of Markov parameters, but we estimate at most $2n + 1$ Markov parameters independently of the degree of stability. This is achieved through a different proof technique that avoids linear regression and handling sub-Gaussian matrices. In fact, applying LTI methods to LSSs raises challenges, such as difficulties in establishing the sub-Gaussianity of the regressor due to switching, and exponentially large matrices when estimating $n_Q^T$ Markov parameters. Note, that identifying LSSs in general cannot be achieved by parallel LTI identification of its subsystems, see Example 2 in [16]. In contrast to [10], we assume that the switching is observed, which allows us to use the Ho-Kalman algorithm, for details see [17, Appendix D].

## IV. CONCLUSIONS AND FUTURE WORK

We have presented a finite-sample $O(1/\sqrt{N})$ error bound for an identification algorithm for LSS which uses a single time series of length $N$. The bound exhibits the standard properties of finite-sample bounds. The proof is based on concentration inequalities for weakly dependent processes. Future work is directed towards extending the results to more general switching scenarios and non i.i.d. unbounded inputs.

## V. REMAINING PROOFS

**Proof of Lemma 3.4.** The first equation of (8) follows from Assumption 2.1 and equation (3), while the second one follows from the proof of (10). (9) follows from the definition of the Frobenius norm. As for (10), by [11, Theorem 1.1]
$$ \|\hat{H}^{-1} - H^{-1}\|_F \le \sqrt{2} \max\{\|\hat{H}^{-1}\|_2^2, \|H^{-1}\|_2^2\} \|\hat{H} - H\|_F $$
From [8, (5.3.9), page 265] follows that $\|\hat{H}^{-1}\|_2 \le \frac{1}{\sigma_n(\hat{H})}$ and $\|H\|_2^{-1} \le \frac{1}{\sigma_n(H)}$. From [8, Corollary 8.6.2] it follows that $|\sigma_n(\hat{H}) - \sigma_n(H)| \le \|\hat{H} - H\|_2 \le \sqrt{n}\|\hat{H} - H\|_F \le \sqrt{n} \sum_{w \in W} \|M_w - \hat{M}_w\|_F^2$. That is, if for all $w \in W$:
$$ \begin{aligned} & \|M_w - \hat{M}_w\|_F < \frac{0.5\sigma_n(H)}{|W|^{1/\sqrt{n}}} \text{, then } |\sigma_n(\hat{H}) - \sigma_n(H)| \\ & \le 0.5\sigma_n(H) \text{ and hence } \sigma_n(\hat{H}) \ge 0.5\sigma_n(H), \text{ thus } \|\hat{H}^{-1} - H^{-1}\|_F \le \frac{\sqrt{2}}{0.25\sigma_n^2(H)} \|\hat{H} - H\|_F. \end{aligned} $$

**Proof of Lemma 3.3.** We show that $\{X_t\}_{t \in \mathbb{Z}}$ is a Causal Bernoulli Shift [1, Section 3.1.4]. Let $\mathcal{X} = \mathbb{R}^{m'+n_Q}$ viewed as a Banach space with norm $\|\cdot\|_1$. Let $H: \mathcal{X}^N \to \mathbb{R}$ such that there exist real numbers $\{a_j\}_{j=0}^\infty$ with the property that for any $v = \{v_j\}_{j=0}^\infty$, $v' = \{v'_j\}_{j=0}^\infty$, $v_j, v'_j \in \mathcal{X}$,

$$ |H(v) - H(v')| \le \sum_{j=0}^{\infty} a_j |v_j - v'_j|_1, \quad \sum_{j=0}^{\infty} j a_j < \infty \quad (12) $$

Then $X_t$ is a CBS, if for all $t \in \mathbb{Z}$, $X_t = H(\xi_t, \xi_{t-1}, \dots)$, where $\xi_t$ are i.i.d. Note, that for a fixed $l \in [1, m]$

$$ X_i = y(i)z_w^{u[l]}(i) = \sum_{v \in Q^*} M'_v z_v^{\mathbf{r}}(i) z_w^{u[l]}(i) $$

We omit the dependence of $X_i$ on $w$ and $i$ from the notation for simplicity. Let $\xi(t) = [\mathbf{r}^T(t), \chi_1(t), \dots, \chi_{n_Q}(t)]^T \in \mathbb{R}^{m'+n_Q}$. Let $\Xi = \{\xi_t\}_{t \in \mathbb{N}} \in (\mathbb{R}^{m'+n_Q})^N$ and for all $v \in Q^*$

$$ g_v(\Xi) = g'_v(\Xi) \prod_{i=1}^{|v|} \mathrm{sat}_{0,1}(\xi_{|v|-i+1}[v_i + m']) $$

where $g'_v(\Xi) = \mathrm{sat}_{K_u}(\xi_{|v|}[1 : m'])$ for $v \ne w$ and $\mathrm{sat}_{K_u}(\xi_{|v|}[l])$ otherwise. If $|v| > 0$ and $g_e(\Xi) = \mathrm{sat}_K(\xi_0[1 : m'])$, where $\mathrm{sat}_{a,b}(x) = \min\{\max\{x, a\}, b\}$ for $x \in \mathbb{R}$, $\mathrm{sat}_{a,b}(v)[i] = \mathrm{sat}_{a,b}(v[i])$ for any vector $v$ and $\mathrm{sat}_a(x) = \mathrm{sat}_{-a,a}(x)$. Then $\mathbf{X}_i = \sum_{v \in Q^*} M'_v g_v(\Xi) g_w(\Xi) =: H^w(\Xi)$ for $\Xi = \{\xi(t)\}_{t \in \mathbb{N}}$, where $H^w$ is defined as

$$ H^w(\Xi) = \sum_{v \in Q^*} M'_v g_v(\Xi) g_w(\Xi) \quad (13) $$

We show that $H^w$ satisfy (12) for a suitable $L_j$.

**Lemma 5.1:** Let $Q^+ = Q^* \setminus \{\epsilon\}$, $K_{\ge j} = \sum_{|v| \ge j} \|M'_v\|_2$, $K_\infty = \sum_{v \in Q^*} \|M'_v\|_2$ and $K_j = K_u K_M$ if $j = 0$, and for $j \ge 1$: $K_j = \sqrt{m'} K'_u K_{\ge j}$. Let **1** be the indicator function, $L_j = K_j + \sqrt{m'} K_u \mathbf{1}_{\{j \le |w|\}} (K_\infty + (K_\infty + K_M) \mathbf{1}_{\{j = |w|\}})$. Then (13) is absolutely convergent, $K_\infty \le \frac{K_M}{1-\gamma}$, and the process $\mathbf{X}_i$ is a CBS with $H = H^w$ and $a_j = L_j$.

**Proof:** Without loss of generality, we can assume that $q_1 \dots q_k = w = q'_1 \dots q'_k$. Note that for any $\Xi \in (\mathbb{R}^{m'+n_Q})^N$ and $s \in Q^* \|g_s(\Xi)\|_\infty \le K_u$, hence $\|M'_v g_v(\Xi) g_w(\Xi)\| \le \sqrt{m'} \|M'_v\|_2 K_u^2$. From Lemma 2.1 it follows that $\|M'_v\|_2 \le K_M \frac{\lambda|v|}{n_Q^{|v|}}$, implying that (13) can be upper bounded by a convergent geometric series, thus it is convergent.

**Step 1: First part of (12).** For $\Xi, \Xi' \in (\mathbb{R}^{m'+n_Q})^N$ we can upper bound $|H^w(\Xi) - H^w(\Xi')|$ by

$$ \sum_{v \in Q^*} \|M'_v\|_2 \|g_v(\Xi)g_w(\Xi) - g_v(\Xi')g_w(\Xi')\|_2 $$

For the sake of readibility, let

$$ \begin{aligned} \Gamma^{v,w}(\Xi, \Xi') &= g_v(\Xi)g_w(\Xi) - g_v(\Xi')g_w(\Xi') \\ \chi'_c(j) &:= \mathrm{sat}_{0,1}(\xi'_j[c + m']), \quad \chi_c(j) := \mathrm{sat}_{0,1}(\xi_j[c + m']) \end{aligned} $$

$$ \chi'_v = \prod_{i=1}^{k} \chi'_{v_i}(k-i), \quad \chi_v = \prod_{i=1}^{k} \chi_{v_i}(k-i) $$

for any $v = v_1 \dots v_k \in Q^+$, $v_i \in Q$, $i \in [1, k]$.

Let $\bar{u}_k = \mathrm{sat}_{K_u}(\xi_k[1 : m'])$, $\bar{u}'_k = \mathrm{sat}_{K_u}(\xi'_k[1 : m'])$, $s = \mathrm{sat}_{K_u}(\xi_{|v|}[l])$ and $s' = \mathrm{sat}_{K_u}(\xi'_{|v|}[l])$ for all $k$. Then

$$ \|\Gamma^{v,w}(\Xi, \Xi')\|_2 = \|\bar{u}_{|v|} s \chi_v \chi_w - \bar{u}'_{|v|} s' \chi'_v \chi'_w\|_2 $$

This yields to

$$ \begin{aligned} \|\Gamma^{v,w}(\Xi, \Xi')\|_2 &\le \|\bar{u}_{|v|} s \chi_v \chi_w - \bar{u}'_{|v|} s' \chi_v \chi_w\|_2 \\ &\quad + \|\bar{u}'_{|v|} s' \chi_v \chi_w - \bar{u}'_{|v|} s' \chi'_v \chi'_w\|_2 \end{aligned} $$

Now $\|\mathrm{sat}_{K_u}(x)\|_2 \le \sqrt{m'} K_u$ and $\|\mathrm{sat}_{0,1}(x)\|_2 \le \sqrt{m'}$. As $|\chi_v \chi_w| \le 1$ and $\max\{\|\bar{u}_k\|_2, \|\bar{u}'_k\|_2\} \le \sqrt{m'} K_u$, thus

$$ \begin{aligned} & \|\bar{u}_{|v|} s \chi_v \chi_w - \bar{u}'_{|v|} s' \chi_v \chi_w\|_2 \\ & \le K_u \|\bar{u}_{|v|} - \bar{u}'_{|v|}\|_1 + \sqrt{m'} K_u |s - s'| \end{aligned} $$

Moreover, notice that

$$ \begin{aligned} & \|\bar{u}'_{|v|} s' \chi_v \chi_w - \bar{u}'_{|v|} s' \chi'_v \chi'_w\|_2 \le \|\bar{u}'_{|v|} s'\|_2 |\chi_v \chi_w - \chi'_v \chi'_w| \\ & \le \sqrt{m'} K_u^2 (|\chi_v - \chi'_v| + |\chi_w - \chi'_w|) \le \sqrt{m'} K_u^2 \cdot ( \\ & \quad \sum_{j=1}^{|v|} \sum_{c \in Q} |\chi_c(j) - \chi'_c(j)| + \sum_{j=1}^{|w|} \sum_{c \in Q} |\chi_c(j) - \chi'_c(j)|) \end{aligned} $$

As $\|\bar{u}_k - \bar{u}'_k\|_1 \le \|u_k - u'_k\|_1 = \|\xi_k[1 : m'] - \xi'_k[1 : m']\|_1$,
$|\chi_c(j) - \chi'_c(j)| \le |\xi_j[c + m'] - \xi'_j[c + m']|$ for all
$1 \le j \le |v| + |w|$, because $\text{sat}_{a,b}$ is 1-Lipschitz, implying

$$
\begin{aligned}
\|\Gamma^{v,w}(\Xi, \Xi')\|_2 &\le K_u \|\xi_{|v|}[1 : m'] - \xi'_{|v|}[1 : m']\|_2 \\
&\quad + \sqrt{m'} K_u |\xi_{|w|}[l] - \xi'_{|w|}[l]| \\
&\quad + \sqrt{m'} K_u^2 \sum_{\substack{j=1 \\ \max\{|v|,|w|\}}} c_j \sum_{c \in Q} |\xi_j[c + m'] - \xi'_{j}[c + m']|
\end{aligned}
$$

where $c_j = 2$ for $j \le |w|$ and $c_j = 1$ for $j > |w|$. Note that

$$
\begin{aligned}
\|\Gamma^{\epsilon,w}(\Xi, \Xi')\|_2 &\le K_u \|\xi_0[1:m'] - \xi'_0[1:m']\|_2 \\
&\quad + \sqrt{m'} K_u |\xi_{|w|}[l] - \xi'_{|w|}[l]|
\end{aligned}
$$

We have

$$
|H^w(\Xi) - H^w(\Xi')| \le \sum_{v \in Q^*} \|M_v'\|_2 \|\Gamma^{v,w}(\Xi, \Xi')\|_2
$$

$$
\begin{aligned}
&\le \sum_{j=1}^{\infty} \left[ \left( \|\xi_j[1:m'] - \xi'_j[1:m']\|_2 K_u \sum_{|v|=j} \|M_v'\|_2 \right. \right. \\
&\qquad \left. \left. + K_u \sum_{c \in Q} |\chi_c(j) - \chi'_c(j)| \right) (\sqrt{m'} K_u (\sum_{|v| \ge j} \|M_v'\|_2 \right. \\
&\qquad \left. + \chi(j \le |w|) \sum_{v \in Q^+} \|M_v'\|_2) \right] \\
&\qquad + |\xi_{|w|}[l] - \xi'_{|w|}[l]| \sqrt{m'} K_u \left( \|M_\epsilon'\|_2 + \sum_{v \in Q^+} \|M_v'\|_2 \right)
\end{aligned}
$$

By using that by Lemma 2.1 $\|M'_{\epsilon}\|_2 \le K_M$ and the definition of $L_j$ and by $\|\cdot\|_2 \le \|\cdot\|_1$ we have $|H^w(\Xi) - H^w(\Xi')| \le \sum_{j=0}^{\infty} L_j \|\xi_j - \xi'_{j}\|_1$.

**Step 2: Second part of (12).** Note, that $K_{\ge j} \le K_{\infty}$ and

$$
K_{\infty} = \sum_{j=0}^{\infty} \sum_{|v|=j} \|M_v'\|_2 \le \sum_{j=0}^{\infty} K_M n_Q^j \frac{\gamma^j}{n_Q^k} = \frac{K_M}{1-\gamma}
$$

by Lemma 2.1. As for the second equation in (12),

$$
\begin{aligned}
\sum_{j=0}^{\infty} j L_j &= \sum_{j=1}^{\infty} \left[ j \sqrt{m'} K_u \sum_{|v| \ge j} \|M_v'\|_2 \right. \\
&\qquad \left. + \sqrt{m'} K_u \left( \sum_{j=1}^{|w|} j K_\infty + |w|(K_\infty + K_M) \right) \right] \quad (14)
\end{aligned}
$$

Again, due to Lemma 2.1 and the definition of $K_{\ge j}$,

$$
\sum_{j=1}^{\infty} j K_{\ge j} \le \sum_{j=1}^{\infty} j K_M \sum_{k=j}^{\infty} n_Q^k \frac{\gamma^k}{n_Q^k} = \frac{K_M \gamma}{(1-\gamma)^3} \quad (15)
$$

**Proof:** [Proof of Lemma 3.3] From [1, Proposition 4.2] it follows that for a CBS, if $\|\xi_0\|_1 \le b$, then $\theta_{\infty,N}(1) \le 2b \sum_{j=0}^{\infty} ja_j$. From the proof of Lemma 5.1 we have that $\|\xi_0\|_1 \le m'K_u + n_Q$. Then the statement follows from (14) and (15) and the definition of $K_\theta$, and using $|w| \le 2n + 1$ due to the definition of $W$.

REFERENCES

[1] P. Alquier and O. Wintenberger. Model selection for weakly dependent time series forecasting. Bernoulli, 18(3):883 – 913, 2012.

[2] M. Bastug, M. Petreczky, R. Wisniewski, and J. Leth. Model reduction by nice selections for linear switched systems. IEEE Trans. Autom. Control, 61:3422–3437, 2016.

[3] O.L.V. Costa, M.D. Fragoso, and R.P. Marques. Discrete-Time Markov Jump Linear Systems. London, UK: Springer Verlag, 2005.

[4] P. B. Cox, M. Petreczky, and R. Tóth. Towards efficient maximum likelihood estimation of LPV-SS models. Automatica, 97(9):392–403, 2018.

[5] P. B. Cox and R. Tóth. Linear parameter-varying subspace identification: A unified framework. Automatica, 123:109296, 2021.

[6] D. Eringis, J. Leth, Z-H. Tan, R. Wisniewski, and M. Petreczky. Pac- bayes generalisation bounds for dynamical systems including stable rns. In AAAI, volume 38, pages 11901–11909, 2024.

[7] D. Eringis, J. Leth, Zh.-H. Tan, R. Wisniewski, and M. Petreczky. Pac- bayesian error bound, via rényi divergence, for a class of linear time- invariant state-space models. In ICML, pages 12560–12587. PMLR, 2024.

[8] G.H. Golub and C.F. Van Loan. Matrix Computations. Baltimore, MD, USA: The Johns Hopkins Univ. Press, 2013.

[9] F. Lauer and G. Bloch. *Hybrid System Identification: Theory and Algorithms for Learning Switching Models*. Cham, Switzerland: Springer Nature, 2019.

[10] L. Massucci, F. Lauer, and M. Gilson. Regularized switched system identification: a statistical learning perspective. IFAC-PapersOnLine, 54(5):55–60, 2021.

[11] L. Meng and B. Zheng. The optimal perturbation bounds of the moore–penrose inverse under the frobenius norm. Linear Algebra and its Appl., 432(4):956–963, 2010.

[12] S. Oymak and N. Ozay. Revisiting ho–kalman-based system identi- fication: Robustness and finite-sample analysis. IEEE Trans. Autom. Control, 67(4):1914–1928, 2022.

[13] M. Petreczky. Realization theory of linear hybrid systems. In Hybrid Dynamical Systems: Observation and control, pages 59–101. Cham, Switzerland: Springer International, 2015.

[14] M. Petreczky and L. Bako. On the notion of persistence of excitation for linear switched systems. Nonlinear Anal.: Hybrid Syst., 48:101308, 2023.

[15] M. Petreczky and R. Peeters. Spaces of nonlinear and hybrid systems representable by recognizable formal power series. In MTNS, volume 5, 2010.

[16] Mihály Petreczky, Laurent Bako, and Jan H van Schuppen. Identifiability of discrete-time linear switched systems. In Proceedings of the 13th ACM international conference on hybrid systems: Computation and control, pages 141–150, 2010.

[17] Dániel Rácz, Mihály Petreczky, and Bálint Daróczy. A finite-sample bound for identifying partially observed linear switched systems from a single trajectory. arXiv preprint arXiv:2503.13766, 2025.

[18] E. Rouphael, M. Mejari, M. Petreczky, and L. Belkoura. Minimal covariance realization and system identification algorithm for a class of stochastic linear switched systems with i.i.d. switching. In IEEE CDC, pages 6355–6362, 2024.

[19] T. Sarkar, A. Rakhlin, and M. Dahleh. Nonparametric system identi- fication of stochastic switched linear systems. In IEEE CDC, pages 3623–3628, 2019.

[20] Y. Sattar, Y. Jedra, M. Fazel, and S. Dean. Finite sample identification of partially observed bilinear dynamical systems, 2025. arxiv:2501.07652.

[21] B. Sayedana, M. Afshari, P. E Caines, and A. Mahajan. Strong consistency and rate of convergence of switched least squares system identification for autonomous markov jump linear systems. IEEE Trans. Autom. Control, 69(6):3952–3959, 2024.

[22] S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge, UK: Cambridge Univ. Press, 2014.

[23] S. Shi, O. Mazhar, and B. De Schutter. Finite-sample analysis of identification of switched linear systems with arbitrary or restricted switching. IEEE Control Syst. Lett., 7:121–126, 2022.

[24] M. Simchowitz, H. Mania, S. Tu, M. I. Jordan, and B. Recht. Learning without mixing: Towards a sharp analysis of linear system identification. In COLT, pages 439–473. PMLR, 2018.

[25] R. Tóth. Modeling and identification of linear parameter-varying systems. Heidelberg, Germany: Springer Berlin, 2010.

[26] A. Tsiamis, I. Ziemann, N. Matni, and G. J. Pappas. Statistical learning theory for control: A finite-sample perspective. IEEE Control Syst. Mag., 43(6):67–97, 2023.

[27] I. M. Ziemann, H. Sandberg, and N. Matni. Single trajectory nonpara- metric learning of nonlinear dynamics. In COLT, pages 3333–3364. PMLR, 2022.