Exercises


2.1 Let be an algebra over W.

  1. Show by means of a counterexample that if W is infinite, sets in may not be the union of basic sets. (Hint: Let consist of all finite and cofinite subsets of W, where a set is cofinite if its complement is finite.)

  2. Show that if W is finite, then every set in is the union of basic sets. (That is, the basic sets in form a basis for if W is finite.)

2.2 This exercise examines countable additivity and the continuity properties (2.1) and (2.2). Suppose that is a σ-algebra.

  1. Show that if U1, U2, U3, is an increasing sequence of sets all in , then i=1Ui .

  2. Show that if U1, U2, U3, is a decreasing sequence of sets, then i=1Ui .

  3. Show that the following are equivalent in the presence of finite additivity:

    1. μ is countably additive,

    2. μ satisfies (2.1),

    3. μ satisfies (2.2).

2.3 Show that if consists of the finite and cofinite subsets of , and μ(U) = 0 if U is finite and 1 if U is cofinite, then is an algebra and μ is a finitely additive probability measure on .

2.4 Show by using P2 that if U V, then μ(U) μ(V).

* 2.5 Let αU = sup{β : (U, β) (U, 1 β)}. Show that (U, α) (U, 1 α) for all α < αU and (U, 1 α) (U, α) for all α > αU. Moreover, if U1 and U2 are disjoint sets, show that if the agent is rational, then αU1 + αU2 = αU1U2. More precisely, show that if αU1 + αU2 αU1U2, then there is a set of bets (on U1, U2, and U1 U2) that the agent should be willing to accept given her stated preferences, according to which she is guaranteed to lose money. Show exactly where RAT4 comes into play.

2.6 Suppose that (a) if (V, β) (U, α) for all α > α* then (V, β) (U, α*) and (b) if (U, α) (V, β) for all α < α* then (U, α*) (V, β). Show that it follows that the agent must be indifferent between (U, αU) and (U, 1 αU) (i.e., each is preferred to the other).

2.7 Show that if W is finite then μ*(U) = μ(V1), where V1 = {B : B U} and μ*(U) = μ(V2), where V2 = {B : U B}.

* 2.8 This exercise examines the proof of Theorem 2.3.3.

  1. Show that if , μ is defined on , and μ′ is an extension of μ defined on , then μ*(U) μ′(U) μ*(U) for all U .

  2. Given U - , let (U) be the smallest subalgebra of containing U and . Show that (U) consists of all sets of the form (V U) (V U) for V, V .

  3. Define μU on (U) by setting μU ((V U) (V U)) = μ*(V U) + μ* (V U). Show that μU is a probability measure on (U) that extends μ. Moreover, if μ is countably additive, then so is μU. Note that μU (U) = μ*(W U) + μ*(∅∩ U) = μ*(U).

  4. Show that a measure μ′U can be defined on (U) such that μ′U (U) = μ*(U). It follows from part (a) that, if μ φ, then μ* (U (μ)*(U) and (μ)*(U) μ*(U). It follows from part (c) that as long as the probability measure μU can be extended to , then μ*(U) = μ)*(U); similarly, part (d) shows that as long as μ′U can be extended to , then μ*(U) = *(U). Thus, Theorem 2.3.3 follows under the assumption that both μU and μ′U can be extended to . It easily follows from the construction of parts (b) and (c) that μU and μ′U can indeed be extended to if there exist finitely many sets, say U1, , Un, such that is the smallest algebra containing and U1, , Un. This is certainly the case if W is finite. Essentially the same argument works even if W is not finite. However, in general, the measure μ′ on is not countably additive, even if μ is countably additive. Indeed, in general, there may not be a countably additive measure μ′ on extending μ. (See the notes for further discussion and references.)

2.9 Show that inner and outer measures satisfy (2.3) and (2.4).

2.10 Prove the inclusion-exclusion rule (Equation (2.7)). (Hint: Use induction on n, the number of sets in the union.)

