$\require{mathtools} % %%% GENERIC MATH %%% % % Environments \newcommand{\al}[1]{\begin{align}#1\end{align}} % need this for \tag{} to work \renewcommand{\r}{\mathrm} % % Greek \newcommand{\eps}{\epsilon} \newcommand{\veps}{\varepsilon} \let\fi\phi % because it looks like an f \let\phi\varphi % because it looks like a p % % Miscellaneous shortcuts \newcommand{\ob}{\overbrace} \newcommand{\ub}{\underbrace} \newcommand{\ol}{\overline} \newcommand{\tld}{\widetilde} \newcommand{\HAT}{\widehat} \newcommand{\f}{\frac} \newcommand{\s}[2]{#1 /\mathopen{}#2} \newcommand{\sse}{\subseteq} \newcommand{\ce}{\coloneqq} \newcommand{\ec}{\eqqcolon} \newcommand{\la}{\lessapprox} \newcommand{\ga}{\greaterapprox} \newcommand{\sr}{\stackrel} \newcommand{\q}{\quad} \newcommand{\qq}{\qquad} \newcommand{\heart}{\heartsuit} % % Delimiters % (I needed to create my own because the MathJax version of \DeclarePairedDelimiter doesn't have \mathopen{} and that messes up the spacing) \newcommand{\p}[1]{\mathopen{}\left( #1 \right)} \newcommand{\b}[1]{\mathopen{}\left[ #1 \right]} \newcommand{\set}[1]{\mathopen{}\left\{ #1 \right\}} \newcommand{\abs}[1]{\mathopen{}\left\lvert #1 \right\rvert} \newcommand{\floor}[1]{\mathopen{}\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\mathopen{}\left\lceil #1 \right\rceil} \newcommand{\inner}[1]{\mathopen{}\left\langle #1 \right\rangle} % .... (use phantom to force at least the standard height of double bars) \newcommand{\norm}[1]{\mathopen{}\left\lVert #1 \vphantom{f} \right\rVert} \newcommand{\frob}[1]{\norm{#1}_\mathrm{F}} %% .. two-part \newcommand{\incond}[2]{#1 \mathop{}\middle|\mathop{} #2} \newcommand{\cond}[2]{ {\left.\incond{#1}{#2}\right.}} \newcommand{\pco}[2]{\p{\incond{#1}{#2}}} \newcommand{\bco}[2]{\b{\incond{#1}{#2}}} \newcommand{\setco}[2]{\set{\incond{#1}{#2}}} \newcommand{\at}[2]{\left.#1\right|_{#2}} % ..... (use phantom to force at least the standard height of double bar) \newcommand{\oldpara}[2]{#1\vphantom{f} \mathop{}\middle\|\mathop{} #2} %\newcommand{\para}[2]{#1\vphantom{f} \mathop{}\middle\|\mathop{} #2} \newcommand{\para}[2]{\mathchoice{\begin{matrix}#1\\\hdashline#2\end{matrix}}{\begin{smallmatrix}#1\\\hdashline#2\end{smallmatrix}}{\begin{smallmatrix}#1\\\hdashline#2\end{smallmatrix}}{\begin{smallmatrix}#1\\\hdashline#2\end{smallmatrix}}} \newcommand{\ppa}[2]{\p{\para{#1}{#2}}} \newcommand{\bpa}[2]{\b{\para{#1}{#2}}} %\newcommand{\bpaco}[4]{\bpa{\incond{#1}{#2}}{\incond{#3}{#4}}} \newcommand{\bpaco}[4]{\bpa{\cond{#1}{#2}}{\cond{#3}{#4}}} % % Miscellaneous \newcommand{\LHS}{\mathrm{LHS}} \newcommand{\RHS}{\mathrm{RHS}} % .. operators \DeclareMathOperator{\poly}{poly} \DeclareMathOperator{\polylog}{polylog} \DeclareMathOperator{\quasipoly}{quasipoly} \DeclareMathOperator{\negl}{negl} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator*{\argmax}{arg\,max} % .. functions \DeclareMathOperator{\id}{id} \DeclareMathOperator{\sign}{sign} \DeclareMathOperator{\err}{err} \DeclareMathOperator{\ReLU}{ReLU} % .. analysis \let\d\undefined \newcommand{\d}{\operatorname{d}\mathopen{}} \newcommand{\df}[2]{\f{\d #1}{\d #2}} \newcommand{\ds}[2]{\s{\d #1}{\d #2}} \newcommand{\part}{\partial} \newcommand{\partf}[2]{\f{\part #1}{\part #2}} \newcommand{\parts}[2]{\s{\part #1}{\part #2}} \newcommand{\grad}[1]{\mathop{\nabla\!_{#1}}} % .. sets \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\F}{\mathbb{F}} \newcommand{\zo}{\set{0,1}} \newcommand{\pmo}{\set{\pm 1}} % %%% SPECIALIZED MATH %%% % % Logic \renewcommand{\and}{\wedge} \newcommand{\AND}{\bigwedge} \newcommand{\or}{\vee} \newcommand{\OR}{\bigvee} \newcommand{\xor}{\oplus} \newcommand{\XOR}{\bigoplus} \newcommand{\union}{\cup} \newcommand{\inter}{\cap} \newcommand{\UNION}{\bigcup} \newcommand{\INTER}{\bigcap} \newcommand{\comp}{\overline} \newcommand{\true}{\r{true}} \newcommand{\false}{\r{false}} \newcommand{\tf}{\set{\true,\false}} \DeclareMathOperator{\One}{\mathbb{1}} \DeclareMathOperator{\1}{\mathbb{1}} % % Linear algebra \renewcommand{\span}{\mathrm{span}} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\proj}{proj} \DeclareMathOperator{\dom}{dom} \DeclareMathOperator{\Img}{Im} \newcommand{\transp}{\mathsf{T}} \renewcommand{\t}{^\transp} % ... named tensors \newcommand{\namedtensorstrut}{\vphantom{fg}} % milder than \mathstrut \newcommand{\name}[1]{\mathsf{\namedtensorstrut #1}} \newcommand{\nbin}[2]{\mathbin{\underset{\substack{#1}}{\namedtensorstrut #2}}} \newcommand{\ndot}[1]{\nbin{#1}{\odot}} \newcommand{\ncat}[1]{\nbin{#1}{\oplus}} \newcommand{\nsum}[1]{\sum\limits_{\substack{#1}}} \newcommand{\nfun}[2]{\mathop{\underset{\substack{#1}}{\namedtensorstrut\mathrm{#2}}}} \newcommand{\ndef}[2]{\newcommand{#1}{\name{#2}}} \newcommand{\nt}[1]{^{\transp(#1)}} % % Probability \newcommand{\Normal}{\mathcal{N}} \let\Pr\undefined \DeclareMathOperator*{\Pr}{Pr} \DeclareMathOperator*{\G}{\mathbb{G}} \DeclareMathOperator*{\Odds}{Od} \DeclareMathOperator*{\E}{E} \DeclareMathOperator*{\Var}{Var} \DeclareMathOperator*{\Cov}{Cov} \DeclareMathOperator*{\corr}{corr} \DeclareMathOperator*{\median}{median} \newcommand{\dTV}{d_{\mathrm{TV}}} \newcommand{\dHel}{d_{\mathrm{Hel}}} \newcommand{\dJS}{d_{\mathrm{JS}}} % ... information theory \let\H\undefined \DeclareMathOperator*{\H}{H} \DeclareMathOperator*{\I}{I} \DeclareMathOperator*{\D}{D} % %%% SPECIALIZED COMPUTER SCIENCE %%% % % Complexity classes % .. classical \newcommand{\Poly}{\mathsf{P}} \newcommand{\NP}{\mathsf{NP}} \newcommand{\PH}{\mathsf{PH}} \newcommand{\PSPACE}{\mathsf{PSPACE}} \renewcommand{\L}{\mathsf{L}} % .. probabilistic \newcommand{\formost}{\mathsf{Я}} \newcommand{\RP}{\mathsf{RP}} \newcommand{\BPP}{\mathsf{BPP}} \newcommand{\MA}{\mathsf{MA}} \newcommand{\AM}{\mathsf{AM}} \newcommand{\IP}{\mathsf{IP}} \newcommand{\RL}{\mathsf{RL}} % .. circuits \newcommand{\NC}{\mathsf{NC}} \newcommand{\AC}{\mathsf{AC}} \newcommand{\ACC}{\mathsf{ACC}} \newcommand{\TC}{\mathsf{TC}} \newcommand{\Ppoly}{\mathsf{P}/\poly} \newcommand{\Lpoly}{\mathsf{L}/\poly} % .. resources \newcommand{\TIME}{\mathsf{TIME}} \newcommand{\SPACE}{\mathsf{SPACE}} \newcommand{\TISP}{\mathsf{TISP}} \newcommand{\SIZE}{\mathsf{SIZE}} % .. keywords \newcommand{\co}{\mathsf{co}} \newcommand{\Prom}{\mathsf{Promise}} % % Boolean analysis \newcommand{\harpoon}{\!\upharpoonright\!} \newcommand{\rr}[2]{#1\harpoon_{#2}} \newcommand{\Fou}[1]{\widehat{#1}} \DeclareMathOperator{\Ind}{\mathrm{Ind}} \DeclareMathOperator{\Inf}{\mathrm{Inf}} \DeclareMathOperator{\Der}{\mathrm{D}} \DeclareMathOperator{\Stab}{\mathrm{Stab}} \DeclareMathOperator{\T}{T} \DeclareMathOperator{\sens}{\mathrm{s}} \DeclareMathOperator{\bsens}{\mathrm{bs}} \DeclareMathOperator{\fbsens}{\mathrm{fbs}} \DeclareMathOperator{\Cert}{\mathrm{C}} \DeclareMathOperator{\DT}{\mathrm{DT}} \DeclareMathOperator{\CDT}{\mathrm{CDT}} % canonical \DeclareMathOperator{\ECDT}{\mathrm{ECDT}} \DeclareMathOperator{\CDTv}{\mathrm{CDT_{vars}}} \DeclareMathOperator{\ECDTv}{\mathrm{ECDT_{vars}}} \DeclareMathOperator{\CDTt}{\mathrm{CDT_{terms}}} \DeclareMathOperator{\ECDTt}{\mathrm{ECDT_{terms}}} \DeclareMathOperator{\CDTw}{\mathrm{CDT_{weighted}}} \DeclareMathOperator{\ECDTw}{\mathrm{ECDT_{weighted}}} \DeclareMathOperator{\AvgDT}{\mathrm{AvgDT}} \DeclareMathOperator{\PDT}{\mathrm{PDT}} % partial decision tree \DeclareMathOperator{\DTsize}{\mathrm{DT_{size}}} \DeclareMathOperator{\W}{\mathbf{W}} % .. functions (small caps sadly doesn't work) \DeclareMathOperator{\Par}{\mathrm{Par}} \DeclareMathOperator{\Maj}{\mathrm{Maj}} \DeclareMathOperator{\HW}{\mathrm{HW}} \DeclareMathOperator{\Th}{\mathrm{Th}} \DeclareMathOperator{\Tribes}{\mathrm{Tribes}} \DeclareMathOperator{\RotTribes}{\mathrm{RotTribes}} \DeclareMathOperator{\CycleRun}{\mathrm{CycleRun}} \DeclareMathOperator{\SAT}{\mathrm{SAT}} \DeclareMathOperator{\UniqueSAT}{\mathrm{UniqueSAT}} % % Dynamic optimality \newcommand{\OPT}{\mathsf{OPT}} \newcommand{\Alt}{\mathsf{Alt}} \newcommand{\Funnel}{\mathsf{Funnel}} % % Alignment \DeclareMathOperator{\Amp}{\mathrm{Amp}} % %%% TYPESETTING %%% % % In text \renewcommand{\th}{^{\mathrm{th}}} \newcommand{\degree}{^\circ} % % Fonts % .. bold \newcommand{\BA}{\boldsymbol{A}} \newcommand{\BB}{\boldsymbol{B}} \newcommand{\BC}{\boldsymbol{C}} \newcommand{\BD}{\boldsymbol{D}} \newcommand{\BE}{\boldsymbol{E}} \newcommand{\BF}{\boldsymbol{F}} \newcommand{\BG}{\boldsymbol{G}} \newcommand{\BH}{\boldsymbol{H}} \newcommand{\BI}{\boldsymbol{I}} \newcommand{\BJ}{\boldsymbol{J}} \newcommand{\BK}{\boldsymbol{K}} \newcommand{\BL}{\boldsymbol{L}} \newcommand{\BM}{\boldsymbol{M}} \newcommand{\BN}{\boldsymbol{N}} \newcommand{\BO}{\boldsymbol{O}} \newcommand{\BP}{\boldsymbol{P}} \newcommand{\BQ}{\boldsymbol{Q}} \newcommand{\BR}{\boldsymbol{R}} \newcommand{\BS}{\boldsymbol{S}} \newcommand{\BT}{\boldsymbol{T}} \newcommand{\BU}{\boldsymbol{U}} \newcommand{\BV}{\boldsymbol{V}} \newcommand{\BW}{\boldsymbol{W}} \newcommand{\BX}{\boldsymbol{X}} \newcommand{\BY}{\boldsymbol{Y}} \newcommand{\BZ}{\boldsymbol{Z}} \newcommand{\Ba}{\boldsymbol{a}} \newcommand{\Bb}{\boldsymbol{b}} \newcommand{\Bc}{\boldsymbol{c}} \newcommand{\Bd}{\boldsymbol{d}} \newcommand{\Be}{\boldsymbol{e}} \newcommand{\Bf}{\boldsymbol{f}} \newcommand{\Bg}{\boldsymbol{g}} \newcommand{\Bh}{\boldsymbol{h}} \newcommand{\Bi}{\boldsymbol{i}} \newcommand{\Bj}{\boldsymbol{j}} \newcommand{\Bk}{\boldsymbol{k}} \newcommand{\Bp}{\boldsymbol{p}} \newcommand{\Bq}{\boldsymbol{q}} \newcommand{\Br}{\boldsymbol{r}} \newcommand{\Bs}{\boldsymbol{s}} \newcommand{\Bt}{\boldsymbol{t}} \newcommand{\Bu}{\boldsymbol{u}} \newcommand{\Bv}{\boldsymbol{v}} \newcommand{\Bw}{\boldsymbol{w}} \newcommand{\Bx}{\boldsymbol{x}} \newcommand{\By}{\boldsymbol{y}} \newcommand{\Bz}{\boldsymbol{z}} \newcommand{\Balpha}{\boldsymbol{\alpha}} \newcommand{\Bbeta}{\boldsymbol{\beta}} \newcommand{\Bgamma}{\boldsymbol{\gamma}} \newcommand{\Bdelta}{\boldsymbol{\delta}} \newcommand{\Beps}{\boldsymbol{\eps}} \newcommand{\Bveps}{\boldsymbol{\veps}} \newcommand{\Bzeta}{\boldsymbol{\zeta}} \newcommand{\Beta}{\boldsymbol{\eta}} \newcommand{\Btheta}{\boldsymbol{\theta}} \newcommand{\Biota}{\boldsymbol{\iota}} \newcommand{\Bkappa}{\boldsymbol{\kappa}} \newcommand{\Blambda}{\boldsymbol{\lambda}} \newcommand{\Bmu}{\boldsymbol{\mu}} \newcommand{\Bnu}{\boldsymbol{\nu}} \newcommand{\Bxi}{\boldsymbol{\xi}} \newcommand{\Bomicron}{\boldsymbol{\omicron}} \newcommand{\Bpi}{\boldsymbol{\pi}} \newcommand{\Brho}{\boldsymbol{\rho}} \newcommand{\Bsigma}{\boldsymbol{\sigma}} \newcommand{\Btau}{\boldsymbol{\tau}} \newcommand{\Bupsilon}{\boldsymbol{\upsilon}} \newcommand{\Bphi}{\boldsymbol{\phi}} \newcommand{\Bfi}{\boldsymbol{\fi}} \newcommand{\Bchi}{\boldsymbol{\chi}} \newcommand{\Bpsi}{\boldsymbol{\psi}} \newcommand{\Bomega}{\boldsymbol{\omega}} % .. calligraphic \newcommand{\CA}{\mathcal{A}} \newcommand{\CB}{\mathcal{B}} \newcommand{\CC}{\mathcal{C}} \newcommand{\CD}{\mathcal{D}} \newcommand{\CE}{\mathcal{E}} \newcommand{\CF}{\mathcal{F}} \newcommand{\CG}{\mathcal{G}} \newcommand{\CH}{\mathcal{H}} \newcommand{\CI}{\mathcal{I}} \newcommand{\CJ}{\mathcal{J}} \newcommand{\CK}{\mathcal{K}} \newcommand{\CL}{\mathcal{L}} \newcommand{\CM}{\mathcal{M}} \newcommand{\CN}{\mathcal{N}} \newcommand{\CO}{\mathcal{O}} \newcommand{\CP}{\mathcal{P}} \newcommand{\CQ}{\mathcal{Q}} \newcommand{\CR}{\mathcal{R}} \newcommand{\CS}{\mathcal{S}} \newcommand{\CT}{\mathcal{T}} \newcommand{\CU}{\mathcal{U}} \newcommand{\CV}{\mathcal{V}} \newcommand{\CW}{\mathcal{W}} \newcommand{\CX}{\mathcal{X}} \newcommand{\CY}{\mathcal{Y}} \newcommand{\CZ}{\mathcal{Z}} % .. typewriter \newcommand{\TA}{\mathtt{A}} \newcommand{\TB}{\mathtt{B}} \newcommand{\TC}{\mathtt{C}} \newcommand{\TD}{\mathtt{D}} \newcommand{\TE}{\mathtt{E}} \newcommand{\TF}{\mathtt{F}} \newcommand{\TG}{\mathtt{G}} \newcommand{\TH}{\mathtt{H}} \newcommand{\TI}{\mathtt{I}} \newcommand{\TJ}{\mathtt{J}} \newcommand{\TK}{\mathtt{K}} \newcommand{\TL}{\mathtt{L}} \newcommand{\TM}{\mathtt{M}} \newcommand{\TN}{\mathtt{N}} \newcommand{\TO}{\mathtt{O}} \newcommand{\TP}{\mathtt{P}} \newcommand{\TQ}{\mathtt{Q}} \newcommand{\TR}{\mathtt{R}} \newcommand{\TS}{\mathtt{S}} \newcommand{\TT}{\mathtt{T}} \newcommand{\TU}{\mathtt{U}} \newcommand{\TV}{\mathtt{V}} \newcommand{\TW}{\mathtt{W}} \newcommand{\TX}{\mathtt{X}} \newcommand{\TY}{\mathtt{Y}} \newcommand{\TZ}{\mathtt{Z}}$

Adapted from Chapter 5 of “The probabilistic method” by Noga Alon and Joel H. Spencer.

Context

Say you have $m$ bad events $E_1, \ldots, E_m$, each happening with probability at most $p$, and you want to prove that sometimes, none of them happen. For example: you could do that if:

  • If $pm < 1$, then this follows by a union bound.
  • Or maybe they’re all independent, in which case with probability $\geq (1-p)^m$, none of them will happen.

But what if $pm \geq 1$ and they’re not independent? In the general case, there’s nothing you can do (e.g. if they’re all disjoint and happening with probability exactly $1/m$). But what if they’re mostly independent? Can you then relax the condition $pm < 1$ a bit and still get a non-zero probability of none of them happening? This is exactly what the Lovász local lemma is for!

Lemma

Let $E_1, \ldots, E_m$ be $m$ bad events such that $\Pr[E_j] \leq p$ and each $E_j$ is independent of all but $d$ of the other events.1 If $4pd \leq 1$, then $\Pr\b{\AND_j \overline{E_j}} > 0$.

Interpretation

This is the best thing we could have hoped for (up to constants)! Comparing condition $4pd \leq 1$ to the condition $pm < 1$ we had before, this intuitively means that we’re “only union-bounding over” the events that each $E_j$ is actually dependent on, instead of union-bounding over all $m$ events.

Example 1

Let $f$ be a CNF with the following properties:

  • each clause is an OR of at least $k$ literals;
  • each clause intersects with at most $2^{k}/4$ other clauses.

Then $f$ is satisfiable.

Indeed, for each clause $C_j$, we can define a bad event $E_j$ as the event that the clause is unsatisfied, and we have:

  • $\Pr[E_j] \leq 2^{-k} \eqqcolon p$;
  • each $E_j$ is independent of all but $d \coloneqq 2^k/4$ of the other events (the events for the clauses it intersects with);
  • and $4pd = 1$.

Therefore there is a non-zero probability that all the clauses are simultaneously satisfied, which would make the CNF satisfied.

In fact, not only is $f$ satisfiable, but a satisfying assignment can be efficiently found (despite the fact that they might be exponentially rare): this is Moser’s Algorithmic Lovász local lemma.

Example 2

A hypergraph has “property B” if it can be bicolored so that no edge is monochromatic. Then any $k$-uniform hypergraph such that each edge intersects with $\leq d \coloneqq 2^{k-3}$ other edges has property B.

Indeed, under a uniformly random coloring, each edge is monochromatic with probability $p \coloneqq 2 \cdot 2^{-k}$, and $4pd = 1$.

Proof

Intuition and plan

We have

\[\begin{align} \Pr\b{\AND_j \comp{E_j}} &= \prod_j \Pr\bco{\comp{E_j}}{\AND_{l<j} \comp{E_l}}\\ &= \prod_j \p{1-\Pr\bco{E_j}{\AND_{l<j} \comp{E_l}}}. \end{align}\]

So if we can show that no bad event $E_j$ becomes too much more likely after conditioning on other events, we can show that $\Pr\b{\AND_j \comp{E_j}} > 0$.

Intuitively, the events we should be most worried about conditioning on are the events $\set{E_l}_{l \in S}$ (with $|S| \leq d$) that $E_j$ is not independent from. So if we can show $\Pr\bco{E_j}{\AND_{l \in S} \overline{E_l}} < 1$, this would already be a good sign.

In fact, using the condition $4pd \leq 1$, we can show that the probability that $E_j$ happens doesn’t increase too much when we’re conditioning on those events. To start out, we have

\[ \Pr\bco{E_j}{\AND_{l \in S} \comp{E_l}} = \frac{\Pr\b{E_j \and \p{\AND_{l \in S} \comp{E_l}}}}{\Pr\b{\AND_{l \in S} \comp{E_l}}} \leq \frac{\Pr[E_j]}{\Pr\b{\AND_{l \in S} \comp{E_l}}}. \]

So if we can prove that $\Pr\b{\AND_{l \in S} \comp{E_l}}$ isn’t too small, we’re good. And indeed, by a union bound,

\[ \Pr\b{\AND_{l \in S} \comp{E_l}} \geq 1 - \sum_{l \in S} \Pr[E_l] \geq 1 - \sum_{l \in S} p \geq 1 - dp \geq 3/4, \]

so we have $\Pr\bco{E_j}{\AND_{l \in S} \comp{E_l}} \leq \frac{4}{3}\Pr[E_j] \leq \frac{4}{3}p$.

However, it’s not clear that this stays true once we also condition on other events than those in $S$: even though those other events are independent of $E_j$, the can have dependencies with the events $\set{E_l}_{l \in S}$, which could screw up the conditional probability. To deal with this, we will prove the following claim by induction.

Claim

For any event $E_j$ and any set $S \subseteq [m] \setminus \set{j}$ to condition on, we have, $\Pr\bco{E_j}{\AND_{l \in S} \comp{E_l}} \leq 2p$. That is, no bad event becomes too much more likely after you condition on some other events not happening.

Proof of lemma assuming claim

As suggested above, just apply the chain rule:

\[\begin{align} \Pr\b{\AND_j \comp{E_j}} &= \prod_j \Pr\bco{\comp{E_j}}{\AND_{l<j} \comp{E_l}}\\ &= \prod_j \p{1-\Pr\bco{E_j}{\AND_{l<j} \comp{E_l}}}\\ &\geq (1-2p)^m\tag{by claim}\\ &> 0. \end{align}\]

Note that the lower bound we get on the probability is only slightly worse than the $(1-p)^m$ probability we would have gotten if the events were all perfectly independent!

Proof of claim

By induction on $|S|$. This is clearly true if $|S| = 0$. Suppose this is true for all $i$ and all sets $S \subseteq [m] \setminus \set{j}$ of size $\leq s$.

Take some set $S$ with $|S|=s+1$. Let’s split $S$ into $S_\mathrm{dep}$ and $S_{\mathrm{ind}}$, where $|S_\mathrm{dep}| \leq d$ is the set of events in $S$ that $E_j$ depends on.2 We have

\[ \Pr\bco{E_j}{\AND_{l \in S} \comp{E_l}} = \frac{\Pr\bco{E_j \and \p{\AND_{l \in S_\r{dep}} \overline{E_l}}}{\AND_{l \in S_\r{ind}} \comp{E_l}}}{\Pr\bco{\AND_{l \in S_\r{dep}} \comp{E_l}}{\AND_{l \in S_\r{ind}} \comp{E_l}}}. \]

We can upper-bound the numerator as

\[ \Pr\bco{E_j \and \p{\AND_{l \in S_\r{dep}} \comp{E_l}}}{\AND_{l \in S_\r{ind}} \overline{E_l}} \leq \Pr\bco{E_j}{\AND_{l \in S_\r{ind}} \comp{E_l}} = \Pr[E_j] \leq p, \]

where the equality holds because $E_j$ is independent of the events in $S_\mathrm{ind}$.3

On the other hand, we can apply a union bound and use the induction hypothesis to show that the denominator never gets very small:

\[\begin{align} \Pr\bco{\AND_{l \in S_\r{dep}} \comp{E_l}}{\AND_{l \in S_\r{ind}} \comp{E_l}} &\geq 1 - \sum_{l \in S_\r{dep}} \Pr\bco{E_l}{\AND_{l \in S_\r{ind}} \overline{E_l}}\tag{by union bound}\\ &\geq 1 - \sum_{l \in S_\r{dep}}2p\tag{by induction}\\ &\geq 1 - 2dp\\ &\geq 1/2. \end{align}\]

The reason why we can apply the induction hypothesis is that in each of those probabilities, we’re conditioning on at least one fewer events than the entirety of $S$, so we’re only conditioning on $\leq s$ events.

Combining these two bounds, we get

\[ \Pr\bco{E_j}{\AND_{l \in S} \comp{E_l}} \leq \frac{p}{1/2} = 2p. \]
  1. More precisely, for each $j$, there is a set $S \subseteq [m] \setminus \set{j}$, $|S| \leq d$, such that $E_j$ is independent from $\set{E_l}_{l \in [m] \setminus S \setminus \set{j}}$. That is, fixing the outcome of the events $E_l$ for $l \not\in S \cup \set{j}$ doesn’t affect the probability that $E_j$ happens. Importantly, this doesn’t require the events in $[m] \setminus S \setminus \set{j}$ to be independent of each other

  2. Assume $S_\mathrm{dep}$ is not empty; otherwise, we have $\Pr[E_j \mid \wedge_{l \in S} \overline{E_l}] = \Pr[E_j \mid \wedge_{l \in S_\mathrm{ind}} \overline{E_l}] = \Pr[E_j] \leq p$ so we’re done. 

  3. Note that we only really need that $\Pr\b{E_j \mid \AND_{l \in S_\mathrm{ind}} \overline{E_l}} \leq p$, not full independence. That is, we only need to make sure that the probability $E_j$ doesn’t increase too much when we condition on the events in $S_\mathrm{ind}$