11institutetext: School of Computer Science, Peking University, China
11email<EMAIL_ADDRESS>Department of Computer Science,
Shanghai Jiao Tong University, China
22email<EMAIL_ADDRESS>IST Austria
33email<EMAIL_ADDRESS>The Hong Kong
University of Science and Technology
44email<EMAIL_ADDRESS>
# Automated Tail Bound Analysis for Probabilistic Recurrence
Relations††thanks: Mainland Chinese authors are ordered by contribution, while
Austrian and Chinese Hong Kong authors are ordered alphabetically. The code
and benchmarks are available at https://github.com/boyvolcano/PRR

Yican Sun 11 Hongfei Fu Corresponding Author22 Krishnendu Chatterjee 33
Amir Kafshdar Goharshady 44

###### Abstract

Probabilistic recurrence relations (PRRs) are a standard formalism for
describing the runtime of a randomized algorithm. Given a PRR and a time limit
$\kappa$, we consider the classical concept of tail probability
$\Pr[T\geq\kappa]$, i.e., the probability that the randomized runtime $T$ of
the PRR exceeds the time limit $\kappa$. Our focus is the formal analysis of
tail bounds that aims at finding a tight asymptotic upper bound
$u\geq\Pr[T\geq\kappa]$ in the time limit $\kappa$. To address this problem,
the classical and most well-known approach is the cookbook method by Karp
(JACM 1994), while other approaches are mostly limited to deriving tail bounds
of specific PRRs via involved custom analysis.

In this work, we propose a novel approach for deriving exponentially-
decreasing tail bounds (a common type of tail bounds) for PRRs whose
preprocessing time and random passed sizes observe discrete or (piecewise)
uniform distribution and whose recursive call is either a single procedure
call or a divide-and-conquer. We first establish a theoretical approach via
Markov’s inequality, and then instantiate the theoretical approach with a
template-based algorithmic approach via a refined treatment of exponentiation.
Experimental evaluation shows that our algorithmic approach is capable of
deriving tail bounds that are (i) asymptotically tighter than Karp’s method,
(ii) match the best-known manually-derived asymptotic tail bound for
QuickSelect, and (iii) is only slightly worse (with a $\log\log n$ factor)
than the manually-proven optimal asymptotic tail bound for QuickSort.
Moreover, our algorithmic approach handles all examples (including realistic
PRRs such as QuickSort, QuickSelect, DiameterComputation, etc.) in less than
0.1 seconds, showing that our approach is efficient in practice.

##  1 Introduction

Probabilistic program verification is a fundamental area in formal
verification [4]. It extends the classical (non-probabilistic) program
verification by considering randomized computation in a program and hence can
be applied to the formal analysis of probabilistic computations such as
probabilistic models [16], randomized algorithms [33, 11, 32, 3], etc. In this
line of research, verifying the time complexity of probabilistic recurrence
relations (PRRs) is an important subject [33, 11]. PRRs are a simplified form
of recursive probabilistic programs and extend recurrence relations by
incorporating randomization such as randomized preprocessing and divide-and-
conquer. They are widely used in analyzing the time complexity of randomized
algorithms (e.g., QuickSort [18], QuickSelect [19], and DiameterComputation
[29, Chapter 9]). Compared with probabilistic programs, PRRs abstract away
detailed computational aspects, such as problem-specific divide-and-conquer
and data-structure manipulations, and include only key information on the
runtime of the underlying randomized algorithm. Hence, PRRs provide a clean
model for time-complexity analysis of randomized algorithms and randomized
computations in a general sense.

In this work, we focus on the formal analysis of PRRs and consider the
fundamental problem of tail bound analysis that aims at bounding the
probability that a given PRR does not terminate within a prescribed time
limit. In the literature, prominent works on tail bound analysis include the
following. First, Karp proposed a classic “cookbook” formula [23] similar to
Master Theorem. This method is further improved, extended, and mechanized by
follow-up works [15, 33, 6]. While Karp’s method has a clean form and is easy
to use and automate, the bounds from the method are known to be not tight (see
e.g. [28, 17]). Second, the works [28] and resp. [17] performed ad-hoc custom
analysis to derive asymptotically tight tail bounds for the PRRs of QuickSort
and resp. QuickSelect, respectively. These methods require manual effort and
do not have the generality to handle a wide class of PRRs.

From the literature, an algorithmic approach capable of deriving tight tail
bounds over a wide class of PRRs is a major unresolved problem. Motivated by
this challenge, we have the following contributions to this work:

  * •

Based on Markov’s inequality, we propose a novel theoretical approach to
derive exponentially-decreasing tail bounds, a common type for many randomized
algorithms. We further show that our theoretical approach can always derive an
exponentially-decreasing tail bound at least as tight as Karp’s method under
mild assumptions.

  * •

From our theoretical approach, we propose a template-based algorithmic
approach for a wide class of PRRs that have (i) common probability
distributions such as (piecewise) uniform distribution and discrete
probability distributions and (ii) either a single call or a divide-and-
conquer for the form of the recursive call. The technical novelties in our
algorithm lie in a refined treatment of the estimation of the exponential term
arising from our theoretical approach via integrals, suitable over-
approximation, and the monotonicity of the template function.

  * •

Experiments show that our algorithmic approach derives asymptotically tighter
tail bounds when compared with Karp’s method. Furthermore, the tail bounds
derived from our approach match the best-known bound for QuickSelect [17], and
are only slightly worse by a $\log\log n$ factor against the optimal manually-
derived bound for QuickSort [28]. Moreover, our algorithm synthesizes each of
these tail bounds in less than 0.1 seconds and is efficient in practice.

A limitation of our approach is that we do not consider the transformation
from a realistic implementation of a randomized algorithm into its PRR
representation. However, such a transformation would require examining a
diversified number of randomization patterns (e.g., randomized divide-and-
conquer) in randomized algorithms and thus is an orthogonal direction. In this
work, we focus on the tail bound analysis and present a novel approach to
address this problem.

##  2 Preliminaries

Below we present necessary background in probability theory and the tail bound
analysis problem we consider.

A _probability space_ is a triple
$(\mathrm{\mathrm{\Omega}},\mathcal{F},\mathrm{Pr})$ such that
$\mathrm{\Omega}$ is a non-empty set termed as the _sample space_ ,
$\mathcal{F}$ is a _$\sigma$ -algebra_ over $\mathrm{\Omega}$ (i.e., a
collection of subsets of $\mathrm{\Omega}$ that contains the empty set
$\emptyset$ and is closed under complement and countable union), and
$\mathrm{Pr}(\cdot)$ is a _probability measure_ on $\mathcal{F}$ (i.e., a
function $\mathcal{F}\to[0,1]$ such that $\Pr(\mathrm{\Omega})=1$ and for
every pairwise disjoint set-sequence $A_{1},A_{2},\dots$ in $\mathcal{F}$, we
have that $\sum_{i\geq 1}\Pr(A_{i})=\Pr\left(\bigcup_{i\geq 1}A_{i}\right)$.

A _random variable_ $X$ from a probability space
$(\mathrm{\Omega},\mathcal{F},\mathrm{Pr})$ is an $\mathcal{F}$-measurable
function $X:\mathrm{\Omega}\to\mathbb{R}$, i.e., for every $d\in\mathbb{R}$,
we have that $\\{\omega\in\mathrm{\Omega}\mid X(\omega)<d\\}\in\mathcal{F}$.
We denote $\mathbb{E}[X]$ as its expected value; formally, we have
$\mathbb{E}[X]:=\int X\,\mathrm{d}\mathrm{Pr}$. A _discrete probability
distribution_ (DPD) over a countable set $U$ is a function $\eta:U\to[0,1]$,
such that $\sum_{u\in U}{\eta(u)}=1$. The _support_ of the DPD is defined as
$\mathrm{supp}(\eta):=\\{u\in U\mid\eta(u)>0\\}$. We abbreviate finite-support
DPD as FSDPD.

A _filtration_ of probability space $(\mathrm{\Omega},\mathcal{F},\Pr)$ is an
infinite sequence of $\\{\mathcal{F}_{n}\\}_{n\geq 0}$ of $\sigma$-algebra
over $\mathrm{\Omega}$ such that
$\mathcal{F}_{n}\subseteq\mathcal{F}_{n+1}\subseteq\mathcal{F}$ for every
$n\geq 0$. Intuitively, it models the information at the $n$-th step. A
_discrete-time stochastic process_ is an infinite sequence
$\mathrm{\Gamma}=\\{X_{n}\\}_{n\geq 0}$ of random variables from the
probability space $(\mathrm{\Omega},\mathcal{F},\Pr)$. The process
$\mathrm{\Gamma}$ is _adapted_ to a filtration $\\{\mathcal{F}_{n}\\}_{n\geq
0}$ if for all $n\geq 0$, $X_{n}$ is $\mathcal{F}_{n}$-measurable. Given a
filtration $\\{\mathcal{F}_{n}\\}_{n\geq 0}$, a _stopping time_ is a random
variable $\tau:\Omega\to\mathbb{N}$, such that for every $n\geq 0$,
$\\{\omega\in\mathrm{\Omega}\mid\tau(\omega)\leq n\\}\in\mathcal{F}_{n}$.

A discrete-time stochastic process $\Gamma=\\{X_{n}\\}_{n\in\mathbb{N}}$
adapted to a filtration $\\{\mathcal{F}_{n}\\}_{n\in\mathbb{N}}$ is a
_martingale_ (resp. _supermartingale_) if for every $n\in\mathbb{N}$,
$\mathbb{E}[|X_{n}|]<\infty$ and it holds a.s. that $\mathbb{E}\left[X_{n+1}\
|\ \mathcal{F}_{n}\right]=X_{n}$ (resp. $\mathbb{E}\left[X_{n+1}\ |\
\mathcal{F}_{n}\right]\leq X_{n}$). Intuitively, a martingale (resp.
supermartingale) is a discrete-time stochastic process in which for an
observer who has seen the values of $X_{0},\ldots,X_{n}$, the expected value
at the next step, i.e. $\mathbb{E}\left[X_{n+1}\ |\ \mathcal{F}_{n}\right]$,
is equal to (resp. no more than) the last observed value $X_{n}$. Also, note
that in a martingale, the observed values for $X_{0},\ldots,X_{n-1}$ do not
matter given that $\mathbb{E}\left[X_{n+1}\ |\ \mathcal{F}_{n}\right]=X_{n}.$
In contrast, in a supermartingale, the only requirement is that
$\mathbb{E}\left[X_{n+1}\ |\ \mathcal{F}_{n}\right]\leq X_{n}$ and hence
$\mathbb{E}\left[X_{n+1}\ |\ \mathcal{F}_{n}\right]$ may depend on
$X_{0},\ldots,X_{n-1}.$ Also, note that $\mathcal{F}_{n}$ might contain more
information than just the observations of $X_{i}$’s.

###### Example 1

Consider the classical gambler’s ruin: a gambler starts with $Y_{0}$ dollars
of money and bets continuously until he loses all of his money. If the bets
are unfair, i.e. the expected value of his money after a bet is less than its
expected value before the bet, then the sequence
$\\{Y_{n}\\}_{n\in\mathbb{N}_{0}}$ is a supermartingale. In this case, $Y_{n}$
is the gambler’s total money after $n$ bets. On the other hand, if the bets
are fair, then $\\{Y_{n}\\}_{n\in\mathbb{N}_{0}}$ is a martingale. See
Appendix 0.A for another illustrative example of martingales. ∎

We refer to standard textbooks (such as [37, 7]) for a detailed treatment of
all the concepts illustrated above.

###  2.1 Probabilistic Recurrence Relations

In this work, we focus on probabilistic recurrence relations (PRRs) that
describe the runtime behaviour of a single recursive procedure. Instead of
having a direct syntax for a PRR, we propose a mini programming language LRec
that captures a wide class of PRRs that have common probability distributions
such as (piecewise) uniform distributions and discrete probability
distributions, and whose recursive call consists of either a procedure call or
two procedure calls in a divide-and-conquer style. We present the grammar of
LRec in Figure 1.

(PRR) | proc | ::= | $\mathtt{def}\ p(n;c_{p})=\\{\mathsf{comm}\\}$
---|---|---|---
(Command) | comm | ::= | $\mathtt{sample}\ v\leftarrow\mathsf{dist}\ \mathtt{in}\ \\{\mathsf{body}\\}\mid\bigoplus_{i=1}^{k}c_{i}\\!:\\!\mathsf{comm}_{i}$
(Recursive Body) | $\mathsf{body}$ | ::= | $\mathtt{pre}(\mathsf{expr});\mathtt{invoke}\ \mathsf{call}$
(Recurive Call) | $\mathsf{call}$ | ::= | $p(v);p(\mathsf{size}-v)\,\mid\,p(v)\,\mid\,p(\mathsf{size}-v)$
|  |  |  (where $\mathsf{size}$ is either $\lfloor\frac{n}{b}\rfloor+c$ or $\lceil\frac{n}{b}\rceil+c$)
(Distribution) | $\mathsf{dist}$ | ::= |  uniform$(n)$ $\mid$ muniform$(n)$ $\mid$ discrete $\mid$ $\ldots$
(Expression) | $\mathsf{expr}$ | ::= | ${v}\mid{v}^{-1}\mid\ln{v}\mid n\mid\ln n\mid n^{-1}\mid{c}$
|  |  | $\mid\mathsf{expr}\\!+\\!\mathsf{expr}\mid\mathsf{expr}\\!-\\!\mathsf{expr}\mid\mathsf{expr}\\!\times\\!\mathsf{expr}$
Figure 1: The Grammar of LRec

In the grammar, we have two positive-integer valued variables $n,v$ which
stand for the input size and the sampled value in the randomization of the
passed size to the recursive calls of a procedure, respectively. We use
$b>0,c,c_{p}$ to denote integer constants, and use $p$ to denote the name of
the single procedure in the PRR. We consider arithmetic expressions
$\mathsf{expr}$ as polynomials over $v,v^{-1},\ln v$ and $n,n^{-1},\ln n$
(which we call _pseudo-polynomials_ in this work) and common probability
distributions, including (i) the uniform distribution uniform$(n)$ over
$\\{0,1,\dots,n-1\\}$, (ii) the piecewise uniform distribution muniform$(n)$
that returns $\max\\{i,n-i-1\\}$ where $i$ observes the uniform distribution
$\mathtt{uniform}(n)$, and (iii) any FSDPD (indicated by discrete) whose
probabilities and values are constants and pseudo-polynomials, respectively.
We also support other piecewise uniform distribution, e.g, the distribution
that each $v\in\\{0,\ldots,n/2\\}$ has probability $\frac{2}{3n}$ and each
$v\in\\{n/2+1,\ldots,n-1\\}$ has probability $\frac{4}{3n}$.

The nonterminal proc generates the PRR in the form $\mathtt{def}\
p(n;c_{p})=\\{\mathsf{comm}\\}$, for which $c_{p}$ is an integer constant as
the threshold of recursion, meaning that the procedure halts immediately when
$n<c_{p}$, and $\mathsf{comm}$ is the function body of the procedure. The
nonterminal comm generates all statements with one of the two forms as
follows.

  * •

A sampling statement (indicated by sample) followed by first a special
expression $\mathtt{pre}(\mathsf{expr})$ that stands for the preprocessing
time of $\mathsf{expr}$ amount, then the recursive calls generated by the
nonterminal $\mathsf{call}$.

  * •

A probabilistic choice in the form
$\bigoplus_{i=1}^{k}c_{i}\\!:\\!\mathsf{comm}_{i}$ where each statement
$\mathsf{comm}_{i}$ is executed with probability $c_{i}$.

We restrict the recursive calls to be either a single recursive call $p(v)$ or
$p(\mathsf{size}-v)$, or a divide-and-conquer composed of two consecutive
recursive calls $p(v)$ and $p(\mathsf{size}-v)$, for which we consider a
general setting that the relevant overall size $\mathsf{size}$ is in the form
of the input size $n$ divided by some positive integer $b$ with possibly an
offset $c$. Choosing $b=1,c=-1$ means the normal situation that the overall
size is $n-1$, i.e., removing one element from the original input.

Given a PRR $p$, we use $\mathsf{func}(p)$ to represent its function body.

We always assume that the given PRR is _well-formed_ , i.e., every $c_{i}$ in
a probabilistic choice is within $[0,1]$ and every random passed size (e.g.
$v,\mathsf{size}-v$) falls in $[0,n]$. Below, we present two examples for
PRRs.

######  Example 2 (QuickSelect)

Consider the problem of finding the $d$-th smallest element in an unordered
array of $n$ distinct elements. A classical randomized algorithm for solving
this problem is QuickSelect [19] with $O(n)$ expected running time. We present
the detail of this algorithm in Appendix 0.B. We model the algorithm as the
following PRR:

$\textstyle\mathtt{def}\ p(n;2)=\\{\mathtt{sample}\
v\leftarrow\mathtt{muniform}(n)\ \mathtt{in}\ \\{\mathtt{pre}(n);\
\mathtt{invoke}\ p(v);\\}\\}$

Here, we use $p(n;2)$ to represent the number of comparisons performed by
QuickSelect over an input of size $n$, and $v$ is the variable that captures
the size of the remaining array that has to be searched recursively. It
observes as the value $\max\\{i,n\\!-1\\!-i\\}$ where the value of $i$ is
sampled uniformly from $\\{0,\ldots,n\\!-\\!1\\}$, we use
$\mathtt{muniform}(n)$ to represent this distribution. ∎

######  Example 3 (QuickSort)

Consider the classical problem of sorting an array of $n$ distinct elements. A
well-known randomized algorithm for solving this problem is QuickSort [18]. We
model the algorithm as the following PRR. The detail of this algorithm is also
presented in Appendix 0.B.

$\mathtt{def}\ p(n;2)=\\{\mathtt{sample}\ v\leftarrow\mathtt{uniform}(n)\
\mathtt{in}\ \\{\mathtt{pre}(n);\ \mathtt{invoke}\ p(v);p(n-1-v);\\}\\}$

Here, $v$ and $n-1-v$ capture the sizes of the two sub-arrays. ∎

Below we present the semantics of a PRR in a nutshell. We relegate the details
of the semantics in Appendix 0.C. Consider a PRR generated by LRec with the
procedure name $p$, a _configuration_ $\sigma$ is a pair $\sigma=(\mbox{\sl
comm},\widehat{n})$ where comm represents the current statement to be executed
and $\widehat{n}\geq c_{p}$ is the current value for the variable $n$. A _PRR
state_ $\mu$ is a triple $\langle\sigma,C,\mathbf{K}\rangle$ for which:

  * •

$\sigma$ is either a configuration, or $\mathsf{halt}$ for the termination of
the whole PRR.

  * •

$C\geq 0$ records the cumulative preprocessing time so far.

  * •

$\mathbf{K}$ is a stack of configurations that remain to be executed.

We use $\mathsf{emp}$ to denote an empty stack, and say that a PRR state
$\langle\sigma,C,\mathbf{K}\rangle$ is _final_ if $\mathbf{K}=\mathsf{emp}$
and $\sigma=\mathsf{halt}$. Note that in a final PRR state
$\langle\mathsf{halt},C,\mathsf{emp}\rangle$, the value $C$ represents the
total execution runtime of the PRR. The semantics of the PRR is defined as a
discrete-time Markov chain whose state space is the set of all PRR states and
whose transition function $\mathbf{P}$, where $\mathbf{P}(\mu,\mu^{\prime})$
is the probability that the next PRR state is $\mu^{\prime}$ given the current
PRR state is $\mu=((\mbox{\sl comm},\widehat{n}),C,\mathbf{K})$. The
probability is determined by the following cases.

  * •

For final PRR states $\mu$, $\mathbf{P}(\mu,\mu):=1$ and
$\mathbf{P}(\mu,\mu^{\prime}):=0$ for other $\mu^{\prime}\neq\mu$. This means
that the PRR stays at termination once it terminates.

  * •

In the divide-and-conquer case $\mbox{\sl comm}=\mathtt{sample}\
v\leftarrow\mbox{\sl dist}\ \mathtt{in}\ \\{\mathtt{pre}(e);\\\
\mathtt{invoke}\ p(v);p(s-v)\\}$, we first sample $v$ from the distribution
dist. Then, with probability $\mbox{\sl dist}(v)$, we accumulate the
preprocessing time $e$ into the cumulative processing time $C$. We recursively
invoke $p(v)$ and push the remaining task $p(s-v)$ into the stack. The
probability for the single recursion case is defined analogously. The only
difference is that there is no need to push some recursive call into the stack
in the single recursion case.

  * •

In the case $\mbox{\sl comm}=\bigoplus_{i=1}^{k}c_{i}\\!:\\!\mbox{\sl
comm}_{i}$, we have that $\mathbf{P}(\mu,\mu_{i})={c_{i}}$ for each $1\leq
i\leq k$ for which we have $\mu_{i}:=((\mbox{\sl
comm}_{i},\widehat{n}),C,\mathbf{K})$.

With an initial PRR state $((\mathsf{func}(p),n^{*}),0,\mathsf{emp})$ where
$n^{*}\geq c_{p}$ is the input size, the Markov chain induces a probability
space where the sample space is the set of all infinite sequences of PRR
states, the $\sigma$-algebra is generated by all _cylinder sets_ over infinite
sequences of PRR states , and the probability measure is uniquely determined
by the transition function $\mathbf{P}$. We refer to [4] for details. We use
$\Pr_{n^{*}}$ for the probability measure where $n^{*}\geq c_{p}$ is the input
size.

We further define the random variable $\tau$ such that for any infinite
sequence of PRR states $\rho=\mu_{0},\mu_{1},\dots,\mu_{t},\dots$ with each
$\mu_{t}=((\mbox{\sl comm}_{t},\widehat{n}_{t}),C_{t},\mathbf{K}_{t})$,
$\tau(\rho)$ equals the first moment that the sequence reaches a final PRR
state, i.e., ${\tau(\rho)}=\inf\\{t\mid\mbox{the PRR state }\mu_{t}\mbox{ is
final}\\}$, for which $\inf\emptyset=\infty$. We will always ensure that
$\tau$ is almost-surely finite, i.e., $\Pr_{n^{*}}(\tau<\infty)=1$). Note that
the random cumulative processing time $C_{\tau}$ in the PRR state
$\mu_{\tau}\in\rho$ is the total execution time of the given PRR.

