kelly.tex typeset

Transcript

1 A New Interpretation of Information Rate reproduced with permission of AT&T J. L. Kelly, jr. By (Manuscript received March 21, 1956) If the input symbols to a communication channel represent the outcomes of a chance event on which bets are available at odds consistent with their probabilities (i.e., \fair" odds), a gambler can use the knowledge given him by the received symbols to cause his money to grow exponentially. The maximum exponential rate of growth of the gambler's capital is equal to the rate of transmission of information over the channel. This result is generalized to include the case of arbitrary odds. Thus we Ønd a situation in which the transmission rate is signiØcant even though no coding is contemplated. Previously this quantity was given signiØcance only by a theorem of Shannon's which asserted that, with suitable encoding, binary digits could be transmitted over the channel at this rate with an arbitrarily small probability of error. introduction Shannon deØnes the rate of transmission over a noisy communication channel 1 This deØnition is given signiØcance by a in terms of various probabilities. theorem which asserts that binary digits may be encoded and transmitted over the channel at this rate with arbitrarily small probability of error. Many workers in the Øeld of communication theory have felt a desire to attach signiØcance to the rate of transmission in cases where no coding was contemplated. Some have even proceeded on the assumption that such a signiØcance did, in fact, exist. For example, in systems where no coding was desirable or even possible (such as radar), detectors have been designed by the criterion of maximum transmission rate or, what is the same thing, minimum equivocation. Without further analysis such a procedure is unjustiØed. The problem then remains of attaching a value measure to a communication 1 C.E. Shannon, A Mathematical Theory of Communication, B.S.T.J., 27 , pp. 379-423, 623-656, Oct., 1948. 917

2 918 the bell system technical journal, july 1956 system in which errors are being made at a non-negligible rate, i.e., where optimum coding is not being used. In its most general formulation this problem seems to have but one solution. A cost function must be deØned on pairs of symbols which tells how bad it is to receive a certain symbol when a speciØed signal is transmitted. Furthermore, this cost function must be such that its expected value has signiØcance, i.e., a system must be preferable to another if 2 shows us one way its average cost is less. The utility theory of Von Neumann to obtain such a cost function. Generally this cost function would depend on things external to the system and not on the probabilities which describe the system, so that its average value could not be identiØed with the rate as deØned by Shannon. The cost function approach is, of course, not limited to studies of commu- nication systems, but can actually be used to analyze nearly any branch of human endeavor. The author believes that it is too general to shed any light on the speciØc problems of communication theory. The distinguishing feature of a communication system is that the ultimate receiver (thought of here as a person) is in a position to proØt from any knowledge of the input symbols or even from a better estimate of their probabilities. A cost function, if it is sup- posed to apply to a communication system, must somehow re∞ect this feature. The point here is that an arbitrary combination of a statistical transducer (i.e., a channel) and a cost function does not necessarily constitute a communication system. In fact (not knowing the exact deØnition of a communication system on which the above statements are tacitly based) the author would not know how to test such an arbitrary combination to see if it were a communication system. What can be done, however, is to take some real-life situation which seems to possess the essential features of a communication problem, and to analyze it without the introduction of an arbitrary cost function. The situation which will be chosen here is one in which a gambler uses knowledge of the received symbols of a communication channel in order to make proØtable bets on the transmitted symbols. the gambler with a private wire Let us consider a communication channel which is used to transmit the results of a chance situation before those results become common knowledge, so that a gambler may still place bets at the original odds. Consider Ørst the case of a noiseless binary channel, which might be 2 Von Neumann and Morgenstein, Theory of Games and Economic Behavior, Princeton Univ. Press, 2nd Edition, 1947.

3 a new interpretation of information rate 919 used, for example, to transmit the results of a series of baseball games between two equally matched teams. The gambler could obtain even money bets even though he already knew the result of each game. The amount of money he could make would depend only on how much he chose to bet. How much would he bet? Probably all he had since he would win with certainty. In this case N times bets he would have 2 his capital would grow exponentially and after N his original bankroll. This exponential growth of capital is not uncommon in economics. In fact, if the binary digits in the above channel were arriving at the rate of one per week, the sequence of bets would have the value of an investment paying 100 per cent interest per week compounded weekly. We will make use called the exponential rate of growth of the gambler's capital, of a quantity G where V 1 N log G = lim !1 N N V 0 V is his starting capital, and is the gambler's capital after N bets, V where 0 N the logarithm is to the base two. In the above example G =1. Consider the case now of a noisy binary channel, where each transmitted , of error and of correct transmission. Now the p q symbol has probability, gambler could still bet his entire capital each time, and, in fact, this would i ; which in this case would be maximize the expected value of his capital, h V N given by N i =(2 q ) V V h 0 N This would be little comfort, however, since when N was large he would probably be broke and, in fact, would be broke with probability one if he continued indeØnitely. Let us, instead, assume that he bets a fraction, ` , of his capital each time. Then L W =(1+ V ) ` (1 ° ` ) V N 0 W L are the number of wins and losses in the N bets. Then and where ∏ ∑ L W log(1 + ` )+ log(1 ° ` ) lim G = !1 N N N = q log(1 + ` )+ p log(1 ° ` ) with probability one Let us maximize ` . The maximum value with respect to G with respect to P of a quantity of the form , subject to the constraint = Y X log Z Y the i i i P = Y , is obtained by putting Y i Y X = ; Y i i X

4 920 the bell system technical journal, july 1956 P . This may be shown directly from the convexity of the X where = X i logarithm. Thus we put )=2 q ` (1 + ` )=2 p (1 ° and log =1+ p log p + q q G max R = which is the rate of transmission as deØned by Shannon. One might still argue that the gambler should bet all his money (make ` =1) in order to maximize his expected win after N times. It is surely true that if the game were to be stopped after N bets the answer to this question would depend on the relative values (to the gambler) of being broke or possessing a fortune. If we compare the fates of two gamblers, however, playing a nonterminating game, the one which uses the value found above will, with probability one, eventually ` get ahead and stay ahead of one using any other ` . At any rate, we will assume that the gambler will always bet so as to maximize G. the general case Let us now consider the case in which the channel has several input symbols, not necessarily equally likely, which represent the outcome of chance events. We will use the following notation: p ( s ) the probability that the transmitted symbol is the s 'th one. p ( ) the conditional probability that the received symbol is the r 'th on the r=s s hypothesis that the transmitted symbol is the 'th one. ( s;r ) the joint probability of the s p r 'th received symbol. 'th transmitted and q ( r ) received symbol probability. q ( s=r ) conditional probability of transmitted symbol on hypothesis of received symbol. the odds paid on the occurrence of the s 'th transmitted symbol, i.e., Æ Æ s s is the number of dollars returned for a one-dollar bet (including that one dollar). a ( s=r ) the fraction of the gambler's capital that he decides to bet on the oc- currence of the s 'th transmitted symbol after observing the r 'th received symbol.

5 a new interpretation of information rate 921 Only the case of independent transmitted symbols and noise will be consid- ered. We will consider Ørst the case of \fair" odds, i.e., 1 = Æ s ( s ) p In any sort of parimutuel betting there is a tendency for the odds to be fair (ignoring the \track take"). To see this Ørst note that if there is no \track take" X 1 =1 Æ s since all the money collected is paid out to the winner. Next note that if 1 > Æ s p ( s ) th for some s s a bettor could insure a proØt by making repeated bets on the outcome. The extra betting which would result would lower Æ . The same feed- s back mechanism probably takes place in more complicated betting situations, such as stock market speculation. There is no loss in generality in assuming that X a ( s=r )=1 s i.e., the gambler bets his total capital regardless of the received symbol. Since X 1 =1 Æ s he can eÆectively hold back money by placing canceling bets. Now Y W sr V ] [ a ( s=r ) Æ = V s 0 N r;s W is the number of times that the transmitted symbol is s where and the sr . received symbol is r X V n s=r = log ( W a ) Æ log s sr V o rs (1) X V 1 N log = ( a s=r ) Æ p ( s;r ) log G = lim s !1 N V N 0 rs with probability one. Since 1 = Æ s p ( s )

6 922 the bell system technical journal, july 1956 here X a ( s=r ) p ( s;r ) log G = ( ) s p rs X p ( s;r ) log a ( s=r )+ H ( X ) = rs ( ) is the source rate as deØned by Shannon. The Ørst term is maxi- where X H mized by putting ( ) s;r p ( s;r ) p P ) = = q ( s=r )= s=r ( a ( ) ) p q k;r r ( k H = ( X ) ° H ( X=Y ), which is the rate of transmission deØned by G Then max Shannon. when the odds are not fair Consider the case where there is no track take, i.e., X 1 =1 Æ s is not necessarily Æ but where s 1 p ( s ) P ( s=r ) = 1 since the gambler can eÆectively hold a It is still permissible to set s . Equation back any amount of money by betting it in proportion to the 1 =Æ s (1) now can be written X X Æ p ( s;r ) log a ( s=r : )+ ) log p ( s = G s s rs is still maximized by placing a ( s=r )= q ( s=r ) and G X ) log = ° H ( X=Y )+ Æ s p ( G max s s ( H Æ ) = H ( X=Y ) ° where X ) log s ( p Æ Æ ( H )= s s Several interesting facts emerge here (a) In this case G is maximized as before by putting a ( s=r )= q ( s=r ). That is, the gambler ignores the posted odds in placing his bets!

7 a new interpretation of information rate 923 ( (b) Since the minimum value of Æ H ) subject to X 1 =1 Æ s s obtains when 1 = Æ s p ( s ) ( X )= H ( Æ ), any deviation from fair odds helps the gambler. and H H Æ ) ° ( ( X )ifhehad (c) Since the gambler's exponential gain would be H R = H ( X ) ° H ( X=Y ) as the increase no inside information, we can interpret due to the communication channel. When there is no channel, i.e., G of max is minimized (at zero) by setting ( X ), H ( X=Y )= H G max 1 = Æ s p s This gives further meaning to the concept \fair odds." when there is a \track take" In the case there is a \track take" the situation is more complicated. It can P ) = 1. The gambler cannot make canceling a ( s=r no longer be assumed that s P ), i.e., the =1 ° s=r a ( b bets since he loses a percentage to the track. Let r s th one. Then the quantity to r fraction not bet when the received symbol is the be maximized is X a s=r p ( s;r ) log[ b ( + Æ (2) )], = G r s rs subject to the constraints X + ( s=r )=1 : a b r s In maximizing (2) it is su±cient to maximize the terms involving a particular value of r and to do this separately for each value of r since both in (2) and in the associated constraints, terms involving diÆerent 's are independent. That r is, we must maximize terms of the type X q ( r ) s=r )] ( ( s=r ) log[ b = + Æ a q G r r s s subject to the constraint X + a ( s=r )=1 b r s

8 924 the bell system technical journal, july 1956 Actually, each of these terms is the same form as that of the gambler's exponential gain where there is no channel X p ( s ) log[ b + Æ a (3) ( s )] : G = s s We will maximize (3) and interpret the results either as a typical term in the general problem or as the total exponential gain in the case of no communication the set of indices, s , for which a ( s ) > 0, and by channel. Let us designate by ∏ 0 the set for which ( s ) = 0. Now at the desired maximum a ∏ p ( s ) Æ @G s = log e = k fors≤∏ + ( ( s ) Æ s ) a @a b s X ) p ( s @G = e log = k s ) Æ b @b + a ( s s Æ p ( s ) @G s 0 = log e 5 k fors≤∏ @a ( s b ) k is a constant. The equations yield where 1 ° p , b = k = log e 1 ° æ b ( p ( s ) ° )= s s≤∏ for a Æ s P P = p ( s ), æ ), and the inequalities yield (1 =Æ = p where s ∏ ∏ p ° 1 0 = 5 b s≤∏ for s ) ( p Æ s æ 1 ° We will see that the conditions æ< 1 ° 1 p s≤∏ for > Æ s ) ( p s æ ° 1 p ° 1 0 s≤∏ for 5 ) p Æ s ( s æ ° 1 completely determine ∏ . If we permute indices so that = Æ +1) s ( p p Æ ) s ( s s +1

9 a new interpretation of information rate 925 ∏ then 5 t where t is a positive integer or zero. Consider must consist of all s how the fraction p ° 1 t = F t ° 1 æ t varies with t , where t t X X 1 ( s ), æ F = = =1 ; p p t 0 t Æ s 1 1 t = = 0 satisØes æ < 1, F until increases with t 1. In this case Æ (1) p Now if t t 1 F > 1 until decreases with t (1) p Æ is empty. If ∏ the desired conditions and t 1 F and the fraction increases until æ = 1. In any case the desired value F t t t +1 its minimum positive value, or if there is more of is the one which gives F t t than one such value of t , the smallest. The maximizing process may be summed up as follows: Æ +1) s ( p = ( p (a) Permute indices so that s Æ ) s s +1 (b) Set b equal to the minimum positive value of t t X X 1 1 ° p t = p ), = p ( s where æ t t 1 ° Æ æ s t 1 1 a ( s )= p ( s ) ° b=Æ (c) Set or zero, whichever is larger. (The a ( s ) will sum to s 1 b .) ° The desired maximum G will then be t X p ° 1 t = ( s ) log p ( s ) Æ p +(1 ° p ) log G t s max ° 1 æ t 1 is the smallest index which gives where t p ° 1 t ° æ 1 t its minimum positive value. s 1 for all < no bets are placed, but if It should be noted that if ) s ( p Æ s s 1, i.e., the > 1 some bets might be made for which p ( ) Æ < ) Æ p the largest ( s s s expected gain is negative. This violates the criterion of the classical gambler who never bets on such an event. conclusion The gambler introduced here follows an essentially diÆerent criterion from the classical gambler. At every bet he maximizes the expected value of the logarithm of his capital. The reason has nothing to do with

10 926 the bell system technical journal, july 1956 the value function which he attached to his money, but merely with the fact that it is the logarithm which is additive in repeated bets and to which the law of large numbers applies. Suppose the situation were diÆerent; for example, suppose the gambler's wife allowed him to bet one dollar each week but not to reinvest his winnings. He should then maximize his expectation (expected value of capital) on each bet. He would bet all his available capital (one dollar) on the event yielding the highest expectation. With probability one he would get ahead of anyone dividing his money diÆerently. It should be noted that we have only shown that our gambler's capital will surpass, with probability one, that of any gambler apportioning his money dif- ferently from ours but still in a Øxed way for each received symbol, independent of time or past events. Theorems remain to be proved showing in what sense, if any, our strategy is superior to others involving a ( s=r ) which are not constant. Although the model adopted here is drawn from the real-life situation of gambling it is possible that it could apply to certain other economic situations. The essential requirements for the validity of the theory are the possibility of reinvestment of proØts and the ability to control or vary the amount of money invested or bet in diÆerent categories. The \channel" of the theory might cor- respond to a real communication channel or simply to the totality of inside information available to the investor. Let us summarize brie∞y the results of this paper. If a gambler places bets on the input symbol to a communication channel and bets his money in the same proportion each time a particular symbol is received, his capital will grow (or shrink) exponentially. If the odds are consistent with the probabilities of occur- rence of the transmitted symbols (i.e., equal to their reciprocals), the maximum value of this exponential rate of growth will be equal to the rate of transmission of information. If the odds are not fair, i.e., not consistent with the transmit- ted symbol probabilities but consistent with some other set of probabilities, the maximum exponential rate of growth will be larger than it would have been with no channel by an amount equal to the rate of transmission of information. In case there is a \track take" similar results are obtained, but the formulae involved are more complex and have less direct information theoretic interpre- tations. acknowledgments I am indebted to R. E. Graham and C. E. Shannon for their assistance in the preparation of this paper.

Related documents