Matthias C M Troffaes

Enrique Miranda

Sebastien Destercke

On the connection between probability boxes and possibility measures

Keywords: Possibility measures, maxitive measures, pboxes, coherent upper previsions, natural extension

We explore the relationship between p-boxes on totally preordered spaces and possibility measures. We start by demonstrating that only those p-boxes who have 0-1valued lower or upper cumulative distribution function can be possibility measures, and we derive expressions for their natural extension in this case. Next, we establish necessary and sufficient conditions for a p-box to be a possibility measure. Finally, we show that almost every possibility measure can be modelled by a p-box. Whence, any techniques for p-boxes can be readily applied to possibility measures. We demonstrate this by deriving joint possibility measures from marginals, under varying assumptions of independence, using a technique known for p-boxes.

Introduction

Possibility measures [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF] are supremum preserving set functions, and are widely applied in many fields, including data analysis [START_REF] Tanaka | Possibilistic Data Analysis for Operations Research[END_REF], cased-based reasoning [START_REF] Hüllermeier | Cased-based approximate reasoning[END_REF], and psychology [START_REF] Raufaste | Testing the descriptive validity of possibility theory in human judgements of uncertainty[END_REF]. In this paper we are concerned with quantitative possibility theory [START_REF] Dubois | Possibility Theory[END_REF], where degrees of possibility range in the unit interval. Their interpretation as upper probability [START_REF] Walley | Measures of uncertainty in expert systems[END_REF][START_REF] De Cooman | Supremum preserving upper probabilities[END_REF] fits our purpose best.

Probability boxes [START_REF] Ferson | Sensitivity analysis using probability bounding[END_REF], or p-boxes for short, are pairs of lower and upper cumulative distribution functions, and are often used in risk and safety studies, in which cumulative distributions play an essential role. P-boxes have been connected to info-gap theory [START_REF] Ferson | Probability boxes as infogap models[END_REF], random sets [START_REF] Kriegler | Utilizing belief functions for the estimation of future climate change[END_REF], and also, partly, to possibility measures [START_REF] Baudrit | Practical representations of incomplete probabilistic knowledge[END_REF]. P-boxes can be defined on arbitrary finite spaces [START_REF] Destercke | Unifying practical uncertainty representations: I. Generalized p-boxes[END_REF], and, more generally, even on arbitrary totally preordered spaces [START_REF] Troffaes | Probability boxes on totally preordered spaces for multivariate modelling[END_REF]-we will use this extensively.

This paper aims to consolidate the connection between possibility measures and p-boxes, making as few assumptions as possible. We prove that almost every possibility measure can be interpreted as a p-box. Conversely, we provide necessary and sufficient conditions for a p-box to be a possibility measure.

To study this connection, we use imprecise probabilities [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF], of which both possibility measures and pboxes are particular cases. Possibility measures are explored as imprecise probabilities in [START_REF] Walley | Measures of uncertainty in expert systems[END_REF][START_REF] De Cooman | Supremum preserving upper probabilities[END_REF][START_REF] Miranda | Epistemic independence in numerical possibility theory[END_REF], and pboxes are studied as imprecise probabilities briefly in [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF]Section 4.6.6] and [START_REF] Troffaes | Optimality, Uncertainty, and Dynamic Programming with Lower Previsions[END_REF], and in much more detail in [START_REF] Troffaes | Probability boxes on totally preordered spaces for multivariate modelling[END_REF].

The paper is organised as follows: in Section 2, we give the basics of the behavioural theory of imprecise probabilities, and recall some facts about p-boxes and possibility measures; in Section 3, we first determine necessary and sufficient conditions for a p-box to be maximum preserving, before determining in Section 4 necessary and sufficient conditions for a p-box to be a possibility measure; in Section 5, we show that almost any possibility measure can be seen as particular p-box, and that many p-boxes can be seen as a couple of possibility measures; some special cases are detailed in Section 6. Finally, in Section 7 we apply the work on multivariate p-boxes from [START_REF] Troffaes | Probability boxes on totally preordered spaces for multivariate modelling[END_REF] to derive multivariate possibility measures from given marginals, and in Section 8 we give a number of additional comments and remarks.

Note that proofs are omitted for brevity, whence beware that results are presented in the order that they appear most logical, and not in the order that they are most easily proven.

Preliminaries

Imprecise Probabilities

We briefly introduce imprecise probabilities; see [START_REF] Boole | An investigation of the laws of thought on which are founded the mathematical theories of logic and probabilities[END_REF][START_REF] Williams | Notes on conditional previsions[END_REF][START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF][START_REF] Miranda | A survey of the theory of coherent lower previsions[END_REF] for more details.

Let Ω be a possibility space. A subset of Ω is called an event. Denote the set of all events by ℘(Ω), and the set of all finitely additive probabilities on ℘(Ω) by P.

An upper probability is any real-valued function P defined on an arbitrary subset K of ℘(Ω). With P, we associate a lower probability P on {A :

A c ∈ K } via P(A) = 1 -P(A c ). Consider the set M (P) = {P ∈ P : (∀A ∈ K )(P(A) ≤ P(A))}.
The upper envelope E of M (P) is called the natural extension [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF]Thm. 3.4.1] of P:

E(A) = sup{P(A) : P ∈ M (P)} for all A ⊆ Ω. The corresponding lower probability is denoted by E, so E(A) = 1 -E(A c ).
Clearly, E is the lower envelope of M (P).

We say that P is coherent (see [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF]Sec. 3.3.3]) when, for all A ∈ K , P(A) = E(A).

P is called coherent whenever P is.

Ω 1 0 1 F F Figure 1: Example of a p-box on [0, 1].

P-Boxes

In this section, we revise p-boxes defined on totally preordered (not necessarily finite) spaces. For further details, see [START_REF] Troffaes | Probability boxes on totally preordered spaces for multivariate modelling[END_REF].

Start with a totally preordered space (Ω, ). So, is transitive, reflexive and any two elements are comparable. As usual, we write x ≺ y for x y and x y, x y for y ≺ x, and x y for x y and y x. For any two x, y ∈ Ω exactly one of x ≺ y, x y, or x y holds. We also use the following common notation for intervals in Ω:

[x, y] = {z ∈ Ω : x z y} (x, y) = {z ∈ Ω : x ≺ z ≺ y}
and similarly for [x, y) and (x, y].

We assume that Ω has a smallest element 0 Ω and a largest element 1 Ω -we can always add these two elements to the space Ω.

A cumulative distribution function is a nondecreasing map

F : Ω → [0, 1] for which F(1 Ω ) = 1. For each x ∈ Ω, F(x) is interpreted as the probability of [0 Ω , x].
The quotient set of Ω with respect to is denoted by Ω/ :

[x] = {y ∈ Ω : y x} for any x ∈ Ω Ω/ = {[x] : x ∈ Ω}. Because F is non-decreasing, F is constant on elements [x] of Ω/ . Definition 1. A probability box, or p-box, is a pair (F, F) of cumulative distribution functions from Ω to [0, 1] satisfying F ≤ F.
A p-box is interpreted as a lower and an upper cumulative distribution function (see Fig. 1), or more specifically, as an upper probability P F,F on the set of events

{[0 Ω , x] : x ∈ Ω} ∪ {(y, 1 Ω ] : y ∈ Ω} defined by P F,F ([0 Ω , x]) = F(x) and P F,F ((y, 1 Ω ]) = 1 -F(y).
We denote by E F,F the natural extension of P F,F to all events. To simplify the expression for natural extension, we introduce an element 0 Ωsuch that:

0 Ω -≺ x for all x ∈ Ω F(0 Ω -) = F(0 Ω -) = F(0 Ω -) = 0. Note that (0 Ω -, x] = [0 Ω , x]. Now, let Ω * = Ω ∪ {0 Ω -},
and define

H = {(x 0 , x 1 ] ∪ (x 2 , x 3 ] ∪ • • • ∪ (x 2n , x 2n+1 ] : x 0 ≺ x 1 ≺ • • • ≺ x 2n+1 in Ω * }. Proposition 2. [13, Prop. 4] For any A ∈ H , that is A = (x 0 , x 1 ] ∪ (x 2 , x 3 ] ∪ • • • ∪ (x 2n , x 2n+1 ] with x 0 ≺ x 1 ≺ • • • ≺ x 2n+1 in Ω * , it holds that E F,F (A) = P H F,F (A), where P H F,F (A) = 1 - n+1 ∑ k=0 max{0, F(x 2k ) -F(x 2k-1 )}, (1) with x -1 = 0 Ω -and x 2n+2 = 1 Ω .
To calculate E F,F (A) for an arbitrary event A ⊆ Ω, use the outer measure [14, Cor. 3.1.9] P H F,F * of the upper probability P H F,F defined in Eq. ( 1):

E F,F (A) = P H F,F * (A) = inf C∈H , A⊆C P H F,F (C). (2)
For intervals, we immediately infer from Proposition 2 and Eq. ( 2) that ('i.p.' stands for 'immediate predecessor')

E F,F ((x, y]) = F(y) -F(x) (3a)
E F,F ([x, y]) = F(y) -F(x-) (3b)
E F,F ((x, y)) = F(y) -F(x) if y has no i.p. F(y-) -F(x) if y has an i.p.

(3c)