We formulate the tail bound analysis over PRRs as follows. Given a time limit
$\alpha\cdot\kappa(n^{*})$ symbolic in the initial input $n^{*}$ and the
coefficient $\alpha$, the goal of tail bound analysis is to infer an upper
bound $u(\alpha,n^{*})$ symbolic in $n^{*}$ and $\alpha$ such that for every
input size $n^{*}$ and plausible value for $\alpha$, we have that

$\textstyle\Pr_{n^{*}}[C_{\tau}\geq\alpha\cdot\kappa(n^{*})]\leq
u(\alpha,n^{*}).$ (1)

As tails bounds are often evaluated asymptotically, we focus on deriving tight
$u(\alpha,n^{*})$ when $\alpha,n^{*}$ are sufficiently large. To compare the
magnitude of two tail bounds, we follow the straightforward way that first
treats $\alpha$ as a fixed constant and compares the bounds over $n^{*}$, and
then if the magnitude over $n^{*}$ is identical, we take a further comparison
over the magnitude on the coefficient $\alpha$.

######  Example 4 (Our result on QuickSelect)

Continue with Example 2, suppose the user is interested in the tail bound
$\Pr[C_{\tau}\geq\alpha\cdot n^{*}]$, where $C_{\tau}$ is the running time of
the QuickSelect algorithm over an array with length $n^{*}$. Then, Karp’s
method produces the symbolic tail bound as follows.

$\Pr[C_{\tau}\geq\alpha\cdot n^{*}]\leq\exp(1.15-0.28\cdot\alpha)$

However, our method can produce the following tail bound.

$\Pr[C_{\tau}\geq\alpha\cdot
n^{*}]\leq\exp(2\cdot\alpha-\alpha\cdot\ln\alpha)$

Note that our method produces tail bounds with a better magnitude on $\alpha$.
∎

######  Example 5 (Our result on QuickSort)

Continue with Example 3, consider the tail bound $\Pr[C_{\tau}\geq\alpha\cdot
n^{*}\cdot\ln n^{*}]$, where $C_{\tau}$ is the running time of QuickSort over
a length-$n^{*}$ array. Then, Karp’s method produces the symbolic tail bound
as:

$\Pr[C_{\tau}\geq\alpha\cdot n^{*}\cdot\ln
n^{*}]\leq\exp(0.5-0.5\cdot\alpha),$

while our method can produce the bound as:

$\Pr[C_{\tau}\geq\alpha\cdot n^{*}\cdot\ln n^{*}]\leq\exp((4-\alpha)\cdot\ln
n^{*})$

Note that our method produces tail bounds with a better magnitude on $n^{*}$.∎

##  3 Exponential Tail Bounds via Markov’s Inequality

In this section, we demonstrate our theoretical approach for deriving
exponentially decreasing tail bounds based on Markov’s inequality. Due to the
space limitation, We relegate all proof details into Appendix 0.D.

Before illustrating our approach, we first translate a PRR in the language
LRec with the single procedure $p$ into the canonical form as follows.

$p(n;c_{p})=\mathtt{pre}(\mbox{\sl S}(n));\mathtt{invoke}\
p(\mathsf{size}_{1}(n));\ldots;p(\mathsf{size}_{r}(n))$ (2)

where (i) $\mbox{\sl S}(n)$ is a random variable related to the input size $n$
that represents the randomized pre-processing time and observes a probability
distribution resulting from a discrete probability choice of piecewise uniform
distributions, and (ii) $\mathtt{invoke}\
p(\mathsf{size}_{1}(n));\ldots;p(\mathsf{size}_{r}(n))$ is a statement that is
either a single recursive call $p(\mathsf{size}_{1}(n))$ or a divide-and-
conquer $p(\mathsf{size}_{1}(n));p(\mathsf{size}_{2}(n))$ upon the resolution
of the randomization. For the latter, we use a random variable $r$ (which is
either $1$ or $2$) to represent the number of recursive calls.

The translation can be implemented by a straightforward recursive procedure
$\mathsf{Tf}(n,{\sl Prog})$ that takes on input a positive integer $n$ (as the
input size) and a statement ${\sl Prog}$ (generated by the nonterminal comm)
to be processed, see Appendix 0.D for details. Note that the procedure
$\mathsf{Tf}(n,{\sl Prog})$ outputs the _joint_ distribution of the random
value $\mbox{\sl S}(n)$ and the random recursive call
$p(\mathsf{size}_{1}(n));\ldots;\\\ p(\mathsf{size}_{r}(n))$ i.e., they may
not be independent.

Our theoretical approach then works directly on the canonical form (2). It
consists of two major steps to derive an exponentially-decreasing tail bound.
In the first step, we apply Markov’s inequality and reduce the tail bound
analysis problem to the over-approximation of the moment generating function
$\mathbb{E}[\exp(t\cdot C_{\tau})]$ where $C_{\tau}$ is the cumulative pre-
processing time defined previously and $t>0$ is a scaling factor that aids the
derivation of the tail bound. In the second step, we apply Optional Stopping
Theorem (a classical theorem in martingale theory) to over-approximate the
expected value $\mathbb{E}[\exp(t\cdot C_{\tau})]$. Below we fix an PRR with
procedure $p$ in the canonical form (2), and a time limit
$\alpha\cdot\kappa(n^{*})$.

Our first step applies Markov’s inequality. Our approach relies on the well-
known exponential form of Markov’s inequality below.

###### Theorem 3.1

For every random variable $X$ and any scaling factor $t>0$, we have that
$\mathbb{\Pr}[X\geq d]\leq\mathbb{E}[\exp(t\cdot X)]/\exp(t\cdot d)$.

The detailed application of Markov’s inequality to tail bound analysis
requires to choose a scaling factor $t:=t(\alpha,n)$ symbolic in $\alpha$ and
$n$. After choosing the scaling factor, Markov’s inequality gives the
following tail bound:

$\Pr[C_{\tau}\geq\alpha\cdot\kappa(n^{*})]\leq\mathbb{E}[\exp(t(\alpha,n^{*})\cdot
C_{\tau})]/\exp(t(\alpha,n^{*})\cdot\alpha\cdot\kappa(n^{*})).$ (3)

The role of the scaling factor $t(\alpha,n^{*})$ is to scale the exponent in
the term $\exp(\kappa(\alpha,n^{*}))$, and this is in many cases necessary as
a tail bound may not be exponentially decreasing directly in the time limit
$\alpha\cdot\kappa(n^{*})$.

An unsolved part in the tail bound above is the estimation of the expected
value $\mathbb{E}[\exp(t(\alpha,n^{*})\cdot C_{\tau})]$. Our second step over-
approximates the expected value $\mathbb{E}[\exp(t(\alpha,n^{*})\cdot
C_{\tau})]$. To achieve this goal, we impose a constraint on the scaling
factor $t(\alpha,n)$ and an extra function $f(\alpha,n)$ and show that once
the constraint is fulfilled, then one can derive an upper bound for
$\mathbb{E}[\exp(t(\alpha,n^{*})\cdot C_{\tau})]$ from $t(\alpha,n)$ and
$f(\alpha,n)$. The theorem is proved via Optional Stopping Theorem. The
theorem requires the almost-sure termination of the given PRR, a natural
prerequisite of exponential tail bound. In this work, we consider PRRs with
finite termination time that implies the almost-sure termination.

###### Theorem 3.2

Suppose we have functions
$t,f:[0,\infty)\times\mathbb{N}\rightarrow[0,\infty)$ such that

$\textstyle\mathbb{E}[\exp(t(\alpha,n)\cdot\mathsf{Ex}(n\mid
f))]\leq\exp(t(\alpha,n)\cdot f(\alpha,n))$ (4)

for all sufficiently large $\alpha,n^{*}>0$ and all $c_{p}\leq n\leq n^{*}$,
where

$\textstyle\mathsf{Ex}(n\mid f):=\mbox{\sl
S}(n)+\sum_{i=1}^{r}f(\alpha,\mathsf{size}_{i}(n)).$

Then for $t_{*}(\alpha,n^{*}):=\min_{c_{p}\leq n\leq n^{*}}t(\alpha,n)$, we
have that

$\mathbb{E}[\exp(t_{*}(\alpha,n^{*})\cdot
C_{\tau})]\leq\mathbb{E}[\exp(t_{*}(\alpha,n^{*})\cdot f(\alpha,n^{*}))].$

Thus, we obtain the upper bound
$u(\alpha,n^{*}):=\exp(t_{*}(\alpha,n^{*})\cdot(f(\alpha,n^{*})-\alpha\cdot\kappa(n^{*})))$
for the tail bound in (1).

_Proof sketch._ We fix a procedure $p$, and some sufficiently large $\alpha$
and $n^{*}$. In general, we apply the martingale theory to prove this theorem.
To construct a martingale, we need to make two preparations.

First, by the convexity of $\exp(\cdot)$, substituting $t(\alpha,n)$ with
$t_{*}(\alpha,n^{*})$ in (4) does not affect the validity of (4).

Second, given an infinite sequence of the PRR states
$\rho=\mu_{0},\mu_{1},\dots$ in the sample space, we consider the subsequence
$\rho^{\prime}=\mu_{0}^{\prime},\mu_{1}^{\prime},\dots$ as follows, where we
represent $\mu_{i}^{\prime}$ as $(({\sf
func}(p),\hat{n}_{i}^{\prime}),C_{i}^{\prime},\mathbf{K}_{i}^{\prime})$. It
only contains states that are either final or at the entry of $p$, i.e., ${\sl
comm}={\sf func}(p)$. We define
$\tau^{\prime}:=\inf\\{t:\mu^{\prime}_{t}\text{ is final}\\}$, then it is
straightforward that $C^{\prime}_{\tau^{\prime}}=C_{\tau}$. We observe that
$\mu_{i+1}^{\prime}$ represents the recursive calls of $\mu_{i}^{\prime}$.
Thus, we can characterize the conditional distribution
$\mu_{i+1}^{\prime}\mid\mu_{i}$ by the transformation function
$\mathsf{Tf}(\hat{n},\mathsf{func}(p))$ as follows.

  * •

We first draw $(\mbox{\sl S},\mathsf{size}_{1},\mathsf{size}_{2},r)$ from
$\mathsf{Tf}(\hat{n}_{i}^{\prime},\mathsf{func}(p))$.

  * •

We accumulate S into the global cost. If there is a single recursion ($r=1$),
we invoke this sub-procedure. If there are two recursive calls, we push the
second call $p(\mathsf{size}_{2})$ into the stack and invoke the first one
$p(\mathsf{size}_{1})$.

Now we construct the super-martingale as follows. For each $i\geq 0$, we
denote the stack as $\mathbf{K}_{i}^{\prime}$ for $\mu_{i}^{\prime}$ as
$(\mathsf{func}(p),\mathsf{s}_{i,1})\cdots(\mathsf{func}(p),\mathsf{s}_{i,q_{i}})$,
where $q_{i}$ is the stack size. We prove that another process
$y_{0},y_{1},\ldots$ that forms a super-martingale, where
$y_{i}:=\exp\left(t_{*}(\alpha,n^{*})\cdot\left(C_{i}^{\prime}+f(\alpha,\hat{n}_{i}^{\prime})+\sum_{j=1}^{q_{i}}f(\alpha,\mathsf{s}_{i,j})\right)\right)$.
Note that $y_{0}=\exp(t_{*}(\alpha,n^{*})\cdot f(\alpha,n^{*}))$, and
$y_{\tau^{\prime}}=\exp(t_{*}(\alpha,n^{*})\cdot
C_{\tau^{\prime}}^{\prime})=\exp\left(t_{*}(\alpha,n^{*})\cdot
C_{\tau}\right)$. Thus we informally have that
$\mathbb{E}\left[\exp\left(t_{*}(\alpha,n^{*})\cdot
C_{\tau}\right)\right]=\mathbb{E}\left[y_{\tau^{\prime}}\right]\\\
\leq\mathbb{E}[y_{0}]=\exp\left(t_{*}(\alpha,n^{*})\cdot
f(\alpha,n^{*})\right)$ and the theorem follows. ∎

It is natural to ask whether our theoretical approach can always find an
exponential-decreasing tail bound over PRRs. We answer this question by
showing that under a difference boundedness and a monotone condition, the
answer is yes. We first present the difference boundedness condition (A1) and
the monotone condition (A2) for a PRR $\Delta$ in the canonical form (2) as
follows.

  * (A1)

$\Delta$ is _difference-bounded_ if there exist two real constants
$M^{\prime}\leq M$, such that for every $n\geq c_{p}$, and every possible
value $(V,s_{1},\dots,s_{k})$ in the support of the probability distribution
$\mathsf{Tf}(n,{\sf func}(p))$, we have that

$\textstyle M^{\prime}\cdot\mathbb{E}[\mbox{\sl S}(n)]\leq
V+(\sum_{i=1}^{k}\mathbb{E}[p(s_{i})])-\mathbb{E}[p(n)]\leq
M\cdot\mathbb{E}[\mbox{\sl S}(n)].$

  * (A2)

$\Delta$ is _expected non-decreasing_ if $\mathbb{E}[\mbox{\sl S}(n)]$ does
not decrease as $n$ increases.

In other words, (A1) says that for any possible concrete pre-processing time
$V$ and passed sizes $s_{1},\dots,s_{k}$, the difference between the expected
runtime before and after the recursive call is bounded by the magnitude of the
expected pre-processing time. (A2) simply specifies that the expected pre-
processing time be monotonically non-decreasing. These conditions are
fulfilled by most randomized algorithms, see Appendix 0.F for details.

With the conditions (A1) and (A2), our theoretical approach guarantees a tail
bound that is exponentially decreasing in the coefficient $\alpha$ and the
ratio ${\mathbb{E}[p(n^{*})]}/{\mathbb{E}[\mbox{\sl S}(n^{*})]}$. The theorem
statement is as follows.

###### Theorem 3.3

Let $\Delta$ be a PRR in the canonical form (2). If $\Delta$ satisfies (A1)
and (A2), then for any function $w:[1,\infty)\rightarrow(1,\infty)$, the
functions $f,t$ given by

$\textstyle f(\alpha,n):=w(\alpha)\cdot\mathbb{E}[p(n)]$ and $\textstyle
t(\alpha,n):=\frac{\lambda(\alpha)}{\mathbb{E}[\mbox{\sl S}(n)]}$ with
$\textstyle\lambda(\alpha):=\frac{8(w(\alpha)-1)}{w(\alpha)^{2}(M_{2}-M_{1})^{2}}$

fulfill the constraint (4) in Theorem 3.2. Furthermore, by choosing
$w(\alpha):=\frac{2\alpha}{1+\alpha}$ in the functions $f,t$ above and
$\kappa(\alpha,n^{*}):=\alpha\cdot\mathbb{E}[p(n^{*})]$, one obtains the tail
bound

$\textstyle\Pr[C_{\tau}\geq\alpha\mathbb{E}[p(n^{*})]]\leq\exp\left(-\frac{2(\alpha-1)^{2}}{\alpha(M_{2}-M_{1})^{2}}\cdot\frac{\mathbb{E}[p(n^{*})]}{\mathbb{E}[\mbox{\sl
S}(n^{*})]}\right).$

_Proof sketch._ We first rephrase the constraint (4) as

$\textstyle\mathbb{E}\left[\exp\left(t(\alpha,n)\cdot(\mbox{\sl
S}(n)+\sum_{i=1}^{r}f(\alpha,\mathsf{size}_{i}(n))-f(\alpha,n))\right)\right]\leq
1$

Then we focus on the exponent in the $\exp(\cdot)$, by (A1), the exponent is a
bounded random variable. By further calculating its expectation and applying
Hoeffiding’s Lemma [20], we obtain the theorem above. ∎

Note that since $\mathbb{E}[p(n)]\geq\mathbb{E}[\mbox{\sl S}(n)]$ when $n\geq
c_{p}$, the tail bound is at least exponentially-decreasing with respect to
the coefficient $\alpha$. This implies that our theoretical approach derives
tail bounds that are at least as tight as Karp’s method when (A1) and (A2)
holds. When $\mathbb{E}[p(n)]$ is of a strictly greater magnitude than
$\mathbb{E}[\mbox{\sl S}(n)]$, our approach derives asymptotically tighter
bounds.

Below, we apply the theorem above to prove tail bounds for Quickselect
(Example 2) and Quicksort (Example 3).

###### Example 6

For QuickSelect, its canonical form is $p(n;2)=n+p(\mathsf{size}_{1}(n))$,
where $\mathsf{size}_{1}(n)$ observes as $\mathtt{muniform}(n)$. Solving the
recurrence relation, we obtain that $\mathbb{E}[p(n)]=4\cdot n$. We further
find that this PRR satisfies (A1) with two constants $M^{\prime}=-1,M=1$. Note
that the PRR satisfies (A2) obviously. Hence, we apply Theorem 3.3 and derive
the tail bound for every sufficiently large $\alpha$:

$\textstyle\Pr[C_{\tau}\geq 4\cdot\alpha\cdot
n^{*}]\leq\exp\left(-\frac{2(\alpha-1)^{2}}{\alpha}\right).$

On the other hand, Karp’s cookbook has the tail bound

$\textstyle\Pr[C_{\tau}\geq 4\cdot\alpha\cdot
n^{*}]\leq\exp\left(1.15-1.12\cdot\alpha\right).$

Our bound is asymptotically the same as Karp’s but has a better coefficient.∎

###### Example 7

