[proofplan]
The proof is a deterministic counting argument followed by the assumed [complementary-pairs stability-selection](/page/Complementary%20Pairs%20Stability%20Selection) product bound. For a fixed variable, selection frequency above $\pi_{\mathrm{thr}}>1/2$ forces simultaneous selection in both halves of a positive fraction of complementary pairs by the elementary binary-indicator inequality. Summing this implication over null variables bounds $V$ by the number of null variables selected in both halves, multiplied by $(2\pi_{\mathrm{thr}}-1)^{-1}$. Writing $\mathcal D$ for the observed sample, taking $\mathbb E_{\mathrm{sub}}[\cdot]=\mathbb E[\cdot\mid \mathcal D]$, [conditional expectation](/page/Conditional%20Expectation) with respect to $\mathcal D$, and inserting the product bound gives the claimed inequality; the product bound is the only probabilistic input used after the deterministic counting step.
[/proofplan]
[step:Convert high empirical frequency into simultaneous selection across complementary pairs]
Fix $j \in \{1,\dots,p\}$. For each $b \in \{1,\dots,B\}$ define the binary [random variable](/page/Random%20Variable) $X_{b,j}:=\mathbb{1}_{\{j \in A_\lambda(I_b)\}}$. Also define the binary random variable $Y_{b,j}:=\mathbb{1}_{\{j \in A_\lambda(I_b^c)\}}$. These definitions are legitimate because the theorem declares $A_\lambda$ as a map from admissible subsample index sets $J\subset\{1,\dots,n\}$ to selected-variable sets $A_\lambda(J)\subset\{1,\dots,p\}$, and both $I_b$ and $I_b^c$ are admissible by construction. Define the empirical [stability-selection](/page/Stability%20Selection) frequency $\hat{\pi}_j$ by
\begin{align*}
\hat{\pi}_j:=\frac{1}{2B}\sum_{b=1}^B (X_{b,j}+Y_{b,j}).
\end{align*}
With this notation, the stability-selected set at penalty $\lambda$ and threshold $\pi_{\mathrm{thr}}$ is
\begin{align*}
\hat S_{\mathrm{stab}}(\lambda,\pi_{\mathrm{thr}}):=\{j\in\{1,\dots,p\}:\hat\pi_j\geq\pi_{\mathrm{thr}}\}.
\end{align*}
For binary variables $x,y \in \{0,1\}$ one has
\begin{align*}
xy \geq x+y-1.
\end{align*}
Applying this with $x=X_{b,j}$ and $y=Y_{b,j}$ and summing over $b$ gives
\begin{align*}
\frac{1}{B}\sum_{b=1}^B X_{b,j}Y_{b,j} \geq \frac{1}{B}\sum_{b=1}^B (X_{b,j}+Y_{b,j}-1).
\end{align*}
By the definition of the empirical selection frequency $\hat{\pi}_j$, the right-hand side equals $2\hat{\pi}_j-1$.
Therefore, if $j \in \hat S_{\mathrm{stab}}(\lambda,\pi_{\mathrm{thr}})$, then $\hat{\pi}_j \geq \pi_{\mathrm{thr}}$, and hence
\begin{align*}
2\pi_{\mathrm{thr}}-1
\leq
\frac{1}{B}\sum_{b=1}^B X_{b,j}Y_{b,j}.
\end{align*}
Since $\pi_{\mathrm{thr}}>1/2$, the denominator $2\pi_{\mathrm{thr}}-1$ is positive, so
\begin{align*}
\mathbb{1}_{\{j \in \hat S_{\mathrm{stab}}(\lambda,\pi_{\mathrm{thr}})\}}
\leq
\frac{1}{2\pi_{\mathrm{thr}}-1}
\frac{1}{B}\sum_{b=1}^B X_{b,j}Y_{b,j}.
\end{align*}
[guided]
Fix a variable $j \in \{1,\dots,p\}$. We want to translate the condition that $j$ is selected often across all half-samples into a statement about being selected in both halves of the same complementary pair. For each pair index $b \in \{1,\dots,B\}$ define $X_{b,j}:=\mathbb{1}_{\{j \in A_\lambda(I_b)\}}$ and $Y_{b,j}:=\mathbb{1}_{\{j \in A_\lambda(I_b^c)\}}$. These two indicator variables are well-defined because the theorem declares $A_\lambda$ as a map from admissible subsample index sets $J\subset\{1,\dots,n\}$ to selected-variable sets $A_\lambda(J)\subset\{1,\dots,p\}$, and both members of each complementary pair are admissible by construction. Define the empirical [stability-selection](/page/Stability%20Selection) frequency $\hat{\pi}_j$ by
\begin{align*}
\hat{\pi}_j:=\frac{1}{2B}\sum_{b=1}^B (X_{b,j}+Y_{b,j}).
\end{align*}
Thus $X_{b,j}=1$ means that $j$ is selected on the first half of pair $b$, $Y_{b,j}=1$ means that $j$ is selected on the complementary half, and $\hat{\pi}_j$ is the fraction of the $2B$ half-sample selections in which $j$ appears. The stability-selected set is defined from these empirical frequencies by
\begin{align*}
\hat S_{\mathrm{stab}}(\lambda,\pi_{\mathrm{thr}}):=\{j\in\{1,\dots,p\}:\hat\pi_j\geq\pi_{\mathrm{thr}}\}.
\end{align*}
The elementary binary inequality is
\begin{align*}
xy \geq x+y-1
\end{align*}
for $x,y \in \{0,1\}$. Applying this to $x=X_{b,j}$ and $y=Y_{b,j}$ gives
\begin{align*}
X_{b,j}Y_{b,j} \geq X_{b,j}+Y_{b,j}-1.
\end{align*}
Averaging over all complementary pairs yields
\begin{align*}
\frac{1}{B}\sum_{b=1}^B X_{b,j}Y_{b,j} \geq \frac{1}{B}\sum_{b=1}^B (X_{b,j}+Y_{b,j}-1).
\end{align*}
Expanding the average gives
\begin{align*}
\frac{1}{B}\sum_{b=1}^B (X_{b,j}+Y_{b,j}-1)=\frac{1}{B}\sum_{b=1}^B (X_{b,j}+Y_{b,j})-1.
\end{align*}
By this definition of $\hat{\pi}_j$, we obtain
\begin{align*}
\frac{1}{B}\sum_{b=1}^B (X_{b,j}+Y_{b,j})-1=2\hat{\pi}_j-1.
\end{align*}
Now suppose $j \in \hat S_{\mathrm{stab}}(\lambda,\pi_{\mathrm{thr}})$. By the definition of the stability-selected set, $\hat{\pi}_j \geq \pi_{\mathrm{thr}}$. Substituting this lower bound into the previous inequality gives
\begin{align*}
\frac{1}{B}\sum_{b=1}^B X_{b,j}Y_{b,j}
\geq
2\hat{\pi}_j-1
\geq
2\pi_{\mathrm{thr}}-1.
\end{align*}
The assumption $\pi_{\mathrm{thr}}>1/2$ is used exactly here: it makes $2\pi_{\mathrm{thr}}-1>0$, so division by this quantity is legitimate. Therefore
\begin{align*}
\mathbb{1}_{\{j \in \hat S_{\mathrm{stab}}(\lambda,\pi_{\mathrm{thr}})\}}
\leq
\frac{1}{2\pi_{\mathrm{thr}}-1}
\frac{1}{B}\sum_{b=1}^B X_{b,j}Y_{b,j}.
\end{align*}
This inequality says that a variable cannot cross a threshold above one half unless it appears in both halves of enough complementary pairs.
[/guided]
[/step]
[step:Sum the simultaneous-selection bound over null variables]
Using the inequality from the previous step and summing over $j \in N$, we first have
\begin{align*}
V=\sum_{j \in N}\mathbb{1}_{\{j \in \hat S_{\mathrm{stab}}(\lambda,\pi_{\mathrm{thr}})\}}.
\end{align*}
The previous step therefore gives
\begin{align*}
V \leq \frac{1}{2\pi_{\mathrm{thr}}-1}\frac{1}{B}\sum_{b=1}^B\sum_{j \in N}\mathbb{1}_{\{j \in A_\lambda(I_b)\}}\mathbb{1}_{\{j \in A_\lambda(I_b^c)\}}.
\end{align*}
For each $b \in \{1,\dots,B\}$, the inner sum equals $|A_\lambda(I_b) \cap A_\lambda(I_b^c) \cap N|$, so
\begin{align*}
V \leq \frac{1}{2\pi_{\mathrm{thr}}-1}\frac{1}{B}\sum_{b=1}^B |A_\lambda(I_b) \cap A_\lambda(I_b^c) \cap N|.
\end{align*}
The last equality is the definition of cardinality of the intersection: the inner sum counts exactly those null variables selected by both members of complementary pair $b$.
[guided]
The previous step gave a pointwise inequality for each individual variable $j$. To turn that into a false-discovery count, we sum only over the null variables $j\in N$, because
\begin{align*}
V=|\hat S_{\mathrm{stab}}(\lambda,\pi_{\mathrm{thr}})\cap N|
=\sum_{j\in N}\mathbb{1}_{\{j\in \hat S_{\mathrm{stab}}(\lambda,\pi_{\mathrm{thr}})\}}.
\end{align*}
Substituting the individual bound from the previous step gives
\begin{align*}
V \leq \frac{1}{2\pi_{\mathrm{thr}}-1}\frac{1}{B}\sum_{b=1}^B\sum_{j \in N}\mathbb{1}_{\{j \in A_\lambda(I_b)\}}\mathbb{1}_{\{j \in A_\lambda(I_b^c)\}}.
\end{align*}
For a fixed pair index $b$, the product of indicators is $1$ exactly when the null variable $j$ belongs to both selected sets $A_\lambda(I_b)$ and $A_\lambda(I_b^c)$. Therefore the inner sum counts the cardinality of the triple intersection, namely
\begin{align*}
\sum_{j \in N}\mathbb{1}_{\{j \in A_\lambda(I_b)\}}\mathbb{1}_{\{j \in A_\lambda(I_b^c)\}}
=|A_\lambda(I_b) \cap A_\lambda(I_b^c) \cap N|.
\end{align*}
Thus
\begin{align*}
V \leq \frac{1}{2\pi_{\mathrm{thr}}-1}\frac{1}{B}\sum_{b=1}^B |A_\lambda(I_b) \cap A_\lambda(I_b^c) \cap N|.
\end{align*}
[/guided]
[/step]
[step:Take conditional subsampling expectation and apply the assumed product bound]
Let $\mathcal D$ denote the observed sample. For every integrable random variable $Z$ depending on the subsampling randomness, define the conditional subsampling expectation by
\begin{align*}
\mathbb E_{\mathrm{sub}}[Z]:=\mathbb E[Z\mid \mathcal D].
\end{align*}
The inequality from the previous step is pointwise in the subsampling randomness, and all quantities are nonnegative finite sums. Taking $\mathbb E_{\mathrm{sub}}$ of both sides therefore gives
\begin{align*}
\mathbb E_{\mathrm{sub}}[V] \leq \frac{1}{2\pi_{\mathrm{thr}}-1}\mathbb E_{\mathrm{sub}}\left[\frac{1}{B}\sum_{b=1}^B |A_\lambda(I_b) \cap A_\lambda(I_b^c) \cap N|\right].
\end{align*}
By the complementary-pairs product bound stated explicitly in the theorem hypothesis,
\begin{align*}
\mathbb E_{\mathrm{sub}}
\left[
\frac{1}{B}
\sum_{b=1}^B
|A_\lambda(I_b) \cap A_\lambda(I_b^c) \cap N|
\right]
\leq
\frac{q^2}{p}.
\end{align*}
Combining these two inequalities yields
\begin{align*}
\mathbb E_{\mathrm{sub}}[V] \leq \frac{1}{2\pi_{\mathrm{thr}}-1}\frac{q^2}{p}=\frac{q^2}{(2\pi_{\mathrm{thr}}-1)p}.
\end{align*}
This is the desired false discovery bound.
[guided]
Let $\mathcal D$ denote the observed sample. The subsampling expectation is conditional expectation over the random complementary-pair draws, namely
\begin{align*}
\mathbb E_{\mathrm{sub}}[Z]:=\mathbb E[Z\mid \mathcal D]
\end{align*}
for every integrable random variable $Z$ depending on the subsampling randomness. The bound from the previous step holds for every realised collection of complementary pairs, and its right-hand side is a finite nonnegative sum. Therefore conditional expectation preserves the inequality and gives
\begin{align*}
\mathbb E_{\mathrm{sub}}[V] \leq \frac{1}{2\pi_{\mathrm{thr}}-1}\mathbb E_{\mathrm{sub}}\left[\frac{1}{B}\sum_{b=1}^B |A_\lambda(I_b) \cap A_\lambda(I_b^c) \cap N|\right].
\end{align*}
Now we use the assumed complementary-pairs product bound. Its hypothesis is exactly the quantity appearing on the right-hand side:
\begin{align*}
\mathbb E_{\mathrm{sub}}
\left[
\frac{1}{B}
\sum_{b=1}^B
|A_\lambda(I_b) \cap A_\lambda(I_b^c) \cap N|
\right]
\leq
\frac{q^2}{p}.
\end{align*}
Substituting this estimate into the conditional expectation inequality yields
\begin{align*}
\mathbb E_{\mathrm{sub}}[V] \leq \frac{1}{2\pi_{\mathrm{thr}}-1}\frac{q^2}{p}=\frac{q^2}{(2\pi_{\mathrm{thr}}-1)p}.
\end{align*}
This proves the stated false discovery bound.
[/guided]
[/step]