E F,F ([x, y)) = F(y) -F(x-) if y has no i.p. F(y-) -F(x-) if y has an i.p. ( 3d
)
for any x ≺ y in Ω, 1 where F(y-) denotes sup z≺y F(z) and similarly for F(x-). If Ω/ is finite, then one can think of zas the immediate predecessor of z in the quotient space Ω/ for any z ∈ Ω. We also have that

E F,F ({x}) = F(x) -F(x-) (4)
for any x ∈ Ω.

Possibility and Maxitive Measures

Brevity is stipulated; see [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF][START_REF] Dubois | Possibility Theory[END_REF][START_REF] Walley | Measures of uncertainty in expert systems[END_REF][START_REF] De Cooman | Supremum preserving upper probabilities[END_REF] for details. Possibility measures are a particular case of maxitive measures.

Definition 5. A (normed) possibility distribution is a mapping π : Ω → [0, 1] satisfying sup x∈Ω π(x) = 1. A possibility distribution π induces a possibility measure Π on ℘(Ω), given by:

Π(A) = sup x∈A π(x) for all A ⊆ Ω.
If we write E Π for the conjugate lower probability of the upper probability Π, then:

E Π (A) = 1 -Π(A c ) = 1 -sup x∈A c π(x).
A possibility measure is maxitive, but not all maxitive measures are possibility measures.

As an imprecise probability model, possibility measures are not as expressive as for instance p-boxes. This poor expressive power is also illustrated by the fact that, for any event A:

Π(A) < 1 =⇒ E Π (A) = 0, and E Π (A) > 0 =⇒ Π(A) = 1,
meaning that every event has a trivial probability bound on at least one side. Their main attraction is that calculations with them are very easy: to find the upper (or lower) probability of any event, a simple supremum suffices.

In the following sections, we characterize the circumstances under which a possibility measure Π is the natural extension of some p-box (F, F). In order to do so, we first characterise the conditions under which a p-box induces a maxitive measure.

P-boxes as Maxitive Measures

Necessary and Sufficient Condition for Maxitivity

Let us begin by characterising under which conditions the natural extension of a p-box is maxitive:

Theorem 6. The natural extension E F,F of a p-box (F, F) is maximum preserving if and only if at least one of F or F is 0-1-valued.
Hence, for the purposes of this paper we can restrict our attention to p-boxes (F, F) where at least one of F or F is 0-1-valued. Next, we provide expressions for the natural extensions of such p-boxes, and determine under which conditions these are possibility measures.

Natural Extension of Maxitive P-Boxes

In case of 0-1-valued F, we arrive at the following expression: Proposition 7. Let (F, F) be a p-box with 0-1-valued F, and let B = {x ∈ Ω * : F(x) = 0}. Then, for any A ⊆ Ω,

E F,F (A) = min y∈B c inf x∈Ω * : A∩[0 Ω ,y] x F(x).
Here, A x means z x for all z ∈ A, and similarly y ≺ A means y ≺ z for all z ∈ A. Thus, / 0 x and y ≺ / 0 for all x and y.

An important special case is summarized in the following corollary:

Corollary 8. Let (F, F) be a p-box with 0-1-valued F, and let B = {x ∈ Ω * : F(x) = 0}. If Ω/ is order com- plete, then, for any A ⊆ Ω, E F,F (A) = min y∈B c F(sup A ∩ [0 Ω , y]).
If, in addition, B c has a minimum, then

E F,F (A) = F(sup A ∩ [0 Ω , min B c ]).
If, in addition,

F = I [1 Ω ] , then E F,F (A) = F(sup A). (5)
Note that Eq. ( 5) is essentially due to [7, paragraph preceeding Theorem 11]-they work with chains and multivalued mappings, whereas we work with total preorders. The case of order complete Ω/ is applicable for instance when Ω is a finite space, or when it is an interval of real numbers.

In case of 0-1-valued F, we arrive at the following expression:

Proposition 9. Let (F, F) be a p-box with 0-1-valued F, and let C = {x ∈ Ω * : F(x) = 0}. Then, for any A ⊆ Ω, E F,F (A) = 1 -max x∈C sup y∈Ω * : y≺A∩(x,1 Ω ] F(y).
Again, we summarize an important special case in the following corollary: Corollary 10. Let (F, F) be a p-box with 0-1-valued F, and let C = {x ∈ Ω * : F(x) = 0}. If Ω/ is order complete, and C has a maximum, then, for any A ⊆ Ω,

E F,F (A) =          1 -F(inf A ∩C c ) if A ∩C c has no minimum 1 -F((min A ∩C c )-) if A ∩C c has a minimum. If, in addition, F = 1, then E F,F (A) = 1 -F(inf A) if A has no minimum 1 -F(min A-) if A has a minimum.

P-Boxes as Possibility Measures.

In this section, we identify when p-boxes coincide exactly with a possibility measure. All results in this section rely on the following trivial, yet important, lemma: Lemma 11. For a p-box (F, F) there is a possibility measure Π such that E F,F = Π if and only if

E F,F (A) = sup x∈A E F,F ({x}) for all A ⊆ Ω and in such a case, π(x) = E F,F ({x}).
We say that a p-box (F, F) is a possibility measure when the conditions of Lemma 11 are satisfied.

Taking into account that every possibility measure is maxitive, we deduce from Theorem 6 that, for a p-box to be a possibility measure, it is necessary that at least one of F or F is 0-1-valued. The next corollary characterizes the additional regularity conditions to arrive at necessity and sufficiency: Corollary 12. Assume that Ω/ is order complete and let (F, F) be a p-box. Then (F, F) is a possibility measure if and only if either (L1) F is 0-1-valued, (L2) F(x) = F(x-) for all x ∈ Ω that have no immediate predecessor, and

(L3) {x ∈ Ω * : F(x) = 1} has a minimum, or (U1) F is 0-1-valued, (U2) F(x) = F(x+)
for all x ∈ Ω that have no immediate successor, and

(U3) {x ∈ Ω * : F(x) = 0} has a maximum.
Note that, in case Observation 9]. Also note that, for E F,F to be a possibility measure, the conditions are still necessary even when Ω/ is not order complete: the proof in this direction does not require order completeness.

