Independence in Graphical model of $p(h_{1:T}|v_{1:T})$ of an HMM

Question

I am studying Hidden Markov Models and I'm trying to understand the following exercise:

Consider Hidden Markov Model with hidden states $h_{1:T} = \{h_1,...,h_T\}$ and observed states $v_{1:T}=\{v_1,...,v_T\}$.

When the sequence of outcomes $v_{1:T}$ is observed, it induces the distribution on the hidden states $p_v(h_{1:T}) = p(h_{1:T}|v_{1:T})$.

Question 1: What is the graphical model of this distribution?

Question 2: Based on the graphical model, is $h_1$ independent of $h_T$ in this distribution?

Question 3: Is is possible to sample efficiently from $p_v(h_{1:T})$?

My answers are:

Answer to Question 1: We have that $p(h_1,...,h_n|v_{1:n})$ forms a first order Markov chain. The simplest way to show this is to notice that the undirected graph for the hidden Markov model is the same as the DAG but with the arrows removed as there are no colliders in the DAG. Moreover, conditioning corresponds to removing nodes from an undirected graph. This leaves us with a chain that connects the $h_i$.

By graph separation, we see that $p(h_1,...,h_n|v_{1:n})$ forms a first-rder Markov chain so that e.g. $h_{1:t-1}$ is independent of $h_{t+1:n}$ given $h_t$ (past independent from the future given the present).

Answer to question 2: We can see from the Markov model that $h_1$ has a path leading to $h_T$ which is not blocked, hence they are not independent.

Answer to question 3: It is possible to efficiently sample from $p(h_{1:T}|v_{1:T})$ using an MCMC method like Gibbs sampling, since $p_v(h_{1:T})$ is a Markov chain.

Is my understanding correct with my answers?

Answer 1

Your first question:
Your answer is correct, the hidden states form a first-order Markov chain. If one is only interested in conditional independencies (CIs), then indeed, in Markov networks you simply remove the observed nodes with all incident edges and then consider the connected components. However, it sometimes makes sense to keep the observed points but shade them differently like this:

That way it is emphasized that you have selection bias: The probabilities of the hidden states $h_i$ are different for different ("selections" of) observations $v_i$.
Also, note that marginalization is what is really associated with removing nodes, but then the edges are handled differently.

Your second question:
Your answer is correct. You have a Markov network that consists of a single connected component, thus you cannot deduce any independencies. (And the whole point of HMMs is that the states form a Markov chain and thus depend on each other.)

Your third question:
In your case, you should do ancestral sampling, which is faster than e.g. Gibbs. Just start with sampling from $p(h_1|v_1)$, then use the $h_1$-sample to sample from $p(h_2|h_1, v_2)$, and so forth. And then note that the observations $v_i$ influence the conditional probabilities of the hidden states $h_i$, which you get reminded of when leaving the conditioned (i.e. observed) variables in the graph as shown above.

For the sampling from the conditional probabilities $p(h_i| h_{i-1}, v_i)$ you might have to use MCMC, depending on the type of distribution.