# WUSTL ESE 523 - ESE523Lect9-2013 (17 pages)

Previewing pages*1, 2, 3, 4, 5, 6*of 17 page document

**View the full content.**## ESE523Lect9-2013

Previewing pages
*1, 2, 3, 4, 5, 6*
of
actual document.

**View the full content.**View Full Document

## ESE523Lect9-2013

0 0 68 views

- Pages:
- 17
- School:
- Washington University in St. Louis
- Course:
- Ese 523 - Information Theory

**Unformatted text preview:**

ESE 523 Information Theory Lectures 9 10 Joseph A O Sullivan Samuel C Sachs Professor Electrical and Systems Engineering Washington University 2120E Green Hall 211 Urbauer Hall 314 935 4173 jao wustl edu 9 25 13 J A O Sullivan ESE 523 Lectures 9 10 1 Chapter 6 Gambling and Data Compression Basis for analytical approach to gambling Basis for investment strategies Dual view of data compression gave the best estimates of the entropy of English up to about ten years ago 2 9 25 13 J A O Sullivan ESE 523 Lectures 9 10 Roulette in the Language of Horse Races Kelly Gambling Consider a roulette wheel Major Assumptions Numbers 1 36 numbers 0 and 00 Odds on a number classic or straight bet is 36 for 1 this is also called 35 to 1 1 bet yields 35 profit Equivalently 1 bet at the beginning of a spin will return 36 if the number wins All money must be bet on every spin of the wheel Money may be distributed arbitrarily over the numbers Only one number wins each with probability 1 38 The wheel is spun many times Question 1 What is the optimal bet at each spin Question 2 If the odds change does the bet 3 9 25 13 J A O Sullivan ESE 523 Lectures 9 10 Theorem Proportional betting is log optimal Optimal bet does not Horses k 1 2 m depend on the odds as Probabilities pk 0 long as all odds are Odds ok 0 positive Fraction bet bk 0 Reformulation Wealth relative S X Doubling rate W Portfolio b Optimal doubling rate m b k 1 n n i 1 i 1 k 1 S n S 0 S X i S 0 b X i o X i 1 log S n E log b X o X W b p n n m W b p pk log bk ok k 1 S n 2nW b p 9 25 13 J A O Sullivan ESE 523 Lectures 9 10 4 Optimal Doubling Rate Form Lagrangian Set derivatives equal to 0 Solve subject to the constraint max W b p b P P bk 0 b 1 k k 1 m m W b p pk log bk ok k 1 m m Conclusion proportional J b pk log bk ok bk betting is log optimal k 1 k 1 independent of odds J b pk log e 0 bk pk This proves the theorem bk bk W p W b p m W p pk log ok H p k 1 9 25 13 J A O Sullivan ESE 523 Lectures 9 10 5 Odds m Betting can be viewed as 1 1 r Fair odds if 1 k estimating the o ok k 1 k probabilities m m b Odds are fair if the sum of W b p pk log bk ok pk log k rk inverse odds is one k 1 k 1 m If a bookie sets fair odds bk pk D p r D p b W p log b p then the bettor wins if he k rk pk k 1 is a better estimator than the bookie the doubling W p D p r rate equals the difference 1 between relative constant Uniform odds if ok entropies For uniform fair odds the 1 1 sum of the doubling rate Uniform fair odds if ok m and the entropy is a constant 1 W p D p log m H p m 9 25 13 J A O Sullivan ESE 523 Lectures 9 10 6 Holding Money as Cash For fair odds there is no advantage to holding money as cash proportional betting is log optimal Superfair odds proportional betting is log optimal Dutch book is risk free guaranteed profit Subfair odds real life where house takes a cut optimal strategy found through KuhnTucker conditions water filling 9 25 13 m Hold fraction as cash b0 b0 bk 1 k 1 S X b 0 b X o X m Fair odds 1 X b X b 0 1 set b o X k 1 ok m 1 1 k 1 ok Superfair odds Dutch book b X c o X m 1 Subfair odds 1 k 1 ok J A O Sullivan ESE 523 Lectures 9 10 7 Holding Cash Solve the Lagrangian use the Kuhn Tucker condition Solve for b 0 and b x under the conditions that they are positive use the solutions for b x in that for b 0 m Hold fraction as cash b0 b0 bk 1 k 1 W b p p x log b 0 b x o x x W p max p x log b 0 b x o x b P x J b p x log b 0 b x o x b 0 b x x x p x J b o x 0 if b x 0 b x b 0 b x o x p x J b 0 if b 0 0 b 0 x b 0 b x o x p x b 0 b x if b x 0 o x A x b x 0 o x x A 9 25 13 x X A p x 0 b 0 b 0 J A O Sullivan ESE 523 Lectures 9 10 x X A p x 18 1 o x x A Holding Cash p x b x b 0 if b x 0 o x A x b x 0 o x x A x X A p x 0 b 0 b 0 p x x X A 1 x A o x 1 b 0 b x 1 b 0 b x 1 x X x A p x p x b 0 1 o x 1 x A 1 x A o x p x p x p x 1 1 x X A x X A x X A 1 1 1 x A o x 1 1 o x o x x A x A x X A 9 25 13 1 9 J A O Sullivan ESE 523 Lectures 9 10 Holding Money as Cash One solution is b p b 0 0 local extremum Increasing b 0 successively sets values of b x to 0 when b 0 gets larger than p x o x b 0 increases by discrete steps by subtracting elements from A For subfair odds W may continue to increase as b 0 increases leading to a maximum at b 0 1 For superfair odds there is always a maximum for b 0 1 m Hold fraction as cash b0 b0 bk 1 k 1 W b p p x log b 0 b x o x x W p max p x log b 0 b x o x b P b x p x x b 0 if b x 0 o x A x b x 0 b 0 p x x X A 1 1 o x x A 10 9 25 13 J A O Sullivan ESE 523 Lectures 9 10 Revisit Roulette Exercise Consider a …

View Full Document