F = I [1 Ω ] , condition (L2) is essen- tially due to [7,
As a special case, when Ω/ is finite, E F,F is a possibility measure with possibility distribution

π(x) = F(x) if x min{y : F(y) = 1} 0 otherwise.
when F is 0-1-valued, and

π(x) = 1 -F(x-) if F(x) = 1 0 otherwise.
when F is 0-1-valued. We now characterise when, conversely, possibility measures can be represented as p-boxes. We shall see that this is possible for almost all of them.

From Possibility Measures to P-Boxes

Possibility Measures as Specific P-Boxes

[11] already discuss the link between possibility measures and p-boxes defined on the real line with the usual ordering. They show that any possibility measure can be approximated by a p-box, however at the expense of losing some information. We substantially strengthen their result, and even reverse it: we prove that any possibility measure with compact range can be exactly represented by a p-box with vacuous lower cumulative distribution function, that is, with

F = I [1 Ω ] .
In other words, generally speaking, possibility measures are a special case of p-boxes on totally preordered spaces.

Theorem 13. For every possibility measure Π on Ω with possibility distribution π such that π(Ω) = {π(x) : x ∈ Ω} is compact, there is a preorder on Ω and an upper cumulative distribution function F such that the p-box (F = I [1 Ω ] , F) is a possibility measure with possibility distribution π. In fact, one may take the preorder to be the one induced by π (so x y whenever π(x) ≤ π(y)) and F = π.

The representing p-box is not necessarily unique: Example 14. Let Ω = {x 1 , x 2 } and let Π be the possibility measure determined by the possibility distribution

π(x 1 ) = 0.5 π(x 2 ) = 1.
By Theorem 13, this possibility measure can be obtained if we consider the order x 1 ≺ x 2 and the p-box

(F 1 , F 1 )
given by

F 1 (x 1 ) = 0 F 1 (x 2 ) = 1 F 1 (x 1 ) = 0.5 F 1 (x 2 ) = 1.
However, we also obtain it if we consider the order x 2 ≺ x 1 and the p-box (F 2 , F 2 ) given by

F 2 (x 1 ) = 1 F 2 (x 2 ) = 0.5 F 2 (x 1 ) = 1 F 2 (x 2 ) = 1.
Indeed, by Corollary 12, E F 2 ,F 2 is a possibility measure. By Eq. ( 4), its associated possibility distribution is

E F 2 ,F 2 (x 2 ) = F(x 2 ) -F(x 2 -) = 1 E F 2 ,F 2 (x 1 ) = F(x 1 ) -F(x 1 -) = 0.5,
i.e., π, as with the given ordering, x 2 -= 0 Ωand

x 1 -= x 2 .
Moreover, a p-box may be maximum preserving even if neither the lower nor the upper distribution function is vacuous, as we have shown in Corollary 12.

Also, there are possibility measures which cannot be represented as p-boxes when π(Ω) is not compact:

Example 15. Let Ω = [0, 1], and consider the possibility distribution given by π(x) = (1 + 2x)/8 if x < 0.5, π(0.5) = 0.4 and π(x) = x if x > 0.5; note that π(Ω) = [0.125, 0.25) ∪ {0.4} ∪ (0.5, 1] is not compact. The ordering induced by π is the usual ordering on [0, 1]. Let Π be the possibility measure induced by π. We show that there is no p-box (F, F) on ([0, 1], ), regardless of the ordering on [0, 1], such that E F,F = Π.

By Corollary 12, if E F,F = Π, then at least one of F or F is 0-1-valued. Assume first that F is 0-1-valued. By Eq. ( 4), E F,F ({x}) = F(x)-F(x-) = π(x). Because π(x) > 0 for all x, it must be that F(x-) = 0 for all x, so F = π. Because F is non-decreasing, x y if and only if F(x) ≤ F(y); in other words, can only be the usual ordering on [0, 1] for (F, F) to be a p-box. Hence, F = I {1} .

For (F, F) to induce the possibility measure Π, we know from Corollary 12 that F(x) = F(x-) for every

x that has no immediate predecessor, that is, for every x > 0. But, F(0.5) = 0.4 = 0.25 = F(0.5-).

Similarly, if F would be 0-1-valued, then we deduce from Eq. (4) that F(x) = 1 for every x, again because π(x) > 0 for all x. Therefore, F(x-) = 1-π(x) for all x. But, because F is non-decreasing, one can easily show that can only be the inverse of the usual ordering on [0, 1] for (F, F) to be a p-box. Now, for (F, F) to induce the possibility measure Π, we know from Corollary 12 that F(x) = F(x+) for every x that has no immediate successor in with respect to , that is, for every x ≺ 0, or equivalently, for every x > 0. Whence,

F(x) = F(x+) = inf y x F(y-) = 1 -sup y<x π(y)
for all x > 0. This leads to a contradiction: by the definition of π, we have on the one hand,

F(0.5-) = sup x>0.5 (1 -sup y<x π(y)) = 0.5
and on the other hand,

F(0.5-) = 1 -π(0.5) = 0.6.
Hence, E F,F coincides with Π in neither case.

Another way of relating possibility measures and pboxes goes via random sets (see for instance [START_REF] Kriegler | Utilizing belief functions for the estimation of future climate change[END_REF] and [START_REF] Destercke | Unifying practical uncertainty representations: I. Generalized p-boxes[END_REF]).

P-boxes as Conjunction of Possibility Measures

In [START_REF] Destercke | Unifying practical uncertainty representations: I. Generalized p-boxes[END_REF], where p-boxes are studied on finite spaces, it is shown that a p-box can be interpreted as the conjunction of two possibility measures, in the sense that M (P F,F ) is the intersection of two sets of additive probabilities induced by two possibility measures. The next proposition extends this result to arbitrary totally preordered spaces.

Proposition 16. Let (F, F) be a p-box such that (F, I Ω ) and (I [1 Ω ] , F) are possibility measures (see Corollary 12). Then, (F, F) is the intersection of two possibility measures defined by the distributions

π F (x) = F(x) and π F (x) = 1 -F(x-), in the sense that M (P F,F ) = M (Π π F ) ∩ M (Π π F ).
This suggests a simple way (already mentioned in [START_REF] Destercke | Unifying practical uncertainty representations: I. Generalized p-boxes[END_REF]) to conservatively approximate E F,F by using the two possibility distributions: it holds that

max{E π F (A), E π F (A)} ≤ E F,F (A) ≤ E F,F (A) ≤ min{E π F (A), E π F (A)}.
This approximation is computationally attractive, as it allows us to use the supremum preserving properties of possibility measures. However, as next example shows, the approximation will usually be very conservative, and hence not likely to be helpful.

Example 17. Consider x ≺ y ∈ Ω. The distance between E F,F and its approximation min{E π F , E π F } on the interval (x, y] is given by

min{E π F ((x, y]), E π F ((x, y])} -E((x, y]) = min{F(y), 1 -F(x)} -(F(y) -F(x)) = min{F(x), 1 -F(y)}.
Therefore, the approximation will be close to the exact value only when either F(x) is close to zero or F(y) is close to one.

In general, the set M (Π 1 ) ∩ M (Π 2 ) associated with two possibility distributions π 1 and π 2 is not a p-box. Indeed, it may be empty (take for instance Ω = {1, 2} and the possibility measures determined by the distributions π 1 (1) = 1, π 1 (2) = 0.25, π 2 (1) = 0.25, π 2 (2) = 1), or result in another uncertainty model, such as a cloud [START_REF] Dubois | Interval-valued fuzzy sets, possibility theory and imprecise probability[END_REF]. In particular, when M (Π 1 ) ∩ M (Π 2 ) is non-empty, the resulting coherent upper probability is in general not a possibility measure. An interesting open problem is then to characterise under which conditions some of the properties (i.e., maxitivity, complete monotonicity) of Π 1 and Π 2 still hold for the coherent upper probability determined by M (Π 1 ) ∩ M (Π 2 ).

Natural Extension of 0-1-Valued P-Boxes

From Proposition 7, we can derive an expression for the natural extension of a 0-1-valued p-box:

B c has a minimum and C has a maximum.

In particular, we can characterise under which conditions a precise p-box, i.e., one where F = F := F, induces a possibility measure. The natural extension of precise p-boxes on the unit interval was considered in [START_REF] Miranda | Finitely additive extensions of distribution functions and moment sequences: the coherent lower prevision approach[END_REF]Section 3.1]. From Theorem 6, the natural extension of F can only be a possibility measure when F is 0-1-valued. If we apply Propositions 18 and 19 with B = C we obtain the following: Corollary 20. Let (F, F) be a precise p-box where F = F is 0-1-valued, and let B = {x ∈ Ω * : F(x) = 0}. Then, for every subset A of Ω,

E F,F (A) =      0 if there are x ∈ B, y ∈ B c s.t. A ∩ B x and y ≺ A ∩ B c 1 otherwise.
If moreover Ω/ is order complete, then (F, F) is a possibility measure if and only if B has a maximum and B c has a minimum.

As a consequence, we deduce that a precise 0-1valued p-box never induces a possibility measure in case

(Ω, ) = ([0, 1], ≤), except if F = I [0,1] .

Constructing Multivariate Possibility Measures from Marginals

In [START_REF] Troffaes | Probability boxes on totally preordered spaces for multivariate modelling[END_REF], multivariate p-boxes were constructed from marginals. We next apply this construction together with the p-box representation of possibility measures, given by Theorem 13, to build a joint possibility measure from some given marginals. As particular cases, we consider the joint, (i) either without any assumptions about dependence or independence between variables, that is, using the Fréchet-Hoeffding bounds [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF],

(ii) or assuming epistemic independence between all variables, which allows us to use the factorization property [START_REF] De Cooman | Independent natural extension[END_REF].

Let us consider n variables X 1 , . . . , X n , and assume that for each variable X i we are given a possibility measure Π i with corresponding possibility distribution π i on X i . We assume that the range of all marginal possibility distributions is [0, 1]; in particular, Theorem 13 applies, and each marginal can be represented by a p-box on (X i , i ), with vacuous F i , and F i = π i . Remember that the preorder i is the one induced by π i .

Multivariate Possibility Measures

The construction in [START_REF] Troffaes | Probability boxes on totally preordered spaces for multivariate modelling[END_REF]Sect. 7] employs the following mapping Z, which induces a preorder on

Ω = X 1 × • • • × X n : Z(x 1 , . . . , x ) = n max i=1 π i (x i ).
With this choice of Z, we can easily find the possibility measure which represents the joint as accurately as possible, under any rule of combination of coherent lower probabilities:

Lemma 21. Let be any rule of combination of coherent upper probabilities, mapping the marginals P 1 , . . . , P n to a joint coherent upper probability n i=1 i on all events. If there is a continuous function u for which

n i=1 P i n ∏ i=1 A i = u(P 1 (A 1 ), . . . , P n (A n ))
for all A 1 ⊆ X 1 , . . . , A n ⊆ X n , then the possibility distribution π defined by π(x) = u(Z(x), . . . , Z(x)) induces the least conservative upper cumulative distribution function on (Ω, ) that dominates the combina-

tion n i=1 Π i of Π 1 , . . . , Π n .
This result is a consequence of [13, Lemma 22], which gives the least conservative p-box that dominates the natural extension of the combination of some marginal p-boxes by . Here we are considering the particular case where the marginal p-boxes represent possibility measures, and approximating of the corresponding p-box by a possibility measure.

Natural Extension: The Fréchet Case

The natural extension n i=1 P i of P 1 , . . . , P n is the upper envelope of all joint (finitely additive) probability measures whose marginal distributions are compatible with the given marginal upper probabilities. So, the model is completely vacuous (that is, it makes no assumptions) about the dependence structure, as it includes all possible forms of dependence. See [24, p. 120, §3.1] for a rigorous definition. In this paper, we only need the following equality, which is one of the Fréchet bounds (see for instance [14, p. 122, §3.1.1]):

n i=1 P i n ∏ i=1 A i = n min i=1 P i (A i ) for all A 1 ⊆ X 1 , . . . , A n ⊆ X n . Theorem 22. The possibility distribution π(x) = n max i=1 π i (x i ) (6)
induces the least conservative upper cumulative distribution function on (Ω, ) that dominates the natural extension n i=1 Π i of Π 1 , . . . , Π n . In other words, if we consider the marginal credal sets M (Π 1 ), . . . , M (Π n ) and consider the set M of all the finitely additive probabilities on Ω whose X i -marginals belong to M (Π i ) for i = 1, . . . , n, then M is included in the credal set of the possibility distribution π as defined in Eq. [START_REF] Walley | Measures of uncertainty in expert systems[END_REF].

