[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*}[/step]

[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: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$.[/step]

[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: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.[/step]

[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]