# Concentration of emperical conditional probability

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$.

• You need some assumptions, such as irreducibility. Assuming that, you converge exponentially in $n$. This follows e.g. from the Large Deviations for the empirical measure and the pair empirical measure. – ofer zeitouni Jan 13 '18 at 15:36
• Yeah, I forgot to mention the irreduciblity. Pair empirical measure is more concerned with joint probability of $x_{i-1}$ and $x_i$ (I am not sure though), for which we can directly use Glynn'02. My question is how to extend it for the conditional probability? – Robert Jan 14 '18 at 9:57
• both numerator and denominator concentrate.... – ofer zeitouni Jan 14 '18 at 12:36

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)$.