Since it is based on very mild assumptions, it is not surprising that the possibility distribution given by Eq. ( 6) is very uninformative (that is, very close to a vacuous model where π(x) = 1 for every x): we shall have π(x) = 1 as soon as π i (x i ) = 1 for some i, even if π j (x j ) = 0 for every j = i. In particular, if one of the marginal possibility distributions is vacuous, then so is π. This also shows that the corresponding possibility measure Π may not have Π 1 , . . . , Π n as its marginals.

Independent Natural Extension

In contrast, we can consider joint models which satisfy the property of epistemic independence between the different X 1 , . . . , X n . This property means, roughly speaking, that the conditional models that we can derive from the joint coincide with the marginals. The most conservative of these models is called the independent natural extension ⊗ n i=1 P i of P 1 , . . . , P n . See [START_REF] De Cooman | Independent natural extension[END_REF] for a rigorous definition and properties, and [START_REF] Miranda | Epistemic independence in numerical possibility theory[END_REF] for a study of joint possibility measures that satisfy epistemic independence in the case of two variables. In this paper, we only need the following equality for the independent natural extension:

n i=1 P i n ∏ i=1 A i = n ∏ i=1 P i (A i ) (7)
for all A 1 ⊆ X 1 , . . . , A n ⊆ X n .

Theorem 23. The possibility distribution

π(x) = n max i=1 π i (x i ) n (8)
induces the least conservative upper cumulative distribution function on (Ω, ) that dominates the independent natural extension ⊗ n i=1 Π i of Π 1 , . . . , Π n . Note that the possibility measure determined Eq. ( 8) is only an outer approximation of the independent natural extension: as shown in [START_REF] Miranda | Epistemic independence in numerical possibility theory[END_REF]Sec. 6], there is no least conservative possibility measure that corresponds to the independent natural extension of possibility measures.

One interesting consequence of Theorem 23 is that we can also use the possibility distribution determined by Eq. ( 8) under some other independence conditions for imprecise probabilities, such as strong or Kuznetsov independence [START_REF] Cozman | Constructing sets of probability measures through Kuznetsov's independence condition[END_REF][START_REF] De Cooman | Factorisation properties of the strong product[END_REF]. This is because the joint model they determine also satisfies the factorization condition given by Eq. ( 7), and as a consequence the least conservative upper cumulative distribution that dominates the strong or the Kuznetsov product of the marginal possibility measures is also determined by Eq. ( 8). See [START_REF] De Cooman | Independent natural extension[END_REF] for more information on the relationship between factorization and independence.

We do not consider the minimum rule and the product rule

n min i=1 π i (x i ) and n ∏ i=1 π i (x i ),
as their relation with the theory of coherent lower previsions is still unclear. However, we can compare the above approximation with the following outer approximation given by [27, Proposition 1]:

π(x) = n min i=1 (1 -(1 -π i (x i )) n ). (9)
The above equation is an outer approximation in case of random set independence, which is slightly more conservative than the independent natural extension [28, Sec. 4], so in particular, it is also an outer approximation of the independent natural extension. Essentially, each distribution π i is transformed into 1 -(1π i ) n before applying the minimum rule. It can be expressed more simply as 1 -

n max i=1 (1 -π i (x i )) n .
If for instance π(x i ) = 1 for at least one i, then this formula provides a more informative (i.e., lower) upper bound than Theorem 23. On the other hand, when all π(x i ) are, say, less than 1/2, then Theorem 23 does better. Finally, note that neither Eq. ( 8) nor Eq. ( 9) are proper joints, in the sense that, in both cases, the marginals of the joint are outer approximations of the original marginals, and will in general not coincide with the original marginals.

Conclusions

Both possibility measures and p-boxes can be seen as coherent upper probabilities. We used this framework to study the relationship between possibility measures and p-boxes. Following [START_REF] Troffaes | Probability boxes on totally preordered spaces for multivariate modelling[END_REF], we allowed p-boxes to be defined on arbitrary totally preordered spaces, whence including p-boxes on finite spaces, on real intervals, and even multivariate ones.

We began by considering the more general case of maxitive measures, and proved that a necessary and sufficient condition for a p-box to be maxitive is that at least one of the cumulative distribution functions of the p-box must be 0-1 valued. Moreover, we determined the natural extension of a p-box in those cases and gave a necessary and sufficient condition for the p-box to be supremum-preserving, i.e., a possibility measure. As special cases, we also studied p-boxes where both the lower and the upper distribution functions are 0-1valued, and in particular precise 0-1 valued p-boxes.

Secondly, we showed that almost every possibility measure can be represented as a p-box. Hence, in general, p-boxes are more expressive than possibility measures, while still keeping a relatively simple representation and calculus [START_REF] Troffaes | Probability boxes on totally preordered spaces for multivariate modelling[END_REF], unlike many other models, such as for instance lower previsions and credal sets, which typically require far more advanced techniques, such as linear programming.

Finally, we considered the multivariate case in more detail, by deriving a joint possibility measure from given marginals using the p-box representation established in this paper and results from [START_REF] Troffaes | Probability boxes on totally preordered spaces for multivariate modelling[END_REF].

In conclusion, we established new connections between both models, strengthening known results from literature, and allowing many results from possibility theory to be embedded into the theory of p-boxes, and vice versa.

As future lines of research, we point out the generalisation of a number of properties of possibility measures to p-boxes, such as the connection with fuzzy logic [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF] or the representation by means of graphical structures [START_REF] Borgelt | Possibilistic graphical models[END_REF], and the study of the connection of p-boxes with other uncertainty models, such as clouds and random sets.

Definition 3 .

 3 A maxitive measure is an upper probability P on ℘(Ω) satisfying P(A ∪ B) = max{P(A), P(B)} for every A and B ⊆ Ω. Proposition 4. [16, Def. 3.22, Thm. 3.46] A maxitive measure P is coherent whenever P( / 0) = 0 and P(Ω) = 1.

Proposition 18 .0

 18 Let (F, F) be a p-box where F = I C c , F = I B c for some C ⊆ B ⊆ Ω. Then for any A ⊆ Ω, if there are x ∈ C and y ∈ B c s.t. A ∩C x, A ∩ B ∩C c = / 0, y ≺ A ∩ B c 1 otherwise. Moreover, Corollary 12 allows us to determine when this p-box is a possibility measure: Proposition 19. Assume that Ω/ is order complete. Let (F, F) be a p-box where F = I C c , F = I B c for some C ⊆ B ⊆ Ω. The following statements are equivalent: 1. (F, F) is a possibility measure.

In case x = 0 Ω , evidently, 0 Ωis the immediate predecessor.

Acknowledgements

Work partially supported by projects TIN2008-06796-C04-01 and MTM2010-17844 and by a doctoral grant from the IRSN.


Troffaes M C M Matthias
email: matthias.troffaes@gmail.com

Sébastien Destercke

Matthias Troffaes

Sebastien Destercke
email: sebastien.destercke@cirad.fr

Probability boxes on totally preordered spaces for multivariate modelling

Keywords: p-box, natural extension, multivariate, elicitation, independence, Fréchet, lower prevision

Probability boxes (pairs of cumulative distribution functions) are among the most popular models used in imprecise probability theory. In this paper, we provide new efficient tools to construct multivariate pboxes and develop algorithms to draw inferences from them. For this purpose, we formalise and extend the theory of p-boxes using lower previsions. We allow p-boxes to be defined on arbitrary totally preordered spaces, hence thereby also admitting multivariate pboxes. We discuss the construction of multivariate pboxes under various independence assumptions. An example demonstrates the practical feasibility of our results.

Introduction

Imprecise probability [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF] refers to uncertainty models applicable in situations where the available information does not allow us to single out a unique probability measure for the random variables involved. They require more complex mathematical tools, such as non-linear functionals. It is therefore of interest to consider models that yield simpler mathematical descriptions, at the expense of generality, but gaining ease of use, elicitation, and representation.

We consider one such model: pairs of lower and upper distribution functions, also called probability boxes, or p-boxes [START_REF] Ferson | Constructing probability boxes and Dempster-Shafer structures[END_REF][START_REF] Ferson | Sensitivity analysis using probability bounding[END_REF]. They are often used in risk studies, where cumulative distributions are central. Many theoretical properties and practical aspects of p-boxes have already been studied in the literature. Previous work includes probabilistic arithmetic [START_REF] Williamson | Probabilistic arithmetic I: Numerical methods for calculating convolutions and dependency bounds[END_REF], which provides a very efficient numerical framework for particular inferences with p-boxes (and which we generalise in this paper). In [START_REF] Ferson | Probability boxes as info-gap models[END_REF], p-boxes are connected to info-gap theory [START_REF] Ben-Haim | Info-gap decision theory: decisions under severe uncertainty[END_REF]. The relation between p-boxes and random sets was investigated in [START_REF] Kriegler | Utilizing belief functions for the estimation of future climate change[END_REF]. Finally, an extension of p-boxes to arbitrary finite spaces [START_REF] Destercke | Unifying practical uncertainty representations: I. Generalized p-boxes[END_REF] yields potential applications to much more general problems.

