A step in the proof of Erdos-Tetali Lemma.

Question

I got confused reading this expression. Would be great if someone could help elaborate.

$$\sum_{(i_1,...,i_s) \in [m]^s} \prod_{j=1}^s \mathbb{P}(E_{i_{j}}) = \left(\sum_{i \in [m]} \mathbb{P}(E_i)\right)^s$$

Answer 1

The left side is the sum of all products of $s$ not necessarily distinct $\mathbb P(E_i)$’s, where order matters. If you expand the right side, each such product is written out exactly once. Simply imagine “choosing” the term $P(E_{{i_j}})$ for the $j$th term in the product.

As an example, note that $xx+xy+yx+yy=(x+y)^2$. The equation in question is not too different.