ESE 523 Information Theory Lectures 9-10Chapter 6: Gambling and Data CompressionRoulette in the Language of Horse Races (Kelly Gambling)Theorem: Proportional betting is log optimalOptimal Doubling RateOddsHolding Money as CashHolding CashHolding CashHolding Money as CashRevisit Roulette ExerciseGambling with Side InformationData Compression CommentsHorse RaceSlide Number 152007 CommentsChapter 6 Gambling and Data Compression9/25/13 J. A. O'Sullivan ESE 523 Lectures 9-10 1ESE 523 Information TheoryLectures 9-10Joseph A. O’SullivanSamuel C. Sachs ProfessorElectrical and Systems EngineeringWashington University2120E Green Hall211 Urbauer [email protected]/25/13 J. A. O'Sullivan ESE 523 Lectures 9-102Chapter 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)9/25/13 J. A. O'Sullivan ESE 523 Lectures 9-103Roulette in the Language of Horse Races (Kelly Gambling) Consider a roulette wheel 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. Major Assumptions: 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?9/25/13 J. A. O'Sullivan ESE 523 Lectures 9-104Theorem: Proportional betting is log optimal Optimal bet does not depend on the odds as long as all odds are positive. Reformulation Wealth relative S(X) Doubling rate W Portfolio b Optimal doubling rate()()() ( )100111(,)Horses: 1, 2,...Probabilities: 0Odds: 0Fraction bet: 0, 1() ()()1log log ()() ,,log2kkmkkknnni iiiinnmkkkknWnkmpobbSS SX S bXoXSE bXoX WnWpboS===→∞==>>≥===⎡⎤→=⎣⎦==∑∏∏∑bpbpbp9/25/13 J. A. O'Sullivan ESE 523 Lectures 9-105Optimal Doubling Rate Form Lagrangian Set derivatives equal to 0 Solve subject to the constraint Conclusion: proportional betting is log-optimal independent of odds This proves the theorem()() ( )()() ( )() ( )11111max ,0, 1,log() log()log 0**,*log()mkkkmkkkkmmkkk kkkkkkkkmkkkWbbWpboJpbobpJebpbbWWWpoHλλ∈=====⎧⎫≥=⎨⎬⎩⎭==+∂=+=⇒=∂==−∑∑∑∑∑bbpbpbbpbpppPP=9/25/13 J. A. O'Sullivan ESE 523 Lectures 9-106Odds Betting can be viewed as estimating the probabilities.  Odds are fair if the sum of inverse odds is one. If a bookie sets fair odds, then the bettor wins if he is a better estimator than the bookie (the doubling rate equals the difference between relative entropies). For uniform fair odds, the sum of the doubling rate and the entropy is a constant ()() ()()() ( )() ()111111Fair odds if 1; ,log log,log ||||*||1Uniform odds if constant11Uniform fair odds if 1*||logmkkkkmmkkkk kkkkmkkkkkkkkroobWpboprbpWp DDrpWDoomWD mHm==========−===⎛⎞==−⎜⎟⎝⎠∑∑∑∑bpbp p r p bpprpp p9/25/13 J. A. O'Sullivan ESE 523 Lectures 9-107Holding 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 Kuhn-Tucker conditions (water-filling)001111Hold fraction as cash , 1() (0) ()()1(0)Fair odds 1 set ( ) ( )()1Superfair odds 1Dutch book: ( )()1Subfair odds 1mkkmkkmkkmkkbb bSX b bXoXbbX bXooXocbXoXo====+==+=⇒ = +<⇒=>∑∑∑∑9/25/13 J. A. O'Sullivan ESE 523 Lectures 9-108Holding 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) [][][]001Hold fraction as cash , 1(, ) ()log (0) ()()*() max ()log (0) ()()() ()log (0) ()() (0) ()() ()() 0 if () 0() (0) ()()()mkkxxxxbb bW px b bxoxW px b bxoxJpxbbxoxbbxJpxox bxbx b bxoxJλλ=∈+==+=+⎡⎤=+−+⎢⎥⎣⎦∂=−=>∂+∂∑∑∑∑∑bbppbbbP{}()0 if (0) 0(0) (0) ( ) ( )() (0)() if () 0():() 0()()0(0)() (0)11()xxxxxpxbbbbxoxpx bbx bxoxxbxpxpxbox boxλλλλλ∈∈∈∈=−=>∂+=− >=>+−=⇒=⎡⎤−⎢⎥⎣⎦∑∑∑∑∑X-AAX-AAA9/25/13 J. A. O'Sullivan ESE 523 Lectures 9-109Holding Cash{}() (0)() if () 0():() 0()()0(0)() (0)11()(0) ()1 (0) ()1()() (0)1()11()()xxxxxxxxxxpx bbx bxoxxbxpxpxbox boxbbxbbxpxpx boxoxpxλλλλλλ∈∈∈∈∈∈∈∈∈∈=− >=>+−=⇒=⎡⎤−⎢⎥⎣⎦+=⇒+=⇒⎡⎤+−=⇒⎢⎥⎡⎤⎣⎦−⎢⎥⎣⎦∑∑∑∑∑∑∑∑∑∑X-AAX-AAXAX-AAAX-AA() ()111()1111() ()1xxxxxpx pxoxox oxλλλλλ∈∈∈∈∈⎡⎤+−− =⇒⎢⎥⎡⎤ ⎡⎤⎣⎦−−⎢⎥ ⎢⎥⎣⎦ ⎣⎦=∑∑∑∑∑X-A X-AAAA9/25/13 J. A. O'Sullivan ESE 523 Lectures 9-1010Holding 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[][]{}001Hold fraction as cash , 1(, ) ()log (0) ()()*() max ()log (0) ()()(0)() () if () 0():() 0()(0)11()mkkxxxxbb bW px b bxoxWpxbbxoxbbx px bxoxxbxpxbox=∈∈∈+==+=+=− >=>=⎡⎤−⎢⎥⎣⎦∑∑∑∑∑bbppPX-AAA9/25/13 J. A. O'Sullivan ESE 523 Lectures 9-1011Revisit Roulette Exercise Consider a roulette wheel Numbers 1-36; numbers 0 and 00; equally likely Odds at casinos on a number (classic or straight bet) is 36 for 1 Altered odds: outcomes 0 and 00 are 36 for 1; red is 36(1.1) for 1; black is 36(0.9) for 1 Money can be held in cash What is the optimal portolio? What is the resulting doubling rate?9/25/13 J. A. O'Sullivan ESE 523 Lectures 9-1012Gambling with Side Information The increase in doubling rate due to side information equals mutual information For a sequence of dependent horse races, the doubling rate is determined by the entropy rate of the random process() ( )()()()11(|Horses: 1,