In this paper, we study p-boxes using lower previsions [START_REF] Williams | Notes on conditional previsions[END_REF][START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF]. From the point of view of lower previsions, p-boxes were studied briefly in [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF]Section 4.6.6] and [START_REF] Troffaes | Optimality, Uncertainty, and Dynamic Programming with Lower Previsions[END_REF]. This has at least two advantages. Firstly, they can be defined on arbitrary spaces. Secondly, they come with a powerful inference tool, called natural extension. We will study the natural extension of a p-box, and we derive a number of useful expressions for it, whence providing new numerical tools for exact inferences on arbitrary random quantities and events. As mentioned, [START_REF] Destercke | Unifying practical uncertainty representations: I. Generalized p-boxes[END_REF] extended p-boxes to finite totally preordered spaces. In this paper, we extend p-boxes further to arbitrary totally preordered spaces, leading to many useful features that classical p-boxes do not have. Firstly, we encompass, in one sweep, pboxes defined on finite spaces and on closed real intervals. Secondly, as we do not impose anti-symmetry on the ordering, we can also handle product spaces by considering an appropriate total preorder, and thus also admit multivariate non-finite p-boxes, which have not been considered before. 1 Whence, we can specify p-boxes directly on the product space. Contrast this with the usual multivariate approach to p-boxes, such as probabilistic arithmetic [START_REF] Williamson | Probabilistic arithmetic I: Numerical methods for calculating convolutions and dependency bounds[END_REF], that consider one marginal p-box per dimension and draw inferences from a joint model built around some information about variable dependencies. Finally, our approach is also useful in elicitation, as it allows uncertainty to be expressed as probability bounds over any collection of (possibly multivariate) nested sets, because we can always find a total preorder that is compatible with any collection of nested sets.

The paper is organised as follows: Section 2 provides a brief introduction to the theory of coherent lower previsions. Section 3 introduces and studies the pbox model from the point of view of lower previsions. Section 4 provides an expression for the natural extension of a p-box to all events, and Section 5 studies the natural extension to all gambles. Section 6 studies an important special case of p-boxes whose preorder is induced by a real-valued mapping, as this is a convenient way to specify a multivariate p-box. Section 7 discusses the construction of such multivariate p-boxes from marginal coherent lower previsions under arbitrary dependency models. Section 8 demonstrates the theory with an example.

Preliminaries

This section introduces lower previsions, see [START_REF] Boole | An investigation of the laws of thought on which are founded the mathematical theories of logic and probabilities[END_REF][START_REF] Williams | Notes on conditional previsions[END_REF][START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF][START_REF] Miranda | A survey of the theory of coherent lower previsions[END_REF] for details.

The possibility space is Ω. A gamble on Ω is a bounded real-valued map on Ω. The set of all gambles on Ω is L(Ω), or L if Ω is evident. A subset of Ω is an event. The indicator of A is the gamble that is 1 on A and 0 elsewhere: write I A , or A if confusion fails.

A lower prevision P is a real-valued map on an arbitrary subset K of L: for any f in K, P (f ) represents a subject's supremum buying price for f (see [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF] for actual explanation). A lower prevision on a set of indicators of events is a lower probability.

P denotes the conjugate upper prevision of P : for every -f ∈ K, P (f ) = -P (-f ); it represents a subject's infimum selling price for f . A real-valued map P on L satisfying P (f ) ≥ inf f and P (f + g) = P (f ) + P (g) for all f and g ∈ L is a linear prevision on L [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF]p. 88,Sec. 2.4.8]. The set of all linear previsions on L is denoted by P. A linear prevision is essentially an expectation operator.

Of particular interest is the set

M(P ) = {Q ∈ P : (∀f ∈ K)(Q(f ) ≥ P (f ))}.
If M(P ) = ∅, then P is said to avoid sure loss, in which case the natural extension of P [18, Sec. 3.4.1] [19, p. 18] when it coincides with E on K.

E(f ) = min Q∈M(P ) Q(f ) for all f ∈ L extends P to L. Finally, P is called coherent
A lower prevision P defined on a lattice of gambles K, i.e., a set of gambles closed under point-wise maximum and point-wise minimum, is called n-monotone if for all p ∈ N, p ≤ n, and all f , f 1 , . . . , f p in K [START_REF] De Cooman | n-Monotone exact functionals[END_REF]:

I⊆{1,...,p} (-1) |I| P f ∧ i∈I f i ≥ 0.
A lower prevision which is n-monotone for all n ∈ N is called completely monotone.

P-Boxes

Next, we introduce the formalism of p-boxes defined on totally preordered spaces. In contrast to [START_REF] Ferson | Constructing probability boxes and Dempster-Shafer structures[END_REF], we do not restrict p-boxes to intervals on the real line.

Let (Ω, ) be a total preorder: so is transitive and reflexive and any two elements are comparable. We write x ≺ y for x y and x y, x y for y ≺ x, and x y for x y and y x. For any two x, y ∈ Ω exactly one of x ≺ y, x y, or x y holds. We also use the following common notation for intervals in Ω:

[x, y] = {z ∈ Ω : x z y} (x, y) = {z ∈ Ω : x ≺ z ≺ y}
and similarly for [x, y) and (x, y].

For simplicity, we assume that Ω has a smallest element 0 Ω and a largest element 1 Ω (we can always add them to Ω).

A cumulative distribution function is a mapping F : Ω → [0, 1] which is non-decreasing and satisfies moreover F (1 Ω ) = 1. For each x ∈ Ω, we interpret F (x) as the probability of the interval [0 Ω , x]. We do not impose F (0 Ω ) = 0, so we allow {0 Ω } to carry nonzero mass, which happens commonly if Ω is finite. No continuity assumptions are made.

By Ω/ we denote the quotient set of Ω with respect to the equivalence relation induced by , that is:

[x] = {y ∈ Ω : y x} for any x ∈ Ω Ω/ = {[x] : x ∈ Ω} Because F is non-decreasing, F is constant on ele- ments [x] of Ω/ . Definition 1. A probability box, or p-box, is a pair (F , F ) of cumulative distribution functions from Ω to [0, 1] satisfying F ≤ F .
A p-box is interpreted as a lower and an upper cumulative distribution function. In Walley's framework, this means that a p-box is interpreted as a lower probability P F ,F on the set of events

K = {[0 Ω , x] : x ∈ Ω} ∪ {(y, 1 Ω ] : y ∈ Ω} by P F ,F ([0 Ω , x]) = F (x) and P F ,F ((y, 1 Ω ]) = 1 -F (y).
P-boxes on a totally preordered space (Ω, ) are coherent (the proof is virtually identical to the one given in [START_REF] Troffaes | Optimality, Uncertainty, and Dynamic Programming with Lower Previsions[END_REF]p. 93,Thm. 3.59], which considered p-boxes on [a, b] ⊆ R). We denote by E F ,F the natural extension of P F ,F to all gambles.

When F = F , we say that (F , F ) is precise, and we denote the corresponding lower prevision on K by P F and its natural extension to L by E F (with

F := F = F ).
We end with a useful approximation theorem: Theorem 2. Let P be any coherent lower prevision defined on L. The least conservative p-box (F , F ) on (Ω, ) whose natural extension is dominated by P is

F (x) = P ([0 Ω , x])), F (x) = P ([0 Ω , x]), ∀x ∈ Ω.

Natural Extension to All Events

The remainder of this paper is devoted to finding convenient expressions for the natural extension E F ,F of P F ,F . We start by giving the form of the natural extension on the field of events generated by K.

Extension to the Field Generated by the Domain

Let H be the field of events generated by the domain K of the p-box, i.e., events of the type

[0 Ω , x 1 ] ∪ (x 2 , x 3 ] ∪ • • • ∪ (x 2n , x 2n+1 ] for x 1 ≺ x 2 ≺ x 3 ≺ • • • ≺ x 2n+1
in Ω (if n is 0 we simply take this expression to be [0 Ω , x 1 ]) and

(x 2 , x 3 ] ∪ • • • ∪ (x 2n , x 2n+1 ] for x 2 ≺ x 3 ≺ • • • ≺ x 2n+1 in Ω.
Clearly, these events form a field: the union and intersection of any two events in H is again in H, and the complement of any event in H also is again in H.

To simplify the description of this field, and the expression of natural extension, we introduce an element 0 Ω -such that 0 Ω -≺ x for all x ∈ Ω and:

F (0 Ω -) = F (0 Ω -) = F (0 Ω -) = 0 So, (0 Ω -, x] = [0 Ω , x]. With Ω * = Ω ∪ {0 Ω -}, H = {(x 0 , x 1 ] ∪ (x 2 , x 3 ] ∪ • • • ∪ (x 2n , x 2n+1 ] : (1)
x 0 ≺ x 1 ≺ • • • ≺ x 2n+1 in Ω * }.
To calculate the natural extension of P F ,F to all gambles, we first consider the extension from K to H, then to all events, and finally to all gambles.

A precise p-box P F has a unique extension to a finitely additive probability measure on H:

Proposition 3. E F restricted to H is a finitely ad- ditive probability measure. Moreover, for any A ∈ H, that is A = (x 0 , x 1 ] ∪ (x 2 , x 3 ] ∪ • • • ∪ (x 2n , x 2n+1 ] with x 0 ≺ x 1 ≺ • • • ≺ x 2n+1 in Ω * , it holds that E F (A) = n k=0 (F (x 2k+1 ) -F (x 2k )) (2)
Proposition 3 extends to p-boxes as follows:

