Adaptive conditional failure budgets compose by a union bound

The stage-failure events are part of the given execution model. The events $F_1,\dots ,F_L$ are pairwise disjoint: one execution cannot have two different first failing stages. Their union is exactly the event that some stage fails, because every failing finite history has a least index at which failure first occurs.

For $r$ mutually independent trials with failure events $E_j$, [F3] gives $\mathbb{P}({\bigcap }_{j=1}^r{E}_j)={\prod }_{j=1}^r\mathbb{P}(E_j)\le (1-p{)}^r$. Apply [F4] to obtain the stated exponential bound, including $p=0$ and $p=1$.

For fixed $j$, partition $F_j$ by the finite successful histories $h$ that reach stage $j$. For each such history, the hypothesis gives $\mathbb{P}(F_j\mid h)\le {\delta }_j$; histories of probability zero contribute zero. Summing the conditional probabilities weighted by $\mathbb{P}(h)$ gives $\mathbb{P}(F_j)\le {\delta }_j\mathbb{P}(\text{stage }j\text{ is reached successfully})\le {\delta }_j$. By [F2] and step 1.1, $\mathbb{P}({\bigcup }_j{F}_j)={\sum }_j\mathbb{P}(F_j)\le {\sum }_j{\delta }_j$.

Let $T_r$ be the number of trials used by the capped repeat-until-success procedure, with $T_r=r$ if all $r$ trials fail. For $1\le j\le r$, $\{T_r\ge j\}$ is the event that the first $j-1$ trials fail, so $\mathbb{P}(T_r\ge j)=(1-p{)}^{j-1}$. For a finite nonnegative integer-valued variable, $\mathbb{E}[T_r]={\sum }_{j=1}^r\mathbb{P}(T_r\ge j)$ by summing its finite outcome weights; hence for $p>0$ the finite geometric sum is $[1-(1-p{)}^r]\mathrm{/}p$. By step 1.2, $(1-p{)}^r\to 0$ as $r\to \mathrm{\infty }$, so this capped expectation tends to $1\mathrm{/}p$.