Concentration-Bound Analysis for Probabilistic Programs and Probabilistic Recurrence Relations

A discrete probability distribution over a countable set $U$ is a function $p:U\rightarrow[0,1]$ such that $\sum_{u\in U}p(u)=1$. The support of $p$ is defined as ${\mathrm{supp}}{\left(p\right)}:=\{u\in U\mid p(u)>0\}$.

A probability space is a triple $(\Omega,\mathcal{F},\Pr)$, where $\Omega$ is a non-empty set (called the sample space), $\mathcal{F}$ is a $\sigma$-algebra over $\Omega$ (i.e. a collection of subsets of $\Omega$ that contains the empty set $\emptyset$ and is closed under complementation and countable union) and $\Pr$ is a probability measure on $\mathcal{F}$, i.e. a function $\Pr\colon\mathcal{F}\rightarrow[0,1]$ such that (i) $\Pr(\Omega)=1$ and (ii) for all set-sequences $A_{1},A_{2},\dots\in\mathcal{F}$ that are pairwise-disjoint (i.e. $A_{i}\cap A_{j}=\emptyset$ whenever $i\neq j$) it holds that $\sum_{i=1}^{\infty}\Pr(A_{i})=\Pr\left(\bigcup_{i=1}^{\infty}A_{i}\right)$. Elements of $\mathcal{F}$ are called events. An event $A\in\mathcal{F}$ holds almost-surely (a.s.) if $\Pr(A)=1$.

A random variable $X$ from a probability space $(\Omega,\mathcal{F},\Pr)$ is an $\mathcal{F}$-measurable function $X\colon\Omega\rightarrow\mathbb{R}\cup\{-\infty,+\infty\}$, i.e. a function such that for all $d\in\mathbb{R}\cup\{-\infty,+\infty\}$, the set $\{\omega\in\Omega\mid X(\omega)<d\}$ belongs to $\mathcal{F}$.

The expected value of a random variable $X$ from a probability space $(\Omega,\mathcal{F},\Pr)$, denoted by $\mathbb{E}(X)$, is defined as the Lebesgue integral of $X$ w.r.t. $\Pr$, i.e. $\mathbb{E}(X):=\int X\,\mathrm{d}\Pr$. The precise definition of Lebesgue integral is somewhat technical and is omitted here (cf. (Williams, 1991a, Chapter 5) for a formal definition). If $\mbox{\sl range}~{}X=\{d_{0},d_{1},\ldots\}$ is countable, then we have $\mathbb{E}(X)=\sum_{k=0}^{\infty}d_{k}\cdot\Pr(X=d_{k})$.

A filtration of a probability space $(\Omega,\mathcal{F},\Pr)$ is an infinite sequence $\{\mathcal{F}_{n}\}_{n\in\mathbb{N}_{0}}$ of $\sigma$-algebras over $\Omega$ such that $\mathcal{F}_{n}\subseteq\mathcal{F}_{n+1}\subseteq\mathcal{F}$ for all $n\in\mathbb{N}_{0}$. Intuitively, a filtration models the information available at any given point of time.

Let $X$ be any random variable from a probability space $(\Omega,\mathcal{F},\Pr)$ such that $\mathbb{E}(|X|)<\infty$. Then, given any $\sigma$-algebra $\mathcal{G}\subseteq\mathcal{F}$, there exists a random variable (from $(\Omega,\mathcal{F},\Pr)$), denoted by ${\mathbb{E}}{\left({X}{\mid}{\mathcal{G}}\right)}$, such that:

• (E1)

  ${\mathbb{E}}{\left({X}{\mid}{\mathcal{G}}\right)}$ is $\mathcal{G}$-measurable, and

• (E2)

  $\mathbb{E}\left(\left|{\mathbb{E}}{\left({X}{\mid}{\mathcal{G}}\right)}\right|\right)<\infty$, and

• (E3)

  for all $A\in\mathcal{G}$, we have $\int_{A}{\mathbb{E}}{\left({X}{\mid}{\mathcal{G}}\right)}\,\mathrm{d}\Pr=\int_{A}{X}\,\mathrm{d}\Pr$.

The random variable ${\mathbb{E}}{\left({X}{\mid}{\mathcal{G}}\right)}$ is called the conditional expectation of $X$ given $\mathcal{G}$. The random variable ${\mathbb{E}}{\left({X}{\mid}{\mathcal{G}}\right)}$ is a.s. unique in the sense that if $Y$ is another random variable satisfying (E1)–(E3), then $\Pr(Y={\mathbb{E}}{\left({X}{\mid}{\mathcal{G}}\right)})=1$. We refer to  (Williams, 1991a, Chapter 9) for details. Intuitively, ${\mathbb{E}}{\left({X}{\mid}{\mathcal{G}}\right)}$ is the expectation of $X$, when assuming the information in $\mathcal{G}$.