Proposition 4. For any A ∈ H, that is A = (x 0 , x 1 ]∪ (x 2 , x 3 ]∪• • •∪(x 2n , x 2n+1 ] with x 0 ≺ x 1 ≺ • • • ≺ x 2n+1 in Ω * , it holds that E F ,F (A) = P H F ,F (A)
, where

P H F ,F (A) = n k=0 max{0, F (x 2k+1 ) -F (x 2k )}. (3) For E F ,F , use E F ,F (A) = 1 -E F ,F (A c ).

Inner Measure

The inner measure P H F ,F * of the coherent lower probability P H F ,F defined in Eq. ( 3) coincides with E F ,F on all events [18, Cor. 3.1.9, p. 127]:

E F ,F (A) = P H F ,F * (A) = sup C∈H,C⊆A P H F ,F (C). (4)
For ease of notation, from now onwards, we denote E F ,F by E when no confusion about the functions F and F determining the p-box can arise.

In principle, the problem of natural extension to all events is solved: simply calculate the inner measure as in Eq. ( 4), using Eq. ( 3) to calculate P H F ,F (C) for elements C in H. However, the inner measure still involves calculating a supremum. What we show next is that Eq. ( 3) can be extended to arbitrary events, by first taking the topological interior with respect to a very simple topology, followed by a (possibly infinite) sum over the so-called full components of this interior.

The Partition Topology

Consider the partition topology on Ω generated by τ := {[x] : x ∈ Ω}. The open sets in this topology are all unions of equivalence classes (or, subsets of Ω/ , if you like). Hence, every open set is also closed. In particular, every interval in (Ω, ) is clopen.

The topological interior of a set A is given by the union of all equivalence classes contained in A:

int(A) = {[x] : [x] ⊆ A} (5)
and the topological closure is given by the union of all equivalence classes which intersect with A:

cl(A) = {[x] : [x] ∩ A = ∅}. (6)
Lemma 5. For any subset A of Ω, E(A) = E(int(A)) and E(A) = E(cl(A)).

Additivity on Full Components

Next, we determine a constructive expression of the natural extension E on the clopen subsets of Ω.

Definition 6. [16, §4.4] A set S ⊆ Ω is called full if [a, b] ⊆ S for any a b in S.
What do these full sets look like?

Lemma 7. Every full set is clopen.

Under an additional completeness assumption, the full sets are precisely the intervals.

Lemma 8. If Ω/ is order complete, that is, if every subset of Ω/ has a supremum (minimal upper bound) and infimum (maximal lower bound), then every full set is an interval, that is, it can be written as [x, y], [x, y), (x, y], or (x, y), for some x, y in Ω.

Note that Ω/ can be made order complete via the Dedekind completion [16, §4.34]. We can prove that the natural extension E is additive on full components. Recall that the sum of a family (x λ ) λ∈Λ of non-negative real numbers is defined as

λ∈Λ x λ = sup L⊆Λ L finite λ∈L x λ
If the above sum is a finite number, at most countably many of the x λ 's are non-zero [16, 10.40].

Theorem 11. Let B be a clopen subset of Ω. Let (B λ ) λ∈Λ be the full components of B, and let (C λ ) λ∈Λ be the components of B c . Then

E(B) = λ∈Λ E(B λ ) and E(B) = 1 - λ∈Λ E(C λ )
In other words, the natural extension E of a p-box is arbitrarily additive on full components (but obviously not additive on arbitrary events). Interestingly, additivity on full components is not sufficient for a lower probability to be equivalent to a p-box.

Practical computations over events

Let us explain how Proposition 4 can be generalized to all events (at least when Ω/ is order complete).

Consider an arbitrary event A. By Lemma 5, it suffices to find the natural extension of int(A) or cl(A).

Calculating the interior or closure with respect to the partition topology will usually be trivial (see examples further on). Because the topological interior or closure of a set is always clopen, we only need to know the natural extension of clopen sets. Now, by Theorem 11, we only need to calculate the natural extension of the (clopen) full components (B λ ) λ∈Λ of int(A) or the (clopen) full components (C λ ) λ∈Λ of cl(A) c = int(A c ). Finding the full components will often be a trivial operation. By Lemma 8, if Ω/ is order complete, then each full component is an interval. And for intervals, we immediately infer from Proposition 4 and Eq. ( 4) that (i.p. standing for immediate predecessor):

E((x, y]) = max{0, F (y) -F (x)} (7a) E((x, y)) = max{0, F (y-) -F (x)} (7b) E([x, y]) = max{0, F (y) -F (x)} if x has no i.p. max{0, F (y) -F (x-)} if x has an i.p. (7c) E([x, y)) = max{0, F (y-) -F (x)} if x has no i.p. max{0, F (y-) -F (x-)} if x has an i.p. ( 7d
)
for any x ≺ y in Ω, 2 where F (y-) denotes sup z≺y F (z) and similarly for F (x-). The equalities hold because, if x ≺ y in Ω, and x-is an immediate predecessor of x, then [x, y] = (x-, y] and [x, y) = (x-, y). Recall also that F (0 Ω -) = F (0 Ω -) = 0 by convention. If Ω/ is finite, then one can think of z-as the immediate predecessor of z in Ω/ .

In other words, we have a simple constructive means of calculating the natural extension of any event.

Special Cases

The above equations hold for any (Ω, ) with order complete quotient space. In most cases in practice, either Ω/ is finite, or Ω/ is connected, meaning that for any two elements x ≺ y in Ω there is a z in Ω such that x ≺ z ≺ y,3 (this is the case for instance when Ω is a closed interval in R and is the usual ordering of reals). Moreover, if Ω/ is connected, then, in practice, F will satisfy F (y-) = F (y) for all y in Ω. For example, in case Ω is a closed interval in R, this happens precisely when F (0) = 0 and F is left-continuous in the usual sense.

If Ω/ is finite, then every element of Ω has an immediate predecessor (remember, we take the immediate predecessor of 0 Ω to be 0 Ω -), and if Ω/ is connected, then no element except 0 Ω has an immediate predecessor. So:

Corollary 12. If Ω/
is finite, then every full set B ⊆ Ω is of the form [a, b] and for every event A ⊆ Ω,

E(A) = λ∈Λ max{0, F (b λ ) -F (a λ -)} E(A) = 1 - λ∈Λ max{0, F (b λ ) -F (a λ -)}
where ([a λ , b λ ]) λ∈Λ are the full components of int(A), and

([a λ , b λ ]) λ∈Λ are the full components of int(A c ) = cl(A) c . Corollary 13. If Ω/
is order complete and connected, and F (y-) = F (y) for all y in Ω, then

E(A) = λ∈Λ max{0, F (sup B λ ) -F (inf B λ )} E(A) = 1 - λ∈Λ max{0, F (sup C λ ) -F (inf C λ )}
where (B λ ) λ∈Λ are the full components of int(A) and

(C λ ) λ∈Λ are the full components of int(A c ) = cl(A) c .
Beware of F (0 Ω ) = F (0 Ω -) = 0 in the last corollary.

Example

Let's investigate a particular type of p-boxes on the unit square [0, 1] 2 . First, we must specify a preorder on Ω. A natural yet naive way of doing so is, for instance, saying that (x 1 , y 1 ) (x 2 , y 2 ) whenever x 1 + y 1 ≤ x 2 + y 2 . Consider a p-box (F , F ) on ([0, 1] 2 , ). Since F is required to be non-decreasing with respect to , it follows that F (x, y) is constant on elements of [0, 1] 2 / , which means that F (x 1 , y 1 ) = F (x 2 , y 2 ) whenever x 1 + y 1 = x 2 + y 2 . Thus, we may think of F (x, y) as a function of a single variable z = x + y, and we write F (z). Similarly, we write F (z). So, our p-box specifies bounds on the probability of right-angled triangles (restricted to [0, 1] 2 ) whose hypothenuses are orthogonal to the diagonal:

F (z) ≤ p({(x, y) ∈ [0, 1] 2 : x + y ≤ z}) ≤ F (z) (8)
Observe that the p-box is given directly on the twodimensional product space, without the need to define marginal p-boxes for each dimension. The base τ for our partition topology is given by

τ = {{(x, y) ∈ [0, 1] 2 : x + y = z} : z ∈ [0, 2]} x + y ≤ 0.5 0.5 ≤ x + y ≤ 1.2 x + y ≥ 1.2 b d x + y ≤ min{b, d} a c x + y ≥ 1 + max{a, c}
int([0, b]×[0, d]) ={(x, y) ∈ [0,1] 2 : x+y ≤ min{b, d}} int([a, 1]×[c, 1]) ={(x, y) ∈ [0,1] 2 : x+y ≥ 1+max{a, c}}
Consequently, E(A) = 0 for all rectangles A, except

E([0, b] × [0, d]) = F (min{b, d}) E([a, 1] × [c, 1]) = 1 -F (1 + max{a, c})
Fig. 1 illustrates the situation. So, for the purpose of making inferences about the lower probability of events that are rectangles, the ordering was obviously poorly chosen. In general, one should choose in a way that Ω/ contains good approximations for all events of interest.

For example, a strategy would be to start from a reference point (e.g., an elicited modal value) and then to choose the ordering such that intervals correspond to concentric regions of interests around the reference point. Again, all of this is possible because our theory concerns p-boxes on arbitrary totally preordered spaces, and is not limited to the real line with its natural ordering. More realistic examples in which such concentric regions are used are given in Section 8.

