No, così non va; quella regola di Knuth vale perr una sola formula, non per passaggi da un’espressione all’altra.
In questo caso io continuerei ad usare l’ambiente align* che hai usato tu, ma andrei a capo subito prima degli uguale in tutte le espresioni, trnane nella prima riga:`\begin{align*}
\mathbb{P} \Set{T \le M} \ge \mathbb{P} \Set{X_{M}\\
&= X_{M}'} \ge \mathbb{P} \Set{X_{M} = s_{1}, X_{M}' = s_{1}}\\
&=\mathbb{P} \Set{X_{M} = s_{1}} \mathbb{P} \Set{X_{M}' = s_{1}} \\
&=\left( \sum_{i=1}^{k} \mathbb{P} \Set{X_{0} = s_{i}, X_{M} = s_{1}} \right) \left( \sum_{i=1}^{k} \mathbb{P} \Set{X_{0}' = s_{i}, X_{M}' = s_{1}} \right) \\
&=\left( \sum_{i=1}^{k} \mathbb{P} \Set{X_{0} = s_{i}} \mathbb{P}\Set{X_{M} = s_{1} | X_{0} = s_{i}} \right) \\
&\qquad \times \left( \sum_{i=1}^{k} \mathbb{P} \Set{X_{0}' = s_{i}} \mathbb{P}\Set{X_{M}' = s_{1} | X_{0}' = s_{i}} \right) \\
& \ge \left(\alpha \sum_{i=1}^{k} \mathbb{P} \Set{X_{0} = s_{i}} \right)\left( \alpha \sum_{i=1}^{k} \mathbb{P} \Set{X_{0}' = s_{i}} \right) \\
&=\alpha^{2}
\end{align*}
`
Per le testatine che cosa c’è che non va secondo te? Se le hai costruite con fancyhdr, ricordati di metterci uno \strut da qualche parte, altrimenti il filetto ti appare a distanze diverse a seconda che il testo della testatina abbia o non abbia caratteri con discendenti.