# 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) > 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 > 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) > 0\}$ is bounded below by some $\epsilon > 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.

• Isn't it just the case that $K_r(x) = K_r^i(x)$ for some $i$, so, by definition of supremum, $K_r(x) \le \sup_i K_r^i(x)$? – Sasho Nikolov Dec 10 '16 at 0:05
• I guess I don't see why $K_r(x) = K_r^i(x)$ for some $i$. If I know $a(x) > \epsilon$ whenever $a(x)$ is non-zero, then I think I see how you might be able to argue that, since then perhaps you consider i such that $i \cdot \epsilon > r$. – user43585 Dec 10 '16 at 2:03
• By the way, I think a more standard way of dealing with this kind of material is via random sequences with stopping times, analyzed via Wald's equation and its variants, including so-called "drift" analyses. You can read more about that here: algnotes.info/on/background/stopping-times . – Neal Young Dec 15 '16 at 18:46

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 > 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 > r] ~~=~ \sup_i \Pr[\textstyle\sum_{j=0}^{i-1} a_j > r].$$ Define random variable $T = \min\{i : \sum_{j=0}^{i-1} a_j > 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 < \infty] ~=~ \sup_i \Pr[T \le i].$$ But that equation follows from basic definitions as follows: $$\Pr[T < \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
• Let $T(x)$ be any random function satisfying the recurrence. Let $T^*(x)=\sum_{j=0}^\infty a_j$ be $T$ as in the answer. "Couple" $T$ and $T^*$ in the natural way to the same random experiment. Let r.v. $N(x)=\min\{i : h^{(i)}(x) \le d\}$ be the number of "iterations". In outcomes with $N(x)<\infty$, the values of $T(x)$ and $T^*(x)$ must be equal. So, if $\Pr[N(x)<\infty] = 1$, we must have $\Pr[T(x) = T^*(x)] = 1$, and in that sense $T$ must be the same as $T^*$. (In contrast, consider $T(x) = x/2 + T(x/2)$ and $T(0)=0$. Both $T(x)=x$ and $T(x)=x+1$ (for $x>0$) meet this recurrence.) – Neal Young Dec 15 '16 at 16:45
• (continued from previous comment). Consider the recurrence relation $T(x)=T(h(x))$, where $h(x)$ is 0 with probability 1/2 and $x$ otherwise. Then $T^*(x)$ as defined in the answer is identically zero, even in the (zero probability) event that $N(x)=\infty$. But it also consistent with the recurrence to take $T(x)$ to be the random variable that is zero when $N(x)<\infty$, and $1$ otherwise. Then arguably $T(x)$ is not identical to $T^*(x)$ even though $\Pr[N(x)<\infty]=1$. You can construct more interesting variations of this example... – Neal Young Dec 15 '16 at 18:33