{'fraction_non_alphanumeric': 0.0584729381443299, 'fraction_numerical': 0.01780856242840779, 'mean_word_length': 3.924900837373292, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Chance-constrained optimization with tight confidence bounds

Convex sample approximations of chance-constrained optimization problems are considered, in which chance constraints are replaced by sets of sampled constraints. We propose a randomized sample selection strategy that allows tight bounds to be derived on the probability that the solution of the sample approximation is feasible for the original chance constraints when a subset of the sampled constraints is discarded. These confidence bounds are shown to be tighter than the bounds that apply if constraints are discarded according to optimal or greedy discarding strategies. We further show that the same confidence bounds apply to solutions that are obtained from a two stage process in which a sample approximation of a chance-constrained problem is solved, then an empirical measure of the violation probability of the solution is obtained by counting the number of violations of an additional set of sampled constraints. We use this result to design a repetitive scenario approach that meets required tolerances on violation probability given any specified a priori and a posteriori probabilities. These bounds are tighter than confidence bounds available for previously proposed repetitive scenario approaches, and we show that the posterior bounds are exact for a particular problem subclass. The approach is illustrated through numerical examples, and extensions to problems involving multiple chance constraints are discussed.


Introduction
An important class of optimization problems involves chance constraints, namely constraints dependent on stochastic parameters, which are required to hold with specified probabilities. Solution methods and applications for optimization under chance constraints were first considered in the context of problems in economics and management [13,14]. More recently, chance-constrained optimization has been applied to diverse problems in finance [17,4], process design [25,8], model predictive control [11,23] and building control [21]. Further applications and references are discussed in [2].
For problems with constraints that may be violated up to prescribed limits on violation probability, chance constraints are less stringent than their robust counterparts, which impose constraints for all realizations of uncertainty. However, methods of handling chance constraints using explicit probability distributions can lead to intractable optimization problems. This motivates the use of scenario or sample-based methods in which constraints are imposed for finite sets of independent samples of the uncertain parameters. These approaches have the advantages that convexity is preserved, assuming that the constraints are convex in the decision variables for all uncertainty realizations, and that probabilistic bounds can be determined on the confidence with which the solution satisfies constraints [7,8,9]. In order to keep computation within practicable limits, it is important to understand how the sample size affects the accuracy with which the solution of the sampled problem approximates the solution of the chance-constrained problem.
The seminal papers [9,5] provide bounds on the confidence that a decision variable satisfies a chance constraint, conditioned on the fact that the decision variable is optimal for a sampled problem in which the chance constraint is replaced by a randomly extracted set of sampled constraints. These bounds are tight in the sense that they cannot be improved without additional information about the sampled problem, and they are exact (i.e. they coincide with the actual distribution of violation probabilities) for a particular problem subclass. However, since this approach assumes that the sampled problem invokes the entire set of sampled constraints, a high level of confidence necessitates a large number of samples and hence a low probability of constraint violation. Consequently the approach cannot generally deliver a high degree of accuracy of approximation for problems involving chance constraints with violation probabilities that are not close to zero.
Alternative formulations, which are more suitable for approximating chance constraints with arbitrary violation probabilities, use a certain proportion of parameter samples to define a set of sampled constraints and discard the rest. Bounds on the confidence with which a solution of the resulting sampled problem satisfies a given chance constraint are derived in [5,10]. However, these bounds are obtained under the assumption that sampled contraints are discarded optimally with respect to the objective function, or that constraint selection heuristics are used to approximate an optimal sample discarding procedure. The solutions of the sampled problem may therefore have poor gener-alization properties, and we show in this paper that, relative to a randomized sample discarding procedure, this leads to a lower confidence of satisfying the underlying chance constraints.
A third type of scenario approach for chance-constrained programming selects a solution from among the solutions of a set of sampled problems, with constraints defined in each case by an independently extracted set of parameter samples [12,6]. By incorporating a posteriori empirical constraint violation tests based on additional parameter samples that are not used in the definition of the sampled problem, this approach can potentially provide tighter bounds on the confidence of satisfying an associated chance constraint. However [12] does not provide a priori confidence bounds, and the posterior confidence bounds (based on [3]) are necessarily conservative for the convex setup employed here; on the other hand, the bounds given in [6] are nonconservative only for a particular problem subclass, as we show in this paper.
This paper explores and develops the connection between the confidence of chance constraint satisfaction for single-shot scenario approaches with and without sample discarding [9,5,10], and repetitive scenario approaches [12,6]. Considering the properties of problems with sampled constraints that are discarded at random rather than according to a deterministic algorithm, we derive new bounds on the confidence that the solution is feasible for an associated chance-constrained problem. These bounds are tight (in the sense that they cannot be improved without additional information on the problem), and, since a combinatorial factor appearing in the bounds of [5,10] is not required, they demonstrate that a considerable improvement in approximation accuracy can be achieved using a randomized sample discarding approach. We discuss a procedure for implementing randomized sample discarding based on the repetitive scenario approach. We describe how to determine the number of sampled problems that must be solved, and their respective sample sizes, in order to ensure specified tolerances on the violation probability of the solution for any given prior and posterior probabilities. The resulting posterior confidence bound coincides with that of [6] for a specific problem subclass, however, we show that it is in fact exact for this case and we give tight bounds in all other cases.
The rest of the paper is organised as follows. Section 2 gives the problem definition. Section 3 gives the main results, then discusses related results on the optimal value of the objective function and comparisons with existing results for deterministic sample discarding procedures. Section 4 describes an algorithm for approximating the solution of a chance-constrained problem with specified prior and posterior confidence bounds on constraint violation probability. Two examples are given to illustrate the algorithm: an application to the problem of determining the smallest hypersphere containing a given probability mass, and an application to a finite horizon optimal control problem considered in [6], generalized to the case of multiple chance constraints. Section 5 draws conclusions.

Problem definition and assumptions
Consider the chance-constrained optimization problem with decision variable x ∈ R n : minimize Here ǫ is a specified probability, δ ∈ ∆ ⊆ R d is a vector of random parameters and P a probability measure defined on ∆. Note that ǫ can take any value in the interval [0, 1], and in particular ǫ is not assumed to be close to 0. The domain X ⊂ R n of the decision variable x and the function f : R n × ∆ → R satisfy the following assumption.
Assumption 1 For all δ ∈ ∆, f (·, δ) is convex and lower-semicontinuous, and X is compact and convex.
The chance constraint P{f (x, δ) > 0} ≤ ǫ is not necessarily convex in x (except for certain special cases, see e.g. [22]), and problem (2.1) is therefore nonconvex in general. To avoid the computational difficulties associated with the chance constraint in (2.1), we consider an approximate problem formulation using samples of the uncertain parameter δ. Let ω m = {δ (1) , . . . , δ (m) } ∈ ∆ m denote a collection of m independent identically distributed (i.i.d.) samples δ (i) of the random variable δ. The sample indices are assumed to be statistically independent of the sample values, so that ω r = {δ (1) , . . . , δ (r) } denotes a randomly selected subset of ω m , for any r < m.
To motivate a discussion of sample selection methods, we define (following [5,10]) the sample approximation of (2.1) with optimal sample discarding as minimize ω⊆ωm x∈X for a given integer q, with n ≤ q ≤ m. The optimal values of ω and x in (2.2) are denoted ω * and x * (ω * ) respectively. Since X is compact and convex, and since f (x, δ) ≤ 0 is a convex constraint on x, the sampled problem (2.2) can be expressed as a mixed integer program with a convex continuous relaxation. This implies that (2.2) can be solved exactly using a branch and bound approach (see e.g. [18]). However, unless m is large, the solution x * (ω * ) can have poor generalization properties since, as discussed in Section 3 of this paper, the available bounds on the confidence that x * (ω * ) satisfies the chance constraint of (2.1) are not tight for general uncertainty distributions. Moreover the computation required to solve for x * (ω * ) grows rapidly with m and m − q.
In this paper we therefore consider problems with sampled constraints that are defined by randomly selecting subsets of the multisample ω m . Let and define Ω q (ω m ) for any given q ≤ m as the collection of all q-element subsets ω of ω m such that x * (ω) violates the constraint f (x, δ) ≤ 0 for all δ ∈ ω m \ ω, i.e.
The feasibility requirement of Assumption 2 is trivially satisfied if the robust optimization corresponding to (2.1) with ǫ = 0 is feasible. Clearly Assumption 2 could be restrictive since it is equivalent to the requirement that, with probability 1, an x exists satisfying the constraints of (2.3) with ω = ω r , for any r ≤ m. We note, however, that the results of this paper could be extended to situations in which (2.3) has a non-zero probability of infeasibility by using a framework for analysis such as that described in [5]. On the other hand, by convexity Assumption 3 holds if and only if, for any r < m, problem (2.3) with ω = ω r is non-degenerate with probability 1 (i.e. the dual of problem (2.3) almost surely has a unique solution [16]).
In general Ω q (ω m ) may contain more than one subset of ω m . In the sequel we refer to each distinct ω ∈ Ω q (ω m ) as a level-q subset of ω m and to the corresponding solutions x * (ω) of (2.3) for ω ∈ Ω q (ω m ) as level-q solutions.
An essential set consists of samples δ ∈ ω that are associated with active constraints at the solution x * (ω) of (2.3). If Assumptions 2 and 3 hold, then Es(ω) is necessarily uniquely determined by conditions (i) and (ii). We define the maximum support dimension of (2.3), denotedζ, as the least upper bound that holds almost surely on the number of elements in the essential set of (2.3) for any size of multisample ω, namely the maximum value of ess sup ω∈∆ m |Es(ω)| over all finite integers m ≥ 1. It is easy to show thatζ (which is equivalent to Helly's dimension for (2.2) [5, Def. 3.1]) cannot be greater than n if Assumptions 2 and 3 hold. Similarly we define the minimum support dimension of (2.3), denoted ζ, as the minimum value of ess inf ω∈∆ m |Es(ω)| for all finite m ≥ζ. Clearly ζ ≥ 0 must hold for all problems.

Main results
The results presented in this section enable a randomized procedure to be constructed that ensures tight a priori and a posteriori bounds on the confidence of finding a solution of (2.3) that satisfies the chance constraint in (2.1). For given x ∈ R n , V (x) denotes the violation probability We first derive bounds on the conditional probability that x * (ω) satisfies V x * (ω) ≤ ǫ given that ω is a randomly selected level-q subset of ω m . We then give bounds on the conditional probability that a level-q solution x * (ω) satisfies V x * (ω) ≤ ǫ given that x * (ω) is a randomly selected level-r solution, for any given r ≤ q. These provide the basis for a posteriori bounds on the confidence that x * (ω) satisfies V x * (ω) ≤ ǫ. Finally we provide bounds on the probability of generating a level-q subset of ω m using a randomized sample selection procedure; these bounds make it possible to determine a priori bounds on the probability of obtaining a level-q solution.
The solution of a randomized optimization problem based on a finite multisample cannot in general satisfy with certainty the chance constraint in (2.1). Instead we seek a solution x ∈ X such that the constraint violation probability V (x) lies in a given interval, (ǫ,ǭ], with a specified level of confidence, p prior ∈ (0, 1). Two-sided confidence bounds are important in this context because the violation probability V (x) should be close to ǫ with a high degree of confidence in order that x approximates the solution of the chance-constrained problem (2.1) for any given ǫ ∈ [0, 1].
In order to define the probability of an event that depends on the multisample ω m ∈ ∆ m , we use P m to denote the product measure on ∆ m . The binomial distribution function is denoted so that Φ(n; N, p) is the probability of n or fewer events occuring in N independent trials, each of which has probability p.
Theorem 1 (Confidence bounds for level-q solutions) For any ǫ ∈ [0, 1] and integers q and m such thatζ ≤ q ≤ m we have

1)
and, for ζ ≤ q ≤ m, Theorem 1 (which is proved in Section 3.1) provides upper and lower bounds on the probability of the event V (x * (ω q )) ≤ ǫ, conditioned on the event that Ω q (ω m ) contains ω q . Since ω q = {δ (1) , . . . , δ (q) } is statistically identical to a randomly selected subset of ω m of cardinality q, a direct consequence of Theorem 1 is that the probability of the event V (x(ω)) ≤ ǫ, given that ω is a randomly selected member of Ω q (ω m ), also satisfies the upper and lower bounds in (3.1) and (3.2).
Whenever q < m andζ > 1, the lower confidence bound in (3.1) is greater than the bound derived in [5,10] on the probability that the solution of (2.2) (in which samples are discarded optimally) satisfies V (x * (ω * )) ≤ ǫ; this is discussed in detail in Section 3.4. The resulting improvement in the confidence bound for a randomly selected level-q solution is significant because a combinatorial factor that appears in the bounds of [5,10] is not required in (3.1). Furthermore, the confidence bounds of Theorem 1 hold with equality if the support dimension of (2.3) is unique, i.e. if ζ =ζ. An example of this is the class of fully supported problems, for which ζ =ζ = n [5,10].
For general values of m, q and n, it is not computationally tractable to identify all level-q subsets of the multisample ω m and then select one at random in order to take advantage of the confidence bounds in Theorem 1. Clearly the optimal solution of (2.2), if available, could be used to identify a level-q subset (namely ω * ), and likewise greedy constraint selection algorithms are able to identify suboptimal level-q subsets (see e.g. [5,Sec. 5.1]). However the deterministic constraint discarding strategies employed by these methods cannot be used to select an element of Ω q (ω m ) at random.
Instead we consider a randomized constraint selection strategy. This is based on the observation that the essential set of (2.3) for a randomly chosen subset of ω m , such as ω r = {δ (1) , . . . , δ (r) } for given r, is almost surely the essential set of a randomly selected level-q subset, where q is the number of elements of the multisample ω m that satisfy the constraint f (x * (ω r ), δ) ≤ 0. Thus we can determine q for given r by first solving (2.3) for ω = ω r , then counting the number of samples that satisfy f (x * (ω r ), δ) ≤ 0 and setting q = θ r (ω m ), where Since ω r is statistically independent of the samples contained in ω m \ ω r , it can be shown that confidence bounds analogous to those provided by Theorem 1 apply to V (x * (ω r )). These bounds, which are stated in Theorem 2 (and proved in Section 3.2), provide a posteriori bounds on the confidence of constructing a solution of (2.2) with a specified constraint violation probability.
Theorem 2 (A posteriori confidence bounds conditioned on θ r (ω m )) For any ǫ ∈ [0, 1] and integers r, q and m such thatζ ≤ r ≤ q ≤ m we have

4)
and, for ζ ≤ r ≤ q ≤ m, Theorem 2 provides tight bounds on the conditional distribution of V (x * (ω r )) given the value of θ r (ω m ). But θ r (ω m ) depends on the random sample ω m , and, for arbitrary r, there may be a only small probability that θ r (ω m ) lies in the required range in order that x * (ω r ) has, with a sufficiently high level of confidence, a constraint violation probability in the desired range. However, as we discuss in Section 4, it is possible to choose the value of r so as to maximize the probability that θ r (ω m ) lies in the required range. For this we make use of the following result (proof of which is given in Section 3.2).
Theorem 3 (Probability of selecting a level-q subset of ω m ) For any integers r, q and m such thatζ ≤ r ≤ q ≤ m we have and where B(a, b) denotes the beta function for integers a and b.
From Theorem 3 it is possible to compute the value of r that maximizes the probability with which θ r (ω m ) lies in any specified range. In conjunction with Theorem 2, this allows a priori bounds to be determined on the confidence that the violation probability V (x * (ω r )) lies in the desired interval, (ǫ,ǭ]. These confidence bounds make it possible to compute an upper bound on the number of times the procedure of solving (2.3) for x * (ω r ) and determining θ r (ω m ) must be repeated in order to ensure that a solution is obtained that satisfies V (x * (ω r )) ∈ (ǫ,ǭ] with a probability exceeding any given a priori confidence level p prior . The proposed solution procedure, which is described in Section 4, therefore meets a priori bounds on the confidence of determining a solution with a violation probability in the required range. The computational cost of determining θ r (ω m ) in (3.3) for given x * (ω r ) is typically small compared to the cost of solving (2.3) for x * (ω r ). For problems in which large numbers of samples are easy to obtain, this makes the use of large values of m computationally attractive. In particular, by using a large value of m it is possible to obtain very sharp a posteriori confidence bounds. In such cases the main factor limiting a priori confidence bounds is the structural uncertainty in solutions of (2.2), namely the difference between the maximum and minimum support dimensions of (2.3).