A (discrete-time) stochastic process is a sequence $\Gamma=\{X_{n}\}_{n\in\mathbb{N}_{0}}$ of random variables where $X_{n}$’s are all from some probability space $(\Omega,\mathcal{F},\Pr)$. The process $\Gamma$ is adapted to a filtration $\{\mathcal{F}_{n}\}_{n\in\mathbb{N}_{0}}$ if for all $n\in\mathbb{N}_{0}$, $X_{n}$ is $\mathcal{F}_{n}$-measurable. Intuitively, the random variable $X_{i}$ models some value at the $i$-th step of the process.

A stochastic process $\Gamma=\{X_{n}\}_{n\in\mathbb{N}_{0}}$ adapted to a filtration $\{\mathcal{F}_{n}\}_{n\in\mathbb{N}_{0}}$ is a martingale (resp. supermartingale) if for every $n\in\mathbb{N}_{0}$, $\mathbb{E}(|X_{n}|)<\infty$ and it holds a.s. that ${\mathbb{E}}{\left({X_{n+1}}{\mid}{\mathcal{F}_{n}}\right)}=X_{n}$ (resp. ${\mathbb{E}}{\left({X_{n+1}}{\mid}{\mathcal{F}_{n}}\right)}\leq X_{n}$). We refer to  (Williams, 1991a, Chapter 10) for a deeper treatment.

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}}{\mid}{\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}}{\mid}{\mathcal{F}_{n}}\right)}=X_{n}.$ In contrast, in a supermartingale, the only requirement is that ${\mathbb{E}}{\left({X_{n+1}}{\mid}{\mathcal{F}_{n}}\right)}\leq X_{n}$ and hence ${\mathbb{E}}{\left({X_{n+1}}{\mid}{\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.

Given a probability space $(\Omega,\mathcal{F},\Pr)$, a stopping time w.r.t a filtration $\{\mathcal{F}_{n}\}_{n\in\mathbb{N}_{0}}$ is a random variable $T:\Omega\rightarrow\mathbb{N}_{0}\cup\{\infty\}$ such that $\{\omega\mid T(\omega)=n\}\in\mathcal{F}_{n}$.

The termination-time random variable counts the number of steps a program takes to termination. In the setting of probabilistic programs, the termination-time random variable is defined as the first time the program hits its termination program counter, which is a stopping time. For convenience, we treat each termination-time random variable as the total accumulated cost until the program terminates, for which each execution step of the program causes a single unit of cost. In the setting of probabilistic recurrence relations, since the amount of steps in a preprocessing stage is directly added to the termination time, we treat the number of steps in a preprocessing stage as the cost at current execution step, and define the termination-time variable as the total accumulated cost until the recurrence relation runs into the empty stack (i.e., terminates). In both cases, we consider the termination time random variable as the total accumulated cost until the stopping time of termination.

A concentration bound of a random variable $C$ is an inequality of the form $\Pr(C\geq d)\leq f(d)$ or $\Pr(C\leq d)\leq f(d)$ which specifies whether the probability that the value of $C$ grows too large or too small is bounded by a function $f$, which tends to zero when $d\rightarrow\infty$ (for $\Pr(C\geq d)$) or $d\rightarrow-\infty$ (for $\Pr(C\leq d)$). Concentration bounds are an important probabilistic property of random variables as they witness that a random variable will have a substantially small probability of large deviation. When applied to termination time, the concentration bound specifies the following property: the probability that a randomized algorithm runs inefficiently, i.e. takes much longer than its expected termination time, is very small. Thus compared with expected termination time, concentration bounds provide a much finer characterization of the running time of randomized algorithms.

In this work, we consider the following problems: For probabilistic programs, we consider unnested probabilistic while loops. Our aim is to have automated approaches for deriving much tighter exponentially-decreasing concentration bounds in comparison with the existing approach through Azuma or Hoeffding inequalities (Chatterjee et al., 2018b). For probabilistic recurrence relations, our goal is to derive substantially finer bounds compared with the classical results of (Karp, 1994), and for quicksort, we try to derive bounds comparable to the optimal result proposed in (McDiarmid and Hayward, 1996). Obtaining more precise (tighter) concentration bounds is important in many applications, e.g. resource-contention resolution (Kleinberg and Tardos, 2006, Chapter 13), or in resource-constrained environments such as embedded systems.

We implemented the algorithm of Section 4.2 using Matlab. All results were obtained on a machine with an Intel Core i7-8700 processor (3.2 GHz) and 16 GB of memory, running Microsoft Windows 10.

We use benchmarks from (Chatterjee et al., 2018b; Ngo et al., 2018; Chatterjee et al., 2018a). Our benchmarks are as follows:

• •

  AdvRW1D: This program models a 1-dimensional adversarial random walk and is taken from (Chatterjee et al., 2018b).

• •

  rdwalk1, rdwalk2, rdwalk3: These programs model skewed 1-dimensional random walks, in which the probabilities of going to the left and to the right at each step are not equal. They are taken from (Ngo et al., 2018). In rdwalk1 there is a $0.75$ probability of moving left and a $0.25$ probability of moving right. In rdwalk2 the probabilities are $0.875,0.125$, and in rdwalk3, they are $0.9375,0.0625$.

• •

  prspeed: This example is also a random walk taken from (Ngo et al., 2018). The main difference is that the step length is not necessarily $1$.

• •

  mini-Rou, mini-Rou2: These programs are taken from (Chatterjee et al., 2018a). They are implementations of the mini-roulette casino game as probabilistic programs. mini-Rou is the benchmark in (Chatterjee et al., 2018a), while mini-Rou2 is a variant where the probabilities of losing gambles are increased in order to reduce the runtime.

Our experimental results are presented in Table 1. We compare our concentration bounds with those obtained using Azuma’s inequality and Hoeffding’s inequality in (Chatterjee et al., 2018b). As shown in Table 1 our approach successfully obtains tighter bounds in every case. Moreover, note that our approach is very efficient and can obtain these bounds in a few seconds.

In this section, we consider general Probabilistic Recurrence Relations (PRRs) as defined in (Karp, 1994). A PRR is a relation of the following form:

in which $a(n)$ is a non-negative value and each $h_{i}(n)$ is a non-negative random variable such that we always have $\sum_{i=1}^{\ell}h_{i}(n)\leq n-1$. Intuitively, we think of $\mathcal{T}(n)$ as the time it takes for a randomized divide-and-conquer algorithm to solve an instance of size $n$. The algorithm first performs a preprocessing procedure, which leads to $\ell$ smaller instances of random sizes $h_{1}(n),\ldots,h_{\ell}(n).$ It then solves the smaller instances recursively and merges the solutions in a postprocessing phase. We assume that the preprocessing and postprocessing on an instance of size $n$ take $a(n)$ units of time overall. Our goal is to obtain upper bounds on the tail probability $\Pr\left[\mathcal{T}(n^{*})\geq\kappa\right]$, where $n^{*}$ is the size of our initial input.

In order to apply our general approach to PRRs, we first need to embed them in stochastic processes. Suppose we are given a PRR of the following form:

Moreover, assume that we are interested in $\mathcal{T}(n^{*})$ for a specific initial value $n^{*}$. We model this PRR as a Markov chain $(X_{m})_{m\geq 0}$ in which each state $X_{i}$ consists of a non-negative integer $k_{i}$, and a stack of $k_{i}$ additional non-negative integers. Formally, for every $i$, we have $X_{i}=(k_{i},\langle n_{1}^{(i)},n_{2}^{(i)},\ldots,n_{k_{i}}^{(i)}\rangle).$ Intuitively, each $X_{i}$ models a state of our probabilistic divide-and-conquer algorithm in which there are $k_{i}$ more recursive calls waiting to be executed, and the $j$-th call needs to process an instance of size $n_{j}^{(i)}.$ Following this intuition, the transitions of $(X_{m})_{m\geq 0}$ are defined as follows:

Basically, we start with the state $(1,\langle n^{*}\rangle).$ In other words, in the beginning, we have to process an instance of size $n^{*}$. At each step in the Markov chain, if $X_{m-1}$ contains a call to process an instance of size $1$, we can easily remove that call from the stack when transitioning to $X_{m}$, because we assumed that $\mathcal{T}(1)=0.$ Otherwise, we have to perform a call on an instance of size $n_{1}^{(m-1)},$ which by definition leads to further recursive calls to instances of sizes $h_{1}(n_{1}^{(m-1)}),\ldots,h_{\ell}(n_{1}^{(m-1)}).$

Let $\tau$ be the stopping time of $(X_{m})_{m\geq 0}.$ Formally, $\tau:=\min\{i~{}|~{}k_{i}=0\}.$ We further define $(C_{m})_{m\geq 0}$ to model the total cost of execution until reaching $X_{m}$:

Following the definitions, it is easy to see that $C_{\tau}$ is the total time cost of running the divide-and-conquer algorithm on an instance of size $n^{*}$.

Suppose that we are given a function $f:\mathbb{N}\rightarrow[0,\infty),$ such that $f(n)\geq\mathbb{E}[\mathcal{T}(n)]$ for all $n\in\mathbb{N}.$ In other words, $f(n)$ is an upper-bound for the expected runtime of our divide-and-conquer algorithm on an instance of size $n$. Finding such upper-bounds is a well-studied problem and can be automated using approaches such as (Chatterjee et al., 2017). We define a new stochastic process $(Y_{m})_{m\geq 0}$ as follows:

Moreover, let $\alpha:=\alpha(n^{*})>1$ be a constant that depends on the initial input size $n^{*}$, and define a new stochastic process $(Z_{m})_{m\geq 0}$ defined as $Z_{m}:=\alpha^{C_{m}+Y_{m}}.$ Note that if $Z_{m}$ is a supermartingale, then we can obtain a concentration bound for $\mathcal{T}(n^{*}).$ More formally, we have the following lemma: