Pearl's Causal Inference In Statistics: Study Question 1.5.3 Problem Statement: Consider a graph $X_1\to X_2\to X_3\to X_4$ of binary random variables, and assume
that the conditional probabilities between any two consecutive variables are given by
\begin{align*}
P(X_i=1|X_{i-1}=1)&=p\\
P(X_i=1|X_{i-1}=0)&=q\\
P(X_1=1)&=p_0.
\end{align*}
Compute the following probabilities
\begin{align*}
&P(X_1=1,X_2=0,X_3=1,X_4=0)\\
&P(X_4=1|X_1=1)\\
&P(X_1=1|X_4=1)\\
&P(X_3=1|X_1=0,X_4=1).
\end{align*}
My Answer: First, we have
\begin{align*}
P(X_1=1,X_2=0,X_3=1,X_4=0)
&=P(X_1=1)P(X_2=0|X_1=1)P(X_3=1|X_2=0)P(X_4=0|X_3=1)\\
&=p_0(1-p)^2q.
\end{align*}
This is due to the Rule of Product Decomposition. I understand how this works for conjunctions like the first probability. But I feel like that's a warmup question. Pearl has no examples to show how to compute these probabilities when you leave out terms in the graph. Can you please give me some hints on the last three probabilities? For example, how do you work forward through a graph, such as for $P(X_4=1|X_1=1),$ versus working backwards through the graph, such as for $P(X_1=1|X_4=1)?$
Thanks for your time!
 A: First write conditional probability formula:
$$P(X_4=1|X_1=1)=\frac{P(X_1=1,X_4=1)}{P(X_1=1)}$$
Then, write the numerator in terms of the full joint:
$$\begin{align}P(X_1=1,X_4=1)&=\sum_{x_2\in (0,1)}\sum_{x_3\in(0,1)}P(X_1=1,X_2=x_2,X_3=x_3,X_4=1)\end{align}$$
which can be calculated expanding the joint wrt graph provided.
You can calculate $P(X_4)$ to be used in $P(X_1=1|X_4=1)$ in a similar way.
A: Since this specification satisfies the Markov property, the simplest way to frame the problem is as a Markov chain.  Let $X_t$ denote the value at "time" $t$, and note that it has the transition probability matrix:
$$\mathbf{P} = \begin{bmatrix} 1-q & & q \\ 1-p & & p \\ \end{bmatrix}.$$
For simplicity, take the row labels and column labels for this matrix to be $i,j=0,1$.  All of the listed probabilities can be computed from standard probability results for discrete Morkov chains.  For example, to get the second probability on your list, you take three steps of the chain, using the transition probabilities in the matrix:
$$\mathbf{P}^3 = \begin{bmatrix} 
1 - q + q^2 - q^3 - q p + 2 q^2 p - q p^2 & & q - q^2 + q^3 - 2 q^2 p + q p^2 + q p \\[6pt]
1 - q + q^2 - q p - q^2 p + 2 q p^2 - p^3 & & q - q^2 + q p + q^2 p - 2 q p^2 + p^3 \\[6pt]
\end{bmatrix}.$$
So you get:
$$\begin{equation} \begin{aligned}
\mathbb{P}(X_4=1|X_1=1) = [\mathbf{P}^3]_{1,1} = q - q^2 + q p + q^2 p - 2 q p^2 + p^..
\end{aligned} \end{equation}$$
The remaining probabilities in the list can be obtained similarly, though in one case you should reverse the "time"-direction Markov chain.