For QuickSort, its canonical form is
$p(n;2)=n+p(\mathsf{size}_{1}(n))+p(\mathsf{size}_{2}(n))$, where
$\mathsf{size}_{1}(n)$ observes as $\mathtt{muniform}(n)$ and
$\mathsf{size}_{2}(n)\\!=\\!n\\!-\\!1\\!-\\!\mathsf{size}_{1}(n)$. Similar to
the example above, we first calculate
$\mathbb{E}[p(n)]\\!=\\!2\\!\cdot\\!n\\!\cdot\\!\ln n$. Note that this PRR
also satisfies two assumptions above with two constants $M^{\prime}=-2\log
2,M=1$. Hence, for every sufficiently large $\alpha$, we can derive the tail
bound as follows:

$\textstyle Pr[C_{\tau}\geq 2\cdot\alpha\cdot n^{*}\cdot\ln
n^{*}]\leq\exp\left(-\frac{0.7(\alpha-1)^{2}}{\alpha}\cdot\ln n^{*}\right).$

On the other hand, Karp’s cookbook has the tail bound

$\textstyle Pr[C_{\tau}\geq 2\cdot\alpha\cdot n^{*}\cdot\ln
n^{*}]\leq\exp\left(-\alpha+0.5\right).$

Note that our tail bound is tighter than Karp’s with a $\ln n$ factor.∎

From the generality of Markov’s inequality, our theoretical approach can
handle to general PRRs with three or more sub-procedure calls. However, the
tail bounds derived from Theorem 3.3 is still not tight since the theorem only
uses the expectation and bound of the given distribution. For example, for
QuickSelect, the tightest known bound
$\exp(-{\rm\Theta}(\alpha\cdot\ln\alpha))$ [17], is tighter than that derived
from Theorem 3.3. Below, we present an algorithmic approach that fully
utilizes the distribution information and derives tight tail bounds that can
match [17].

##  4 An Algorithmic Approach

In this section, we demonstrate an algorithmic implementation for our
theoretical approach (Theorem 3.2). Our algorithm synthesizes the functions
$t,f$ through template and a refined estimation on the exponential terms from
the inequality (4). The estimation is via integration and the monotonicity of
the template. Below we fix a PRR $p(n;c_{p})$ in the canonical form (2) and a
time limit $\alpha\cdot\kappa(n^{*})$.

Recall that to apply Theorem 3.2, one needs to find functions $t,f$ that
satisfy the constraint (4). Thus, the first step of our algorithm is to have
pseudo-monomial template for $f(\alpha,n)$ and $t(\alpha,n)$ in the following
form:

$\textstyle f(\alpha,n)$
$\textstyle:=c_{f}\cdot\alpha^{p_{f}}\cdot\ln^{q_{f}}\alpha\cdot
n^{u_{f}}\cdot\ln^{v_{f}}n$ (5) $\textstyle t(\alpha,n)$
$\textstyle:=c_{t}\cdot\alpha^{p_{t}}\cdot\ln^{q_{t}}\alpha\cdot
n^{u_{t}}\cdot\ln^{v_{t}}n$ (6)

In the template, we have $p_{f},q_{f},u_{f},v_{f},p_{t},q_{t},u_{t},v_{t}$ are
given integers, and $c_{f},c_{t}>0$ are unknown positive coefficients to be
solved. For several compatibility reasons (see Proposition 1 and 2 in the
following), we require that $u_{f},v_{f}\geq 0$ and $u_{t},v_{t}\leq 0$. We
say that the concrete values $\overline{c_{f}},\overline{c_{t}}$ for the
unknown coefficients $c_{f},c_{t}>0$ are _valid_ if the concrete functions
$\overline{f},\overline{t}$ obtained by substituting
$\overline{c_{f}},\overline{c_{t}}$ for $c_{f},c_{t}$ in the template (5) and
(6) satisfy the constraint (4) for every sufficiently large $\alpha,n^{*}\geq
0$ and all $c_{p}\leq n\leq n^{*}$.

We consider the pseudo-polynomial template since the runtime behavior of
randomized algorithms can be mostly captured by pseudo-polynomials. We choose
monomial templates since our interest is the asymptotic magnitude of the tail
bound. Thus, only the monomial with the highest degrees matter.

Our algorithm searches the values for
$p_{f},q_{f},u_{f},v_{f},p_{t},q_{t},u_{t},v_{t}$ by an enumeration within a
bounded range $\\{-B,\dots,B\\}$, where $B$ is a manually specified positive
integer. To avoid exhaustive enumeration, we use the following proposition to
prune the search space.

###### Proposition 1

Suppose that we have functions
$t,f:[0,\infty)\times\mathbb{N}\rightarrow[0,\infty)$ that fulfill the
constraint (4). Then it holds that (i)

$(p_{f},q_{f})\leq(1,0)$ and $(p_{t},q_{t})\geq(-1,0)$, and (ii)

$f(\alpha,n)={\rm\Omega}(\mathbb{E}[p(n)])$, $f(\alpha,n)=O(\kappa(n))$ and
$t(\alpha,n)={\rm\Omega}(\kappa(n)^{-1})$ for any fixed $\alpha>0$, where we
write $(a,b)\leq(c,d)$ for the lexicographic order, i.e., $(a\leq
c)\land(a=c\rightarrow b\leq d)$.

Proof. Except for the constraint that
$f(\alpha,n)={\rm\Omega}(\mathbb{E}[p(n)])$, the other constraints simply
ensure that the tail bound is exponentially-decreasing. To see why
$f(\alpha,n)={\rm\Omega}(\mathbb{E}[p(n)])$, we apply Jensen’s inequality [31]
to (4) and obtain $f(n)\geq\mathbb{E}[\mathsf{Ex}(n|f)]=\mathbb{E}[\mbox{\sl
S}(n)+\sum_{i=1}^{r}f(\mathsf{size}_{i}(n))]$. Then we imitate the proof of
Theorem 3.2 and derive that $f(n)\geq\mathbb{E}[p(n)]$. ∎

Proposition 1 shows that it suffices to consider (i) the choice of
$u_{f},v_{f}$ that makes the magnitude of $f$ to be within $\mathbb{E}[p(n)]$
and $\kappa(n)$, (ii) the choice of $u_{t},v_{t}$ that makes the magnitude of
$t^{-1}$ within $\kappa(n)$, and (iii) the choice of $p_{f},q_{f},p_{t},q_{t}$
that fulfills $(p_{f},q_{f})\leq(1,0),(p_{t},q_{t})\geq(-1,0)$. Note that an
over-approximation of $\mathbb{E}[p(n)]$ can be either obtained manually or
derived from automated approaches [11].

###### Example 8

Consider the quickselect example (Example 2), suppose we are interested in the
tail bound $\Pr[C_{\tau}\geq\alpha\cdot n]$, and we enumerate the eight
integers in the template from $-1$ to $1$. Since $\mathbb{E}[p(n)]=4\cdot n$,
by the proposition above, we must have that $(u_{f},v_{f})=(1,0)$,
$(u_{t},v_{t})\geq(-1,0)$, $(p_{t},q_{t})\geq(-1,0)$,
$(p_{f},q_{f})\leq(1,0)$. This reduces the number of choices for the template
from $1296$ to $128$, where these numbers are automatically generated by our
implementation. A choice is
$f(\alpha,n):=c_{f}\cdot\alpha\cdot(\ln\alpha)^{-1}\cdot n$ and
$t(\alpha,n):=c_{t}\cdot\ln\alpha\cdot n^{-1}$.∎

In the second step, our algorithm solves the unknown coefficients
$c_{t},c_{f}$ in the template. Once they are solved, our algorithm applies
Theorem 3.2 to obtain the tail bound. In detail, our algorithm computes
$t_{*}(\alpha,n^{*})$ as the minimum of $t(\alpha,n)$ over $c_{p}\leq n\leq
n^{*}$, and by $u_{t},v_{t}\leq 0$, $t_{*}(\alpha,n^{*})$ is simply
$t(\alpha,n^{*})$, so that we obtain the tail bound
$u(\alpha,n^{*})=\exp(t(\alpha,n^{*})\cdot(f(\alpha,n^{*})-\alpha\cdot\kappa(n^{*})))$.

###### Example 9

Continue with Example 8. Suppose we have successfully found that
$\overline{c_{f}}=2,\overline{c_{t}}=1$ is a valid concrete choice for the
unknown coefficients in the template. Then $t_{*}(\alpha,n^{*})$ is
$t(\alpha,n^{*})=\ln\alpha\cdot(n^{*})^{-1}$, and we have the tail bound
$u(\alpha,n^{*})=\exp(2\cdot\alpha-\alpha\cdot\ln\alpha)$, which has better
magnitude than the tail bound by Karp’s method and our Theorem 3.3 (See
Example 6). ∎

Our algorithm follows the guess-and-check paradigm. The guess procedure
explores possible values $\overline{c_{f}},\overline{c_{t}}$ for $c_{f},c_{t}$
and invokes the check procedure to verify whether the current choice is valid.
Below we present the guess procedure in Section 4.1, and the check procedure
in Section 4.2.

###  4.1 The Guess Procedure $\mathsf{Guess}(f,t)$

The pseudocode for our guess procedure $\mathsf{Guess}(f,t)$ is given in
Algorithm 1. In detail, it first receives a positive integer $M$ as the
doubling and halving number (Line 1), then iteratively enumerates possible
values for the unknown coefficients $c_{f}$ and $c_{t}$ by doubling and
halving for $M$ times (Line 3 – Line 4), and finally calls the check procedure
(Line 5). It is justified by the following theorem (proved in Appendix 0.E).

###### Theorem 4.1

Given the template for $f(\alpha,n)$ and $t(\alpha,n)$ as in (5) and (6), if
$\overline{c_{f}},\overline{c_{t}}$ are valid choices, then (i) for every
$k>1$, $k\cdot\overline{c_{f}},\overline{c_{t}}$ remains to be valid, and (ii)
for every $0<k<1$, $\overline{c_{f}},k\cdot\overline{c_{t}}$ remains to be
valid.

Input : Template for $f(\alpha,n)$ and $t(\alpha,n)$ as in (5) and (6)

Output : $\overline{c_{f}},\overline{c_{t}}>0$ for (5) and (6)

1 Parameter: $M$ for the maximum steps of doubling and halving.

2 Procedure  _Guess(_$f,t$_)_:

3

4 for  _$\overline{c_{t}}:=1,2^{-1},\dots,2^{-M}$_ do

5 for  _$\overline{c_{f}}:=\frac{1}{2},1,2,\dots,2^{M-1}$_ do

6 if  _CheckCond $(\overline{c_{f}},\overline{c_{t}})$_ then

7 $\mathbf{Return}\ (\overline{c_{f}},\overline{c_{t}})$

8

9

10

Algorithm 1 Guess Procedure

By Theorem 4.1, if the check procedure is sound and complete (i.e.,
$\mathsf{CheckCond}$ always terminates and $\overline{c_{f}},\overline{c_{t}}$
fulfills the constraint (4) iff
$\mathsf{CheckCond}(\overline{c_{f}},\overline{c_{t}})$ returns true), then
the guess procedure guarantees to find a solution
$\overline{c_{f}},\overline{c_{t}}$ (if it exists) when the parameter $M$ is
large enough.

###### Example 10

Continued with Example 8, suppose $M=2$, we enumerate $\overline{c_{f}}$ from
$\\{\frac{1}{2},1,2\\}$, and $\overline{c_{t}}$ from
$\\{1,\frac{1}{2},\frac{1}{4}\\}$. We try every possible combination, and we
find that $\mathsf{CheckCond}(2,1)$ returns true. Thus, we return $(2,1)$ as
the result. In Section 4.2, we will show how to conclude that
$\mathsf{CheckCond}(2,1)$ is true.∎

###  4.2 The Check Procedure
$\mathsf{CheckCond}(\overline{c_{f}},\overline{c_{t}})$

The check procedure takes as input the concrete values
$\overline{c_{f}},\overline{c_{t}}$ for the unknown coefficients in the
template, and outputs whether they are valid. It is the most involved part in
our algorithm due to the difficulty to tackle the validity of the constraint
(4) that involves the composition of polynomials, exponentiation and
logarithms. The existence of a sound and complete decision procedure for such
validity is extremely difficult and is a long-standing open problem [1, 36].

To circumvent this difficulty, the check procedure first strengthens the
original constraint (4) into a canonical constraint with a specific form, so
that a decision algorithm that is sound and complete up to any additive error
applies. Below we fix a PRR with procedure $p$ in the canonical form (2). We
also discuss possible extensions for the check procedure in Remark 1.

The Canonical Constraint. We first present the canonical constraint
$Q(\alpha,n)$ and how to decide the canonical constraint. The constraint is
given by (where $\forall^{\infty}\alpha$ means “for all sufficiently large
$\alpha$” or formally $\exists\alpha_{0}.\forall\alpha\geq\alpha_{0}$)

$\textstyle Q(\alpha,n):=\forall^{\infty}\alpha.\forall n\geq
c_{p}.\left[\sum_{i=1}^{k}{\gamma_{i}\cdot\exp(f_{i}(\alpha)+g_{i}(n))}\leq
1\right]$ (7)

subject to:

  * (C1)

For each $1\leq i\leq k$, we have $\gamma_{i}>0$ is a positive constant,
$f_{i}(\alpha)$ is a pseudo-polynomial in $\alpha$, and $g_{i}(n)$ is a
pseudo-polynomial in $n$.

  * (C2)

For each $1\leq i\leq k$, the exponents for $n$ and $\ln n$ in $g_{i}(n)$ are
non-negative.

We use $Q_{L}(\alpha,n)$ to represent the summation term
$\sum_{i=1}^{k}{\gamma_{i}\cdot\exp(f_{i}(\alpha)+g_{i}(n))}$ in (7). Below we
show that this can be checked by the algorithm Decide up to any additive
error. We present an overview of this algorithm. We also present its pseudo-
code in Algorithm 2. The details are relegated into Appendix 0.E.

The algorithm Decide requires an external function ${\sf NegativeLB}(P(n))$
that takes on input a pseudo-polynomial $P(n)$ and outputs an integer
$T_{n}^{*}$ such that $P(n)\leq 0$ for every $n\geq T_{n}^{*}$, or output
$+\infty$ for the absence of $T_{n}^{*}$. The idea of this function is to
apply the monotonicity of pseudo-polynomials. With the function ${\sf
NegativeLB}(P(n))$, the algorithm Decide consists of two steps as follows.

_First_ , we can change the bound of $n$ from $[c_{p},\infty)$ into
$[c_{p},T_{n}]$, where $T_{n}$ is a constant, without affecting the soundness
and completeness. This is achieved by the observation that either: (i) we can
conclude $Q(\alpha,n)$ does not hold, or (ii) there is an integer $T_{n}$ such
that $Q_{L}(\alpha,n)$ is non-increasing when $n\geq T_{n}$. Hence, it
suffices only to consider $c_{p}\leq n\leq T_{n}$. Below we show how to
compute $T_{n}$ by case analysis of the limit $M_{i}$ of $g_{i}(n)$ as
$n\to\infty$, for each $1\leq i\leq k$.

  * •

If $M_{i}\\!=\\!+\infty$, then $\exp(g_{i}(n)+f_{i}(\alpha))$ could be
arbitrarily large when $n\to\infty$. As a result, we can conclude that
$Q(\alpha,n)$ does not hold.

  * •

Otherwise, by (C2), either $g_{i}(n)$ is a constant function, or
$M_{i}\\!=\\!-\infty$. In both cases, $g_{i}(n)$ is non-increasing for every
sufficiently large $n$. More precisely, there exists $L_{i}$ such that
$g_{i}^{\prime}(n)\leq 0$ for every $n\geq L_{i}$, where $g_{i}^{\prime}(n)$
is the derivative of $g_{i}(n)$. Moreover, we can invoke ${\sf
NegativeLB}(g_{i}^{\prime}(n))$ to get $L_{i}$.

Finally, we set $T_{n}$ as the maximum of $L_{i}$’s and $c_{p}$.

_Second_ , for every integer $c_{p}\leq\overline{n}\leq T_{n}$, we substitute
$n$ with $\overline{n}$ to eliminate $n$ in $Q(\alpha,n)$. Then, each exponent
$f_{i}(\alpha)+g_{i}(\overline{n})$ becomes a pseudo-polynomial solely over
$\alpha$. Since we only concern sufficiently large $\alpha$, we can compute
the limit $R_{\overline{n}}$ for $Q_{L}(\alpha,\overline{n})$ as
$\alpha\to\infty$. We decide based on the limit $R_{\overline{n}}$ as follows.

  * •

If $R_{\overline{n}}<1$ for every $c_{p}\\!\leq\\!\overline{n}\\!\leq\\!L$, we
conclude that $Q(\alpha,n)$ holds.

  * •

If $R_{\overline{n}}\geq 1$ for some $c_{p}\\!\leq\\!\overline{n}\\!\leq\\!L$,
we conclude that $Q(\alpha,n)$ does not hold to ensure soundness.

Input : A canonical constraint $Q(\alpha,n)$ in the form of (7)

Output : Decide whether $Q(\alpha,n)$ holds.

1 Procedure  _Decide(_$Q(\alpha,n)$_)_:

$T_{n}:=c_{p}$;

// $\triangleleft$ The first step

2 for  _$i:=1,2,\ldots,k$_ do

3 $M_{i}:=$ The limit of $g_{i}(n)$ as $n\to\infty$.

4 if  _$M_{i}=+\infty$_ then

5 Return False

6 else

7 $g_{i}^{\prime}(n):=$ the derivative of $g_{i}(n)$

8 $T_{n}:=\max\\{T_{n},{\sf NegativeLB}(g_{i}^{\prime}(n))\\}$

9

10 for  _$\overline{n}:=c_{p},\ldots,T_{n}$_ do // $\triangleleft$ The second
step

11 $R:=0$

12 for  _$i:=1,2,\ldots,k$_ do

13 $\Delta:=$ the limit of $f_{i}(\alpha)+g_{i}(\overline{n})$ as
$\alpha\to\infty$.

14 if  _$\Delta=+\infty$_ then

15 Return False

16 else

17 $R:=R+\gamma_{i}\cdot\exp(\Delta)$

18 if $R\geq 1$ then Return False

19

20 Return True

Algorithm 2 The Decision procedure for canonical constraints

Algorithm Decide is sound, and complete up to any additive error, as is
illustrated by the following theorem. The proof is conducted directly via the
definition of the limit and is relegated to Appendix 0.E.

###### Theorem 4.2

Algorithm Decide has the following properties:

  * •

(Completeness) If $Q(\alpha,n)$ does not hold for infinitely many $\alpha$ and
some $n\geq c_{p}$, then the algorithm returns false.

  * •

(Soundness) For every $\varepsilon>0$, we have that if $Q_{L}(\alpha,n)\leq
1-\varepsilon$ for all sufficiently large $\alpha$ and all $n\geq c_{p}$, then
the algorithm returns true.

The Strengthening Procedure. Then we show how to strengthen the constraint (4)
into the canonical constraint (7), so that Algorithm Decide applies. We
rephrase (4) as

