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](https://www.google.se/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwjR3fitmNDYAhXC_iwKHaI9AfkQFggpMAA&url=https%3A%2F%2Fweb.stanford.edu%2F~glynn%2Fpapers%2F2002%2FGOrmoneit02.pdf&usg=AOvVaw0PbgpKi4yOyp0ws-ftgzUC) for $Y$.



Concentration of emperical conditional probability
A simple answer is the minimum convergence rate of the nominator and the denominator, to their respective true probabilities. 


If you consider $\frac{a\_n}{b\_n}$ where $a\_n \to a$ and $b\_n \to b$ with some convergence rates $f\_1(n)$ and $f\_2(n)$,then for sufficiently large $n$ (at which $|b\_n - b|\leq \epsilon$), $\frac{a\_n}{b\_n} \to \frac{a}{b}$ at rate $f\_1(n) + f\_2(n)$. 


