Proof of the basic differential privacy composition theorem
You are right, we need to assume the coin toss of mechanisms are independent to each other, as stated in the proof.

You are right, again. The proof in the paper seems to be problematic. Here's the modified proof:
\begin{align}
Pr[(x_1, x_2) \in S] &amp;= Pr[x_1 \in S_1] Pr[x_2 \in S_2 | x_1 \in S_1] \\
&amp;\le (\min(1, e^\epsilon Pr[x_2' \in S_2 | x_1 \in S_1]) + \delta )Pr[x_1 \in S_1] \\
&amp;\le \min(1, e^\epsilon Pr[x_2' \in S_2 | x_1 \in S_1])Pr[x_1 \in S_1] + \delta \\
&amp;\le \min(1, e^\epsilon Pr[x_2' \in S_2 | x_1 \in S_1])(e^\epsilon Pr[x_1' \in S_1] + \delta) + \delta \\
&amp;\le e^{2\epsilon} Pr[(x_1', x_2') \in S] + 2\delta
\end{align}


The key to avoid the problem you stated is instead of using
$$
Pr[x \in S] \le e^\epsilon Pr[x' \in S] + \delta
$$
we use
$$
Pr[x \in S] \le \min(1, e^\epsilon Pr[x' \in S]) + \delta
$$
for the inequalities.