Gambling and Shannon’s Entropy Function Part 2.

In the last post I gave an introduction of Kelly’s paper where he describes optimal gambling strategies based on information received over a potentially noisy channel. Here I’ll talk about the general case, where the channel has several inputs symbols, each with a given probability  of being transmitted, and which represent the outcome of some chance event. First, we need to set up some notation:

p(s) –  probability that the transmitted symbol is s.

p(r | s) – the conditional probability that the received symbols is r given that the transmitted symbol is s.

p(r, s) –  the joint probability that the received symbol is r and the transmitted symbol is s.

q(r) –  probability that the received symbol is r.

q(s | r) – the conditional probability that the transmitted symbol is s given that the received symbols is r.

\alpha_s – the odds paid on the occurrence of s, i.e. the number of dollars returned on a one-dollar bet on s.

a(s/r) – the fraction of capital that the gambler decides to bet on the occurrence of s after receiving r.

First, suppose that \alpha_s = \frac{1}{p(s)}. Note that if \alpha_s > \frac{1}{p(s)}, then the gambler can capitalize on making repeated bets on s, and this extra betting would in turn lower \alpha_s in most natural settings (this is known as “arbitrage” in the market world). Also, lets suppose that there is no “track take,” i.e. \sum \frac{1}{\alpha_s} = 1 , and that the gambler bets his entire capital regardless of the symbol received, i.e. \sum_s a(s/r)=1 (note: he can withhold money by placing canceling bets so this is a reasonable assumption).

The amount of capital after N bets is now V_N = \prod_{r,s} [a(s/r) \alpha_s]^{W_{sr}} V_0, where W_{sr} is the number of times the transmitted symbol is s and the received symbol is r. The log difference of the N’th and starting bet is

log(\frac{V_N}{V_0}) = \sum_{rs} W_{r,s} \log(\alpha_s a(s/r)),

and we have

G = \lim_{N \rightarrow \infty} \frac{1}{N} \log(\frac{V_N}{V_0}) = \sum_{r,s} p(s,r) log(\alpha_s a(s/r))

with probability 1.

Since \alpha_s = \frac{1}{p(s)} we have that

G = \sum_{r,s} p(s,r) \log(\frac{a(s/r)}{p(s)})=

\sum_{r,s} \log (a(s/r)) + \sum_{s} \sum_{r} p(s,r) \log (\frac{1}{p(s)})=

\sum_{r,s} \log(a(s/r)) + \sum_{s} p(s) \log(\frac{1}{p(s)}) =

\sum_{r,s} \log(a(s/r)) + H(X),

where H(X) is Shannon’s source rate.  We can maximize the firs term by putting a(s/r) = \frac{p(s,r)}{q(r)} = q(s/r) and what we get is G_{max} = H(X) - H(X|Y) which is the Shannon’s rate of transmission as talked about by Matt here.

Now if \alpha_s \leq \frac{1}{p(s)}, we have

G = \sum_{r,s} p(s,r) \log(a(s/r)) + \sum_s \log(\alpha_s),

and G is still maximized by setting a(s/r) = q(s/r). Hence,

G_{max} = -H(X|Y) + \sum_s p(s) \log(\alpha_s) = H(\alpha) - H(X|Y),

where

H(\alpha) = \sum_s p(s) \log(\alpha).

Notice that to maximize G, the gambler has ignored the odds, i.e. it is only the information rate that matters in his strategy. In a future post I’ll discuss further implication of these results, as well as the “track take” scenario.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: