Extra Problems for Chapter 6

T.M. Cover and J.A. Thomas

1. Horse race. Consider a horse race with 4 horses. Assume that each of the horses pays 4-for-1 if it wins. Let the probabilities of winning of the horses be . If you started with $100 and betted optimally to maximize your long term growth rate, what are your optimal bets on each horse? Approximately how much money would you have after 20 races with this strategy ?
2. Lotto. The following analysis is a crude approximation to the games of Lotto conducted by various states. Assume that the player of the game is required pay $1 to play and is asked to choose 1 number from a range 1 to 8. At the end of every day, the state lottery commission picks a number uniformly over the same range. The jackpot, i.e., all the money collected that day, is split among all the people who chose the same number as the one chosen by the state. E.g., if 100 people played today, and 10 of them chose the number 2, and the drawing at the end of the day picked 2, then the $100 collected is split among the 10 people, i.e., each of persons who picked 2 will receive $10, and the others will receive nothing.

   The general population does not choose numbers uniformly - numbers like 3 and 7 are supposedly lucky and are more popular than 4 or 8. Assume that the fraction of people choosing the various numbers is , and assume that n people play every day. Also assume that n is very large, so that any single person's choice choice does not change the proportion of people betting on any number.

   1. What is the optimal strategy to divide your money among the various possible tickets so as to maximize your long term growth rate? (Ignore the fact that you cannot buy fractional tickets.)
   2. What is the optimal growth rate that you can achieve in this game?
   3. If , and you start with $1, how long will it be before you become a millionaire?
3. Horse race. Suppose one is interested in maximizing the doubling rate for a horse race. Let denote the win probabilities of the m horses. When do the odds yield a higher doubling rate than the odds ?
4. Horse race with probability estimates
   1. Three horses race. Their probabilities of winning are . The odds are (4-for-1, 3-for-1 and 3-for-1). Let be the optimal doubling rate.

      Suppose you believe the probabilities are . If you try to maximize the doubling rate, what doubling rate W will you achieve? By how much has your doubling rate decreased due to your poor estimate of the probabilities, i.e., what is ?

   2. Now let the horse race be among m horses, with probabilities and odds . If you believe the true probabilities to be , and try to maximize the doubling rate W, what is ?
5. The two envelope problem: One envelope contains b dollars, the other 2b dollars. The amount b is unknown. An envelope is selected at random. Let X be the amount observed in this envelope, and let Y be the amount in the other envelope.

   Adopt the strategy of switching to the other envelope with probability p(x), where . Let Z be the amount that the player receives. Thus

   

   

   1. Show that .
   2. Show that E(Y/X) = 5/4. Since the expected ratio of the amount in the other envelope to the one in hand is 5/4, it seems that one should alwyas switch. (This is the origin of the switching paradox.) However, observe that . Thus, although E(Y/X) > 1, it does not follow that E(Y) > E(X).
   3. Let J be the index of the envelope containing the maximum amount of money, and let J' be the index of the envelope chosen by the algorithm. Show that for any b, I(J; J') > 0. Thus the amount in the first envelope always contains some information about which envelope to choose.
   4. Show that E(Z) > E(X). Thus you can do better than always staying or always switching. In fact, this is true for any monotonic decreasing switching function p(x).
6. Gambling. Find the horse win probabilities
   1. maximizing the doubling rate for given fixed known odds .
   2. minimizing the doubling rate for given fixed odds .
7. Horse race. Suppose one is interested in maximizing the doubling rate for a horse race. Let denote the win probabilities of the m horses. When do the odds yield a higher doubling rate than the odds ?
8. Entropy of a fair horse race.
   Let , , denote the winner of a horse race. Suppose the odds o(x) are fair with respect to p(x), i.e., . Let b(x) be the amount bet on horse x, , . Then the resulting wealth factor is S(x)=b(x)o(x), with probability p(x).
   1. Find the expected wealth ES(X).
   2. Find , the optimal growth rate of wealth.
   3. Suppose

      

      If this side information is available before the bet, how much does it increase the growth rate ?

   4. Find I(X;Y).
9. Negative horse race Consider a horse race with m horses with win probabilities Here the gambler hopes a given horse will lose. He places bets , on the horses, loses his bet if horse i wins, and retains the rest of his bets. (No odds.) Thus , with probability and one wishes to maximize subject to the constraint
   1. Find the growth rate optimal investment strategy . Do not constrain the bets to be positive, but do constrain the bets to sum to 1. (This effectively allows short selling and margin.)
   2. What is the optimal growth rate?

Latex file

Postscript file