Confidence bounds for randomly selected level-q solutions
The proof of Theorem 1 is derived from the properties of a randomly selected level-q subset of the multisample ω m . In order to simplify the analysis of problems with non-unique support dimensions (i.e. with ζ =ζ), we introduce a regularized version of the essential set that has a fixed cardinality. To define this set we assign (similarly to [5]) a random label λ (i) to each sample δ (i) , where λ (i) is uniformly distributed on [0, 1] and independent of λ (j) for all i = j. Furthermore, for any multisample ω m = {δ (1) , . . . , δ (m) } with associated labels {λ (1) , . . . , λ (m) } we define Λ k (ω m ) as the subset of ω m containing the k samples with smallest labels, so that |Λ k (ω m )| = k and δ (i) ∈ Λ k (ω m ) if and only if λ (i) < λ (j) for all j such that δ (j) ∈ ω m \ Λ k (ω m ). The regularized essential set Es ′ k (ω m ) is defined for a given integer k as follows.
Definition 2 (Regularized essential set) For a multisample ω and integer k such that 0 ≤ k ≤ |ω|, the regularized essential set is given by Definition 2 implies that |Es ′ k (ω)| = k almost surely, and that Using the regularized essential set we define a regularized version of violation probability: is equal to the probability that, for given k, the regularized essential set associated with problem (2.3) changes when the multisample ω is extended to include a newly extracted sample δ ∈ ∆. The regularized essential set also allows a regularized version of the set of level-q subsets of ω m to be defined for k ≤ q ≤ m by . This section finds (in Lemma 2) the probability that ω k = {δ (1) , . . . , δ (k) } is equal to the regularized essential set Es ′ k (ω) of (2.3) for some ω ∈ Ω ′ q,k (ω m ), for any given k and q with 0 ≤ k ≤ q ≤ m. This enables the conditional probability that V ′ k (ω q ) ≤ ǫ given that ω q is an element of Ω ′ q,k (ω m ) to be determined (in Lemma 3), and the bounds in Theorem 1 on the conditional probability of V (x * (ω)) ≤ ǫ given that ω ∈ Ω q (ω m ) are subsequently derived using this result. The approach is based on a fundamental result, stated in Lemma 1, on the distribution of the regularized violation probability V ′ k (ω k ). Related results are available in the literature (see e.g. [9, Eq. 3.2] and [5,Eq. 3.11]). The proofs of Lemmas 1, 2 and 3 are provided in Appendix A.

