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!


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.

  • $\begingroup$ No doubt it's obvious to you, but it's not to me; your first equation there is simply the definition of conditional probability. Where does your second equation come from? It kind of makes sense as an equation, but I'm just wanting to know its source. Thanks for your time! $\endgroup$ – Adrian Keister Mar 13 '20 at 16:07
  • $\begingroup$ @AdrianKeister It's basically marginalization: en.wikipedia.org/wiki/Marginal_distribution in its simplest form: $$P(A) = P(A\cap B) + P(A\cap B')$$ $\endgroup$ – gunes Mar 13 '20 at 16:09
  • 1
    $\begingroup$ Ah, I see. Many thanks! $\endgroup$ – Adrian Keister Mar 13 '20 at 16:10

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.

  • $\begingroup$ Thanks, that's informative! While I understand the basic idea of Markov chains, I haven't studied them in detail; I imagine this would all make more sense once I do (it's on my list to study, since I'm extremely interested in queueuing theory). Thanks again! $\endgroup$ – Adrian Keister Mar 13 '20 at 14:04

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.