\noindent \textbf{From expectation to high probability.}

%\begin{lemma}\label{lemma:nd}
%    Let $A\subseteq\mathcal{U}$ and $x=(v,c)\in\mathcal{U}\setminus A$, then
%    the function $b\mapsto \mathcal{O}(A\cup\{x\},b)-\mathcal{O}(A,b)$ is
%    non-decreasing over $\reals^+$.
%\end{lemma}






\begin{proof}[of Proposition~\ref{main_result}]
    For each realization of the neighbors $R$, let us define by $X_R$ the
    random set which includes each $u\in R$ with probability $q_u$ on the
    second day and:
    \begin{displaymath}
        \tilde{X}_R=
    \begin{cases}
        X_R&\text{if } |X_R|\leq t\\
        \emptyset&\text{otherwise}
    \end{cases}
    \end{displaymath}
    where $t = k-|S|$. $\tilde{X}_R$ is a random variable over the feasible
    solutions on the second day. As a consequence:
    \begin{displaymath}
        A(S) \geq \sum_{R\subseteq\neigh{S}} p_R\mathbb{E}\big[f(\tilde{X}_R)\big]
    \end{displaymath}
    Let us define by $Y$ the random set which includes each $u\in\neigh{X}$
    with probability $p_uq_u$ and:
    \begin{displaymath}
        \tilde{Y}=
        \begin{cases}
            Y&\text{if } |Y|\leq t\\
            \emptyset&\text{otherwise}
        \end{cases}.
    \end{displaymath}
    It is easy to see that $\tilde{X}_R$ is the conditional expectation of
    $\tilde{Y}$ given
    $R$. Hence:
    \begin{displaymath}
        \sum_{R\subseteq\neigh{S}} p_R\mathbb{E}\big[f(\tilde{X}_R)\big]
        = \mathbb{E}\big[f(\tilde{Y})\big]
    \end{displaymath}
    But:
    \begin{align*}
        \mathbb{E}\big[f(\tilde{Y})\big]
        &=\sum_{T\subseteq\neigh{X}}\mathbb{P}\big[\tilde{Y}=T\big]f(T)
    = \sum_{\substack{T\subseteq\neigh{X}\\|T|\leq
    t}}\mathbb{P}\big[Y=T\big]f(T)\\
    &= \mathbb{E}\big[f(Y)\big]-\sum_{\substack{T\subseteq\neigh{X}\\|T|>
    t}}\mathbb{P}\big[Y=T\big]f(T)
    \end{align*}
    Roughly:
    \begin{displaymath}
        \sum_{\substack{T\subseteq\neigh{X}\\|T|>
        t}}\mathbb{P}\big[Y=T\big]f(T)\leq
        \frac{1}{2}\mathbb{E}\big[f(Y)\big]
    \end{displaymath}
    Combining the above inequalities we get:
    \begin{displaymath}
        A(S)\geq \frac{1}{2} \mathbb{E}\big[f(Y)\big]
    \end{displaymath}
    But $\mathbb{E}\big[f(Y)\big]$ is precisely the value of the non-adaptive
    solution computed by Algorithm~\ref{alg:comb} which is
    a $\left(1-\frac{1}{e}\right)$ approximation of the
    optimal non adaptive solution. Hence:
    \begin{displaymath}
        A(S) \geq \frac{1}{2}\left(1-\frac{1}{e}\right) OPT_{NA}
    \end{displaymath}
    Finally, we conclude with Proposition~\ref{prop:gap}
\end{proof}