Lemma 1 For any v ∈ [0, 1] and integers k and m such that
The probability that ω k is equal to the regularized essential set, Es ′ k (ω) for some ω ∈ Ω ′ q,k (ω m ), where k ≤ q ≤ m, is given by the following result.
Lemma 2 For any integers k, q and m such that 0 ≤ k ≤ q ≤ m we have The confidence bounds of Theorem 1 can be established using the following lemma, which provides a subsidiary result on the regularized version of violation probability. The proof of this lemma is based on Lemmas 1 and 2, and on the properties of a subset of ω m selected at random from Ω ′ q,k (ω m ).

Lemma 3 (Confidence bounds for regularized violation probabilities)
For any ǫ ∈ [0, 1] and integers k, q and m such that 0 ≤ k ≤ q ≤ m we have The conditional distribution derived in Lemma 3 for the regularized violation probability V ′ k (ω q ) given that ω q ∈ Ω ′ q,k (ω m ) is similar in form to the confidence bounds of Theorem 1. However the condition ω q ∈ Ω q (ω m ) employed in Theorem 1 is in general much easier to check than membership of Ω ′ q,k (ω m ) because it requires only a function evaluation to check constraint violation rather than recomputation of the essential set of (2.3), which is needed to determine whether δ ∈ Es ′ k (ω q ∪ {δ}) when k < |Es(ω q )|. In order to link Lemma 3 to Theorem 1 we make use of the independence of the regularized violation probability V ′ k (ω q ) and the cardinality of the essential set, |Es(ω q )|. A consequence of this independence property is that the arguments used to prove Lemmas 1, 2 and 3 can be used to demonstrate that the same set of results hold when all probabilities are conditioned on the event that |Es(ω q )| takes any given value between ζ andζ. For convenience we summarize the independence properties that are relevant to the proof of Theorem 1 as follows.
Lemma 4 For any integers k and q such that ζ ≤ k ≤ζ andζ ≤ q ≤ m we have and Proof The sample labels {λ (1) , . . . , λ (m) } are, by assumption, independent of |Es(ω q )|. Therefore the probability of the event δ ∈ Es ′ k (ω q ∪ {δ}) for a randomly extracted sample δ only depends on the values of k and q, and does not depend on |Es(ω q )|. Hence the events that V ′ k (ω q ) ≤ ǫ and ω q ∈ Ω ′ q,k (ω m ) are necessarily independent of the event that |Es(ω q )| takes any given value. ⊓ ⊔ Proof of Theorem 1 From the observation that the events |Es(ω q )| = k are mutually exclusive and exhaustive for k ∈ {ζ, . . . ,ζ}, we have However the definitions of regularized and non-regularized violation probabilities and essential sets imply that and the bounds in Theorem 1 are derived from this expression using Lemmas 3 and 4. Specifically, from (3.10) and (3.11) it follows that , and using (3.9) we obtain