* 2.11 Show that if μ is a σ-additive probability measure on a σ-algebra , then there exists a function g: 2w such that g(U) U and μ(g(U)) = μ*(U), for all U . Moreover, for any finite subset of can be defined so that g(U U) = g(U) g(U) for all U, U . If W is finite, this result follows easily from Exercise 2.7. Indeed, that exercise shows that g(U) can be taken to be {B : U B}, so that g(U U) = g(U) g(U) for all U, U . If W is infinite, then g(U) is not necessarily {B : U B}. The problem is that the latter set may not even be in , even if is a σ-algebra; it may be a union over uncountably many sets. In the case that W is infinite, the assumptions that is a σ-algebra and μ is countably additive are necessary. (Your proof is probably incorrect if it does not use them!)

2.12 Prove Equation (2.8). (You may assume the results of Exercises 2.10 and 2.11.)

* 2.13 Show that (2.9) follows from (2.8), using the fact that μ*(U) = 1 μ*(U). (Hint: Recall that by the Binomial Theorem, Indeed, note that if f is an arbitrary function on sets that satisfies (2.8) and g(U) = 1 f(U), then g satisfies the analogue of (2.9).

2.14 Show that lower and upper probabilities satisfy (2.10) and (2.11), but show by means of a counterexample that they do not satisfy the analogues of (2.8) and (2.9) in general. (Hint: It suffices for the counterexample to consider four possible worlds and a set consisting of two probability measures; alternatively, there is a counterexample with three possible worlds and a set consisting of three probability measures.)

* 2.15 This exercise and the following one examine the properties that characterize upper and lower probabilities. This exercise focuses on (2.12).

  1. Show that upper and lower probabilities satisfy (2.12).

  2. Show that (2.12) does not follow from (2.10) and (2.11) by defining a set W and functions f and g associating with each subset of W a real number in [0, 1] such that (i) f() = 0, (ii) f(W) = 1, (iii) f(U) = 1 g(U), (iv) f(U V) f(U) + f(V) if U and V are disjoint, (v) g(U V) g(U) + g(V) if U and V are disjoint, but (vi) there exist disjoint sets U and V such that f(U) + g(V) > g(U V). Note that (iii) and (iv) say that f and g satisfy analogues of (2.10) and (2.11), while (vi) says that f and g do not satisfy the analogue of (2.12).

* 2.16 This exercise focuses on (2.13).

  1. Show that lower probabilities satisfy (2.13).

  2. Show that (2.10) and (2.12) follow from (2.13) and (2.11).

  3. Show that *() = 0 and *(W) 1 follow from (2.13).

It can be shown that (2.13) characterizes lower probability in that if g is an arbitrary real-valued function defined on subsets of W that satisfies the analogue of (2.13), that is, if μ={U1, , Uk} covers U exactly m + n times and covers U exactly m times, then ki=1 g(Ui) m + ng(U) and, in addition, g(W) 1, then g = * for some set of probability measures on W. (See the notes to this chapter for references.)

* 2.17 Show that the following property of upper probabilities follows from (2.11) and (2.13).

An almost identical argument shows that (2.13) follows from (2.11) and (2.18). This shows that it is possible to take either upper probabilities or lower probabilities as basic.

* 2.18 Suppose that is a σ-algebra and all the probability measures in are countably additive.

  1. Show that (2.14) holds.

  2. Show that the analogue of (2.1) holds for upper probability, while the analogue of (2.2) does not.

2.19 Show that (3)* = (4)* in Example 2.3.4.

2.20 Let W ={w, w} and define Bel({w}) = 1/2, Bel({w}) = 0, Bel(W) = 1, and Bel() = 0. Show that Bel is a belief function, but there is no probability μ on W such that Bel = μ*. (Hint: To show that Bel is a belief function, find a corresponding mass function.)

2.21 Construct two belief functions Bel1 and Bel2 on {1, 2, 3} such that Bel1(i) = Bel2(i) = 0 for i = 1, 2, 3 (so that Bel1 and Bel2 agree on singleton sets) but Bel1({1, 2}) Bel2({1, 2}). (Hint: Again, to show that the functions you construct are actually belief functions, find the corresponding mass functions.)

2.22 Show that Bel(U) Plaus(U) for all sets U.

* 2.23 Prove Theorem 2.4.1.

2.24 Construct a belief function Bel on W ={a, b, c} and a set Bel of probability measures such that Bel = * (and hence Plaus = *).

* 2.25 Prove Theorem 2.4.3. (Hint: Proving that Belm is a belief function requires proving B1, B2, and B3. B1 and B2 are obvious, given M1 and M2. For B3, proceed by induction on n, the number of sets in the union, using the fact that Belm(A1 An+1) = Belm((A1 An) An+1). To construct m given Bel, define m({w1, , wn}) by induction on n so that (2.17) holds. Note that the induction argument does not apply if W is infinite. Indeed, as observed in Exercise 2.26, the theorem does not hold in that case.)

* 2.26 Show that Theorem 2.4.3 does not hold in general if W is infinite. More precisely, show that there is a belief function Bel on an infinite set W such that there is no mass function m on W such that Bel(U) = {U:U′⊆U} m(U). (Hint: Define Bel(U) = 1if U is cofinite, i.e., U is finite, and Bel(U) = 0 otherwise.)

2.27 Show that if W is finite and μ is a probability measure on 2W, then the mass function mμ corresponding to μ gives positive mass only to singletons, and mμ(w) = μ(w). Conversely, if m is a mass function that gives positive mass only to singletons, then the belief function corresponding to m is in fact a probability measure. (This argument can be generalized so as to apply to probability measures defined only on some algebra , provided that belief functions defined only on are allowed. That is, if μ is a probability measure on , then it can be viewed as a belief function on . There is then a corresponding mass function defined only on that gives positive measure only to the basic sets in . Conversely, if m is a mass function on that gives positive mass only to the basic sets in , then Belm is a probability measure on .)

2.28 Suppose that m1 and m2 are mass functions, Bel1 and Bel2 are the corresponding belief functions, and there do not exist sets U1 and U2 such that U1 U2 ≠∅ and m1(U1)m2(U2)> 0. Show that there must then be sets V1, V2 such that Bel1(V1) = Bel2(V2) = 1 and V1 V2 =.

2.29 Show that the definition of in the Rule of Combination guarantees that m1 m2 is defined iff the renormalization constant c is positive and that, if m1 m2 is defined, then it is a mass function (i.e., it satisfies M1 and M2).

2.30 Show that is commutative and associative, and that mvac is the neutral element for .

2.31 Poss3 says that Poss(U V) = max(Poss(U), Poss(V)) for U, V disjoint. Show that Poss(U V) = max(Poss(U), Poss(V)) even if U and V are not disjoint. Similarly, if κ is a ranking function, show that κ(U V) = min(κ(U), κ(V)) even if U and V are not disjoint.

2.32 This exercise and the next investigate properties of possibility measures defined on infinite sets.

  1. Show that if Poss0 is defined as in Example 2.5.1, then it satisfies Poss1–3.

  2. Show that Poss0 does not satisfy Poss3.

  3. Show that if Poss1 is defined as in Example 2.5.2, then it satisfies Poss1, Poss2, and Poss3.

  4. Show that if Poss2 is defined as in Example 2.5.3, it satisfies Poss1, Poss2, and Poss3, but does not satisfy Poss3+.

  5. Show that if Poss3 is defined as in Example 2.5.3, then it satisfies Poss1, Poss2, and Poss3.

* 2.33 This exercise considers Poss3 and Poss3+ in more detail.

  1. Show that Poss3 and Poss3+ are equivalent if W is countable. (Note that the possibility measure Poss2 defined in Example 2.5.3 and considered in Exercise 2.32 shows that they are not equivalent in general; Poss2 satisfies Poss3, but not Poss3+.)

  2. Consider the following continuity property:

    Show that (2.19) together with Poss3 is equivalent to Poss3.

  3. Show that the following stronger continuity property together with Poss3 is equivalent to Poss3+:

* 2.34 Show that possibility measures satisfy (2.16) and hence are plausibility functions. (Hint: Show that

by induction on n.)

2.35 Show that Nec(U) Poss(U) for all sets U, using Poss1–3.

* 2.36 Prove Theorem 2.5.4. In addition, show that the argument that Plausm is a possibility measure works even if W is infinite.

* 2.37 Define Poss on [0, 1] by taking Poss(U) = sup U if U ≠∅, Poss() = 0. Show that Poss is a possibility measure and that Poss(αUα) = supα Poss(Uα), where {Uα} is an arbitrary collection of subsets of [0, 1]. However, show that there is no mass function m such that Poss = Plausm.

2.38 Show that max(μ(U), μ(V)) μ(U V) min(μ(U) + μ(V), 1). Moreover, show that these bounds are optimal, in that there is a probability measure μ and sets U1, V1, U2, and V2 such that μ(U1 V1) = max(U1, V1) and μ(U2 V2) = min(μ(U2) + μ(V2), 1).

2.39 Show that Possκ (as defined in Section 2.5) is a possibility measure.

2.40 Fix an infinitesimal and a nonstandard probability measure μ. Define κ(U) to be the smallest natural number k such that μ(U)> α k for some standard real α > 0. Show that κ is a ranking function (i.e., κ satisfies Rk1–3).

2.41 Show that if is a partial preorder, then the relation defined by w w if w w and w w is irreflexive, transitive, and antisymmetric.

2.42 Prove Theorem 2.7.1.

2.43 Prove Theorem 2.7.2. Moreover, show that if is a total preorder, then the assumption that is determined by singletons can be replaced by the assumption that the strict partial order determined by has the union property. That is, show that if is a total preorder on 2W that respects subsets and has the union property, such that the strict partial order determined by also has the union property, then there is a total preorder such that e=.

* 2.44 Show directly that e has the qualitative property if is total.

2.45 Show that U e V iff for all v V U, there exists u U such that u v.

2.46 Show that if U s V then U e V. Note that Example 2.7.3 shows that the converse does not hold in general. However, show that the converse does hold if is total. (Thus, for total preorders, s and e agree on finite sets.)

2.47 Show that if W is finite, and for all v V there exists u U such that u v, then for all v V there exists u U such that u v and u dominates V. Show, however, that if W is infinite, then even if is a total preorder, there can exist disjoint sets U and V such that for all v V, there exists u U such that u > v, yet there is no u U that dominates V.

* 2.48 Prove Theorem 2.7.5.

2.49 Show that if is a conservative qualitative relation and ▹′ is the strict partial order determined by , then and ▹′ agree on disjoint sets (i.e., if U and V are disjoint, the U V iff U ▹′ V.) Since s is a conservative qualitative relation, it follows that s and s agree on disjoint sets and hence that s is qualitative.

2.50 Complete the proof of Theorem 2.7.6.

2.51 Suppose that Poss is a possibility measure on W. Define a partial preorder on W such that w w if Poss(w) Poss(w).

  1. Show that U e V implies Poss(U) Poss(V).

  2. Show that Poss(U) > Poss(V) implies U e V.

  3. Show that the converses to parts (a) and (b) do not hold in general. (Hint: Consider the case where one of U or V is the empty set.)

  4. Show that if Poss(w) > 0 for all w W, then the converses to parts (a) and (b) do hold.

2.52 Show directly (without using Theorem 2.7.1) that Poss is qualitative; in fact, show that if Poss(U1 U2)> Poss(U3) and Poss(U1 U3)> Poss(U2), then Poss(U1)> Poss(U2 U3). (This is true even if U1, U2, and U3 are not pairwise disjoint.) An almost identical argument shows that ranking functions have the qualitative property.

2.53 State and prove an analogue of Exercise 2.51 for ranking functions.

2.54 Show that as defined on W/~ in Section 2.8 is well defined (i.e., if U, U [U] and V, V [V ] that U V iff U V .

2.55 Suppose that |W | 4. Show that there exists a set of probability measures on W and subsets U, V of W such that

  1. *(U) < *(V) and *(U) > *(V); and

  2. μ(U) < μ(V) for all μ but *(U) = *(V) and *(U) = *(V).

2.56 Show that there exist a set W, a belief function Bel on W, and pairwise disjoint subsets U1, U2, V1, V2 of W such that Bel(U1) = Bel(V1), Bel(U2) = Bel(V2), but Bel(U1 U2) Bel(V1 V2).

2.57 Consider the following property of plausibility measures:

  1. Show that Pl3 implies Pl3.

  2. Show that probability measures, possibility measures, and ranking functions satisfy Pl3.

  3. Show that probability measures satisfy the converse of Pl3 (if μ(U V) μ(U V), then μ(U) μ(U)), but possibility measures and ranking functions do not.

  4. Show by example that belief functions, and similarly lower probability measures and inner measures, do not satisfy Pl3 or its converse.




Reasoning About Uncertainty
Reasoning about Uncertainty
ISBN: 0262582597
EAN: 2147483647
Year: 2005
Pages: 140

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net