How to prove **$k_1$-wise independence implies $k_2$-wise independence if $k_1 \geq k_2$** The Definition 1 shows the  the meaning of k-wise independence. So can anybody help to  prove $k_1$-wise independence implies $k_2$-wise independence if $k_1 \geq k_2$? By the way, I did not understand the Example 2 either, since I did not know how to calculate the variable $X_3$ there.

 A: Notice that it is enough to prove that $k$-wise independence implies $(k-1)$-wise independence.  Suppose the collection $X_1, X_2, \cdots, X_n$ is $k$-wise independent.  Now, choose $k-1$ indices $1\le i_1 < i_2 < \cdots < i_{k-1} \le n$, and also choose $k-1$ values $a_i \in A_i$ for $i=i_1,i_2,\cdots, i_{k-1}$.  Now, we want to show
$$\Pr(X_{i_1} = a_{i_1} \land  X_{i_2} = a_{i_2} \land  \cdots \land X_{i_{k-1}} =a_{i_{k-1}}) = \prod_{j=1}^{k-1} \Pr(X_{i_j} = a_{i_j} )$$
Now, let $i_k$ be an index distinct from $i_1, i_2, \cdots, i_{k-1}$ * Then,
$$\Pr(X_{i_1} = a_{i_1} \land  X_{i_2} = a_{i_2} \land  \cdots \land X_{i_{k-1}} =a_{i_{k-1}}) = \sum_{a_{i_k} \in A_{i_k}} \Pr(X_{i_1} = a_{i_1} \land  X_{i_2} = a_{i_2} \land  \cdots \land X_{i_{k-1}} =a_{i_{k-1}} \land X_{i_k} = a_{i_k})$$
But also
$$\Pr(X_{i_1} = a_{i_1} \land  X_{i_2} = a_{i_2} \land  \cdots \land X_{i_{k-1}} =a_{i_{k-1}} \land X_{i_k} = a_{i_k}) = \prod_{j=1}^{k} \Pr(X_{i_j} = a_{i_j} )$$
and
$$\sum_{a_{i_k} \in A_{i_k}} \prod_{j=1}^{k} \Pr(X_{i_j} = a_{i_j} ) = \left(\prod_{j=1}^{k-1} \Pr(X_{i_j} = a_{i_j} )\right)\left(\sum_{a_{i_k} \in A_{i_k}} \Pr(X_{i_k} = a_{i_k})\right) = \sum_{a_{i_k} \in A_{i_k}} \Pr(X_{i_k} = a_{i_k})$$
giving us the desired result.

*: The fact that $X_1, X_2, \cdots, X_n$ is $k$-wise independent implies $k \le n$, so such an index variable exists.  Can you see why?
