[proofplan]
The proof separates the algorithm into one fixed rejection-sampling stage and the adaptive update. At a fixed stage, the proposal density is the exponential envelope normalised by its mass, and multiplying this density by the pointwise acceptance probability cancels the envelope exactly, leaving $\gamma/C_S$. Integrating gives the acceptance probability $Z/C_S$, and conditioning on acceptance gives the target density $\gamma/Z$. Finally, adding a rejected point only adds one more tangent line to the family whose pointwise minimum defines the hull, so the hull can only decrease.
[/proofplan]
[step:Verify that tangent lines dominate the log-density]
Fix a finite support set $S \subset \operatorname{int}(I)$ and a point $s \in S$. Since $\ell: I \to \mathbb{R}$ is concave and differentiable at $s$, the first-order concavity inequality gives
\begin{align*}
\ell(x) \le \ell(s) + \ell'(s)(x-s)
\end{align*}
for every $x \in I$. Therefore $\ell(x) \le a_s(x)$ for every $x \in I$ and every $s \in S$. Taking the minimum over $s \in S$ gives
\begin{align*}
\ell(x) \le u_S(x)
\end{align*}
for every $x \in I$ whenever $u_S$ is finite.
Consequently,
\begin{align*}
0 < \frac{\gamma(x)}{\exp(u_S(x))} = \exp(\ell(x)-u_S(x)) \le 1
\end{align*}
for every $x \in I$. Hence the stated acceptance rule defines a valid conditional acceptance probability.
[/step]
[step:Compute the accepted density at a fixed stage]
Fix one stage and write $S$ for the current finite support set. Define the envelope normalising constant
\begin{align*}
C_S := \int_I \exp(u_S(x))\, d\mathcal{L}^1(x).
\end{align*}
By hypothesis, $0 < C_S < \infty$, because $\exp(u_S(x)) > 0$ for every $x \in I$ and the integral is finite. The proposal density $r_S: I \to [0,\infty)$ is
\begin{align*}
r_S(y) = \frac{\exp(u_S(y))}{C_S}.
\end{align*}
Let $B \subset I$ be a Borel set. Since $V$ is independent of $Y$ and $V \sim \operatorname{Unif}(0,1)$, the [conditional probability](/page/Conditional%20Probability) of acceptance given $Y=y$ is
\begin{align*}
\mathbb{P}(A_S \mid Y=y) = \frac{\gamma(y)}{\exp(u_S(y))}.
\end{align*}
Thus
\begin{align*}
\mathbb{P}(Y \in B \text{ and } A_S) = \int_B r_S(y)\frac{\gamma(y)}{\exp(u_S(y))}\, d\mathcal{L}^1(y).
\end{align*}
Substituting the formula for $r_S$ gives
\begin{align*}
\mathbb{P}(Y \in B \text{ and } A_S) = \int_B \frac{\gamma(y)}{C_S}\, d\mathcal{L}^1(y).
\end{align*}
[guided]
We fix the support set $S$ because the adaptive part of the algorithm changes only between proposals. During one proposal, $S$ is fixed, so the current upper hull $u_S: I \to \mathbb{R}$ and the constant
\begin{align*}
C_S := \int_I \exp(u_S(x))\, d\mathcal{L}^1(x)
\end{align*}
are deterministic quantities. The assumptions give $0 < C_S < \infty$, so
\begin{align*}
r_S: I &\to [0,\infty)
\end{align*}
\begin{align*}
y &\mapsto \frac{\exp(u_S(y))}{C_S}
\end{align*}
is a probability density with respect to $\mathcal{L}^1$.
Now take a Borel set $B \subset I$. We want the unnormalised law of proposals that both land in $B$ and are accepted. Since $V$ is independent of $Y$ and has the uniform distribution on $(0,1)$, conditioning on the realised proposal value $Y=y$ gives
\begin{align*}
\mathbb{P}(A_S \mid Y=y) = \mathbb{P}\left(V \le \frac{\gamma(y)}{\exp(u_S(y))}\right) = \frac{\gamma(y)}{\exp(u_S(y))}.
\end{align*}
The last equality is valid because the previous step proved $0 \le \gamma(y)/\exp(u_S(y)) \le 1$.
Therefore the joint probability of proposing in $B$ and accepting is obtained by multiplying the proposal density by the conditional acceptance probability:
\begin{align*}
\mathbb{P}(Y \in B \text{ and } A_S) = \int_B r_S(y)\frac{\gamma(y)}{\exp(u_S(y))}\, d\mathcal{L}^1(y).
\end{align*}
Substituting the definition of $r_S$ cancels the envelope exactly:
\begin{align*}
r_S(y)\frac{\gamma(y)}{\exp(u_S(y))} = \frac{\exp(u_S(y))}{C_S}\frac{\gamma(y)}{\exp(u_S(y))} = \frac{\gamma(y)}{C_S}.
\end{align*}
Hence
\begin{align*}
\mathbb{P}(Y \in B \text{ and } A_S) = \int_B \frac{\gamma(y)}{C_S}\, d\mathcal{L}^1(y).
\end{align*}
This cancellation is the core rejection-sampling mechanism: the proposal over-samples according to the envelope, and the acceptance probability removes exactly the excess factor.
[/guided]
[/step]
[step:Condition on acceptance to obtain the target density]
Apply the previous formula with $B=I$. Since
\begin{align*}
Z := \int_I \gamma(y)\, d\mathcal{L}^1(y),
\end{align*}
we get
\begin{align*}
\mathbb{P}(A_S) = \mathbb{P}(Y \in I \text{ and } A_S) = \frac{Z}{C_S}.
\end{align*}
Because $0 < Z < \infty$ and $0 < C_S < \infty$, this acceptance probability is positive.
For any Borel set $B \subset I$, the conditional probability of $Y \in B$ given acceptance is therefore
\begin{align*}
\mathbb{P}(Y \in B \mid A_S) = \frac{\mathbb{P}(Y \in B \text{ and } A_S)}{\mathbb{P}(A_S)}.
\end{align*}
Using the formulas already obtained,
\begin{align*}
\mathbb{P}(Y \in B \mid A_S) = \frac{\int_B \gamma(y)C_S^{-1}\, d\mathcal{L}^1(y)}{ZC_S^{-1}}.
\end{align*}
Thus
\begin{align*}
\mathbb{P}(Y \in B \mid A_S) = \int_B \frac{\gamma(y)}{Z}\, d\mathcal{L}^1(y).
\end{align*}
Hence the accepted proposal has density $\gamma/Z$ with respect to $\mathcal{L}^1$ on $I$.
[/step]
[step:Pass from one fixed stage to the adaptive algorithm]
In the adaptive algorithm, let $S_k$ denote the finite support set before the $k$-th proposal, and let $u_{S_k}: I \to \mathbb{R}$ denote the corresponding upper hull. Conditional on all previous proposals, uniforms, acceptances, and rejections, the set $S_k$ is fixed. The $k$-th proposal $Y_k$ is then drawn from the density
\begin{align*}
r_{S_k}(y) = \frac{\exp(u_{S_k}(y))}{C_{S_k}},
\end{align*}
where
\begin{align*}
C_{S_k} = \int_I \exp(u_{S_k}(x))\, d\mathcal{L}^1(x),
\end{align*}
and the $k$-th uniform [random variable](/page/Random%20Variable) $V_k$ is independent of $Y_k$ conditional on the past.
The fixed-stage calculation applies conditionally on the past with $S=S_k$. Therefore, on the event that the $k$-th proposal is accepted, the conditional law of $Y_k$ is
\begin{align*}
\mathbb{P}(Y_k \in B \mid \text{past before stage } k, A_{S_k}) = \int_B \frac{\gamma(y)}{Z}\, d\mathcal{L}^1(y)
\end{align*}
for every Borel set $B \subset I$. Thus every accepted value is conditionally distributed according to the target density $\gamma/Z$ given the current support set. This proves exactness of accepted proposals despite adaptation between proposal stages.
[/step]
[step:Show that adding a rejected point cannot increase the upper hull]
Let $S \subset \operatorname{int}(I)$ be a finite support set, and let $y \in \operatorname{int}(I)$ be a rejected proposal added to the support set. The updated support set is $S \cup \{y\}$. Its upper hull is
\begin{align*}
u_{S \cup \{y\}}(x) = \min_{s \in S \cup \{y\}} a_s(x)
\end{align*}
for every $x \in I$. Since $S \subset S \cup \{y\}$, the minimum over $S \cup \{y\}$ is bounded above by the minimum over $S$:
\begin{align*}
u_{S \cup \{y\}}(x) \le \min_{s \in S} a_s(x) = u_S(x).
\end{align*}
Therefore adding a rejected support point cannot increase the tangent upper hull pointwise.
Since $\ell \le u_{S \cup \{y\}} \le u_S$ and $\exp$ is increasing, the updated envelope remains an upper envelope for $\gamma$ and satisfies
\begin{align*}
\int_I \exp(u_{S \cup \{y\}}(x))\, d\mathcal{L}^1(x) \le \int_I \exp(u_S(x))\, d\mathcal{L}^1(x) < \infty.
\end{align*}
Thus the next adaptive stage again has a finite integrable envelope, and the preceding conditional correctness argument may be iterated. This completes the proof.
[/step]
