## 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.