$\textstyle\mathbb{E}\left[\exp(t(\alpha,n)\cdot\left(\mbox{\sl
S}(n)+\sum_{i=1}^{r}f(\alpha,\mathsf{size}_{i}(n))-f(\alpha,n)\right)\right]\leq
1$ (8)

and consider two functions $\overline{f},\overline{t}$ obtained by
substituting the concrete values $\overline{c_{f}},\overline{c_{t}}$ for
unknown coefficients into the template (5) and (6). We observe that the joint-
distribution of the random quantities $S(n),r\in\\{1,2\\}$ and
$\mathsf{size}_{1}(n),\ldots,\mathsf{size}_{r}(n)$ in the canonical form (2)
over PRRs can be described by several probabilistic branches
$\\{c_{1}:B_{1},\dots,c_{k}:B_{k}\\}$, which corresponds to the probabilistic
choice commands in the PRR. Each probabilistic branch $B_{i}$ has a constant
probability $c_{i}$, a deterministic pre-processing time $S_{i}(n)$, a fixed
number of subprocedure calls $r_{i}$, and a probability distribution for the
variable $v$. The strengthening first handles each probabilistic branch, and
then combines the strengthening results of every branch into a single
canonical constraint.

The strengthening of each branch is an application of a set of rewriting
rules. Intuitively, each rewriting step over-approximates and simplifies the
expectation term in the LHS of (8). Through multiple steps of rewriting, we
eventually obtain the final canonical constraint. Below we present the details
of the strengthening for a single probabilistic branch with the single
recursion case. The divide-and-conquer case follows a similar treatment, see
Appendix 0.E for details.

Consider the single recursion case $r=1$ where a probabilistic branch has
deterministic pre-processing time $S(n)$, distribution $\mathsf{dist}$ for the
variable $v$ and passed size $H(v,n)$ for the recursive call. We have a case
analysis on the distribution $\mathsf{dist}$ as follows.

— _Case I_ : $\mathsf{dist}$ is a FSDPD
$\mathtt{discrete}\\{c^{\prime}_{1}:\mathsf{expr}_{1},\dots,c^{\prime}_{k}:\mathsf{expr}_{k}\\}$,
where $v$ observes as $\mathsf{expr}_{i}$ with probability $c^{\prime}_{i}$.
Then the expectation in (8) is exactly:

$\textstyle\sum_{i=1}^{k}c^{\prime}_{i}\cdot\exp\left(t(\alpha,n)\cdot
S(n)+t(\alpha,n)\cdot f(\alpha,H(\mathsf{expr}_{i},n))-t(\alpha,n)\cdot
f(\alpha,n)\right)$

Thus it suffices to over-approximate the exponent
$X_{i}(\alpha,n):=t(\alpha,n)\cdot\mbox{\sl S}(n)+t(\alpha,n)\cdot
f(\alpha,H(\mathsf{expr}_{i},n))-t(\alpha,n)\cdot f(n)$ into the form subject
to (C1)–(C2). For this purpose, our strengthening repeatedly applies the
following rewriting rules (R1)–(R4) for which $0<a<1$ and $b>0$:

$\textstyle\text{(R1) }f(\alpha,H(\mathsf{expr}_{i},n))\leq f(\alpha,n)\quad$
$\textstyle\text{(R2) }\ln(an-b)\leq\ln n+\ln a\quad\ln(an+b)\leq\ln
n+\ln(\min\\{1,a+\frac{b}{c_{p}}\\})$ $\textstyle\text{(R3) }0\leq n^{-1}\leq
c_{p}^{-1}\quad 0\leq\ln^{-1}n\leq\ln^{-1}c_{p}\quad\text{(R4)
}\lfloor\frac{n}{b}\rfloor\leq\frac{n}{b}\quad\lceil\frac{n}{b}\rceil\leq\frac{n}{b}+\frac{b-1}{b}$

(R1) follows from the well-formedness $0\leq H(\mathsf{size}_{i},n)\leq n$ and
the monotonicity of $f(\alpha,n)$ with respect to $n$. (R2)–(R4) are
straightforward. Intuitively, (R1) can be used to cancel the term
$f(\alpha,H(\mathsf{size}_{i},n))-f(\alpha,n)$, (R2) simplifies the sub-
expression in $\ln$, (R3) is used to remove floors and ceils, and (R4) to
remove $n^{-c}$ and $\ln^{-c}n$ to satisfy the restriction (C2) of the
canonical constraint. To apply these rules, we consider two strategies below.

  * (S1-D)

Apply (R1) and over-approximate $X_{i}(\alpha,n)$ as
$t(\alpha,n)\cdot\mbox{\sl S}(n)$. Then, we repeatedly apply (R3) to remove
terms $n^{-c}$ and $\ln^{-c}n$.

  * (S2-D)

Substitute $f$ and $t$ with the concrete functions $\overline{f},\overline{t}$
and expand $H(\mathsf{expr}_{i},n)$. Then we first apply (R4) to remove all
floors and ceils, and repeatedly apply (R2) to replace all occurrences of
$\ln(an+b)$ with $\ln n+\ln C$ for some constant $C$. By the previous
replacement, the whole term $X_{i}(\alpha,n)$ will be over-approximated as a
pseudo-polynomial over $\alpha$ and $n$. Finally, we eagerly apply (R3) to
remove all terms $n^{-c}$ and $\ln^{-c}n$.

Our algorithm first tries to apply (S2-D), if it fails to derive a canonical
constraint, then we apply the alternative (S1-D) to the original constraint.
If both the strategies fails, we report failure and exit the check procedure.

###### Example 11

Suppose $v$ observes as $\\{0.5:n-1,0.5:n-2\\},S(n):=\ln
n,t(\alpha,n):=\frac{\ln\alpha}{\ln
n},f(\alpha,n):=4\cdot\frac{\alpha}{\ln\alpha}\cdot n\cdot\ln n,H(v,n):=v$. We
consider applying both strategies to the first term $\mathsf{expr}_{1}:=n-1$
and $X_{1}(\alpha,n):=t(\alpha,n)\cdot(\mbox{\sl
S}(n)+f(\alpha,n-1)-f(\alpha,n))$. If we apply (S1-D) to $X_{1}$, it will be
approximated as $\exp(\ln\alpha)$. If we apply (S2-D) to $X_{1}$, it will be
first over-approximated as $\frac{\ln\alpha}{\ln n}\cdot(\ln
n+{4\cdot\frac{\alpha}{\ln\alpha}\cdot v\cdot\ln
n}-4\cdot\frac{\alpha}{\ln\alpha}\cdot n\cdot\ln n)$, then we substitute
$v=n-1$ and derive the final result $\exp(\ln\alpha-4\cdot\alpha)$. Hence,
both the strategies succeed. ∎

— _Case II_ : $\mathsf{dist}$ is $\mathtt{uniform}(n)$ or
$\mathtt{muniform}(n)$. Note that $H(v,n)$ is linear with respect to $v$, thus
$H(v,n)$ is a bijection over $v$ for every fixed $n$. Hence, if $v$ observes
as $\mathtt{uniform}(n)$, then

$\textstyle\mathbb{E}[\exp(t(\alpha,n)\cdot
f(\alpha,H(v,n)))]\leq\frac{1}{n}\sum_{v=0}^{n-1}\exp(t(\alpha,n)\cdot
f(\alpha,v))$ (9)

If $v$ observes as $\mathtt{muniform}(n)$, a similar inequality holds by
replacing $\frac{1}{n}$ with $\frac{2}{n}$. Since $f(\alpha,v)$ is a non-
decreasing function with respect to $v$, we further over-approximate the
summation in (9) by the integral $\int_{0}^{n}\exp(t(\alpha,n)\cdot
f(\alpha,v))\text{d}v$.

###### Example 12

Continue with Example 10, we need to check

$\overline{t}(\alpha,n)=\frac{\ln\alpha}{n}$ and
$\overline{f}(\alpha,n)=\frac{2\cdot\alpha}{\ln\alpha}\cdot n$. By the
inequality (9), we expand the constraint (8) into
$\frac{2}{n}\cdot\exp(\ln\alpha-2\cdot\alpha)\cdot\sum_{v=0}^{n-1}\exp(\frac{2\cdot\alpha\cdot
i}{n})$. By integration, it is further over-approximated as
$\frac{2}{n}\cdot\exp(\ln\alpha-2\cdot\alpha)\cdot\int_{0}^{n}\exp(\frac{2\cdot\alpha\cdot
v}{n})\text{d}v$.∎

Note that we still need to resolve the integration of an exponential function
whose exponent is a pseudo-monomial over $\alpha,n,v$. Below we denote by
$d_{v}$ the degree on the variable $v$ and by $\ell_{v}$ the degree of $\ln
v$. We first list the situations where the integral can be computed exactly.

  * •

If $(d_{v},\ell_{v})=(1,0)$, then the exponent could be expressed as
$W(\alpha,n)\cdot v$,where $W(\alpha,n)$ is a pseudo-monomial over $\alpha$
and $n$. We can compute the integral as $\frac{\exp(n\cdot
W(\alpha,n))-1}{W(\alpha,n)}$ and over-approximate it as $\frac{\exp(n\cdot
W(\alpha,n))}{W(\alpha,n)}$ by removing $-1$ in the numerator.

  * •

If $(d_{v},\ell_{v})=(0,1)$, then the exponent is of the form
$W(\alpha,n)\cdot\ln v$. We follow a similar procedure with the case above and
obtain the over-approximation $\frac{n\cdot\exp(\ln n\cdot
W(\alpha,n))}{W(\alpha,n)}$.

  * •

If $(d_{v},\ell_{v})=(0,0)$, then the result is trivially
$n\cdot\exp(W(\alpha,n))$.

Then we handle the situation where the exact computation of the integral is
infeasible. In this situation, the strengthening further over-approximates the
integral into simpler forms by first replacing $\ln v$ with $\ln n$, and then
replacing $v$ with $n$ to reduce the degrees $\ell_{v}$ and $d_{v}$.
Eventually, the exponent in the integral bows down to one of the three
situations (where the integral can be computed exactly) above, and the
strengthening returns the exact value of the integral.

###### Example 13

Continue with Example 12. We express the exponent as
$\frac{2\cdot\alpha}{n}\cdot v$. Thus, we can plug $\frac{2\cdot\alpha}{n}$
into $W(\alpha,n)$ and obtain the integration result
$\frac{\exp(2\cdot\alpha)}{2\cdot\alpha/n}$. Furthermore, we can simplify the
formula in Example 12 as $\frac{\exp(\ln\alpha)}{\alpha}$.∎

In the end, we move the term $\frac{1}{n}$ (or $\frac{2}{n}$) that comes from
the uniform (or muniform) distribution and the coefficient term $W(\alpha,n)$
into the exponent. If we move these terms directly, it may produce $\ln\ln n$
and $\ln\ln\alpha$ that comes from taking the logarithm of $\ln n$ and
$\ln\alpha$. Hence, we first apply $\ln c_{p}\leq\ln n\leq n$ and
$1\leq\ln\alpha\leq\alpha$ to remove all terms $\ln n$ and $\ln\alpha$ outside
the exponent (e.g., $\frac{\ln\alpha}{\ln n}$ is over-approximated as
$\frac{\alpha}{\ln c_{p}}$). After the over-approximation, the terms outside
the exponentiation form a polynomial over $\alpha$ and $n$, we can trivially
move these terms into the exponent by taking the logarithm. Finally, we apply
(R4) in Case I to remove $n^{-c}$ and $\ln^{-c}n$. If we fail to obtain the
canonical constraint, the strengthening reports failure.

###### Example 14

Continue with Example 13, we move the term $\alpha$ into the exponentiation
and simplify the over-approximation result as ${\exp(\ln\alpha-\ln\alpha)}=1$.
As a result, we over-approximate the LHS of (8) as $1$ and we conclude that
$\mathsf{CheckCond}(2,1)$ holds. ∎

The details of the divide-and-conquer case are similar and relegated to
Appendix 0.E. Furthermore, we present how to combine the strengthening results
for different branches into a single canonical constraint. Suppose for every
probabilistic branch $B_{i}$, we have successfully obtained the canonical
constraint $Q_{L,i}(\alpha,n)\leq 1$ as the strengthening of the original
constraint (8). Then, the canonical constraint for the whole distribution is
$\sum_{i=1}^{k}c_{i}\cdot Q_{L,i}(\alpha,n)\leq 1$. Intuitively, there is
probability $c_{i}$ for the branch $B_{i}$, thus the combination follows by
simply expanding the expectation term.

A natural question is to ask whether our algorithm can always succeed to
obtain the canonical constraint. We have the proposition as follows.

###### Proposition 2

If the template for $t$ has a lower magnitude than $S(n)^{-1}$ for every
branch, then the rewriting always succeeds.

###### Proof

We first consider the single recursion case. When $\mathsf{dist}$ is FSDPD, we
can apply (S1-D) to over-approximate the exponent as $t(\alpha,n)\cdot S(n)$.
Since $t(\alpha,n)$ has a lower magnitude than $S(n)^{-1}$, by further
applying (R3) to eliminate $n^{-c}$ and $\ln^{-c}n$, we obtain the canonical
constraint. If $\mathsf{dist}$ is $\mathtt{uniform}(n)$ or
$\mathtt{muniform}(n)$ , we observe that the over-approximation result for the
integral is either $\frac{\exp(f(\alpha,n))}{f(\alpha,n)\cdot t(\alpha,n)}$
(when $d_{v}>0$) or $\frac{\ln n\cdot\exp(f(\alpha,n))}{f(\alpha,n)\cdot
t(\alpha,n)}$ (when $d_{v}=0$). Thus, we can cancel the term $f(\alpha,n)$ in
the exponent and obtain the canonical constraint by the subsequent steps. The
proof is the same for the divide-and-conquer case. ∎

By Proposition 2, we restrict $u_{t},v_{t}\leq 0$ in the template to ensure
our algorithm never fails.

###### Remark 1

Our algorithm can be extended to support piecewise uniform distributions (e.g.
each of $0,\dots,n/2$ with probability $\frac{2}{3n}$ and each of
$n/2+1,\dots,n-1$ with probability $\frac{4}{3n}$) by handling each piece
separately.

##  5 Experimental Results

In this section, we evaluated our algorithm over classical randomized
algorithms such as QuickSort (Example 3), QuickSelect (Example 2),
DiameterComputation [29, Chapter 9], RandomizedSearch [27, Chapter 9],
ChannelConflictResolution [24, Chapter 13], examples such as Rdwalk and
Rdadder in the literature [8], and four manually-crafted examples (MC1 – MC4).
For each example, we manually compute its expected running time for the
prunning. A detailed description of all these examples is provided in Appendix
0.B.

Figure 2: Plot for QuickSelect

We implemented our algorithm in C++. We choose $B=2$ (as the bounded range for
the template), $M=4$ (in the guess procedure), $Q=8$ (for the number of parts
in the integral), and prune the search space by Theorem 1. All results were
obtained on an Ubuntu 18.04 machine with an 8-Core Intel i7-7900x Processor
(4.30 GHz) and 40 GB of RAM.

We report the tail bound derived by our algorithm in Table 1, where
“Benchmark” lists the benchmarks, “$\alpha\cdot\kappa(n^{*})$” lists the time
limit of interest, “Our bound” lists the tail bound by our approach, “Time(s)”
lists the runtime (in seconds) of our approach, and “Karp’s bound” lists the
bounds by Karp’s method. From the table, our algorithm constantly derives
asymtotically tighter tail bounds than Karp’s method. Moreover, all these
bounds are obtained in a few seconds, demonstrating the efficiency of our
algorithm. Furthermore, our algorithm obtains bounds with tighter magnitude
than our completeness theorem (Theorem 3.3) in 9 benchmarks, and bounds with
the same magnitude as the others, see Appendix 0.F for details.

For an intuitive comparison, we also report the concrete bounds and their
plots of our method and Karp’s method. We choose three concrete choices of
$\alpha$ and $n^{*}$ and plot the concrete bounds over $10\leq\alpha\leq
15,n^{*}=17$. For concrete bounds, we also report the ratio
$\frac{\text{Karp's Bound}}{\text{Our Bound}}$ to show the strength of our
method. Due to space limitations, we only report the results for QuickSelect
(Example 2) in Table 2 and Figure 2, while the rest are relegated to Appendix
0.F.

Table 1: Experimental Result Benchmark |  $\alpha\cdot\kappa(n^{*})$ in (1) | Our bound | Time(s) | Karp’s bound
---|---|---|---|---
QuickSelect | $\alpha\cdot n^{*}$ | $\exp(2\cdot\alpha-\alpha\cdot\ln\alpha)$ | $0.03$ | $\exp(1.15-0.28\cdot\alpha)$
QuickSort | $\alpha\cdot n^{*}\cdot\ln n^{*}$ | $\exp((4-\alpha)\cdot\ln n^{*})$ | $0.02$ | $\exp(0.5-0.5\cdot\alpha)$
L1Diameter | $\alpha\cdot n^{*}$ | $\exp(\alpha-\alpha\cdot\ln\alpha)$ | $0.03$ | $\exp(1.39-0.69\cdot\alpha)$
L2Diameter | $\alpha\cdot n^{*}\cdot\ln n^{*}$ | $\exp(\alpha-\alpha\cdot\ln\alpha)$ | $0.03$ | $\exp(1.39-0.69\cdot\alpha)$
RandSearch | $\alpha\cdot\ln n^{*}$ | $\exp((2\cdot\alpha-\alpha\cdot\ln\alpha)\cdot\ln n^{*})$ | $0.03$ | $\exp(-0.29\cdot\alpha\cdot\ln n^{*})$
Channel | $\alpha\cdot n^{*}$ | $\exp((8-\alpha)\cdot n^{*})$ | $0.05$ | $\exp(1-0.37\cdot\alpha)$
Rdwalk | $\alpha\cdot n^{*}$ | $\exp((0.5-\alpha)\cdot n^{*})$ | $0.05$ | $\exp(0.60-0.41\cdot\alpha)$
Rdadder | $\alpha\cdot n^{*}$ | $\exp((4-0.5\cdot\alpha)\cdot n^{*})$ | $0.04$ | Not applicable
MC1 | $\alpha\cdot\ln n^{*}$ | $\exp((\alpha-\alpha\cdot\ln\alpha)\cdot\ln n^{*})$ | $0.03$ | $\exp(-0.69\cdot\alpha\cdot\ln n^{*})$
MC2 | $\alpha\cdot\ln^{2}n^{*}$ | $\exp((\alpha-\alpha\cdot\ln\alpha)\cdot\ln n^{*})$ | $0.03$ | $\exp(-0.69\cdot\alpha\cdot\ln n^{*})$
MC3 | $\alpha\cdot n^{*}\cdot\ln^{2}n^{*}$ | $\exp(\alpha-\alpha\cdot\ln\alpha)$ | $0.03$ | $\exp(1.15-0.28\cdot\alpha)$
MC4 | $\alpha\cdot n^{*}$ | $\exp(2\cdot\alpha-\alpha\cdot\ln\alpha)$ | $0.04$ | Not applicable
Table 2: Concrete Bounds for QuickSelect Concrete choice | Our bound | Karp’s Bound | Ratio
---|---|---|---
$\alpha=10;n^{*}=13$ | $0.0485$ | $0.192$ | $3.96$
$\alpha=11;n^{*}=15$ | $0.0126$ | $0.145$ | $11.6$
$\alpha=12;n^{*}=17$ | $0.00297$ | $0.110$ | $36.9$

##  6 Related Work

Karp’s Cookbook Our approach is orthogonal to Karp’s cookbook method [23]
since we base our approach on Markov’s inequality, and the core of Karp’s
method is a dedicated proof for establishing that an intricate tail bound
function is a prefixed point of the higher order operator derived from the
given PRR. Furthermore, our automated approach can derive asymptotically
tighter tail bounds than Karp’s method over all 12 PRRs in our benchmark. Our
approach could also handle randomized preprocessing times, which is beyond the
reach of Karp’s method. Since Karp’s proof of prefixed point is ad-hoc, it is
non-trivial to extend his method to handle the randomized cost. Nevertheless,
there are PRRs (e.g., Coupon-Collector, see Appendix 0.G) that can be handled
by Karp’s method but not by ours. Thus, our approach provides a novel way to
obtain asymptotically tighter tail bounds than Karp’s method.

The recent work [33] extends Karp’s method for deriving tail bounds for
parallel randomized algorithms. This method derives the same tail bounds as
Karp’s method over PRRs with a single recursive call (such as QuickSelect) and
cannot handle randomized pre-processing time. Compared with this approach, our
approach derives tail bounds with tighter magnitude on 11/12(92.67

Custom Analysis. Custom analysis of PRRs [17, 28] has successfully derived
tight tail bounds for QuickSelect and QuickSort. Compared with the custom
analysis that requires ad-hoc proofs, our approach is automated, has the
generality from Markov’s inequality, and is capable of deriving bounds
identical or very close to the tail bounds from the custom analysis.

Probabilistic Programs. There are also relevant approaches in probabilistic
program verification. These approaches are either based on martingale
concentration inequalities (for exponentially-decreasing tail bounds) [8, 14,
12, 21, 13], Markov’s inequality (for polynomially-decreasing tail bounds) [9,
25, 34], fixed-point synthesis [35], or weakest precondition reasoning [22,
5]. Compared with these approaches, our approach is dedicated to PRRs (a
light-weight representation of recursive probabilistic programs) and involves
specific treatment of common recursive patterns (such as randomized pivoting
and divide-and-conquer) in randomized algorithms, while these approaches
usually do not consider common recursion patterns in randomized algorithms.
Below we have detailed technical comparisons with these approaches.

– Compared with the approaches based on martingale concentration inequalities
[8, 13, 14, 12, 21], our approach has the same root as them, since martingale
concentration inequalities are often proved via Markov’s inequality. However,
those approaches have more accuracy loss since these martingale concentration
inequalities usually make further relaxations after applying Markov’s
inequality. In contrast, our automated approach directly handles the
constraint after applying Markov’s inequality by having a refined treatment of
exponentiation and hence has better accuracy in deriving tail bounds.

– Compared with the approaches [9, 25, 34] that derive polynomially-decreasing
tail bounds, our approach targets the sharper exponentially-decreasing tail
bounds and hence is orthogonal.

– Compared with the fixed-point synthesis approach [35], our approach is
orthogonal as it is based on Markov’s inequality. Note that the approach [35]
can only handle 3/12 (25

– Compared with weakest precondition reasoning [22, 5] that requires first
specifying the bound functions and then verifying the bound functions by proof
rules related to fixed-point conditions, mainly with manual efforts, our
approach can be automated and is based on Markov’s inequality rather than
fixed point theorems. Although Karp’s method is also based on a particular
tail bound function as a prefixed point and can thus be embedded into the
weakest precondition framework, Karp’s proof of prefixed point requires deep
insight, which is beyond existing proof rules. Moreover, even a slight
relaxation of the tail bound function into a simpler form in Karp’s method no
longer keeps the bound function to be a prefixed point (see Appendix 0.G for
details). Hence, the approach of the weakest precondition may not be suitable
for deriving tail bounds.

## Acknowledgement

We thank Prof. Bican Xia for valuable information on the exponential theory of
reals.

## References

  * [1] Achatz, M., McCallum, S., Weispfenning, V.: Deciding polynomial-exponential problems. In: Sendra, J.R., González-Vega, L. (eds.) Symbolic and Algebraic Computation, International Symposium, ISSAC 2008, Linz/Hagenberg, Austria, July 20-23, 2008, Proceedings. pp. 215–222. ACM (2008). https://doi.org/10.1145/1390768.1390799
  * [2] Agrawal, S., Chatterjee, K., Novotný, P.: Lexicographic ranking supermartingales: an efficient approach to termination of probabilistic programs. PACMPL 2(POPL), 34:1–34:32 (2018)
  * [3] Aguirre, A., Barthe, G., Hsu, J., Kaminski, B.L., Katoen, J.P., Matheja, C.: A pre-expectation calculus for probabilistic sensitivity. Proc. ACM Program. Lang. 5(POPL) (jan 2021). https://doi.org/10.1145/3434333
  * [4] Baier, C., Katoen, J.P.: Principles of model checking. MIT Press (2008)
  * [5] Batz, K., Kaminski, B.L., Katoen, J.P., Matheja, C., Verscht, L.: A calculus for amortized expected runtimes. Proc. ACM Program. Lang. 7(POPL), 1957–1986 (2023). https://doi.org/10.1145/3571260
  * [6] Bertot, Y., Castéran, P.: Interactive Theorem Proving and Program Development - Coq’Art: The Calculus of Inductive Constructions. Texts in Theoretical Computer Science. An EATCS Series, Springer (2004)
  * [7] Billingsley, P.: Probability and Measure. Wiley, 3rd edn. (1995)
  * [8] Chakarov, A., Sankaranarayanan, S.: Probabilistic program analysis with martingales. In: CAV. pp. 511–526 (2013)
  * [9] Chatterjee, K., Fu, H.: Termination of nondeterministic recursive probabilistic programs. CoRR abs/1701.02944 (2017)
  * [10] Chatterjee, K., Fu, H., Goharshady, A.K.: Termination analysis of probabilistic programs through positivstellensatz’s. In: CAV 2016. pp. 3–22 (2016)
  * [11] Chatterjee, K., Fu, H., Murhekar, A.: Automated recurrence analysis for almost-linear expected-runtime bounds. In: Majumdar, R., Kunčak, V. (eds.) Computer Aided Verification. pp. 118–139. Springer International Publishing, Cham (2017)
  * [12] Chatterjee, K., Fu, H., Novotný, P., Hasheminezhad, R.: Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs. TOPLAS 40(2), 7:1–7:45 (2018)
  * [13] Chatterjee, K., Goharshady, A.K., Meggendorfer, T., Zikelic, D.: Sound and complete certificates for quantitative termination analysis of probabilistic programs. In: Shoham, S., Vizel, Y. (eds.) Computer Aided Verification - 34th International Conference, CAV 2022, Haifa, Israel, August 7-10, 2022, Proceedings, Part I. Lecture Notes in Computer Science, vol. 13371, pp. 55–78. Springer (2022). https://doi.org/10.1007/978-3-031-13185-1_4
  * [14] Chatterjee, K., Novotný, P., Žikelić, Đ.: Stochastic invariants for probabilistic termination. In: POPL 2017. pp. 145–160 (2017)
  * [15] Chaudhuri, S., Dubhashi, D.P.: Probabilistic recurrence relations revisited. Theoretical Computer Science 181(1), 45–56 (1997)
  * [16] Goodman, N.D., Mansinghka, V.K., Roy, D., Bonawitz, K., Tenenbaum, J.B.: Church: a language for generative models. In: UAI 2008. pp. 220–229. AUAI Press (2008)
  * [17] Grübel, R.: Hoare’s selection algorithm: A markov chain approach. Journal of Applied Probability 35(1), 36–45 (1998), http://www.jstor.org/stable/3215544
  * [18] Hoare, C.A.R.: Algorithm 64: Quicksort. Commun. ACM 4(7), 321 (1961)
  * [19] Hoare, C.A.R.: Algorithm 65: find. Commun. ACM 4(7), 321–322 (1961)
  * [20] Hoeffding, W.: Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58(301), 13–30 (1963)
  * [21] Huang, M., Fu, H., Chatterjee, K.: New approaches for almost-sure termination of probabilistic programs. In: APLAS. pp. 181–201 (2018)
  * [22] Kaminski, B.L., Katoen, J., Matheja, C., Olmedo, F.: Weakest precondition reasoning for expected runtimes of randomized algorithms. J. ACM 65(5), 30:1–30:68 (2018). https://doi.org/10.1145/3208102
  * [23] Karp, R.M.: Probabilistic recurrence relations. Journal of the ACM 41(6), 1136–1150 (1994)
  * [24] Kleinberg, J.M., Tardos, É.: Algorithm design. Addison-Wesley (2006)
  * [25] Kura, S., Urabe, N., Hasuo, I.: Tail probabilities for randomized program runtimes via martingales for higher moments. In: Vojnar, T., Zhang, L. (eds.) TACAS. LNCS, vol. 11428, pp. 135–153. Springer (2019)
  * [26] Mahmoud, H.: Pólya urn models. CRC press (2008)
  * [27] McConnell, J.J. (ed.): The Analysis of Algorithms: An Active Learning Approach. Jones & Bartlett Learning (2001)
  * [28] McDiarmid, C., Hayward, R.: Large deviations for quicksort. Journal of Algorithms 21(3), 476–507 (1996)
  * [29] Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press (1995)
  * [30] Preparata, F.P., Muller, D.E.: Finding the intersection of n half-spaces in time o(n log n). Theor. Comput. Sci. 8, 45–55 (1979). https://doi.org/10.1016/0304-3975(79)90055-0, https://doi.org/10.1016/0304-3975(79)90055-0
  * [31] Rudin, W.: Real and Complex Analysis, 3rd Ed. McGraw-Hill, Inc., USA (1987)
  * [32] Smith, C., Hsu, J., Albarghouthi, A.: Trace abstraction modulo probability. Proc. ACM Program. Lang. 3(POPL) (jan 2019). https://doi.org/10.1145/3290352, https://doi.org/10.1145/3290352
  * [33] Tassarotti, J., Harper, R.: Verified tail bounds for randomized programs. In: ITP. pp. 560–578 (2018)
  * [34] Wang, D., Hoffmann, J., Reps, T.W.: Central moment analysis for cost accumulators in probabilistic programs. In: Freund, S.N., Yahav, E. (eds.) PLDI ’21: 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, Virtual Event, Canada, June 20-25, 2021. pp. 559–573. ACM (2021). https://doi.org/10.1145/3453483.3454062, https://doi.org/10.1145/3453483.3454062
  * [35] Wang, J., Sun, Y., Fu, H., Chatterjee, K., Goharshady, A.K.: Quantitative analysis of assertion violations in probabilistic programs. In: Freund, S.N., Yahav, E. (eds.) PLDI. pp. 1171–1186. ACM (2021)
  * [36] Wilkie, A.J.: Schanuel’s Conjecture and the Decidability of the Real Exponential Field, pp. 223–230. Springer Netherlands, Dordrecht (1997). https://doi.org/10.1007/978-94-015-8923-9_11
  * [37] Williams, D.: Probability with Martingales. Cambridge university press (1991)

##  Appendix 0.A An Illustrative Example of a Martingale

###### Example 15

Consider an unbiased and discrete random walk, in which we start at a position
$X_{0}$, and at each second walk one step to either left or right with equal
probability. Let $X_{n}$ denote our position after $n$ seconds. It is easy to
verify that
$\mathbb{E}\left(X_{n+1}|X_{0},\ldots,X_{n}\right)=\frac{1}{2}(X_{n}-1)+\frac{1}{2}(X_{n}+1)=X_{n}.$
Hence, this random walk is a martingale. Note that by definition, every
martingale is also a supermartingale. As another example, consider the
classical gambler’s ruin: a gambler starts with $Y_{0}$ dollars of money and
bets continuously until he loses all of his money. If the bets are unfair,
i.e. the expected value of his money after a bet is less than its expected
value before the bet, then the sequence $\\{Y_{n}\\}_{n\in\mathbb{N}_{0}}$ is
a supermartingale. In this case, $Y_{n}$ is the gambler’s total money after
$n$ bets. On the other hand, if the bets are fair, then
$\\{Y_{n}\\}_{n\in\mathbb{N}_{0}}$ is a martingale. See Appendix 0.A for
another illustrative example of martingales. ∎

######  Example 16 (Pólya’s Urn [26])

As a more interesting example, consider an urn that initially contains $R_{0}$
red and $B_{0}$ blue marbles ($R_{0}+B_{0}>0$). At each step, we take one
marble from the urn, chosen uniformly at random, look at its color and then
add two marbles of that color to the urn. Let $B_{n},R_{n}$ and $M_{n}$
respectively be the number of red, blue and all marbles after $n$ steps. Also,
let $\beta_{n}=\frac{B_{n}}{M_{n}}$ and $\rho_{n}=\frac{R_{n}}{M_{n}}$ be the
proportion of marbles that are blue (resp. red) after $n$ steps. Let
$\mathcal{F}_{n}$ model the observations until the $n$-th step. The process
described above leads to the following equations:

$M_{n+1}=1+M_{n},$ $\mathbb{E}\left[B_{n+1}\ |\
\mathcal{F}_{n}\right]=\mathbb{E}\left[B_{n+1}\ |\
B_{1},\ldots,B_{n}\right]=\frac{B_{n}}{M_{n}}\cdot(B_{n}+1)+\frac{R_{n}}{M_{n}}\cdot
B_{n},$ $\mathbb{E}\left[R_{n+1}\ |\
\mathcal{F}_{n}\right]=\mathbb{E}\left[R_{n+1}\ |\
B_{1},\ldots,B_{n}\right]=\frac{R_{n}}{M_{n}}\cdot(R_{n}+1)+\frac{B_{n}}{M_{n}}\cdot
R_{n}.$

Note that we did not need to care about observing $R_{i}$’s, $M_{i}$’s,
$\beta_{i}$’s or $\rho_{i}$’s, because they can be uniquely computed in terms
of $B_{i}$’s. More generally, an observer can observe only $B_{i}$’s, or only
$R_{i}$’s, or only $\beta_{i}$’s or $\rho_{i}$’s and can then compute the rest
using this information. Based on the equations above, we have:

$\mathbb{E}\left[\beta_{n+1}\ |\
\mathcal{F}_{n}\right]=\frac{B_{n}}{M_{n}}\cdot\frac{B_{n}+1}{M_{n}+1}+\frac{M_{n}-B_{n}}{M_{n}}\cdot\frac{B_{n}}{M_{n}+1}=\frac{B_{n}}{M_{n}}=\beta_{n},$
$\mathbb{E}\left[\rho_{n+1}\ |\
\mathcal{F}_{n}\right]=\frac{R_{n}}{M_{n}}\cdot\frac{R_{n}+1}{M_{n}+1}+\frac{M_{n}-R_{n}}{M_{n}}\cdot\frac{R_{n}}{M_{n}+1}=\frac{R_{n}}{M_{n}}=\rho_{n}.$

Hence, both $\\{\beta_{n}\\}_{n\in\mathbb{N}_{0}}$ and
$\\{\rho_{n}\\}_{n\in\mathbb{N}_{0}}$ are martingales. Informally, this means
that the expected proportion of blue marbles in the next step is exactly equal
to their observed proportion in the current step. This might be counter-
intuitive. For example, consider a state where 0.99 of the marbles are blue.
Then, it is more likely that we will add a blue marble in the next state.
However, this is mitigated by the fact that adding a blue marble changes the
proportions much less dramatically than adding a red marble.

##  Appendix 0.B Examples of Probabilistic Recurrence Relations

######  Example 17 (QuickSelect)

Consider the problem of finding the $d$-th smallest element in an unordered
array of $n$ distinct elements. A classical randomized algorithm for solving
this problem is QuickSelect [19]. It begins by choosing a pivot element $u$ of
the array uniformly at random. It then compares all the other $n-1$ elements
of the array with $u$ and divides them into two parts: (i) those that are
smaller than $u$ and (ii) those that are larger. Suppose that there are
$d^{\prime}$ elements in part (i). If $d^{\prime}<d-1,$ then the algorithm
recursively searches for the $(d-d^{\prime}-1)$-th smallest element of part
(ii). If $d^{\prime}=d-1,$ the algorithm terminates by returning $u$ as the
desired answer. Finally, if $d^{\prime}>d-1,$ the algorithm recursively finds
the $d-$th smallest element in part (i). Note that the classical median
selection algorithm is a special case of QuickSelect. While there is an
involved deterministic algorithm for solving the same problem, more involved
linear-time non-randomized algorithms exist for the same problem, QuickSelect
provides a simple randomized variant matching the best-known $O(n)$
deterministic runtime. Since there is only one recursive procedure in
QuickSelect, we model the algorithm as the following PRR.

$\textstyle\mathtt{def}\ p(n;2)=\\{\mathtt{sample}\
v\leftarrow\mathtt{muniform}(n)\ \mathtt{in}\ \\{\mathtt{pre}(n);\
\mathtt{invoke}\ p(v);\\}\\}$

Here, $p(n)$ represents the number of comparisons performed by QuickSelect
over an input of size $n$, and $v$ is the random variable that captures the
size of the remaining array that has to be searched recursively. It can be
derived that $v=\max\\{i,n-i-1\\}$ where $i$ is sampled uniformly from
$\\{0,\ldots,n-1\\}.$ ∎

######  Example 18 (QuickSort)

Consider the classical problem of sorting an array of $n$ distinct elements. A
well-known randomized algorithm for solving this problem is QuickSort. Similar
to QuickSelect, QuickSort begins by choosing a pivot element $u$ of the array
uniformly at random. It then compares all the other $n-1$ elements of the
array with $u$ and divides them into two sub-arrays: (i) those that are
smaller than $u$ and (ii) those that are larger. The algorithm then runs
recursively on both sub-arrays. Compared with its deterministic counterpart,
MergeSort, QuickSort provides a simple randomized variant whose expected
runtime matches the best-known deterministic runtime $O(n\log n)$.

We model the algorithm as the following PRR:

$\mathtt{def}\ p(n;2)=\\{\mathtt{sample}\ v\leftarrow\mathtt{uniform}(n)\
\mathtt{in}\ \\{\mathtt{pre}(n);\ \mathtt{invoke}\ p(v);p(n-1-v);\\}\\}$

Here, $v$ and $n-1-v$ are random variables that capture the sizes of the two
sub-arrays, where $i$ is uniformly sampled from $\\{0,\ldots,n-1\\}.$ ∎

######  Example 19 (DiameterComputation)

Consider the DiameterComputation algorithm [29, Chapter 9] to compute the
diameter of an input finite set $S$ of three-dimensional points. Depending on
the metric, i.e. Eucledian or $L_{1},$ we obtain two different recurrence
relations. For the Euclidean $L_{2}$ metric, we have the following PRR:

$\textstyle\mathtt{def}\ p(n;2)=\\{\mathtt{sample}\
v\leftarrow\mathtt{uniform}(n)\ \mathtt{in}\ \\{\mathtt{pre}(n\cdot\ln n);\
\mathtt{invoke}\ p(v);\\}\\}$

For the $L_{1}$ metric, the PRR is as follows:

$\textstyle\mathtt{def}\ p(n;2)=\\{\mathtt{sample}\
v\leftarrow\mathtt{uniform}(n)\ \mathtt{in}\ \\{\mathtt{pre}(n);\
\mathtt{invoke}\ p(v);\\}\\}$

Note that here we use deterministic versions for the subroutine
HalfspaceIntersection as required in DiameterComputation, see [30] for the
Euclidean case and [29, Problem 9.6, Page 276] for the $L_{1}$ case. ∎

######  Example 20 (RandomizedSearch)

Consider Sherwood’s RandomizedSearch algorithm (cf. [27, Chapter 9]). The
algorithm checks whether an integer value $d$ is present within the index
range $[i,j]$ ($0\leq i\leq j$) in an integer array $ar$ which is sorted in
increasing order and is without duplicate entries. The algorithm outputs
either the index of the item or $-1$ if $d$ is not present in the index range
$[i,j]$. The PRR for this example contains only one recurrence equation*:

$\mathtt{def}\ p(n;2)=\\{\mathtt{sample}\ v\leftarrow\mathtt{muniform}(n)\
\mathtt{in}\ \\{\mathtt{pre}(1);\ \mathtt{invoke}\ p(v);\\}\\}$

∎

######  Example 21 (ChannelConflictResolution)

We consider two network scenarios in which $n$ clients are trying to get
access to a network channel. This problem is also called Resource-Contention
Resolution [24, Chapter 13]. In this problem, if more than one client tries to
access the channel, then no client can access it, and if exactly one client
requests access to the channel, then the request is granted. In the concurrent
setting, the clients share one variable, which is the number of clients which
have not yet been granted access. Also in this scenario, once a client gets an
access the client does not request for access again. For this problem, we
obtain an over-approximating recurrence relation

$\mathtt{def}\
p(n;2)=\bigoplus\begin{cases}\frac{1}{e}:\mathtt{pre}(1);\mathtt{invoke}\
p(n-1);\\\ 1-\frac{1}{e}:\mathtt{pre}(1);\mathtt{invoke}\ p(n);\end{cases}$

######  Example 22 (RandomWalk)

We consider the classic random walk cases appears in many previous literatures
[10, 14, 8, 35],

$\mathtt{def}\
p(n;1)=\bigoplus\begin{cases}0.5:\mathtt{pre}(1);\mathtt{invoke}\ p(n);\\\
0.5:\mathtt{pre}(1);\mathtt{invoke}\ p(n-3);\end{cases}$

######  Example 23 (RandomAdder)

We consider the random accumulator from previous literatures [8, 35],

$\mathtt{def}\
p(n;1)=\bigoplus\begin{cases}0.5:\mathtt{pre}(2);\mathtt{invoke}\ p(n-1);\\\
0.5:\mathtt{pre}(1);\mathtt{invoke}\ p(n-1);\end{cases}$

∎

######  Example 24 (MC1)

We consider the following manually-crafted recurrence relation,

$\mathtt{def}\ p(n;2)=\\{\mathtt{sample}\ v\leftarrow\mathtt{uniform}(n)\
\mathtt{in}\ \\{\mathtt{pre}(1);\ \mathtt{invoke}\ p(v);\\}\\}$

∎

######  Example 25 (MC2)

We consider the following manually-crafted recurrence relation,

$\mathtt{def}\ p(n;2)=\\{\mathtt{sample}\ v\leftarrow\mathtt{uniform}(n)\
\mathtt{in}\ \\{\mathtt{pre}(\ln n);\ \mathtt{invoke}\ p(v);\\}\\}$

∎

######  Example 26 (MC3)

We consider the following manually-crafted recurrence relation,

$\mathtt{def}\ p(n;2)=\\{\mathtt{sample}\ v\leftarrow\mathtt{muniform}(n)\
\mathtt{in}\ \\{\mathtt{pre}(n\cdot\ln n);\ \mathtt{invoke}\ p(v);\\}\\}$

∎

######  Example 27 (MC4)

We consider the following manually-crafted recurrence relation,

$\mathtt{def}\ p(n;2)=\bigoplus\begin{cases}0.5:\\{\mathtt{sample}\
v\leftarrow\mathtt{uniform}(n)\ \mathtt{in}\ \\\
\quad\quad\quad\quad\quad\\{\mathtt{pre}(1);\ \mathtt{invoke}\
p(v);p(n-1-v);\\}\\};\\\ 0.5:\\{\mathtt{sample}\
v\leftarrow\mathtt{muniform}(n)\ \mathtt{in}\ \\{\mathtt{pre}(n);\
\mathtt{invoke}\ p(v);\\}\\}\end{cases}$

∎

##  Appendix 0.C The Detailed Semantics for PRRs

Consider a PRR generated from the grammar in Figure 1 with procedure name $p$,
a _configuration_ $\sigma$ is a pair $\sigma=(\mbox{\sl comm},\widehat{n})$
where comm is a statement that represents the current statement to be executed
and $\widehat{n}\geq c_{p}$ is a positive integer that is the current value
for the variable $n$. A _PRR state_ $\mu$ is a triple
$\langle\sigma,C,\mathbf{K}\rangle$ for which:

  * •

$\sigma$ is either the current configuration or $\mathsf{halt}$ that
represents the termination of the whole PRR.

  * •

$C\geq 0$ records the cumulative preprocessing time so far.

  * •

$\mathbf{K}$ is a stack of configurations that remain to be executed.

We use $\mathsf{emp}$ to denote an empty stack, and say that a PRR state
$\langle\sigma,C,\mathbf{K}\rangle$ is _final_ if $\mathbf{K}=\mathsf{emp}$
and $\sigma=\mathsf{halt}$. Note that in a final configuration
$\langle\mathsf{halt},C,\mathsf{emp}\rangle$, the value $C$ represents the
total execution runtime of the PRR.

The semantics of the PRR is defined as a discrete-time Markov chain whose
state space is the set of all PRR states and whose transition function
$\mathbf{P}$ is defined in the way that the probability
$\mathbf{P}(\mu,\mu^{\prime})$ that the next PRR state is $\mu^{\prime}$ given
the current PRR state $\mu=((\mbox{\sl comm},\widehat{n}),C,\mathbf{K})$ is
determined by the following cases. Below we abbreviate
$e[\widehat{n}/n,\widehat{v}/v],e_{i}[\widehat{n}/n,\widehat{v}/v],(s-v)[\widehat{n}/n,\widehat{v}/v]$
as $\widehat{e},\widehat{e_{i}},\widehat{s}-\widehat{v}$ respectively, and
denote by $\mathsf{top}(\mathbf{K}),\mathsf{pop}(\mathbf{K})$ the top element
and resp. the stack after popping the top element in a stack $\mathbf{K}$
respectively.

  * •

In the case $\mbox{\sl comm}=\mathsf{halt}$ and $\mathbf{K}=\mathsf{emp}$, we
define $\mathbf{P}(\mu,\mu):=1$ and $\mathbf{P}(\mu,\mu^{\prime}):=0$ for
other $\mu^{\prime}$. This means that the PRR stays at termination once it
terminates.

  * •

In the case $\mbox{\sl comm}=\mathtt{sample}\ v\leftarrow\mbox{\sl dist}\
\mathtt{in}\ \\{\mathtt{pre}(e);\mathtt{invoke}\ p(v);p(s-v)\\}$ with
distribution dist, pseudo-polynomial expression $e$ and size expression $s$,
we have that for every $\widehat{v}\in\mathrm{supp}(\mbox{\sl dist})$,
$\mathbf{P}(\mu,\mu_{\widehat{v}}):=\mbox{\sl dist}(\widehat{v})$ for which

$\mu_{\widehat{v}}:=\begin{cases}((\mathsf{func}(p),\widehat{v}),C+\widehat{e},(\mathsf{func}(p),\widehat{s}-\widehat{v})\cdot\mathbf{K})&\mbox{if
}\widehat{v},\widehat{s}-\widehat{v}\geq c_{p}\\\
((\mathsf{func}(p),\widehat{v}),C+\widehat{e},\mathbf{K})&\mbox{if
}\widehat{v}\geq c_{p}~{}\&~{}\widehat{s}-\widehat{v}<c_{p}\\\
((\mathsf{func}(p),\widehat{s}-\widehat{v}),C+\widehat{e},\mathbf{K})&\mbox{if
}\widehat{v}<c_{p}~{}\&~{}\widehat{s}-\widehat{v}\geq c_{p}\\\
(\mathsf{top}(\mathbf{K}),C+\widehat{e},\mathsf{pop}(\mathbf{K}))&\mbox{if
}\widehat{v},\widehat{s}-\widehat{v}<c_{p}~{}\&~{}\mathbf{K}\neq\mathsf{emp}\\\
(\mathsf{halt},C+\widehat{e},\mathsf{emp})&\mbox{if
}\widehat{v},\widehat{s}-\widehat{v}<c_{p}~{}\&~{}\mathbf{K}=\mathsf{emp}\\\
\end{cases}$

  * •

In the case $\mbox{\sl comm}=\mathtt{sample}\ v\leftarrow\mbox{\sl dist}\
\mathtt{in}\ \\{\mathtt{pre}(e);\mathtt{invoke}\ p(v)\\}$ with distribution
dist and pseudo-polynomial expression $e$. we have that for every
$\widehat{v}\in\mathrm{supp}(\mbox{\sl dist})$, we define
$\mathbf{P}(\mu,\mu_{\widehat{v}}):=\mbox{\sl dist}(\widehat{v})$ for which

$\mu^{\prime}_{\widehat{v}}:=\begin{cases}((\mathsf{func}(p),\widehat{v}),C+\widehat{e},\mathbf{K})&\mbox{if
}\widehat{v}\geq c_{p}\\\
(\mathsf{top}(\mathbf{K}),C+\widehat{e},\mathsf{pop}(\mathbf{K}))&\mbox{if
}\widehat{v}<c_{p}~{}\&~{}\mathbf{K}\neq\mathsf{emp}\\\
(\mathsf{halt},C+\widehat{e},\mathsf{emp})&\mbox{if
}\widehat{v}<c_{p}~{}\&~{}\mathbf{K}=\mathsf{emp}\\\ \end{cases}$

The case of $\mbox{\sl comm}=\mathtt{sample}\ v\leftarrow\mbox{\sl dist}\
\mathtt{in}\ \\{\mathtt{pre}(e);\mathtt{invoke}\ p(n-v)\\}$ can be obtained
analogously.

  * •

In the case $\mbox{\sl comm}=\bigoplus_{i=1}^{k}e_{i}\\!:\\!\mbox{\sl
comm}_{i}$, we have that $\mathbf{P}(\mu,\mu_{i})=\widehat{e_{i}}$ for each
$1\leq i\leq k$ for which we have $\mu_{i}:=((\mbox{\sl
comm}_{i},\widehat{n}),C,\mathbf{K})$.

With an initial PRR state $((\mathsf{func}(p),n^{*}),0,\mathsf{emp})$ where
$n^{*}\geq c_{p}$ is the input size, the Markov chain induces a probability
space where the sample space is the set of all infinite sequences of PRR
states, the $\sigma$-algebra is generated by all sets of infinite sequences of
PRR states that share a common prefix (called _cylinder sets_), and the
probability measure is uniquely determined by the probability transition
function $\mathbf{P}$. We refer to [4, Chapter 10] for details. In the
following, we denote the probability measure by $\Pr_{n^{*}}$ where $n^{*}\geq
c_{p}$ is the input size.

##  Appendix 0.D Details in Section 3

###  0.D.1 Details of the translation

The definition of $\mathsf{Tf}(\hat{n},{\sl Prog})$ is defined in Figure 3.
For recursive bodies, the translation is straightforward. For sample, we first
draw $\hat{v}$ from the distribution $\mathsf{dist}$ under the concrete input
$\hat{n}$, and we substitute concrete values $\hat{n},\hat{v}$ with $n,v$ in
the translation result for its recursive body. We use a discrete distribution
for probabilistic choice, where for each choice $1\leq i\leq k$, there is
probability $\mathsf{expr}_{i}$ and returns the translation result for the
sub-command $\mathsf{comm}_{i}$. The following theorem formalizes its
correctness.

###### Theorem 0.D.1

Given a procedure $p(n;c_{p})$, then for every $\hat{n}\geq c_{p}$,
$\mathsf{Tf}(\hat{n},\mathsf{func}(p))$ outputs the joint distribution of the
triple of random variables $(\mbox{\sl
S}(\hat{n}),\mathsf{size}_{1}(\hat{n})$,$\\\ \mathsf{size}_{2}(\hat{n}),r)$ in
(2).

###### Proof

The proof is straightforward by structural induction. The induction cases have
been illustrated in the above text.

(Command) $\textstyle\mathsf{Tf}(\hat{n},\mathtt{sample}\
v\leftarrow\mathsf{dist}\ \mathtt{in}\
\\{\mathsf{body}\\})=[\hat{n}/n,\hat{v}/v]\mathsf{Tf}(\hat{n},{\mathsf{body}})$
$\textstyle\quad where\
\hat{v}~{}is~{}a~{}meta~{}variable~{}drawn~{}from~{}the~{}distribution~{}[\hat{n}/n]\mathtt{dist}$
$\textstyle\mathsf{Tf}(\hat{n},\bigoplus_{i=1}^{k}c_{i}\\!:\\!\mathsf{comm}_{i})$
$\textstyle\quad=\mathsf{discrete}\left\\{c_{1}:\mathsf{Tf}(\hat{n},\mathsf{comm}_{1}),\dots,c_{k}:\mathsf{Tf}(\hat{n},\mathsf{comm}_{k})\right\\}$
(Rec Body)
$\textstyle\mathsf{Tf}(\hat{n},\mathtt{pre}(\mathsf{expr});\mathtt{invoke}\
p(\mathsf{size}_{1});p(\mathsf{size}_{2}))=([\hat{n}/n]\mathsf{expr},[\hat{n}/n]\mathsf{size}_{1},[\hat{n}/n]\mathsf{size}_{2},2)$
$\textstyle\mathsf{Tf}(\hat{n},\mathtt{pre}(\mathsf{expr});\mathtt{invoke}\
p(\mathsf{size}_{1}))=([\hat{n}/n]\mathsf{expr},[\hat{n}/n]\mathsf{size}_{1},0,1)$
Figure 3: Transformation Function $\mathsf{Tf}$

###  0.D.2 Full Proof of Theorem 3.2

Below we present the full proof of Theorem 3.2. To prove Theorem 3.2, we need
the extension of conditional expectation to non-negative random variables that
are not necessarily integrable. We adopt the method in the previous work [2],
where the conditional expectation is extended for non-negative random
variables. A random variable $X$ is _non-negative_ if $X(\omega)\geq 0$ for
all elements $\omega$ in the sample space.

######  Theorem 0.D.2 ([2, Proposition 3.1])

Let $X$ be any non-negative random variable from a probability space
$(\Omega,\mathcal{F},\Pr)$ and $\mathcal{G}$ be a sub-$\sigma$-algebra of
$\mathcal{F}$ (i.e., $\mathcal{G}\subseteq\mathcal{F}$). Then there exists a
random variable $\mathbb{E}\left[X\ |\ \mathcal{G}\right]$ from
$(\Omega,\mathcal{F},\Pr)$ (called a conditional expectation of $X$ w.r.t
$\mathcal{G}$) that fulfills the two conditions (E1) and (E2) below:

  * (E1)

$\mathbb{E}\left[X\ |\ \mathcal{G}\right]$ is $\mathcal{G}$-measurable, and

  * (E2)

for all $A\in\mathcal{G}$, we have $\int_{A}\mathbb{E}\left[X\ |\
\mathcal{G}\right]\,\mathrm{d}\\!\Pr=\int_{A}{X}\,\mathrm{d}\\!\Pr$.

Moreover, the conditional expectation is almost surely unique, i.e., for any
random variables $Y,Z$ from $(\Omega,\mathcal{F},\Pr)$ that both fulfill (E1)
and (E2), we have that $\Pr(Y=Z)=1$.

Below we show that some basic property we utilize in our proof is still valid
upon the extension. Below we fix a probability space
$(\Omega,\mathcal{F},\Pr)$ and a sub-$\sigma$-algebra
$\mathcal{G}\subseteq\mathcal{F}$. The following properties hold for _non-
negative_ random variables $X,Y,Z$.

  * (E3)

(‘Taking out what is known’) If $Z$ is $\mathcal{G}$-measurable, then
$\mathbb{E}\left[Z\cdot X\ |\ \mathcal{G}\right]=Z\cdot\mathbb{E}\left[X\ |\
\mathcal{G}\right]$ a.s. The proof is exactly the same as under ‘Proof of (j)’
on [37, Page 90] for the non-negative case.

Our proof relies on the celebrated optional stopping theorem, which is stated
below:

######  Theorem 0.D.3 (Optional stopping theorem [37, Theorem 10.10])

For any discrete-time supermartingale $\Gamma=\\{X_{n}\\}_{n\in\mathbb{N}}$
adapted to a filtration $\\{\mathcal{F}_{n}\\}_{n\in\mathbb{N}}$ where every
random variable $X_{n}$ is non-negative, and any stopping time $\rho$ w.r.t
the filtration $\\{\mathcal{F}_{n}\\}_{n\in\mathbb{N}}$ that is almost surely
finite (i.e. $\Pr(\rho<\infty)=1$), we have
$\mathbb{E}[X_{\rho}]\leq\mathbb{E}[X_{0}]$.

Now we are ready to prove Theorem 3.2.

######  Proof (Proof of Theorem 3.2)

We fix some sufficiently large $\alpha$ and $n^{*}$. In general, we apply the
martingale theory to prove this theorem. To construct a martingale, we need to
make two preparations.

First, since $t_{*}(\alpha,n^{*})\leq t(\alpha,n)$ for every $c_{p}\leq n\leq
n^{*}$, substituting $t(\alpha,n)$ with $t_{*}(\alpha,n^{*})$ in (4) does not
affect the validity of (4) by the convexity of $\exp(\cdot)$, i.e., $\forall
c_{p}\leq n\leq n^{*}$, we have that:

$\textstyle\mathbb{E}[\exp(t_{*}(\alpha,n^{*})\cdot\mathsf{Ex}(n\mid f))]\leq
t_{*}(\alpha,n^{*})\cdot f(\alpha,n)$ (10)

Second, given an infinite sequence of the PRR states
$\rho=\mu_{0},\mu_{1},\dots$ in the sample space, we construct its entry
subsequence $\rho^{\prime}=\mu^{\prime}_{0},\mu_{1}^{\prime},\dots$ as
follows. We keep all states $(({\sl comm},\hat{n}),C,\mathbf{K})\in\rho$ at
the entry point of the procedure $p$, i.e., ${\sl comm}=\mathsf{func}(p)$, we
also keep all final states, and remove all other states. We further define
$\tau^{\prime}:=\inf\\{t:\mu^{\prime}_{t}\ \text{is final}\\}$. Note that
$C^{\prime}_{\tau^{\prime}}=C_{\tau}$. Furthermore, for every $i\geq 0$, if
the state $\mu_{i}^{\prime}$ is not a final state, then $\mu_{i+1}^{\prime}$
represents the recursive calls of the state $\mu_{i}^{\prime}$. Recall that by
theorem 0.D.1, we have that the function
$\mathsf{Tf}(\hat{n},\mathsf{func}(p))$ outputs the joint distribution of the
quadruple of random variables $(\mbox{\sl
S}(\hat{n}),\mathsf{size}_{1}(\hat{n}),\mathsf{size}_{2}(\hat{n}),r)$ after
executing $\mathsf{func}(p)$. Hence, if some state $\mu_{i}^{\prime}=(({\sl
comm}_{i}^{\prime},\hat{n}_{i}^{\prime}),C_{i}^{\prime},\mathbf{K}_{i}^{\prime})\in\rho^{\prime}$
is not final, $\mu_{i+1}^{\prime}$ observes as the following distribution.

  * •

Sample $(\Delta,\mathsf{s}_{1},\mathsf{s}_{2},r)$ from
$\mathsf{Tf}(\hat{n}_{i}^{\prime},\mathsf{func}(p))$.

  * •

If $r=1$,we have that:

$\mu_{i+1}^{\prime}=\begin{cases}((\mathsf{func}(p),\mathsf{s}_{1}),C_{i}^{\prime}+\Delta,\mathbf{K}_{i}^{\prime})&\mathsf{s}_{1}\geq
c_{p}\\\
(\mathsf{top}(\mathbf{K}_{i}^{\prime}),C_{i}^{\prime}+\Delta,\mathsf{pop}(\mathbf{K}_{i}^{\prime}))&\mathsf{s}_{1}<c_{p}\land\mathbf{K}_{i}^{\prime}\neq\mathsf{emp}\\\
(\mathsf{halt},C_{i}^{\prime}+\Delta,\mathsf{emp})&\mathsf{s}_{1}<c_{p}\land\mathbf{K}_{i}^{\prime}=\mathsf{emp}\end{cases}$

  * •

If $r=2$,we have that:

$\mu_{i+1}^{\prime}=\begin{cases}((\mathsf{func}(p),\mathsf{s}_{1}),C_{i}^{\prime}+\Delta,(\mathsf{func}(p),\mathsf{s}_{2})\cdot\mathbf{K}_{i}^{\prime})&\mathsf{s}_{1}\geq
c_{p}\land\mathsf{s}_{2}\geq c_{p}\\\
((\mathsf{func}(p),\mathsf{s}_{1}),C_{i}^{\prime}+\Delta,\mathbf{K}_{i}^{\prime})&\mathsf{s}_{1}\geq
c_{p}\land\mathsf{s}_{2}<c_{p}\\\
((\mathsf{func}(p),\mathsf{s}_{2}),C_{i}^{\prime}+\Delta,\mathbf{K}_{i}^{\prime})&\mathsf{s}_{1}<c_{p}\land\mathsf{s}_{2}\geq
c_{p}\\\
(\mathsf{top}(\mathbf{K}_{i}^{\prime}),C_{i}^{\prime}+\Delta,\mathsf{pop}(\mathbf{K}_{i}^{\prime}))&\mathsf{s}_{1}<c_{p}\land\mathsf{s}_{2}<c_{p}\land\mathbf{K}_{i}^{\prime}\neq\mathsf{emp}\\\
(\mathsf{halt},C_{i}^{\prime}+\Delta,\mathsf{emp})&\mathsf{s}_{1}<c_{p}\land\mathsf{s}_{2}<c_{p}\land\mathbf{K}_{i}^{\prime}=\mathsf{emp}\end{cases}$

Now we are ready to define the martingale. Given an entry subsequence
$\rho^{\prime}=\mu^{\prime}_{0},\mu_{1}^{\prime},\dots$ in the sample space,
for each $i\geq 0$, suppose $\mu_{i}^{\prime}=(({\sl
comm}_{i}^{\prime},\hat{n}_{i}^{\prime}),C_{i}^{\prime},\mathbf{K}_{i}^{\prime})$
and
$\mathbf{K}_{i}^{\prime}=(\mathsf{func}(p),\mathsf{s}_{i,1})\cdots(\mathsf{func}(p),\mathsf{s}_{i,q_{i}})$,
where $q_{i}$ represent the length of the stack. We define

$\textstyle
y_{i}:=\exp\left(C_{i}^{\prime}+f(\alpha,\hat{n}_{i}^{\prime})+\sum_{1\leq
j\leq q_{i}}f(\alpha,\mathsf{s}_{i,j})\right)$

Note that if $\mu_{i}^{\prime}$ is not final, we have that:

$\textstyle\mathbb{E}[y_{i+1}\mid y_{i}]$ $\textstyle\leq
y_{i}\cdot\mathbb{E}\left[\exp\left(\mbox{\sl
S}(\hat{n}_{i}^{\prime})+\sum_{j=1}^{r}f(\alpha,\mathsf{size}_{j}(\hat{n}_{i}^{\prime}))-f(\alpha,\hat{n}_{i}^{\prime})\right)\right]$
$\textstyle\leq y_{i}$

where the first inequality is obtained by comparing $\mu_{i}^{\prime}$ and
$\mu_{i+1}^{\prime}$ from the explicit formula of $\mu_{i+1}^{\prime}$, and
(E3) of the extended conditional expectation. The second inequality is from
(10). Otherwise, if $\mu_{i}$ is final, then it is straightforward that
$y_{i+1}=y_{i}=1$, thus we also have $\mathbb{E}[y_{i+1}\mid y_{i}]\leq y_{i}$
in this case.

Thus, $y_{0},y_{1},\ldots$ is a supermartingale, thus by the optional stopping
theorem (Theorem 0.D.3), we have that

$\textstyle\mathbb{E}\left[\exp\left(t_{*}(\alpha,n^{*})\cdot
C_{\tau}\right)\right]$
$\textstyle=\mathbb{E}\left[\exp\left(t_{*}(\alpha,n^{*})\cdot
C^{\prime}_{\tau^{\prime}}\right)\right]$
$\textstyle=\mathbb{E}\left[y_{\tau^{\prime}}\right]\leq\mathbb{E}[y_{0}]=\exp\left(t_{*}(\alpha,n^{*})\cdot
f(\alpha,n^{*})\right)$

∎

###  0.D.3 Proof of Theorem 3.3

######  Proof (Proof of Theorem 3.3)

The proof relies on Hoeffiding’s Lemma as follows.

######  Theorem 0.D.4 (Hoeffidng’s Lemma,[20])

For every bounded random variable $a\leq X\leq b$, we have that
$\mathbb{E}[\exp(X)]\leq\exp(\mathbb{E}[X])\cdot\exp\left(\frac{(b-a)^{2}}{8}\right)$.

We first rephrase the constraint (4) as

$\textstyle\mathbb{E}\left[\exp\left(t(\alpha,n)\cdot(\mbox{\sl
S}(n)+\sum_{i=1}^{r}f(\alpha,\mathsf{size}_{i}(n))-f(\alpha,n))\right)\right]\leq
1$

Define $X(\alpha,n)$ as the exponent in the $\exp(\cdot)$,
$X(\alpha,n):=t(\alpha,n)\cdot(\mbox{\sl
S}(n)+\sum_{i=1}^{r}f(\alpha,\mathsf{size}_{i}(n))-f(\alpha,n))$, since we
choose $f(\alpha,n)$ as $w(\alpha)\cdot\mathbb{E}[p(n)]$, and the fact that
$\mathbb{E}[p(n)]=\mathbb{E}[\mbox{\sl
S}(n)]+\sum_{i=1}^{r}\mathbb{E}[p(\mathsf{size}_{i})]$, we have that

$\textstyle\mathbb{E}[X(\alpha,n)]$
$\textstyle=t(\alpha,n)\cdot(\mathbb{E}[\mbox{\sl
S}(n)]+w(\alpha)\cdot\sum_{i=1}^{r}\mathbb{E}[p(\mathsf{size}_{i})]-w(\alpha)\cdot\mathbb{E}[p(n)])$
$\textstyle=t(\alpha,n)\cdot(\mathbb{E}[\mbox{\sl
S}(n)]-w(\alpha)\cdot\mathbb{E}[\mbox{\sl S}(n)])$
$\textstyle=\frac{\lambda(\alpha)}{\mathbb{E}[\mbox{\sl
S}(n)]}\cdot(1-w(\alpha))\cdot\mathbb{E}[\mbox{\sl S}(n)]$
$\textstyle=-\lambda(\alpha)\cdot(w(\alpha)-1)$

Furthermore, by (A1), we have that $X(\alpha,n)$ ranges from
$\lambda(\alpha)\cdot(1-w(\alpha)+w(\alpha)\cdot M_{1})$ to
$\lambda(\alpha)\cdot(1-w(\alpha)+w(\alpha)\cdot M_{2})$. Hence, by the
theorem above, we have that:

$\textstyle\mathbb{E}[\exp(X(\alpha,n))]\leq\exp\left(-\lambda(\alpha)\cdot(w(\alpha)-1)+\frac{\lambda(\alpha)^{2}\cdot
w(\alpha)^{2}\cdot(M_{2}-M_{1})^{2}}{8}\right)\leq 1$

where the second inequality is due to our choice of $\lambda(\alpha)$. Hence
the theorem follows. ∎

##  Appendix 0.E Details in Our Algorithmic Approach

###  0.E.1 Proof of Theorem 4.1

###### Proof

Suppose $c_{t},c_{f}$ are valid and $c_{t}^{\prime},c_{f}^{\prime}$ are also
valid, then due to the convexity, for any $0<\lambda<1$, $\lambda\cdot
c_{t}+(1-\lambda)\cdot c_{t}^{\prime},\lambda\cdot c_{f}+(1-\lambda)\cdot
c_{f}^{\prime}$ is also valid. Thus the second item holds since $0,c_{f}$ is
always valid. The first items holds from the inequality
$\sum_{i=1}^{r}f(\alpha,\mathsf{size}_{i}(n))\leq f(\alpha,n)$ if
$\sum_{i=1}^{r}\mathsf{size}_{i}\leq n$.

###  0.E.2 The Algorithm Decide

We first present some computer algebra backgrounds.

#### Monotonicity of pseudo-monomials

We need a complete depiction of the monotonicity of pseudo monomials, which
could be straightforwardly proved by computing the derivative.

the monotonicity of a pseudo-monomial $n^{a}\cdot\ln^{b}n$ is presented in
Table 3.

Table 3: Monotonicity of pseudo-monomials, where we use $\uparrow\\!(a,b)$ to represent the pseudo-monomial is non-decreasing when $n\in[a,b]$, use $\downarrow\\!(a,b)$ to represent that the function is non-increasing when $n\in[a,b]$. | $b<0$ | $b=0$ | $b>0$
---|---|---|---
$a<0$ | $\downarrow(c_{p},\infty)$ |  $\uparrow(c_{p},\exp\left(-\frac{b}{a}\right))$ and $\downarrow(\exp\left(-\frac{b}{a}\right),\infty)$
$a=0$ | $\downarrow(0,\infty)$ | constant | $\uparrow(c_{p},\infty)$
$a>0$ |  $\downarrow(c_{p},\exp\left(-\frac{b}{a}\right))$ and $\uparrow(\exp\left(-\frac{b}{a}\right),\infty)$ | $\uparrow(c_{p},\infty)$

#### The function $\mathsf{NegativeLB}(P)$

Our decision procedure for canonical forms relies on a function
$\mathsf{NegativeLB}(P)$, it takes on input as a pseudo-polynomial $P(n)$
whose sub-monomial term with highest magnitude is negative, and outputs an
integer $L^{*}$ such that $P(n)<0$ for every $n\geq L^{*}$. It is achieved by
three steps below.

  1. 1.

Our algorithm firstly finds the term with largest order. In detail, our
algorithm will scan each term in the polynomial and finds the term with
highest degree of $n$, if there are several terms with the same highest degree
of $n$, our algorithm chooses the term among them with the highest degree of
$\ln n$. Formally, our algorithm finds the term $n^{a^{*}}\cdot\ln^{b^{*}}n$
with $c_{a^{*},b^{*}}\neq 0$ and highest $a^{*}$, if there are more than one
terms such that their degree of $n$ are all equal to $a^{*}$, we choose the
largest $b^{*}$ among them. Then, our algorithm divides each term in $P(n)$ by
$n^{a^{*}}\cdot\ln^{b^{*}}n$, and derives the pseudo-polynomial $P_{1}(n)$
below:

$\textstyle P_{1}(n)=c_{a^{*},b^{*}}+\sum_{a,b\neq a^{*},b^{*}}c_{a,b}\cdot
n^{a-a^{*}}\cdot\ln^{b-b^{*}}n$

Note that by our choice of $a^{*},b^{*}$, the degree of $n$ and $\ln n$ in
each non-constant term in $P_{1}(n)$, i.e., $a-a^{*},b-b^{*}$ either satisfies
$a-a^{*}\leq-1$, or satisfies $a-a^{*}=0$ and $b-b^{*}\leq-1$. Furthermore, we
have that $P(n)<0$ if and only of $P_{1}(n)<0$ when $n\geq c_{p}$. Hence, the
transformation from $P(n)$ to $P_{1}(n)$ does not affect the answer. Below, we
consider to compute $\mathsf{NegativeLB}(P_{1})$.

  2. 2.

Next, we consider an over-approximation $P_{2}(n)$ the function $P_{1}(n)$ as
follows.

$\textstyle P_{2}(n):=c_{a^{*},b^{*}}+\sum_{a,b\neq
a^{*},b^{*}}\max\\{0,c_{a,b}\\}\cdot n^{a-a^{*}}\cdot\ln^{b-b^{*}}n$

It removes all non-constant terms with negative coefficients. We prove that
there exists a threshold $n_{e}$ such that $P_{2}(n)$ will monotonically
decreasing for every $n\geq n_{e}$. Formally, we have that:

###### Proposition 3

Let

$\textstyle n_{e}:=\lceil\max\\{\exp(-(b-b^{*})/(a-a^{*}))\ |\
(a,b)\neq(a^{*},b^{*})\ \text{and}\ c_{a,b}\neq 0\\}\rceil$

be a constant. Then we have that $P_{2}(n)$ monotonically decreases for every
$n\geq n_{e}$.

###### Proof

Note that every coefficient for non-constant terms in $P_{2}(n)$ is non-
negative. Thus the proposition directly follows from the monotonicity of the
function $n^{a}\cdot\ln^{b}n$ (Table 3).

Since $P_{1}(n)\leq P_{2}(n)$, we have that $\mathsf{NegativeLB}(P_{2})$ also
serves as an valid answer to $\mathsf{NegativeLB}(P_{1})$. Blow, we consider
to compute $\mathsf{NegativeLB}(P_{2})$.

  3. 3.

To compute $\mathsf{NegativeLB}(P_{2})$, we simply enumerate every $n\geq
n_{e}$ until we find some $n^{*}$ such that $P_{2}(n^{*})<0$. Since $P_{2}(n)$
will monotonically decreasing for every $n\geq n_{e}$, for every $n\geq
n^{*}$, $P_{1}(n)\leq P_{2}(n)\leq P_{2}(n^{*})<0$. Thus, $n^{*}$ is a valid
answer to $\mathsf{NegativeLB}(P_{1})$ and $\mathsf{NegativeLB}(P)$.

Since sub-monomial term in $P(n)$ with highest magnitude has negative
coefficient, we have that $c_{a^{*},b^{*}}<0$. Hence, the function
NegativeLB$(P)$ always terminates since as long as $n$ is sufficiently large,
the $P_{2}(n)$ will be negative.

#### The decision procedure

Our goal is to decide if $Q(\alpha,n)$ holds for every sufficiently large
$\alpha,n^{*}$ and every $c_{p}\leq n\leq n^{*}$. Since $Q(\alpha,n)$ is
irrelevant to $n^{*}$, it suffices to check whether the constraint holds over
every sufficiently large $\alpha$ and every $n\geq c_{p}$. For each $1\leq
i\leq k$, we use $S_{i}^{\alpha}$ to represent the sub-monomial term
$f_{i}(\alpha)$ with highest magnitude, i.e., the sub-monomial term that
firstly maximizes the degree of $\alpha$, and then maximizes the degree of
$\ln\alpha$. Similarly, we use $S_{i}^{n}$ to represent the sub-monomial term
$g_{i}(n)$ with highest magnitude. The decision procedure consists of two
steps. The pseudo-code is presented in Algorithm 3.

Input : A constraint $Q(\alpha,n)$ in the canonical form (7)

Output : Decide whether $Q(\alpha,n)$ holds over every sufficiently large
$\alpha$ and every $n\geq c_{p}$.

1 Procedure  _Decide(_$Q(\alpha,n)$_)_:

2 //The first step

3 $L:=c_{p}$

4 for  _$i:=1,2,\ldots,k$_ do

5 $S_{i}^{n}:=$ the sub-monomial term in $g_{i}(n)$ with highest magnitude.

6 if  _$S_{i}^{n} >0$_ then

7 Return False

8 else

9 $g_{i}^{\prime}(n):=$ the derivative of $g_{i}(n)$

10 $L:=\max\\{L,{\sf NegativeLB}(g_{i}^{\prime}(n))\\}$

11

12 //The second step

13 for  _$\overline{n}:=c_{p},\ldots,L$_ do

14 $Q(\alpha,\overline{n}):=$ substitute $n$ with $\overline{n}$ in
$Q(\alpha,n)$

15 $R:=0$

16 for  _$i:=1,2,\ldots,k$_ do

17 $S_{i}^{\alpha}:=$ the sub-monomial term in
$f_{i}(\alpha)+g_{i}(\overline{n})$ with highest magnitude.

18 Calculate $\Delta$ as the limit of $f_{i}(\alpha)+g_{i}(\overline{n})$ when
$\alpha\to\infty$ by Proposition 4.

19 if  _$\Delta=\infty$_ then

20 Return False

21 else

22 $R:=R+\gamma_{i}\cdot\Delta$

23

24 if  _$R\geq 1$_ then Return False;

25

26 Return True

Algorithm 3 The Decision procedure for canonical forms

$\bullet$ _First_ , in Lines 3–10, for each $1\leq i\leq k$, we inspect the
term $S_{i}^{n}$, if $S_{i}^{n}$ has positive coefficient, then clearly
$f_{i}(n)\to\infty$ when $n\to\infty$ . Thus, the term
$\exp(g_{i}(n)+f_{i}(\alpha))$ could be arbitrarily large. As a result, we can
safely conclude that $Q(\alpha,n)$ does not hold (Lines 6–7). Otherwise, by
computing $\mathsf{NegativeLB}(g_{i}^{\prime}(n))$, we have that conclude that
$\exp(g_{i}(n)+f_{i}(\alpha))$ will be non-increasing as long as
$n\geq\mathsf{NegativeLB}(g_{i}^{\prime}(n))$. By taking the maximum over all
$1\leq i\leq k$ (the maximum is stored in $L$) (Line 10), we have that the LHS
of $Q(\alpha,n)$ will be non-increasing as long as $n\geq L$. Hence, it
suffices to check every $c_{p}\leq n\leq L$.

$\bullet$ _Second_ , for every integer $c_{p}\leq\overline{n}\leq L$, we
substitute $n$ with $\overline{n}$ to eliminate $n$ in the exponent of the
canonical form (7). Then, each exponent $f_{i}(\alpha)+g_{i}(\overline{n})$
becomes a pseudo-polynomial solely over $\alpha$. Since we only concern
sufficiently large $\alpha$, we can compute the limit $\Delta$ of
$\exp(f_{i}(\alpha)+g_{i}(\overline{n}))$ when $\alpha\to\infty$ by the
proposition (Proposition 4) below, which could be proved straightforwardly.

###### Proposition 4

The limit $\Delta$ of $\exp(f_{i}(\alpha)+g_{i}(\overline{n}))$ when
$\alpha\to\infty$ is as follows.

  * •

If $S_{i}^{\alpha}$ is superconsant and $S_{i}^{\alpha}>0$, then
$\Delta=\infty$.

  * •

If $S_{i}^{\alpha}$ is superconsant and $S_{i}^{\alpha}<0$, then $\Delta=0$.

  * •

If $S_{i}^{\alpha}$ is constant $C$, then $\Delta=\exp(C)$.

  * •

If $S_{i}^{\alpha}$ is subconstant, then $\Delta=1$.

By sum up the $\Delta$ for every $1\leq i\leq k$ as $R$, we compute the limit
of the LHS of $Q(\alpha,\overline{n})$ when $\alpha\to\infty$. We conclude
that $Q(\alpha,n)$ if and only if $R<1$ for every $c_{p}\leq\overline{n}\leq
L$. The property of our algorithm is as follows.

###### Theorem 0.E.1

The algorithm (Algorithm 3) has the following property.

  * •

If there exists two constants $\varepsilon,M>0$, such that for every
$\alpha\geq M$ and every $n\geq c_{p}$, the LHS of $Q(\alpha,n)\leq
1-\varepsilon$, then our algorithm will conclude that $Q(\alpha,n)$ holds.

  * •

If $Q(\alpha,n)$ does not hold for sufficiently large $\alpha$ and every
$n\geq c_{p}$, then our algorithm will conclude that $Q(\alpha,n)$ does not
hold.

###### Proof

Since $R$ is the limit of $Q(\alpha,n)$, the two items follows by the
definition of limit. ∎

###  0.E.3 Details for the Divide-and-conquer Case

Below we illustrate the divide-and-conquer case. We represent the branch as
$\mathtt{pre}(S(n));p(v);p(H_{2}(n)-v);$, where $H_{2}(n)$ is of the form
$\lceil\frac{n}{b}\rceil+c$ or $\lfloor\frac{n}{b}\rfloor+c$. W.l.o.g., we
assume that $H_{2}(n)$ is $n-1$ or $n$, and other choices of $H_{2}(n)$
follows the same treatment. Similar to the single recursion case, we perform a
case analysis on $\mathsf{dist}$. When $\mathsf{dist}$ is an FSDPD, we follow
the same strategy as (S1-D) and (S2-D). In detail, for (S1-D), we observe that
$f(\alpha,v)+f(\alpha,H_{2}(n)-v)\leq f(\alpha,H_{2}(n))\leq f(\alpha,n)$,
thus we can still over-approximate the expectation in (8) as $t(\alpha,n)\cdot
S(n)$. For (S2-D), we only need to further consider to over-approximate the
extra term $t(\alpha,n)\cdot f(\alpha,H_{2}(n)-v)$ by the same procedure.

When $\mathsf{dist}$ is $\mathtt{uniform}(n)$ (or $\mathtt{muniform}(n)$),
then we can also over-approximate the subterm in the expectation (8)
$L=\mathbb{E}[\exp(t(\alpha,n)\cdot(f(\alpha,v)+f(\alpha,H_{2}(n)-v)))]$
through the summation as follows:

$\textstyle
L\leq\frac{1}{n}\sum_{i=0}^{n-1}\exp(t(\alpha,n)\cdot(f(\alpha,v)+f(\alpha,H_{2}(n)-v)))$
(11)

When $\mathsf{dist}$ is $\mathtt{muniform}(n)$, we simply replace
$\frac{1}{n}$ by $\frac{2}{n}$. Since $f(\alpha,v)+f(\alpha,H_{2}(n)-v)$ is
non-decreasing when $v\in[0,\lceil\frac{H_{2}(n)}{2}\rceil-1]$ and is non-
increasing when $v\in[\lfloor\frac{H_{2}(n)}{2}\rfloor+1,H_{2}(n)]$. Hence, we
can over-approximate the summation in (11) as two integrals:

$\textstyle\left(\int_{0}^{\lceil\frac{H_{2}(n)}{2}\rceil}+\int_{\lfloor\frac{H_{2}(n)}{2}\rfloor}^{H_{2}(n)}\right)\exp(t(\alpha,n)\cdot(f(\alpha,v)+f(\alpha,H_{2}(n)-v))\text{d}v$
$\textstyle=2\int_{0}^{\lceil\frac{H_{2}(n)}{2}\rceil}\exp(t(\alpha,n)\cdot(f(\alpha,v)+f(\alpha,H_{2}(n)-v))\text{d}v$

The integral is more complex than the single recursion case, since we need to
integrate the exponential function whose exponent is a pseudo-polynoimal over
$n,\alpha,v$ and $H_{2}(n)-v$. Thus, it is hard to apply our approach in the
single recursion case. Instead, we cut the integral into $Q$ parts (where $Q$
is also a parameter) with equal length and over-approximate each part using
the maximum value. Intuitively, the over-approximation will be more precise
when $Q$ increases. In this way, we can over-approximate the integral as:

$\textstyle 2\cdot\lceil\frac{H_{2}(n)}{2\cdot
Q}\rceil\sum_{i=1}^{Q}\exp(t(\alpha,n)\cdot(f(\alpha,\frac{i}{Q}\cdot\lceil\frac{H_{2}(n)}{2}\rceil)+f(\alpha,H_{2}(n)-\frac{i}{Q}\cdot\lceil\frac{H_{2}(n)}{2}\rceil))$

Note that the formula above is similar to the case of FSDPD, we apply the same
strategy for FSDPDs to over-approximate the formula above into the canonical
constraint.

##  Appendix 0.F Details in the Empirical Evaluation (Section 5)

###  0.F.1 Detailed Synthesis Result

In Table 4, we present the detailed synthesis results for each benchmark.

Table 4: Detailed Synthesis Result Benchmark | $\kappa(n^{*})$ | Function |  Tail bound $u(\alpha,n^{*})$ | Time(s)
---|---|---|---|---
QuickSelect | $n^{*}$ |  $\overline{f}(\alpha,n)=\frac{2\cdot\alpha}{\ln\alpha}\cdot n$ $\overline{t}(\alpha,n)=\ln\alpha\cdot n^{-1}$ | $\exp(2\cdot\alpha-\alpha\cdot\ln\alpha)$ | $0.03$
QuickSort | $n^{*}\\!\cdot\\!\ln n^{*}$ |  $\overline{f}(\alpha,n)=4\cdot n\cdot\ln n$ $\overline{t}(\alpha,n)=n^{-1}$ | $\exp((4-\alpha)\cdot\ln n)$ | $0.02$
L1Diameter | $n^{*}$ |  $\overline{f}(\alpha,n)=\frac{\alpha}{\ln\alpha}\cdot n$ $\overline{t}(\alpha,n)=\ln\alpha\cdot n^{-1}$ | $\exp(\alpha-\alpha\cdot\ln\alpha)$ | $0.03$
L2Diameter | $n^{*}\\!\cdot\\!\ln n^{*}$ |  $\overline{f}(\alpha,n)=\frac{\alpha}{\ln\alpha}\cdot n\cdot\ln n$ $\overline{t}(\alpha,n)=\ln\alpha\cdot n^{-1}\cdot\ln^{-1}n$ | $\exp(\alpha-\alpha\cdot\ln\alpha)$ | $0.03$
RandSearch | $\ln n^{*}$ |  $\overline{f}(\alpha,n)=\frac{2\cdot\alpha}{\ln\alpha}\cdot\ln n$ $\overline{t}(\alpha,n)=\ln\alpha$ | $\exp((2\cdot\alpha-\alpha\cdot\ln\alpha)\cdot\ln n^{*})$ | $0.03$
Channel | $n^{*}$ |  $\overline{f}(\alpha,n)=8\cdot n$ $\overline{t}(\alpha,n)=1$ | $\exp(\frac{1}{2}\cdot(8-\alpha)\cdot n^{*})$ | $0.05$
Rdwalk | $n^{*}$ |  $\overline{f}(\alpha,n)=0.5\cdot n$ $\overline{t}(\alpha,n)=1$ | $\exp((0.5-\alpha)\cdot n^{*})$ | $0.05$
Rdadder | $n^{*}$ |  $\overline{f}(\alpha,n)=8\cdot n$ $\overline{t}(\alpha,n)=\frac{1}{2}$ | $\exp((4-0.5\cdot\alpha)\cdot n^{*})$ | $0.04$
MC1 | $\ln n^{*}$ |  $\overline{f}(\alpha,n)=\frac{\alpha}{\ln\alpha}\cdot\ln n$ $\overline{t}(\alpha,n)=\ln\alpha$ | $\exp(\alpha-\alpha\cdot\ln\alpha)$ | $0.03$
MC2 | $\ln^{2}n^{*}$ |  $\overline{f}(\alpha,n)=\frac{\alpha}{\ln\alpha}\cdot\ln^{2}n$ $\overline{t}(\alpha,n)=\frac{\ln\alpha}{\ln n}$ | $\exp((\alpha-\alpha\ln\alpha)\cdot\ln n^{*})$ | $0.03$
MC3 | $n^{*}\cdot\ln^{2}n^{*}$ |  $\overline{f}(\alpha,n)=\frac{2\cdot\alpha}{\ln\alpha}\cdot n\cdot\ln^{2}n$ $\overline{t}(\alpha,n)=\frac{\ln\alpha}{n\cdot\ln^{2}n}$ | $\exp(2\cdot\alpha-\alpha\ln\alpha)$ | $0.03$
MC4 | $n^{*}$ |  $\overline{f}(\alpha,n)=\frac{2\cdot\alpha}{\ln\alpha}\cdot n$ $\overline{t}(\alpha,n)=\ln\alpha\cdot n^{-1}$ | $\exp((2\cdot\alpha-\alpha\ln\alpha)\cdot\ln n^{*})$ | $0.04$

###  0.F.2 Concrete Bounds

In Table 5, we present the concrete bounds. For each of our 12 benchmarks, we
evaluate our synthesized symbolic bound (Table 1 in our paper) and Karp’s
symbolic bound with three concrete choices
$(\alpha,n^{*})=(10,13),(11,15),(12,17)$. We also evaluate the ratio between
the two concrete bounds $\frac{\text{Karp's Bound}}{\text{Our Bound}}$ to show
that our approach can derive much tighter bounds.

Table 5: Results for Concrete Bounds Benchmark | Concrete choice | Our bound | Karp’s Bound | Ratio
---|---|---|---|---
QuickSelect | $\alpha=10;n^{*}=13$ | $4.85*10^{-2}$ | $1.92*10^{-1}$ | $3.96$
QuickSelect | $\alpha=11;n^{*}=15$ | $1.26*10^{-2}$ | $1.45*10^{-1}$ | $1.16*10^{1}$
QuickSelect | $\alpha=12;n^{*}=17$ | $2.97*10^{-3}$ | $1.10*10^{-1}$ | $3.69*10^{1}$
QuickSort | $\alpha=10;n^{*}=13$ | $2.07*10^{-7}$ | $1.11*10^{-2}$ | $5.36*10^{4}$
QuickSort | $\alpha=11;n^{*}=15$ | $5.85*10^{-9}$ | $6.74*10^{-3}$ | $1.15*10^{6}$
QuickSort | $\alpha=12;n^{*}=17$ | $1.43*10^{-10}$ | $4.09*10^{-3}$ | $2.85*10^{7}$
L1Diameter | $\alpha=10;n^{*}=13$ | $2.20*10^{-6}$ | $4.05*10^{-3}$ | $1.84*10^{3}$
L1Diameter | $\alpha=11;n^{*}=15$ | $2.10*10^{-7}$ | $2.03*10^{-3}$ | $9.67*10^{3}$
L1Diameter | $\alpha=12;n^{*}=17$ | $1.83*10^{-8}$ | $1.02*10^{-3}$ | $5.58*10^{4}$
L2Diameter | $\alpha=10;n^{*}=13$ | $2.20*10^{-6}$ | $4.05*10^{-3}$ | $1.84*10^{3}$
L2Diameter | $\alpha=11;n^{*}=15$ | $2.10*10^{-7}$ | $2.03*10^{-3}$ | $9.67*10^{3}$
L2Diameter | $\alpha=12;n^{*}=17$ | $1.83*10^{-8}$ | $1.02*10^{-3}$ | $5.58*10^{4}$
RandSearch | $\alpha=10;n^{*}=13$ | $4.26*10^{-4}$ | $5.88*10^{-4}$ | $1.38$
RandSearch | $\alpha=11;n^{*}=15$ | $7.12*10^{-6}$ | $1.77*10^{-4}$ | $2.49*10^{1}$
RandSearch | $\alpha=12;n^{*}=17$ | $6.92*10^{-8}$ | $5.22*10^{-5}$ | $7.55*10^{2}$
Channel | $\alpha=10;n^{*}=13$ | $2.61*10^{-23}$ | $6.72*10^{-2}$ | $2.57*10^{21}$
Channel | $\alpha=11;n^{*}=15$ | $4.84*10^{-30}$ | $4.64*10^{-2}$ | $9.59*10^{27}$
Channel | $\alpha=12;n^{*}=17$ | $1.22*10^{-37}$ | $3.21*10^{-2}$ | $2.64*10^{35}$
Rdwalk | $\alpha=10;n^{*}=13$ | $1.98*10^{-13}$ | $3.02*10^{-2}$ | $1.52*10^{11}$
Rdwalk | $\alpha=11;n^{*}=15$ | $5.18*10^{-17}$ | $2.00*10^{-2}$ | $3.87*10^{14}$
Rdwalk | $\alpha=12;n^{*}=17$ | $4.97*10^{-21}$ | $1.33*10^{-2}$ | $2.67*10^{18}$
Rdadder | $\alpha=10;n^{*}=13$ | $1.98*10^{-13}$ | Not applicable | -
Rdadder | $\alpha=11;n^{*}=15$ | $5.18*10^{-17}$ | Not applicable | -
Rdadder | $\alpha=12;n^{*}=17$ | $4.97*10^{-21}$ | Not applicable | -
MC1 | $\alpha=10;n^{*}=13$ | $3.09*10^{-15}$ | $2.06*10^{-8}$ | $6.67*10^{6}$
MC1 | $\alpha=11;n^{*}=15$ | $8.23*10^{-19}$ | $1.18*10^{-9}$ | $1.44*10^{9}$
MC1 | $\alpha=12;n^{*}=17$ | $1.19*10^{-22}$ | $6.48*10^{-11}$ | $5.46*10^{11}$
MC2 | $\alpha=10;n^{*}=13$ | $3.09*10^{-15}$ | $2.06*10^{-8}$ | $6.67*10^{6}$
MC2 | $\alpha=11;n^{*}=15$ | $8.23*10^{-19}$ | $1.18*10^{-9}$ | $1.44*10^{9}$
MC2 | $\alpha=12;n^{*}=17$ | $1.19*10^{-22}$ | $6.48*10^{-11}$ | $5.46*10^{11}$
MC3 | $\alpha=10;n^{*}=13$ | $4.85*10^{-2}$ | $1.92*10^{-1}$ | $3.96$
MC3 | $\alpha=11;n^{*}=15$ | $1.26*10^{-2}$ | $1.45*10^{-1}$ | $1.16*10^{1}$
MC3 | $\alpha=12;n^{*}=17$ | $2.97*10^{-3}$ | $1.10*10^{-1}$ | $3.69*10^{1}$
MC4 | $\alpha=10;n^{*}=13$ | $2.20*10^{-6}$ | Not applicable | -
MC4 | $\alpha=11;n^{*}=15$ | $2.10*10^{-7}$ | Not applicable | -
MC4 | $\alpha=12;n^{*}=17$ | $1.83*10^{-8}$ | Not applicable | -

###  0.F.3 Plots for Concrete Bounds

In Figures 4–15, we present the plots of our concrete bounds and the Karp’s
concrete bounds over $10\leq\alpha\leq 15,n^{*}=17$.

Figure 4: The Plot for QuickSelect Figure 5: The Plot for QuickSort Figure 6:
The Plot for L1Diameter Figure 7: The Plot for L2Diameter Figure 8: The Plot
for RandSearch Figure 9: The Plot for Channel Figure 10: The Plot for Rdwalk
Figure 11: The Plot for Rdadder Figure 12: The Plot for MC1 Figure 13: The
Plot for MC2 Figure 14: The Plot for MC3 Figure 15: The Plot for MC4

###  0.F.4 Tail Bounds by Our Completeness Theorem 3.3

In Table 6, we present the synthesized tail bound from our completeness
theorem (Theorem 3.3).

Table 6: Tail Bound By the Completeness Theorem Benchmark | $\kappa(n^{*})$ |  Tail bound $u(\alpha,n^{*})$
---|---|---
QuickSelect | $4n^{*}$ | $\exp(-2\cdot\frac{(\alpha-1)^{2}}{\alpha})$
QuickSort | $2n^{*}\\!\cdot\\!\ln n^{*}$ | $\exp(-0.7\cdot\frac{(\alpha-1)^{2}}{\alpha}\cdot\ln n^{*})$
L1Diameter | $2n^{*}$ | $\exp(-\frac{(\alpha-1)^{2}}{\alpha})$
L2Diameter | $2n^{*}\\!\cdot\\!\ln n^{*}$ | $\exp(-\frac{(\alpha-1)^{2}}{\alpha})$
RandSearch | $\ln n^{*}/\ln\frac{4}{3}$ | $\exp(-1.19\cdot\frac{(\alpha-1)^{2}}{\alpha}\cdot\ln n^{*})$
Channel | $en^{*}$ | $\exp(-0.74\cdot\frac{(\alpha-1)^{2}}{\alpha}\cdot n^{*})$
Rdwalk | $0.5n^{*}$ | $\exp(-\frac{1}{3}\cdot\frac{(\alpha-1)^{2}}{\alpha}\cdot n^{*})$
Rdadder | $3n^{*}$ | $\exp(-\frac{(\alpha-1)^{2}}{\alpha}\cdot n^{*})$
MC1 | $\ln n^{*}/\ln 2$ | Not applicable
MC2 | $\ln^{2}n^{*}/\ln 2$ | Not applicable
MC3 | $2n^{*}\cdot\ln^{2}n^{*}$ | $\exp(-\frac{(\alpha-1)^{2}}{\alpha})$
MC4 | $2.5n^{*}$ | $\exp(-\frac{(\alpha-1)^{2}}{\alpha})$

##  Appendix 0.G Missing Details in Related Work (Section 6)

###  0.G.1 Coupon Collector

The example above shows that our approach can obtain bounds that are
considerably tighter than Karp’s method. Moreover, we will now extend the
results to systems of PRRs consisting of several recursive equations (modeling
recursive algorithms with several procedures). This is also beyond the reach
of Karp’s method and all previous methods. However, our approach is unable to
handle a program, called CouponCollector[29, Chapter 3.6] as follows.

###### Example 28

Consider the Coupon-Collector problem with $n$ different types of
coupons$(n\in\mathbb{N})$. The randomized process proceeds in rounds: at each
round, a coupon is collected uniformly at random from the coupon types the
rounds continue until all the $n$ types of coupons are collected. We model the
rounds as a recurrence relation with two variables $n,m$, where $n$ represents
the total number of coupon types and $m$ represents the remaining number of
uncollected coupon types. The recurrence relation is as follows:

$p(n,m;1)=\bigoplus\begin{cases}m/n:\mathtt{pre}(1);\mathtt{invoke}\
p(n,m-1);\\\ 1-m/n:\mathtt{pre}(1);\mathtt{invoke}\ p(n,m);\end{cases}$

Our approach fails in case since it is hard to apply Markov’s inequality to
derive exponentially decreasing tail bounds. However, Karp’s method could
produce the following:

$\Pr[p(n,n)\geq n\ln n+\alpha\cdot n]\leq\exp(-\alpha).$

∎

###  0.G.2 Non-Prefixed-Point of Karp’s Bound on Quick-Select

Consider the PRR for Quick-Select:

$\textstyle\mathtt{def}\ p(n;2)=\\{\mathtt{sample}\
v\leftarrow\mathtt{muniform}(n)\ \mathtt{in}\ \\{\mathtt{pre}(n);\
\mathtt{invoke}\ p(v);\\}\\}$

where $h(n)$ is the muniform distribution. Karp’s method gives the following
tail bound:

$\Pr(p(n)>4\cdot n+k\cdot n)\leq\left(\frac{3}{4}\right)^{k}.$

Although Karp’s result is derived (indirectly) from fixed point theory, we
show that the derived tail bound $\left(\frac{3}{4}\right)^{k}$ is not a
prefixed point when $k$ is allowed to be any non-negative real number. First,
recall that the prefixed point condition for the situation $k\geq 2$ and an
even number $n$ states that

$\left(\frac{3}{4}\right)^{k}\geq
2\cdot\frac{1}{n}\sum_{i=\frac{n}{2}+1}^{n}\left(\frac{3}{4}\right)^{(3+k)-4\cdot\frac{i}{n}}.$

But we have

$\displaystyle
2\cdot\frac{1}{n}\cdot\sum_{i=\frac{n}{2}}^{n-1}\left(\frac{3}{4}\right)^{(3+k)-4\cdot\frac{i}{n}}$
$\displaystyle=$ $\displaystyle
2\cdot\frac{1}{n}\cdot\left(\frac{3}{4}\right)^{k+1}\cdot\frac{1-[(\frac{3}{4})^{-\frac{4}{n}}]^{\frac{n}{2}}}{1-(\frac{3}{4})^{-\frac{4}{n}}}$
$\displaystyle=$ $\displaystyle
2\cdot\frac{1}{n}\cdot\left(\frac{3}{4}\right)^{k+1}\cdot{\frac{-\frac{7}{9}}{1-e^{\frac{4}{n}\cdot\ln\frac{4}{3}}}}$
$\displaystyle\approx$ $\displaystyle
2\cdot\frac{1}{n}\cdot\left(\frac{3}{4}\right)^{k+1}\cdot\frac{\frac{7}{9}}{\frac{4}{n}\cdot\ln\frac{4}{3}}$
$\displaystyle\approx$ $\displaystyle 2\cdot\frac{1}{n}\cdot
n\cdot\left(\frac{3}{4}\right)^{k+1}\cdot{0.676}$ $\displaystyle=$
$\displaystyle(2\cdot 0.75\cdot 0.676)\cdot\left(\frac{3}{4}\right)^{k}\geq
1.01\cdot\left(\frac{3}{4}\right)^{k}$

for which the first $\approx$ are with the ratio $1$ when $n$ tends to
infinity. Hence, we have

$\left(\frac{3}{4}\right)^{k}<2\cdot\frac{1}{n}\sum_{i=\frac{n}{2}+1}^{n}\left(\frac{3}{4}\right)^{(3+k)-4\cdot\frac{i}{n}}.$

As a result, the prefixed point condition is violated for every sufficiently
large even number $n$ and $k\geq 2$.