Understanding proof of Theorem 3.3 in Karp's "Probabilistic Recurrence Relations" Background: In Karp's paper on Probabilistic Recurrence Relations, he develops tail-bounds for random variables satisfying the following recurrence:

$$ T(x) = a(x) + T(h(x)) $$

where $T(x)$ is a random-variable that can be thought of as the cost or run-time of some randomized algorithm when run on an instance of size $x$. Here, $a$ is some deterministic "toll" cost involved in processing the instance prior to a recursive call, and $h(x)$ is a real-valued random-variable in the range [0, x], which gives the size of the instance in the recursive call of $T$.

Assuming the expectation of $h(x)$ is bounded by some function $m(x)$, Karp then considers the deterministic recurrence relation:

$$ u(x) = a(x) + u(m(x)) $$

He then derives various tail-bounds on $T$ in terms of $m$, $a$, and $u$.

Question: My question is about one of the steps in the proof of Theorem 3.3 of the paper. The exact statement of the result is not needed to understand the step I'm stuck on. In this theorem, $a$ and $m$ are assumed to be continuous, there is some $d$ such that $a(x) = 0$ on the interval $[0, d]$, $a$ is strictly increasing on $[d, \infty)$, and $m(x)/x$ is assumed to be non-decreasing.

Karp then defines $K_r(x) = \mathrm{Prob}[T(x) &gt; r]$. He notes that $K_r(x) = E[K_{r - a(x)}(h(x))]$. His goal is to bound $K_r(x)$ by some quantity. To do so, he starts by defining a sequence of functions $K_r^i$ indexed by natural number $i$ as: $K_r^0(x) = 1$ for $r \leq 0$ and $K_r^0(x) = 0$ for $r &gt; 0$; and inductively, $K_r^{i+1}(x) = E[K_{r-a(x)}^i(h(x))]$. He then says that $K_r(x) \leq \sup_{i} K_r^i(x)$, and proceeds to bound each of the $K_r^i$, thus deriving a bound on the supremum and in turn $K_r$.

However, I do not understand why $K_r(x) \leq \sup_{i} K_r^i(x)$. This step is stated without elaboration, so I'm guessing I'm missing something obvious. I see that the $K_r^i$ are defined recursively in terms of the same recurrence about expectation that $K_r$ satisfies, and the supremum of the $K_r^i$ should be a fixed-point of this recurrence, sort of like the construction in Kleene's fixed-point theorem. But that would seem to give a least fixed point, which would justify the opposite inequality: $\sup K_r^i(x) \leq K_r(x)$. I think I see a way to make the argument go through if $\{a(x) | a(x) &gt; 0\}$ is bounded below by some $\epsilon &gt; 0$, but that contradicts the continuity assumption on $a$. Banach's fixed-point theorem would give a unique fixed point, which would do, but I do not see a sense in which this is a contraction.

Other references: this result is mentioned in Chapter 4 of Dubhashi and Panconesi's textbook on Concentration of Measure, but the proof is not included. Chaudhuri and Dubhashi's paper "Probabilistic Recurrence Relations Revisited" proves a similar result but the proof technique is different, so it does not help me understand this argument.
In some cases the recurrence for $T$ does not determine it uniquely. We take the following interpretation of $T$, which gives the minimum $T$ consistent with the recurrence. 

Repeatedly substitute $T(x) = a(x) + T(h(x))$ to expand $T(x)$ as the (random) sum
$$
T(x) = a(x) + a(h(x)) + a(h(h(x))) + \cdots = \sum_{j=1}^\infty a_j
$$
where $a_i = a(h^{(i-1)}(x))$,
in which $h^{(0)}(x) = x$ and and $h^{(i+1)}(x) = h(h^{(i)}(x))$.

lemma. With this definition of $T$, 
we have $K_r(x) \le \sup_i K^i_r(x)$.

Proof.
Inspecting the definitions of $K^i_r$ and $K_r$, we have
$$
K_r(x) = \Pr[\textstyle\sum_{j=0}^\infty a_j &gt; r]
~~\mbox{and}~~
K^i_r(x) = \Pr[\textstyle\sum_{j=0}^{i-1} a_j \ge r].
$$
To prove the lemma, we will show something slightly stronger, namely
$$
\Pr[\textstyle\sum_{j=0}^\infty a_j &gt; r] ~~=~ \sup_i \Pr[\textstyle\sum_{j=0}^{i-1} a_j &gt; r].
$$
Define random variable $T = \min\{i : \sum_{j=0}^{i-1} a_j &gt; r\}$ to be the first step at which the sum of terms exceeds $r$ (with $T=\infty$ if that never happens).
Rewriting the desired equation in this notation, we want to show
$$
\textstyle \Pr[T &lt; \infty] ~=~ \sup_i \Pr[T \le i].
$$
But that equation follows from basic definitions as follows:
$$
\Pr[T &lt; \infty] 
= \sum_{j=0}^\infty \Pr[T = j] 
= \lim_{i\rightarrow\infty} \sum_{j=0}^i \Pr[T=j]
= \lim_{i\rightarrow\infty} \Pr[T \le i]
= \sup_i \Pr[T \le i ].$$
QED