The probability of selecting a level-q subset and a posteriori confidence bounds
This section provides proofs for Theorems 2 and 3. These results are used in Section 4 to determine a randomized constraint selection strategy that is the basis of a method of determining solutions of (2.1) with specified a priori and a posteriori confidence bounds. The posterior confidence bounds in Theorem 2 are derived by an extension of the argument used in the proof of Theorem 1. We then consider Theorem 3, which provides bounds on the probability that the number of samples δ ∈ ω m that satisfy f (x * (ω r ), δ) ≤ 0 is equal to a given value q. The proof of this is based on a subsidiary result given in Lemma 5.
Proof of Theorem 2 The definition of θ r in (3.3) implies that θ r (ω m ) = q if and only if, for some ω ∈ ω m \ ω r , the set ω r ∪ ω belongs to Ω q (ω m ). But the samples contained in ω m \ ω r are statistically identical and independent of the samples in ω r , and hence any event conditioned on θ r (ω m ) = q is identical to the same event conditioned on ω r ∪ {δ (r+1) , . . . , δ (q) } = ω q ∈ Ω q (ω m ). In particular we have The bounds (3.4) and (3.5) then follow from Theorem 1.

⊓ ⊔
To demonstrate the bounds of Theorem 3 we define θ ′ r,k (ω m ) (analogously to θ r (ω m ) in (3.3)) as the number of samples, δ ∈ ω m with the property that the regularized essential set With this definition we have the following result (see Appendix A for a proof).
Lemma 5 (Probability of selecting a regularized level-q subset of ω m ) For any integers k, r, q, m satisfying 0 ≤ k ≤ r ≤ q ≤ m we have Proof of Theorem 3 To derive the bounds (3.6)-(3.7), we note that if |Es(ω r )| = k, then θ r (ω m ) = θ ′ r,k (ω m ), and hence whereas Lemma 4 implies that the event that θ ′ r,k (ω m ) = q is independent of the event |Es(ω m )| = k, so this implies From the law of total probability we therefore have since the events |Es(ω m )| = k, k ∈ {ζ, . . . ,ζ} are mutually exclusive and exhaustive. Therefore and the bounds (3.6)-(3.7) then follow from Lemma 5. ⊓ ⊔

Confidence bounds for optimal cost values
The confidence bounds of Theorems 1 and 2 provide information on the relationship between the optimal values of the cost functions in the chanceconstrained problem (2.1) and the sampled problem (2.3). This section considers these relationships and derives upper and lower bounds on the probability that the optimal cost of (2.1) is less than or equal to that of (2.3) for two cases: when ω in (2.3) is such that the solution x * (ω) satisfies the constraint f (x * (ω), δ) ≤ 0 for a specified number of samples δ ∈ ω m , and when ω is a randomly selected level-q subset of ω m . Let J o (ǫ) and J * (ω) denote the optimal objectives of (2.1) and (2.3) for given ǫ ∈ [0, 1] and ω ⊆ ω m , respectively. The confidence bounds of Theorem 2 imply the following lower bound (proof of which is provided in Appendix A) on the probability that J o (ǫ) is no greater than J * (ω r ) given that the solution of (2.3) satisfies f (x * (ω r ), δ) ≤ 0 for exactly q samples δ ∈ ω m .
An identical argument applied to the lower bound (3.1) of Theorem 1 shows that the probability that J * (ω) is greater than or equal to J o (ǫ), given that ω is a randomly selected level-q subset of ω m , must likewise be at least Φ(q −ζ; m, 1−ǫ). However the upper bounds in (3.2) and (3.5) do not generally lead to upper bounds on the probability that J * (ω) is greater than or equal to J o (ǫ). This is because although (3.2) and (3.5) imply bounds on the probability that the solution of (2.3) is infeasible for (2.1), this event does not necessarily imply that J * (ω) < J o (ǫ). Instead we consider (following [20]) the probability that the solution of (2.1) satisfies the constraints in (2.3).
Although the lower bounds on the probability of J * (ω) ≥ J o (ǫ) are identical to the lower confidence bounds of Theorems 1 and 2, there is no such symmetry between Theorem 4 and the upper bounds of Theorems 1 and 2. Furthermore, for the random discarding strategy described in Section 4, the value of q is likely to be larger than r (perhaps orders of magnitude larger), and in such cases the lower bounds of Corollary 1 change more rapidly from 0 to 1 as ǫ increases than the upper bound of Theorem 4. This is a consequence of the fact that ω r is statistically identical to a randomly selected subset of ω m , rather than optimal in the sense of (2.2). Therefore upper confidence bounds on the probability of J * (ω) ≥ J o (ǫ), which depend on the degree of optimality of solutions of (2.3) with respect to (2.1), are generally more conservative than the corresponding lower bounds, which depend on the probability with which solutions of (2.3) satisfy the constraints of (2.1).

