Rossman, Servedio, and Tan proved that the polynomial hierarchy is infinite relative to a random oracle. This paper strengthens this celebrated result by considering strong separations, witnessed by immune languages.

The main result of the paper shows that with respect to a random oracle the levels of the polynomial hierarchy separate with immunity. Specifically, with probability one over a random oracle $A$, for every $k\geq 1$ there is a language in $\Sigma_{k}^{P,A}$ that is immune to $\Pi_{k}^{P,A}$, and, symmetrically, a language in $\Pi_{k}^{P,A}$ that is immune to $\Sigma_{k}^{P,A}$. We thus extend classical results due to Bennett and Gill and Vereshchagin.

We accomplish this by developing a "rare-or-wrong" approach to strong separations. We highlight the flexibility of the approach by strengthening other separations with respect to a random oracle from the complexity-theoretic literature.