CS 141 Introduction to AI Greenwald

TBA

5:00 PM, Apr 6, 2009

Homework 6: Probability and Utility Theory

Due:

Contents

    1  Almanac Game

    2  Conditional Expectation

    3  Practical Probability Proofs

    4  St. Petersburg Paradox

    5  Almanac Game Answers
        5.1  Part 1
        5.2  Part 2

Objectives

By the end of this homework, you will understand:

  1. conditional expectation

  2. the St. Peterburg’s Paradox

By the end of this homework, you will be able to:

  1. prove simple properties about probabilities

  2. answer trivia questions more precisely than before

Practice

1  Almanac Game

[Adapted from Russell and Norvig (2003)] This exercise concerns the Almanac Game, which is used by decision analysts to calibrate numeric estimations. For each of the questions that follow, give your best guess of the answer, that is, a number that you think is as likely to be too high as it is to be too low. Also give your guess at the 25th percentile estimate, that is, a number that you think has a 25% chance of being too high, and a 75% chance of being too low. Do the same for the 75th percentile. Thus, you should give three estimates in all—low, median, and high—for each question.

  1. What percentage of U.S. households own at least one pet cat?

  2. How many stocks comprise the Dow Jones Industrial Average?

  3. In feet and inches, how tall is Tom Cruise?

  4. In what year did Microsoft launch its first computer operating system?

  5. On average, how many minutes does it take for light to travel from the sun to the Earth?

  6. How many times could the land area of Japan fit into the land area of the U.S.?

  7. Pablo Picasso’s Boy With a Pipe is the most expensive painting ever sold at auction. What was the dollar price paid for this painting?

  8. Of the 538 electoral votes possible, how many did Ronald Reagan receive in the 1984 presidential election?

  9. How many people auditioned for Season 2 of the TV show American Idol?

  10. Reggie Jackson struck out more times than any other Major League Baseball hitter. What percentage of the time did he strike out?

The correct answers appear at the end of the assignment. From the point of view of decision analysis, the interesting thing is not how close your median guesses came to the real answers, but rather how often the real answer came within your 25% and 75% bounds. If it was about half the time, then your bounds are accurate. But if you’re like most people, you will be more sure of yourself than you should be, and fewer than half the answers will fall within the bounds. With practice, you can calibrate yourself to give realistic bounds, and thus be more useful in supplying information for decision making. Try this second set of questions and see if there is any improvement:

  1. In feet, how tall was the tallest giraffe ever recorded?

  2. In what year did MTV play its first music video?

  3. How many siblings does Michael Jackson have?

  4. How many bones are in the adult human body?

  5. How many points did Michael Jordan average per game?

  6. How many miles long is the Mississippi River?

  7. In what year were women in the U.S. granted the right to vote?

  8. How many times larger in volume is the sun than the Earth?

  9. In what year was the comic strip Peanuts first published?

  10. What percentage of U.S. presidents have been elected to at least two terms in office?

2  Conditional Expectation

Let X and Y be discrete random variables with ranges \mathcal{X} and \mathcal{Y}, respectively. The conditional expectation of Y given X is a function of \mathcal{X}, defined as follows:

\E [ Y \mid X=x ] = \sum_{y \in \mathcal{Y}} x \, P [ Y=y \mid X=x ] = \sum_{y \in \mathcal{Y}} x \left( \frac{P[X=x, Y=y]}{P[X=x]} \right)

#1 Suppose a ball is chosen from an urn that contains 11 balls numbered 0 to 10. Assume all balls in the urn are equally likely to be chosen. What is the probability mass function of the random variable X whose range is the possible values of the ball?

#2 After the first ball is chosen, a second ball is chosen from an urn containing x balls numbered 0 to x. As above, assume all balls in this urn also also equally likely to be chosen. What is the conditional probability mass function of the random variable Y whose range is the possible values of the second ball? And what is the joint probability mass function of X and Y?

#3 What is the conditional expectation of Y given X?

Problems

3  Practical Probability Proofs

Prove the following properties of events A and B and probability function P.

(a) If P(B) = 1, then P(A|B) = P(A).

(b) If A ⊆ B, then P(B|A) = 1 and P(A|B) = P(A)/P(B).

(c) Assume P(A), P(B) > 0. If A and B are independent, then they cannot be disjoint, and if A and B are disjoint, then they cannot be independent.

4  St. Petersburg Paradox

[Adapted from Russell and Norvig (2003).] In 1738, Daniel Bernoulli1 published a problem in the Commentaries of the Imperial Academy of Science of Saint Petersburg, which later became known as the St. Petersburg paradox.

The problem is to determine the price you are willing to pay to play the following game of chance:

The pot contains $1 at the start. To play, you toss a fair coin repeatedly. Play continues until the coin lands on heads, at which point the game ends. After the first toss, the pot is doubled; after the second toss, it is doubled again; and so on. You win the contents of the pot at the time the game ends. That is, if the coin lands on heads (for the first time) after the nth toss, you win $2n.

  1. What is the expected monetary value of this game? Explain why this is paradoxical.

Here is Bernoulli’s intuition for how to resolve this paradox:

The determination of the value of an item must not be based on its price, but rather on the utility it yields. There is no doubt that a gain of one thousand ducats is more significant to the pauper than to a rich man though both gain the same amount.

In other words Bernoulli suggested that the utility of money is concave (i.e., money, like other goods and services, has diminishing returns).2 For example, an agent’s utility for money could be measured on a logarithmic scale: U(k) = a \log_2 k + b, where $k is the agent’s wealth.

  1. What is the expected utility of the game under this assumption?

  2. What is the maximum amount that it would be rational for an agent to pay to play the game, assuming the agent’s initial wealth is $k?

5  Almanac Game Answers

5.1  Part 1

  1. 31.6

  2. 30

  3. 5 feet, 7 inches

  4. 1981

  5. 8.5

  6. 24.45

  7. 104,200,000

  8. 525

  9. 50,000

  10. 26.33

5.2  Part 2

  1. 20

  2. 1981

  3. 8

  4. 206

  5. 30.12

  6. 2,302.18

  7. 1920

  8. 1,304,000

  9. 1950

  10. 35.71

1 not to be confused with Jacob, his uncle.

2 This is an application of the Prussian economist Gossen’s (1810-1858) Law of Diminishing Marginal Returns: The amount of any pleasure is steadily decreasing as we continue until at last saturation is reached.

Last modified: Saturday, April 4th, 2009 3:16:57pm