Natural Extension to All Gambles

Next, we establish that the natural extension of pboxes to all gambles can be expressed as a Choquet integral. We further simplify the calculation of this Choquet integral via the lower and upper oscillation of gambles with respect to the partition topology introduced earlier.

Choquet Integral Representation

Extending previous results [START_REF] Destercke | Unifying practical uncertainty representations: I. Generalized p-boxes[END_REF] where the relation between p-boxes and complete monotonicity was established for finite spaces, we can show that the natural extension of p-boxes on totally pre-ordered spaces are completely monotone. Let P H F ,F denote the restriction of E F ,F to H, given by Proposition 4: Theorem 14. P H F ,F is completely monotone.

This allows us to characterise the natural extension on all gambles: Theorem 15. The natural extension E of P F ,F is given by the Choquet integral

E(f ) = inf f + sup f inf f E({f ≥ t}) dt
for every gamble f . Moreover, E is completely monotone on all gambles. Similarly,

E(f ) = inf f + sup f inf f E({f ≥ t}) dt.

Lower and Upper Oscillation

By Lemma 5, to turn Theorem 15 in an effective algorithm, we must calculate int({f ≥ t}) for every t.

Fortunately, there is a very simple way to do this.

For any gamble f on Ω and any topological base τ , define its lower oscillation as the gamble

osc(f )(x) = sup C∈τ : x∈C inf y∈C f (y)
For the partition topology which we introduced earlier, this simplifies to

osc(f )(x) = inf y∈[x] f (y) (9)
The upper oscillation is:

osc(f )(x) = -osc(-f )(x) = sup y∈[x] f (y) (10)
For a subset A of Ω, the lower oscillation of I A is I int(A) , so the lower oscillation is the natural generalisation of the topological interior to gambles. Similarly, the upper oscillation of I A is I cl(A) . Proposition 16. For any gamble f on Ω,

int({f ≥ t}) = {osc(f ) ≥ t} cl({f ≥ t}) = {osc(f ) ≥ t} so, in particular, E(f ) = inf osc(f ) + sup osc(f ) inf osc(f ) E({osc(f ) ≥ t}) dt E(f ) = inf osc(f ) + sup osc(f ) inf osc(f ) E({osc(f ) ≥ t}) dt
Concluding, to calculate the natural extension of any gamble, in practice, we must simply determine the full components of the cut sets of its lower or upper oscillation, and calculate a simple Riemann integral of a monotonic function.

Examples will be given in Section 8.

P-Boxes Whose Preorders are Induced by a Real-Valued Function

In practice, a convenient way to specify a preorder on Ω such that Ω/ is order complete and connected is by means of a bounded real-valued function Z : Ω → R. For instance, in the example in Section 4.7, we used Z(x, y) = x + y. Also see [START_REF] Ben-Haim | Info-gap decision theory: decisions under severe uncertainty[END_REF][START_REF] Fuchs | Potential based clouds in robust design optimization[END_REF]. Let us assume from now onwards that Z is a surjective mapping from Ω to [0, 1].

