I have the following problem:
Suppose we have a Markov chain $X_1 → X_2 → X_3$, where the random variable $X_i$ has support $\chi_i = \{1, . . . , n_i\}$, with $n_1 > n_2$ and $n_2 < n_3$. Show that $I(X1; X3) ≤ \log n_2$.
My try is:
$I(X_1,X_3) \le I(X_2,X_3)= H(X_2)-H(X_2|X_3)$ $I(X_1,X_3) \le I(X_1,X_2)= H(X_2)-H(X_2|X_1)$
So,
$2I(X_1,X_3) \le 2H(X_2)-H(X_2|H_3)-H(X_2|X_1)$.
And finally:
$I(X_1,X_3)\le H(X_2) \le \log n_2$.
My questions are: Is my reasoning well done? Why the suppositions about the length of the supports of $X_i$?.
Thanks in advance.
Unless you've proven it before, you should justify the inequality $I(X_1;X_3) \le I(X_2;X_3)$.
The definition of a Markov chain just says that $$\Pr[X_3{=}x_3 \mid X_2{=}x_2, X_1{=}x_1] = \Pr[X_3{=}x_3 \mid X_2{=}x_2].$$ It implies that $H(X_3 \mid X_1, X_2) = H(X_3 \mid X_2)$ because the definition of $H(X_3 \mid X_1,X_2)$ is in terms of probabilities of the form $\Pr[X_3{=}x_3 \mid X_2{=}x_2, X_1{=}x_1]$, and the definition of $H(X_3 \mid X_2)$ is in terms of probabilities of the form $\Pr[X_3{=}x_3 \mid X_2{=}x_2]$.
We can use this to prove that $I(X_1;X_3) \le I(X_2;X_3)$: \begin{align} I(X_1;X_3) &= H(X_3) - H(X_3 \mid X_1) \\ &\le H(X_3) - H(X_3 \mid X_1,X_2) \\ &= H(X_3) - H(X_3 \mid X_2) \\ &= I(X_2;X_3). \end{align}
You could justify $I(X_1;X_3) \le I(X_1;X_2)$ similarly, by we don't need it. Proceeding as you've done is fine, but we're also happy with just one of these inequalities, since $$ I(X_1;X_3) \le I(X_2;X_3) = H(X_2) - H(X_2 \mid X_3) \le H(X_2) \le \log_2 n_2. $$
Finally, you ask "why the suppositions about the length of the supports?" They're not needed in the proof, but they're needed for the result to be nontrivial. Without any Markov chain properties involved, we already have $$I(X_1;X_3) = H(X_1) - H(X_1 \mid X_3) \le H(X_1) \le \log_2 n_1$$ and similarly $I(X_1;X_3) \le \log_2 n_3$. So the Markov chain property is only a "bottleneck" that gives us useful information in the case where $\min\{x_1,x_2,x_3\} = x_2$.