Comparison with confidence bounds for deterministic discarding strategies
The literature on robust convex programming provides various results on the probability that a sample-based approximate solution of the chance-constrained optimization problem (2.1) satisfies the chance constraints of the original problem. However, all of the available results relating to solution methods in which a proportion of the samples are discarded assume that deterministic discarding methods are used. This is because existing analyses assume either that the sampled problem (2.2) is solved exactly using a discarding strategy that is optimal for the given multisample, or that (2.2) is solved approximately using constraint selection strategies based on greedy or other heuristics. In this section we provide a comparison of these with the confidence bounds for randomly selected level-q solutions that are given in Theorems 1 and 2 and in Corollary 1, and we discuss the improvement that can be obtained using a randomised method of selecting and discarding samples.
Lower bounds on the probability that the optimal solution of (2.2) satisfies the constraints of the problem in (2.1) are given in [5,Thm. 4.1] and [10, Thm. 2.1]. These bounds also apply to suboptimal constraint discarding strategies for solving (2.2) based on greedy or other heuristics. The analyses of [5,10] employ similar assumptions to those that are used here. Specifically, [10] makes assumptions equivalent to Assumptions 2 and 3 (see [10, Assump. 2.1 and 2.2]), while Assumption 4 is replaced by the observation that the support dimension almost surely satisfiesζ ≤ n under these conditions. On the other hand [5] employs Assumption 3 (see [5,Procedure 4.1]) and relaxes Assumption 2 to allow for non-zero probability of infeasibility of the sampled problem (2.2). As a result, although [5] makes an assumption that is analogous to Assumption 4, this has to be modified so that the bound on the support dimension becomesζ ≤ n + 1 (see [5,Def. 3.1 and Assump. 2]). With this modification, the bound in [5,Cor. 4.2] is directly comparable to the lower confidence bounds in Theorems 1 and 2.
Results that are equivalent to the upper bounds in (3.2) and (3.5) are given in [10, eq. (7)] and [5, Thm. 6.2, eq. (6.6)]. However the lower confidence bounds in (3.1), (3.4) and (3.14) are new, and the corresponding bounds in [5,10] are not equivalent. In particular, [ where ω * is the optimal level-q subset of ω m in the sampled problem (2.2). This bound is equivalent to where Ψ is the function defined by Similarly [5, Th. 6.2, eq. (6.6)] gives a bound that is equivalent to Furthermore Φ(q −ζ; m, 1 − ǫ) = Ψ (q,ζ; m, ǫ) only if ζ =ζ = 1 or q = m. In both of these cases there can be at most one level-q subset of ω m ; if ζ =ζ = 1 this follows from the observation that problem (2.3) is then equivalent to a 1dimensional problem, whereas for q = m it follows from the convexity of (2.3). Therefore the confidence bounds (3.17)-(3.18) provided by [5,10] are looser than the bounds (3.1), (3.4) and (3.14) wheneverζ > 1 and q < m. The discrepancy between the lower confidence bound of Theorem 1 (likewise the lower bounds of Theorem 2 and Corollary 1) and the corresponding bounds in [5,10] arises because the strategy of selecting the subset ω * of ω m that is optimal (in the sense of minimizing the objective value of (2.2)) could in principle result in the worst-case probability of chance constraint satisfaction. In fact any strategy employing constraint selection criteria that may be correlated with the constraint violation probability (such as, for example, suboptimal sample discarding strategies based on the objective of (2.2)) are subject to the same worst case confidence bounds. The confidence bounds of Theorems 1 and 2 are shown in Figure 1 for m = 500, q = 375, ζ = 1 andζ = 10. An indication of the accuracy with which x * (ω), for randomly selected ω ∈ Ω q (ω m ), approximates the solution of (2.1) can be obtained from the gap between the bounds Φ(q −ζ; m, 1 − ǫ) and Φ(q − ζ; m, 1 − ǫ) in Fig. 1  For comparison Fig. 1 shows the function Ψ (q,ζ; m, ǫ) defining the lower bound in (3.17), which provides a looser bound than Φ(q −ζ; m, 1 − ǫ).
Sample size m

Random convex optimization with a priori and a posteriori confidence bounds
This section describes a procedure based in the results of Section 3 for determining a solution of the chance-constrained problem (2.1) with specified prior and posterior confidence bounds on violation probability. Prior confidence bounds are imposed by requiring that the solution,x, generated by this procedure has a violation probability V (x) that satisfies V (x) ∈ (ǫ,ǭ] with probability p prior for given a priori bounds ǫ,ǭ and probability p prior . The posterior bounds have the form of bounds on the probability that V (x) lies in an interval given knowledge of how many sampled constraints are satisfied byx. For any sample selection method capable of determining a randomly chosen level-q subset ω of a multisample ω m , Theorem 1 provides a posteriori confidence bounds on the probability that V (x) ≤ ǫ, wherex = x * (ω), based on the value,q, of q. The procedure described here ensures thatx is statistically equivalent to a randomly selected level-q solution of (2.3) by making use of Theorem 2. This results in bounds of the form (3.4)-(3.5), which are tight in the sense that they cannot be improved without information about the statistical distribution of the support dimension of (2.3) in the interval [ζ,ζ]. Moreover, for problems in which ζ =ζ the posterior distribution of the violation probability V (x) is known exactly given knowledge ofq. Using Theorem 3, a bound can be determined on the prior probability thatq lies in a given interval; this allows bounds on the prior distribution of V (x) to be computed, and provides the basis for a guarantee that V (x) satisfies the required a priori confidence bounds.
To exploit the confidence bounds of Theorem 2, the proposed method involves extracting a multisample ω m from the distribution of δ, then solving (2.3) for x * (ω r * ), for a predetermined number, r * , of samples in ω m , before determining the number of samples δ ∈ ω m for which the constraint f (x(ω r * ), δ) ≤ 0 is satisfied. These steps are repeated N trial times, where N trial is chosen so as to meet the required a priori confidence bound on the solutionx. This procedure is similar to the approaches proposed in [12] and [6] for solving chance-constrained problems such as (2.1), both of which repeatedly solve a sampled convex program in the form of (2.3), and determine, for each solution, an empirical estimate of the associated violation probability in order to improve on the confidence bounds of [5,10]. However the procedure proposed here differs in that it uses tight bounds on the distribution of violation probability that are provided by Theorems 1 and 2 to determine prior and posterior confidence bounds.
The details of the method are given in Algorithm 1. The motivation behind the design of parameters in step (i) is to ensure, with a given prior probability, that the computation in step (ii) determines at least one level-q subset of ω m for q ∈ [q,q]. Therefore r * is chosen to maximize p trial , which, by Theorem 3, is a (tight) lower bound on the a priori probability that q ≤q ≤q.
Step (ii) requires (2.3) to be solved for N trial multisamples ω m , and the number of violated constraints determined in each case (note that these N trial solutions and constraint violation counts may be performed in parallel). The method of selectingx in step (iii) ensures that q ≤q ≤q whenever the number of sampled constraints satisfied by one of the N trial solutions of (2.3) computed in step (ii) lies in the interval [q,q]. If the solution of the minimization in step (iii) is nonunique, the index i * can be randomly chosen from the minimizing set.
The value of m can be chosen so that the posterior distribution of the violation probability V (x) has, with probability p post , a maximum uncertainty of ∆ǫ, for given p post and ∆ǫ. This entails choosing m so that the a posteriori confidence bound holds whenever q ≤q ≤q. Using Theorem 2, it can be shown that a sufficient condition is that ǫ a , ǫ b exist satisfying ǫ a − ǫ b ≤ ∆ǫ and (4. 2) The following theorem provides confidence bounds on the solutions generated by Algorithm 1 (see Appendix A for a proof).

(ii) the a posteriori bound (4.1) ifq ∈ [q, q]; and (iii) the a posteriori bounds
for all values of q.

Algorithm 1 Procedure for solving (2.1)
Given violation probability bounds ǫ,ǭ, probabilities p prior < ppost and the sample size, m: (i). Determine q,q, r * and p trial , N trial , where (ii). Draw N trial multisamples, ω (i) m , i = 1, . . . , N trial , and for each i: and return the solution estimate,x = x * (ω The a posteriori bound (4.4) is tight given that the only assumption on the support dimension, ζ, of (2.3) is that ζ ∈ [ζ,ζ]. Furthermore, if ζ =ζ, then (4.4) gives the exact posterior distribution of the violation probability conditioned onq = q. We note that the lower bound in (4.4) coincides with the bound of [6, eq. (15)] for the case of fully supported problems, i.e. if ζ =ζ = n. However, Theorem 5 shows in addition that this bound is exact in the sense that it is equal to the posterior probability of V (x) ≤ ǫ given that q = q. Furthermore, Theorem 5 provides tight posterior bounds for general ζ ≤ζ ≤ n.
The value of p trial is a tight bound on the probability that θ r * (ω (i) m ) ∈ [q,q], and it is exact if ζ =ζ. On the other hand the a priori bound (4.3) is potentially conservative due to the use of the inequality (A.7) in the proof of Theorem 5. We note however that the degree of conservativeness of this a priori bound decreases as m increases (so that Φ(q − ζ; m, 1 − ǫ) more closely approximates 1 ǫ − (q − ζ)/m , where 1(ǫ) is the unit step function), and asǭ − ǫ decreases (so thatq − q decreases).
Although r * is specified as the solution of a combinatorial optimization problem in Algorithm 1, this problem can be solved effectively by exhaustive search since r is a scalar integer variable. However, choosing r * so that p trial is maximized may result in excessively large values of r * ifǭ is close to 0. In this case it may therefore be preferable to limit r * to some maximum value at  Table 1 Variation of r * and N trial with ζ andζ for m = 10 5 , ǫ = 0.19,ǭ = 0.21, ∆ǫ = 0.005, and ppost = 0.5(1 + p prior ), and where p 1 = 0.9, p 2 = 0.95, p 3 = 0.99, p 4 = 0.999. the expense of increasing the number, N trial , of trials needed satisfy the prior probability bound (4.3). Table 1 illustrates the variation of r * and N trial with ζ andζ for representative values of m, ǫ,ǭ, p prior , ∆ǫ and p post . Here it can be seen that, as ζ andζ increase while the gapζ − ζ is kept constant, the values of r * and N trial respectively increase and decrease slowly. On the other hand, N trial grows rapidly with increasingζ if ζ remains constant; this case corresponds to increasing structural uncertainty in the solution of (2.3).

Example: Smallest bounding hypersphere with a priori and a posteriori confidence bounds
Algorithm 1 is applied in this section to the problem of determining the smallest hypersphere in R 4 that has a given probability of containing a normally distributed parameter δ ∼ N (0, I), with specified prior and posterior confidence bounds. Therefore we are interested in minimizing the positive scalar R subject to P{ c − δ 2 > R} ≤ ǫ, where R and c ∈ R 4 are optimization variables and ǫ ∈ [0, 1] is a given probability.
The prior confidence bounds on the solutionx are such that the violation probability, V (x) must lie between ǫ = 0.19 andǭ = 0.21 with a probability of at least p prior = 0.9. We also impose bounds on the posterior distribution by requiring that, with probability p post = 0.95, V (x) should differ from 1 −q/m by no more than ±0.005 whenever the solution satisfiesq ∈ [q,q]. For this problem the support dimension ζ lies almost surely between 2 and 5.
To check whether the posterior confidence bounds are satisfied with a multisample size of m = 10 5 we first determine the respectively minimum and maximum values of ǫ a and ǫ b in (4.2): ǫ a = 0.2125, ǫ b = 0.2075.
Hence (4.1) holds with ∆ǫ = ǫ a −ǫ b = 0.005, which implies that the a posteriori confidence specification is met with m = 10 5 . This can be seen in Figure 3, which shows the upper and lower posterior confidence bounds of Theorem 2 for the extreme cases of q =q and q = q.
The values of r * and N trial that are needed to meet the a priori confidence specification can be determined from Table 1. Thus for p prior = 0.9 and (ζ,ζ) = (2, 5) we obtain r * = 15 and N trial = 84 (which corresponds to p trial = 0.0347). The prior confidence bound requires that the solution provided by Algorithm 1 should satisfyq ∈ [q,q] with a probability not less than p prior /p post = 0.974, and, using the lower bound of Theorem 3 (see Fig. 4), it can be verified that this condition is indeed met. Figure 4 shows moreover that the lower bound (3.6) is conservative, since the empirical distribution ofq closely follows the upper bound given by (3.7) in this example. With this information the value of N trial can be reduced to 39 (which corresponds to r * = 25 samples and p trial = 0.0736) without violating the a priori confidence bound.
The a posteriori lower bound given in [6, eq. 14] on the probability that V (x) ≤ ǫ, conditioned on the value ofq, is shown in Figure 3 for the cases of q = q andq =q with m = 10 5 and r * = 15. Comparing with the posterior bounds of Theorem 2, this lower bound can be seen (in Fig. 3) to underestimate by 10% the posterior probability of |V (x) − (1 −q)/m| ≤ ∆ǫ for ∆ǫ = 0.005 (rising to 75% for ∆ǫ = 0.0035). Furthermore, the upper and lower bounds provided by Theorem 2 are almost indistinguishable at this scale, implying that the posterior distribution of violation probability can be determined very precisely for this example.

Example: Finite horizon optimal control
The optimal control problem considered in [6, Sect. IIIA] is concerned with designing control sequences to drive the state of a dynamical system to a target over a finite horizon with high probability despite model uncertainty. This section considers a generalized version of the problem, which minimizes a weighted sum of probabilistic bounds on the error between the system state and the target state. The resulting controller is able to shape the probability distribution of future states more precisely than can be achieved by minimizing only a robust outer bound on the deviation from the target state. The resulting generalization therefore has potential applications to Multi-period Trading [4] and Stochastic Model Predictive Control [11,19].
The system has an uncertain linear discrete-time model with state z ∈ R nz , control input u ∈ R nu , and unknown parameter δ ∈ ∆ ⊆ R nz×nz . The dependence of the matrix A on δ is given by where δ ij is uniformly distributed on the interval [−ρ, ρ] for all i, j, and e i denotes the ith column of the n z × n z identity matrix. For a horizon of N steps, the control problem is to minimize the deviation of the predicted Nstep ahead state from a target state z ref . This deviation is stochastic because of model uncertainty, and a finite horizon optimal control problem is formulated to control its probability distribution. For given A(δ) and a postulated control sequence u(0), . . . , u(N − 1), the N -step ahead state, z(u N , δ), is , and we define a chance-constrained optimal control problem with decision variables x = u N , R 1 , . . . , R ν ∈ R N nu+ν as: (4.5) Here λ and σ 1 , . . . , σ ν are positive scalar weights and ǫ 1 , . . . , ǫ ν are given maximum violation probabilities. This problem formulation minimizes the weighted sum of ν probabilistic bounds on the deviation of the N -steps ahead state from the target state and the l 2 -norm of the input sequence over N steps. Assuming that multisamples ω m,j = {δ (1) j , . . . , δ (m) j } ∈ ∆ m for j = 1, . . . , ν can be drawn repeatedly from the distribution for δ, we define a sampled optimization problem as: where f j is defined for j = 1, . . . , ν by We next describe briefly how Algorithm 1 can be generalized for the case of multiple chance constraints in order to determine, with a pre-specified probability p prior , a solutionx that satisfies the a priori condition P N trial mν V j (x) ∈ (ǫ j ,ǭ j ], j = 1, . . . , ν ≥ p prior , (4.7) by solving (4.6) N trial times, where V j (x) are violation probabilities defined for j = 1, . . . , ν by V j (x) := P f j (x, δ) > 0 .
Specifically, by applying step (i) of Algorithm 1 for each j ∈ {1, . . . , ν}, the parameters r * j defining each of the ν sampled constraints in (4.6) and parameters q j ,q j , and p trial,j can be computed for each j ∈ {1, . . . , ν} given the values of p prior , p post,j , ǫ j andǭ j . Then applying step (ii) of Algorithm 1 we compute for , of problem (4.6) and count for each j ∈ {1, . . . , ν} the corresponding number of unviolated sampled constraints: Finally, step (iii) of Algorithm 1 can be implemented by computing i * = arg min i∈{1,...,N trial } max j∈{1,...,ν} m,j ) for j = 1, . . . , ν. Then, by using the approach of [24] to generalize Theorem 5 for the case of multiple chance constraints, it is straightforward to show that choosing ensures the prior confidence bound (4.7) and the a posteriori bounds for j = 1, . . . , ν. Hereζ j is the (maximum) support dimension of the constraint f j (x, δ) ≤ 0 (see [24,Def. 3.3(b)]) and ζ j is the corresponding minimum number of sampled constraints f j (x, δ) ≤ 0 that can be active at any solution of (4.6) with non-zero probability.
We consider three versions of problem (4.5) with: (a) a single chance constraint with ǫ 1 = 0.005, (b) a single chance constraint with ǫ 1 = 0.2, and (c) two chance constraints with ǫ 1 = 0.005 and ǫ 2 = 0.2. The model has n z = 6 states, n u = 1 control variables, and A 0 , B are as given in [6]. A horizon of N = 10 steps is employed. Note that in principle a robust bound could be imposed on z ref − z(u N , δ) using standard robust convex programming techniques. However this would require 10 36 second-order conic constraints, thus making the optimization intractable in practice.
The parameters defining the sample approximation (4.6) in each case (a)-(c) are given in Table 2. The posterior constraint violation probabilities are required to satisfy V j (x) − (1 −q j /m) ≤ ∆ǫ j with probability p post,j wheneverq j ∈ [q j ,q j ], with tolerances of ∆ǫ 1 ≤ 0.005 in (a) and (c), and ∆ǫ j ≤ 0.01 for j = 1 in (b) and j = 2 in (c). For the values of p post,j in Table 2, a multisample size of m = 65000 meets these requirements. In each case the prior probability bounds (4.7) are imposed with p prior = 0.9.  Table 2 Finite horizon optimal control problem parameters for m = 65000 and p prior = 0.9.
Time step t The maximization in step (i) of Algorithm 1 results in a very large value of r * 1 (namely r * 1 = 64786) in (a) and (c) becauseǭ 1 is close to 0 and p post,1 is close to 1. For cases (a) and (c) we therefore restrict r * 1 to a maximum of 1000. The resulting reduction in the number of constraints in (4.6) causes N trial to be only slightly greater than its minimum value (e.g. N trial is increased from 1 to 5 in case (a)). The parameters in case (a) are similar to, and allow direct comparison with, the parameters used in [6, Sect. IIIA]. In particular, for any i, the probability that the solution of (4.6) satisfies θ r * 1 ,1 (ω (i) ) ≥ q 1 is p trial = 0.381, implying that (4.6) needs to solved on average 2.6 times before a solution meeting this condition is found. On the other hand, the bounds used in [6] give the bound on the expected number of times that (4.6) should be solved in order to obtain a solution satisfying the same proportion (99.67%) of sampled constraints as 9.6. Thus a three-fold reduction is achieved even though more samples (2000) are present in the counterpart to the optimization (4.6) in [6, Sect. IIIA]; this is a result of the improved bounds of Theorem 2.
The optimal control sequences for problems (a)-(c) with weights λ = 0.005, σ 1 = 1 and σ 2 = 10 are shown in Figure 5, and the associated empirical distributions of the deviations of N -step ahead states from the target are shown in Figures 6 and 7. From Fig. 7 it can be verified that these solutions satisfy V j (x) ∈ (ǫ j ,ǭ j ) for each j. The chance constraint imposed at ǫ 1 = 0.2 in case (b) has the effect of reducing the mode of the N -step ahead state deviation relative to case (a), but this is at the expense of a heavier tail (Fig. 6). The constraints at ǫ 1 = 0.2 and ǫ 2 = 0.005 in case (c) cause a reduction in the modal deviation with only a small increase, relative to (a), in the 99.5% bound on the deviation of the N -step ahead state from the target.

Conclusions
This paper considers sample approximations of chance-constrained optimization problems, and shows that the use of random sample selection strategies in the definition of the sampled problem allows for tighter bounds on the confidence of feasibility with respect to the original chance constraints than sample discarding strategies based on optimality or greedy heuristics. A randomised sample selection can be obtained by solving a sampled problem and determin-ing the number of additionally extracted sampled constraints that are violated by the solution. Using this observation, we propose a randomised algorithm for chance-constrained convex programming with tight a priori and a posteriori confidence bounds. The relationships between optimal costs for the sampled problem and the chance-constrained problem are considered, and extensions of the approach to multiple chance constraints are discussed.
A Omitted proofs is equal to ω k for some q such that k ≤ q ≤ m. This event is equivalent to the event that δ (i) / ∈ Es ′ k (ω k ∪ {δ (i) }) for i = k + 1, . . . , q, and its probability, conditioned on the assumption that V ′ k (ω k ) is equal to v, is given by Using the definition of conditional probability we therefore have and from the continuous version of the law of total probability it follows that But ω k is statistically identical to a randomly selected k-element subset of ωq and, from Assumption 3 and Definition 2, Es ′ k (ωq) is almost surely unique. Therefore the probability that ω k is equal to Es ′ k (ωq) is given by the reciprocal of the number of distinct k-element subsets of ωq, and hence necessarily holds for all q ≥ k. A solution for F k is given by F k (v) = v k , and moreover it can be shown that this solution is unique (since (A.2) is equivalent to a Hausdorff moment problem [15, Sec. VII.3]).

⊓ ⊔
Proof of Lemma 2 From the definition of Ω ′ q,k (ωm) in (3.8), it follows that ω k is equal to the regularized essential set Es ′ k (ω) for some ω ∈ Ω ′ q,k (ωm) if and only if q − k of the m − k samples δ contained in ωm \ ω k satisfy δ / ∈ Es ′ k (ω k ∪ {δ}), and the remaining m − q samples satisfy δ ∈ Es ′ k (ω k ∪ {δ}). The probability of this event, conditioned on the regularized violation probability V ′ k (ω k ) being equal to v, is Therefore, from the definition of conditional probability, we obtain where F k (v) = v k by Lemma 1. Hence we have and the result follows from the definition of the beta function, B(·, ·) (see e.g. [1]). ⊓ ⊔ Proof of Lemma 3 Proceeding as in the proof of Lemma 2, we first consider the probability that ω k is the regularized essential set Es ′ k (ω) for some ω ∈ Ω ′ q,k (ωm) with k ≤ q ≤ m.

Proof of Lemma 5
We begin by determining the probability distribution of V ′ k (ωr), for k and r satisfying 0 ≤ k ≤ r ≤ m. Adopting the approach used in the proof of Lemma 1 and using (A.1) with F k (v) = v k we have But the definition of Ω ′ q,k (ωm) in (3.8) implies that ωr = Ω ′ r,k (ωr), and from Lemma 2 therefore, the probability that ω k is equal to the regularized essential set Es ′ k (ωr) is kB(k, r− k + 1). From the definition of conditional probability it follows that P m V ′ k (ω k ) = v ω k = Es ′ k (ωr) = (1 − v) r−k v k−1 B(k, r − k + 1) dv, and since ω k is statistically identical to a randomly selected k-element subset of ωr, this implies that the probability distribution of V ′ k (ωr) satisfies This distribution can be used to determine the probability that θ ′ r,k (ωm) = q for r ≤ q ≤ m. Specifically, from the definition (3.12) we have that θ ′ r,k (ωm) = q if and only if Es ′ k (ωr) = Es ′ k (ωr ∪ ω) for some ω ⊆ ωm \ ωr such that |ω| = q − r, and this occurs if and only if q − r of the m − r samples δ ∈ ωm \ ωr satisfy δ / ∈ Es ′ k (ωr ∪ {δ}) and the remaining m − q samples satisfy δ ∈ Es ′ k (ωr ∪ {δ}). Hence from (A.5), we have Using the continuous version of the total probability law we therefore obtain P m θ ′ r,k (ωm) = q = m − r q − r which, combined with the confidence bound in (3.4), yields (3.14).

⊓ ⊔
Proof of Theorem 4 The bound (3.15) follows from the observation that the optimal objective of (2.3) must be less than or equal to that of (2.1) whenever the solution of (2.1) is a feasible solution for (2.3). But the solution of (2.1), which we denote as x o (ǫ), satisfies the constraints of (2.3) with ω = ωr if f (x o (ǫ), δ) ≤ 0 for all δ ∈ ωr, and since x o (ǫ) satisfies the constraints of (2.1), so that P{f (x o (ǫ), δ) ≤ 0} ≥ 1 − ǫ, we have With i = i * , these inequalities imply the posterior bounds (4.1) and (4.4). To demonstrate the prior bounds (4.3), we first evaluate the posterior bounds in (4.4) for ǫ = ǫ and ǫ =ǭ, and use the definitions of q andq in step (i) to obtain P N trial m V (x) ≤ǭ |q = q ≥ 1 2 (1 + ppost) for all q ≥ q P N trial m V (x) ≤ ǫ |q = q ≤ 1 2 (1 − ppost) for all q ≤q. Hence Boole's inequality gives P N trial m V (x) ∈ (ǫ,ǭ ] |q = q ≥ ppost for all q ≤ q ≤q, (A.7) and by combining this bound with the law of total probability we obtain P N trial m V (x) ∈ (ǫ,ǭ ] ≥q q=q P N trial m V (x) ∈ (ǫ,ǭ ] |q = q P N trial m q = q ≥ ppost P N trial m q ∈ [q,q] .
But Theorem 3 and the definitions of r * and p trial imply P m θ r * (ω (i) m ) ∈ [q,q] ≥ p trial for each i, and, noting that the definition of i * in step (iii) impliesq ∈ [q,q] if and only if θ r * (ω ⊓ ⊔