For any x and y in Ω, define x y whenever Z(x) ≤ Z(y). Because Z is surjective, Ω/ is order complete and connected. In particular, Ω has a smallest and largest element, for which Z(0 Ω ) = 0 and Z( 1 The topological interior and closure can be related to the so-called lower and upper inverse of Z -1 . Indeed, consider the multi-valued mapping Γ := Z -1 : [0, 1] → ℘(Ω). Because for every x in Ω, it holds that [x] = Γ(Z(x)), it follows that, for any subset A of Ω, int(A) = Γ(Γ * (A)), and cl(A) = Γ(Γ * (A)), where Γ * and Γ * denote the lower and upper inverse of Γ respectively, that is [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF] Γ * (A) = {z ∈ [0, 1] : Γ(z) ⊆ A}, and

Γ * (A) = {z ∈ [0, 1] : Γ(z) ∩ A = ∅}.
Theorem 17. Let A be any subset of Ω. Then

E(A) = λ∈Λ E(I λ ) E(A) = 1 - λ∈Λ E(J λ )
where (I λ ) λ∈Λ are the full components of Z(int(A)) = Γ * (A) and (J λ ) λ∈Λ are the full components of

Z(int(A c )) = Z(cl(A) c ) = Γ * (A c ) = (Γ * (A)) c .
If, in addition, F is left-continuous as a function of z ∈ [0, 1] and F (0) = 0, then

E(A) = λ∈Λ max{0, F (sup I λ ) -F (inf I λ )} E(A) = 1 - λ∈Λ max{0, F (sup J λ ) -F (inf J λ )}
For gambles, the lower oscillation is constant on equivalence classes. So, we may also consider osc(f ) and osc(f ) in Proposition 16 as functions of z ∈ [0, 1].

Constructing Multivariate P-Boxes from Marginals

Next, we construct a multivariate p-box from marginal lower previsions under arbitrary rules of combination. We then focus on two special joint models: the first without any assumptions about dependence between variables (using the Fréchet-Hoeffding bounds [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF]), and the second assuming epistemic independence between all variables (using the factorization property [START_REF] De Cooman | Independent natural extension[END_REF]). Finally, we derive Williamson and Downs's [START_REF] Williamson | Probabilistic arithmetic I: Numerical methods for calculating convolutions and dependency bounds[END_REF] probabilistic arithmetic as a special case of our framework.

Specifically, consider n variables X 1 , . . . , X n assuming values in X 1 , . . . , X n , and marginal lower previsions P 1 , . . . , P n for each variable. Each P i is a coherent lower prevision on L(X i ).

Multivariate P-Boxes

First, we must define a mapping Z to induce a preorder on Ω = X 1 × • • • × X n . The following choice works perfectly for our purpose:

Z(x 1 , . . . , x n ) = n max i=1 Z i (x i )
where each Z i is a surjective mapping from X i to [0, 1] and hence, also induces a marginal preorder i on X i . Each P i can be approximated by a p-box (F i , F i ) on (X i , i ), defined by

F i (z) = P i (Z -1 i ([0, z])) F i (z) = P i (Z -1 i ([0, z]))
This approximation is the best possible one, by Theorem 2.

Beware that even though different choices of Z i may induce the same total preorder i , they might lead to a different total preorder induced by Z. Roughly speaking, the Z i specify how the marginals scale relative to one another. This means that our choice of Z i affects the precision of our inferences: a good choice will ensure that any event of interest can be well approximated by elements of Ω/ . Of course, nothing prevents us, at least in theory, to consider the set of all Z i which induce some given marginal total preorders i , and whence to work with a set of p-boxes. In Section 7.4, we will see an example where this approach is feasible. Anyway, with this choice of Z, we can easily find the p-box which represents the joint as accurately as possible, under any rule of combination of coherent lower previsions:

Theorem 18. Consider any rule of combination of coherent lower and upper previsions, mapping the marginals P 1 , . . . , P n to a joint coherent lower prevision n i=1 P i on all gambles. Suppose there are functions and u for which:

n i=1 P i n i=1 A i = (P 1 (A 1 ), . . . , P n (A n )) and n i=1 P i n i=1 A i = u(P 1 (A 1 ), . . . , P n (A n )), for all A 1 ⊆ X 1 , . . . , A n ⊆ X n . Then, the couple (F , F ) defined by F (z) = (F 1 (z), ..., F n (z)); F (z) = u(F 1 (z), ..., F n (z))
is the least conservative p-box on (Ω, ) whose natural extension E F ,F is dominated by the combination n i=1 P i of P 1 , . . . , P n .

Natural Extension: The Fréchet Case

The natural extension n i=1 P i of P 1 , . . . , P n is the lower envelope of all joint distributions whose marginal distributions are compatible with the given marginal lower previsions. So, the model is completely vacuous about the dependence structure. We refer to for instance [4, p. 120, §3.1] for a rigorous definition. In this paper, we only need to use the Fréchet bounds (see [21, p. 131]), in which case the functions and u of Theorem 18 are respectively the Lukasiewicz and the minimum t-norms.

Theorem 19. The p-box (F , F ) defined by

F (z) = max 0, 1 -n + n i=1 F i (z) F (z) = n min i=1 F i (z)
is the least conservative p-box on (Ω, ) whose natural extension E F ,F is dominated by the natural extension n i=1 P i of P 1 , . . . , P n .

It is easily seen that the joint lower prevision n i=1 P i is in general not completely monotone, hence the joint p-box of Theorem 19 is in general only an outer approximation.

Independent Natural Extension

In contrast, the independent natural extension ⊗ n i=1 P i of P 1 , . . . , P n models epistemic independence between X 1 , . . . , X n . We refer to [START_REF] De Cooman | Independent natural extension[END_REF] for a rigorous definition and properties. In this paper we only need the factorization property, which implies that the functions and u of Theorem 18 are the product rule.

Theorem 20. The p-box (F , F ) defined by

F (z) = n i=1 F i (z) F (z) = n i=1 F i (z)
is the least conservative p-box on (Ω, ) whose natural extension E F ,F is dominated by the indepedent natural extension ⊗ n i=1 P i of P 1 , . . . , P n .

Again, the joint p-box will only be an outer approximation of the actual joint lower prevision.

Special Case: Probabilistic Arithmetic

Let Y = X 1 + X 2 with X 1 and X 2 real-valued random variables. Probabilistic arithmetic [START_REF] Williamson | Probabilistic Arithmetic[END_REF] estimates

P Y ([-∞, y]) = F Y (y) and P Y ([-∞, y]) = F Y (y)
for any y ∈ R under the assumptions that the uncertainty on X 1 and X 2 is given by p-boxes (F 1 , F 1 ) and (F 2 , F 2 ), with 1 and 2 the natural ordering of real numbers, and the dependence structure is completely unknown. Williamson and Downs [START_REF] Williamson | Probabilistic arithmetic I: Numerical methods for calculating convolutions and dependency bounds[END_REF] provide explicit formulae for common arithmetic operations, making inferences from marginal p-boxes very easy.

Let us show, for the particular case of addition, that their results are captured by our joint p-box proposed in Theorem 19. Cases of other arithmetic operators, not treated here to save space, follow from almost identical reasoning. The lower cumulative distribution function F X1+X2 (y) resulting from probabilistic arithmetic is, for any y ∈ R,

sup x1,x2 : x1+x2=y max{0, F 1 (x 1 ) + F 2 (x 2 ) -1}. ( 11
)
Without much loss of generality, assume that both X 1 and X 2 lie in a bounded interval [a, b].

Let Z 1 and Z 2 be any surjective maps [a, b] → [0, 1] which induce the usual ordering on [0, 1] (so both must be continuous and strictly increasing).

To apply Theorem 19, consider the total preorder on Ω = [a, b] 2 induced by Z(x 1 , x 2 ) = max{Z 1 (x 1 ), Z 2 (x 2 )}. Figure 2 illustrates the event 4 {X 1 +X 2 ≤ y}, with y ∈ [2a, 2b], as well as the largest interval Z -1 ([0, z]) included in it. For z such that

4 {X 1 + X 2 ≤ y} is {(x 1 , x 2 ) ∈ [0, 1] 2 : x 1 + x 2 ≤ y}. y y Z -1 2 (z) Z -1 1 (z) {X 1 + X 2 ≤ y} Z -1 ([0, z])
Figure 2: The event {X 1 + X 2 ≤ y}, and the largest interval Z -1 ([0, z]) included in it.

Z -1 1 (z) + Z -1 2 (z) = y, we achieve the largest inter- val Z -1 ([0, z]) which is still included in {X 1 + X 2 ≤ y}.
There is always a unique such z because also

Z -1 1 + Z -1 2
is continuous and strictly increasing.

Using Theorems 19 and 17, we find that

E F ,F ({X 1 + X 2 ≤ y}) = F (Z -1 (z)) = max{0, F 1 (Z -1 1 (z)) + F 2 (Z -1 2 (z)) -1}
But, this holds for every valid choice of Z 1 and Z 2 , whence P 1 P 2 ({X 1 + X 2 ≤ y}) dominates Eq. ( 11).

Example

Next, we investigate an example in which p-boxes are used to model uncertainty around some parameters.

We aim to estimate the minimal required dike height h along a stretch of river, using a model proposed in [START_REF] De Rocquigny | Uncertainty in Industrial Practice: A guide to Quantitative Uncertainty Management, chapter 10. Partial Safety Factors to Deal with Uncertainties in Slope Stability of River Dykes[END_REF]. Although this model is quite simple, it provides a realistic industrial application. Skipping technical details, the model results in the following relationship:

h(q, k, u, d) =      q k √ u-d b 3 5 if q ≥ 0 0 otherwise, (12)
with b and the river width and length, q the river flow rate, k the Strickler coefficient and u, d respectively the upriver and downriver water levels.

For this case study, the river width is b = 300m and the length is = 6400m. The remaining parameters are uncertain. Expert assessment leads to the following distributions.

The river flow rate q has a Gumbel distribution with location and scale parameters µ = 1335m 3 s -1 and β = 716m 3 s -1 . To simplify calculations, we introduce a variable r satisfying q = µ -β ln(-ln(r)). If r is uniform over [0, 1], then q is Gumbel with parameters µ and β. So, after transformation, ((1 ± z)/2, 30 ± 15z, 55 ± z, 50 ± z).

h(r, k, u, d) =      µ-β ln(-ln(r)) k √ u-d b 3 5 if q ≥ 0 0 otherwise. p(k ∈ [30 -15z, 30 + 15z]) k 30 p(k)
The marginal p-boxes are, for r:

F 1 (z) = F 1 (z) = p(2|r -1/2| ≤ z) = z because r is uniformly distributed over [0, 1]. For k: F 2 (z) = F 2 (z) = p(|k -30|/15 ≤ z) = 1 -(1 -z) 2
(see Fig. 3). Similarly, for u and d, it is easily verified that

F 3 (z) = F 3 (z) = F 4 (z) = F 4 (z) = 1 -(1 -z) 2 .
Next, osc(h) and osc(h) are: 1 -F (o -1 (t)) dt = 6.423 Therefore, we should consider average overflowing heights of at least 6.5m. For comparison, using traditional methods and assuming independence between all variables, h has expectation 3.2m, which lies between our lower and upper expectation, as expected. Note that the imprecision has two sources: we have reduced a multivariate problem to a univariate one and we have not made any assumption of independence.

Calculations were relatively simple due to the monotonicity of the target function with respect to the uncertain variables. This may not be the case in general.

Conclusions

We studied inferences (lower and upper expectations) from p-boxes on arbitrary totally preordered spaces. For this purpose, we represented p-boxes as coherent lower previsions, and studied their natural extension. Defining p-boxes on totally pre-ordered spaces allowed us to unify p-boxes on finite spaces and on real intervals, and to extend the theory to the multivariate case.

One interesting result is a practical means of calculating the natural extension of a p-box in this general setting: we proved that it suffices to calculate the full components of the cut sets of the lower oscillation, followed by a simple Riemann integral (Proposition 16).

As examples of how this model can be used in practice, we have detailed the cases of p-boxes whose preorders are induced by a real-valued mapping, and of joint p-boxes built from marginals under various combination rules. We demonstrated our methodology on inference about a river dike assessment, showing that calculations are generally straightforward.

Of course, many open problems regarding p-boxes remain. For instance, can the dependency model inform the choice of preorder, to arrive at tighter bounds? Our choice led to simple expressions, but other choices giving more precise inference could be investigated. Also, the connection of p-boxes with other uncertainty models, such as possibility measures and clouds, deserves further investigation.

Definition 9 .

 9 [16, §4.4] Given a clopen set A ⊆ Ω and an element x of A, the full component C(x, A) of x in A is the largest full set S which satisfies x ∈ S ⊆ A.Lemma 10. The full components of any clopen setA form a partition of A.

Figure 1 :

 1 Figure 1: Shape of intervals induced by , and calculation of the topological interior.

  Ω ) = 1. Moreover, we can think of any cumulative distribution function on (Ω, ) as a function over a single variable z ∈ [0, 1]. Consequently, we can think of any p-box on (Ω, ) as a p-box on ([0, 1], ≤). In particular, for any subset I of [0, 1] we write E(I) for E(Z -1 (I)). For example, for a, b in [0, 1], and A = Z -1 ((a, b]) ⊆ Ω, we have that E(A) = E((a, b]) = max{0, F (a) -F (b)} by Proposition 4. Similar expressions for other types of intervals follow from Eq. (7).

15 45 Figure 3 :

 15453 Figure 3: Derivation of the p-box for a triangular distribution.

F

  osc(h)(z) = inf (r,k,u,d) : Z(r,k,u,d)=z h(r, k, u, d) = o(-z) osc(h)(z) = sup (r,k,u,d) : Z(r,k,u,d)=z h(r, u, d) = o(z) with o(z) =      µ-β ln(-ln((1+z)/2)) (30-15z) function o(z) is increasing, with o(-1) = 0, o(0) = 3.032, and o(1) = +∞.Hence, osc(h)(z) and osc(h)(z) are decreasing and increasing in z, respectively. So, the full components of the eventsL t = {z ∈ [0, 1] : osc(h)(z) ≥ t} = {z ∈ [0, 1] : o(-z) ≥ t} U t = {z ∈ [0, 1] : osc(h)(z) ≥ t} = {z ∈ [0, 1] : o(z) ≥ t} are of the form L t = [0, t ] and U t = [u t , 1], with t = -o -1 (t) for t ≤ o(0) u t = o -1 (t) for t ≥ o(0)With unknown dependence, using Theorem 19,F (z) = max{0, -3 + z + 3(1 -(1 -z) (-o -1 (t)) dt = 1.515 E(h) = o(0) + +∞ o(0)

We still require the preorder to be total. P-boxes for partially preordered spaces might be interesting, but are not considered in this paper.

In case x = 0 Ω , evidently, 0 Ω -is the i.p.

This terminology stems from the fact that, in this case, Ω/ is connected with respect to the order topology [16, §15.46[START_REF] De Rocquigny | Uncertainty in Industrial Practice: A guide to Quantitative Uncertainty Management, chapter 10. Partial Safety Factors to Deal with Uncertainties in Slope Stability of River Dykes[END_REF]].

Acknowledgements

We are particularly grateful to Enrique Miranda for the many very fruitful discussions, extremely useful suggestions, and various contributions to this paper. We also thank Gert de Cooman and Didier Dubois for their help with a very early draft of this paper.