Exercises


  • 6.1 Show that a binary relation is reflexive, symmetric, and transitive if and only if it is reflexive, Euclidean, and transitive.

  • 6.2 Show that is reflexive iff w (w) for all worlds w; is transitive iff, for all worlds w and w, if w (w) then (w) (w); and is Euclidean iff, for all worlds w, w, if w (w), then (w) (w).

  • 6.3 Given the definition of W, 1, and 2, show that the only way the frame F described just before Example 6.2.2 can be consistent with CP is if 1(w1) = 2(w1) = 2(w1) = 2(w2).

  • 6.4 Show that the frame F in Example 6.2.2 does not satisfy CP. (This is not quite as easy as it seems. It is necessary to deal with the case that some sets have measure 0.)

  • 6.5 Show that the construction of probability assignments given in Section 6.4 satisfies CONS and SDP. Moreover, show that CP holds if the agents have a common prior on runs.

  • 6.6 Prove Proposition 6.4.2.

  • 6.7 Show that the analogue of Proposition 6.4.2 does not hold in general in systems where agents do not have perfect recall.

  • 6.8 Prove Proposition 6.4.3.

  • 6.9 This exercise takes a closer look at time-m events and m-prefixes.

    1. Show that every time-m event in a system is the disjoint union of m-prefixes.

    2. Show that if m < m, then an m -prefix is a union of m-prefixes.

    3. Show that if m < m, then the union of a time-m event and a time-m event is a time-m event.

    4. Show that pref is an algebra; that is, it is closed under union and complementation.

  • 6.10 Complete the proof of Proposition 6.5.2 by showing that the probability measure μ defined in the proof is in fact Markovian and is the unique probability measure on pref such that μ(Gn + 1 = g | Gn = g) = τ(g, g) and μ([g0]) = μ0([g0]).

  • 6.11 For the systems constructed in Section 6.7.1, show that

    1. 11, 13, 21, and 23 are synchronous, while 21 and 22 are not;

    2. the Teller has perfect recall in all six systems; and

    3. the Listener has perfect recall in 11 and 21 but not in the other four systems.

  • 6.12 Show that in the system 11 constructed in Section 6.7.1, if r is a run in which the Listener is told "not w" in the mth round, then the set of worlds he considers possible consists of all the worlds he considered possible at time m 1, other than w. Moreover, the Listener considers each of these worlds equally likely.

  • *6.13 Prove Theorem 6.8.1.

  • 6.14 Describe a simple system that captures Example 3.1.2, where Alice is about to look for a book in a room where the light may or may not be on. Explain in terms of Theorem 6.8.1 under what conditions conditioning is appropriate.

  • 6.15 Consider Alice's first protocol for the second-ace puzzle, where in the second round, she tells Bob whether or not she has the ace of spades.

    1. Specify the resulting system formally.

    2. Show that in the runs of this system where Alice has the ace of spades, at time 2, Bob knows that the probability that Alice has both aces is 1/3.

  • 6.16 Consider Alice's second protocol for the second-ace puzzle, where in the second round, she tells Bob which ace she has. Suppose that if she has both aces, she says that she has the ace of spades with probability α.

    1. Specify the resulting system formally.

    2. Show that in the runs of this system where Alice has the ace of spades, at time 2, Bob knows that the probability that Alice has both aces is α/(α + 2).

  • 6.17 Consider the Monty Hall puzzle, under the assumption that Monty must open a door in the second round. Suppose that the probability of his opening door j, if you choose door i and it has a car behind it, is αij.

    1. Specify the resulting system formally (under the assumption that you know the probabilities αij ).

    2. Show that in this system, the probability of gaining by switching is 1/(αij + 1).

  • 6.18 Analyze the three-prisoners puzzle from Example 3.3.1 under the assumption that the probability that the jailer says b given that a lives is α. That is, describe the jailer's protocol carefully, construct the set of runs in the system, and compute the probability that a lives given that the jailer actually says b. Explain in terms of Theorem 6.8.1 when conditioning gives the correct answer and why it gives the incorrect answer in general.

  • 6.19 Show that in F3, Bob knows that the probability of U is either 0 or 1, but he does not know which.

  • 6.20 Show that in F5, Bob knows that the probability of heads is either 0 or 1, but he does not know which.

  • 6.21 This exercise refers to the second system constructed in Example 6.9.5.

    1. Show that there are 221 strategies possible for Charlie. (Hint: Recall that a strategy is a function from what Charlie observes, regarding who tosses a coin and the outcome of his or her coin tosses, to actions (in this case, the decision as to who goes next). Show that there are 21 different sequences of observations that describe what Charlie has seen just before he must move. Since there are two possible actions he can take, this gives the desired result.)

    2. Show that these strategies can be partitioned into 26 sets of 215 strategies each, where each of the strategy in a given set leads to precisely the same outcomes (who tossed the coin at each step and how the coin lands). Note that each of these sets corresponds to one run in the original representation.

    3. Describe the probability on the set of runs corresponding to a fixed strategy for Charlie.




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