Assume sequence $(X_1,X_2, X_3, \ldots)$ is a first-order Markov sequence of real random variables where $X_i \in \mathcal{X}$ for some alphabet $\mathcal{X}$ of finite size $k$. Define emperical conditional probability $p_{X_i| X_{i-1}}(x_{i}|x_{i-1})$ after $n$ samples as $$\hat{p}_{X_{i}|X_{i-1}}(x_{i}|x_{i-1}) = \frac{\sum_{i=2}^{n}\mathbb{I}\{X_{i-1} = x_{i-1} , X_i = x_i\} }{\sum_{i=2}^{n}\mathbb{I}\{X_{i-1} = x_{i-1}\}}.$$ for some $\{x_{i-1},x_i\} \in \mathcal{X}$ and $i >1$ and indicattor function $\mathbb{I}\{\cdot\}$, and the true probability as $p_{X_{i}|X_{i-1}}(x_{i}|x_{i-1})$.

Is there any Hoeffding-type inequality to show concentration rate of $\hat{p}_{X_i |X_{i-1}}(x_i|x_{i-1})$ around $p_{X_{i}|X_{i-1}}(x_i|x_{i-1})$, given that the underlying Markov process is irreducible.

**Possible start:** For the joint probability, $p_{X_{i},X_{i-1}}(x_i,x_{i-1})$, we can define $Y_i = (X_{i-1},X_i)$ for $i > 1$. Then, since $Y_2, Y_3, \ldots$ is Markov, we may use Theorem 2 of Glynn'02 for $Y$.