I am trying to calculate analytically the optimal decision rule for a simple discrete markov chain, following standard decision theory framework (slide 17 in http://www.cse.buffalo.edu/~jcorso/t/CSE555/files/lecture_bayesiandecision.pdf).
suppose we have a Markov chain:
$X_1 \rightarrow X_2 \rightarrow X_3 \rightarrow ... \rightarrow X_{t} \rightarrow ...$
where each random variable is Bernoulli with two values $X_t \in {x_1, x_2}$ and the transition probabilities are:
transition from $x_1$ to $x_1$: $P(X_t = x_1 \mid X_{t-1} = x_1) = \theta_{11}$
transition from $x_2$ to $x_1$: $P(X_t = x_1 \mid X_{t-1} = x_2) = \theta_{21}$
(transition from $x_1$ to $x_2$ is just $1-\theta_{11}$ and similarly for $x_2$ to $x_2$)
assume we make a decision at $X_t$ about what the value of $X_t$ will be, given $X_{t-1}$. there are (fixed) costs associated with each decision. what is the optimal decision rule to maximize our utility, or minimize cost?
the costs for the decision at $X_t$ are:
- predicting $x_1$ correctly: $\lambda_{11}$
- predicting $x_1$ when $X_t = x_2$: $\lambda_{12}$
- predicting $x_2$ correctly: $\lambda_{22}$
- predicting $x_2$ when $X_t = x_1$: $\lambda_{21}$
we want the action $\alpha$ that minimizes the expected conditional cost, or maximizes the negative conditional cost given the data $X_{t-1}$:
$\arg\max_{\alpha}-C(\alpha\mid X_{t-1})$
what is the right way to calculate this?
there are two cases: $X_{t-1} = x_{1}$ and $X_{t-1} = x_{2}$. how do you write this formally to derive the best decision $\alpha$ as a function of the transition probabilities and costs?
We have:
\begin{align} C(1\mid X_{t-1}=1) &= \theta_{11}\lambda_{11}\\ C(2\mid X_{t-1}=1) &= (1-\theta_{11})\lambda_{21}\\ C(1\mid X_{t-1}=2) &= (1-\theta_{21})\lambda_{12} \\ C(2\mid X_{t-1}=2) &= \theta_{21}\lambda_{22},\\ \end{align} so the optimal policy $\alpha^*$ would be $$\alpha^*=\underset\alpha{\operatorname{argmin}}\left\{f\begin{pmatrix}1\\1\end{pmatrix},f\begin{pmatrix}1\\2\end{pmatrix},f\begin{pmatrix}2\\1\end{pmatrix},f\begin{pmatrix}2\\2\end{pmatrix} \right\}, $$ where $$f\begin{pmatrix}i\\j\end{pmatrix}= C(i\mid X_{t-1}=1)+C(j\mid X_{t-1}=2). $$ So, \begin{align} \alpha^*= \underset\alpha{\operatorname{argmin}}\{&\theta_{11}\lambda_{11}+(1-\theta_{21})\lambda_{12},\\&\theta_{11}\lambda_{11}+ \theta_{21}\lambda_{22}, \\&(1-\theta_{11})\lambda_{21}+(1-\theta_{21})\lambda_{12},\\& (1-\theta_{11})\lambda_{21}+\theta_{21}\lambda_{22} \}. \end{align}