2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ofer zeitouni Jan 13 '18 at 15:36
  • $\begingroup$ 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? $\endgroup$ – Robert Jan 14 '18 at 9:57
  • $\begingroup$ both numerator and denominator concentrate.... $\endgroup$ – ofer zeitouni Jan 14 '18 at 12:36
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.