We ask what is the appropriate price c to pay to receive an amount X ≥ 0; X ~ F(x). This is known as the St. Petersburg paradox if Pr{X = 2k} = 2-k, k = 1, 2, ... Here EX = ∞. Is any price c aceptable? We consider this distribution as well as the distribution Pr{X = 22k} = 2-k, k = 1, 2, ..., which might be called the super St. Petersburg paradox in which not only is EX equal to infinity, but E log X is infinity as well. Let μr= (EXr)1/rdenote the rthmean of X. We identify three critical costs, μ-1= 1/E(1/X), μ0= eE lnX, and μ1= EX, and conclude that we want some of X if c ≤ μ1, and that taking all of X is growth optimal if c ≤ μ-1. Thus all prices c are attractive in the St. Petersburg game.

A gambler walks into a hypothetical fair casino with a very real dollar bill, but by the time he leaves he's exchanged that for a random amount of money. What is lost in the process? It may be that the gambler walks out at the end of the day, after a roller-coaster ride of winning and losing, with his dollar still intact-or maybe even with two dollars. But what the gambler loses the moment he places his first bet is position. He exchanges one distribution of money for a distribution of lesser value, and he can't get back to the original distribution. Our first discussion in this work connects known results of economic inequality and majorization to the probability theory of gambling and Martingales. We provide a simple proof that fair gambles cannot increase the Lorenz curve, and we also constructively demonstrate that any sequence of non-increasing Lorenz curves corresponds to at least one Martingale. We next consider the efficiency of gambles. If any fair gamble is available then one can move down the lattice of distributions with respect to the Lorenz ordering. The step from one distribution to the next is not unique. Is there a sense of efficiency with which one can move down the Lorenz stream? One approach would be to minimize the average total volume of money placed on the table. In this case, it turns out that implementing part of the strategy using private randomness can help reduce the need for the casino's randomness, resulting in less money on the table that the casino can get its hands on.

We develop elements of a theory of cooperation and coordination in networks. Rather than considering a communication network as a means of distributing information, or of reconstructing random processes at remote nodes, we ask what dependence can be established among the nodes given the communication constraints. Specifically, in a network with communication rates$\{R_{i,j}\}$between the nodes, we ask what is the set of all achievable joint distributions$p(x_{1},\ldots ,x_{m})$of actions at the nodes of the network. Several networks are solved, including arbitrarily large cascade networks. Distributed cooperation can be the solution to many problems such as distributed games, distributed control, and establishing mutual information bounds on the influence of one part of a physical system on another.

We consider the problem of transmitting data at rate over a state-dependent channel with state information available at the sender and at the same time conveying the information about the channel state itself to the receiver. The amount of state information that can be learned at the receiver is captured by the mutual information between the state sequence and the channel output . The optimal tradeoff is characterized between the information transmission rate and the state uncertainty reduction rate , when the state information is either causally or noncausally available at the sender. In particular, when state transmission is the only goal, the maximum uncertainty reduction rate is given by . This result is closely related and in a sense dual to a recent study by Merhav and Shamai, which solves the problem of masking the state information from the receiver rather than conveying it.

The capacity of a class of deterministic relay channels with the transmitter input X, the receiver output Y, the relay output Y1= f(X,Y), and a separate communication link from the relay to the receiver with capacity R0, is shown to be C(R0) =max min{I(X;Y) + R0, I(X;Y,Y1)}. p(x) Thus every bit from the relay is worth exactly one bit to the receiver. Two alternative coding schemes are presented that achieve this capacity. The first scheme, "hash-and-forward", is based on a variation of the usual random binning on the relay outputs, while the second scheme uses the usual "compress-and- forward". In fact, these two schemes can be combined to give a class of optimal coding schemes. As a corollary, this relay capacity result confirms a conjecture by Ahlswede and Han on the capacity of a channel with rate-limited state information at the decoder in the special case when the channel state is recoverable from the channel input and output.

We consider the problem of transmitting data at rateRover a state dependent channelp(y\x,s)with the state information available at the sender and at the same time conveying the information about the channel state itself to the receiver. The amount of state information that can be learned at the receiver is captured by the mutual information I(Sn;Yn) between the state sequence Snand the channel output Yn. The optimal tradeoff is characterized between the information transmission rateRand the state uncertainty reduction rate Delta, when the state information is either causally or noncausally available at the sender. This result is closely related and in a sense dual to a recent study by Merhav and Shamai, which solves the problem of masking the state information from the receiver rather than conveying it.

We propose the problem of coordinating action over many nodes by distributed communication. The idea is to switch the emphasis from exchanging information to setting up cooperative action. Examples are given. We solve most 3-node problems but one remains open.

Side information can increase the growth rate of wealth in stock market investment. The question is: when is the side information useful and when is it illusory? We propose a statistic to test this. We compare the wealth achieved by the best constant rebalanced portfolio in hindsight on the entire stock market sequence to the wealth resulting from the best constant rebalanced portfolio in hindsight on the subsequences of stocks identified by the states of the side information sequence. If one can't make money from side information given perfect hindsight one never can. We prove, under the null hypothesis of independence of the side information sequence from the stock sequence, that the logarithm of the ratio of optimal wealth with and without side information is asymptotically distributed as half a chi-squared random variable with (d - 1)(m - 1) degrees of freedom, where d is the number of states of side information and m is the number of stocks. This statistic has an asymptotic distribution that is independent of the particular stock sequence or the distribution of the side information sequence. Thus the use of side information can be accepted when the wealth ratio exceeds a certain fixed level given by the appropriate quantile of the chi-squared distribution

We formulate a problem of state information transmission over a state-dependent channel with states known at the transmitter. In particular, we solve a problem of minimizing the mean-squared channel state estimation error E/spl par/S/sup n/ - S/spl circ//sup n//spl par/ for a state-dependent additive Gaussian channel Y/sup n/ = X/sup n/ + S/sup n/ + Z/sup n/ with an independent and identically distributed (i.i.d.) Gaussian state sequence S/sup n/ = (S/sub 1/, ..., S/sub n/) known at the transmitter and an unknown i.i.d. additive Gaussian noise Z/sup n/. We show that a simple technique of direct state amplification (i.e., X/sup n/ = /spl alpha/S/sup n/), where the transmitter uses its entire power budget to amplify the channel state, yields the minimum mean-squared state estimation error. This same channel can also be used to send additional independent information at the expense of a higher channel state estimation error. We characterize the optimal tradeoff between the rate R of the independent information that can be reliably transmitted and the mean-squared state estimation error D. We show that any optimal (R, D) tradeoff pair can be achieved via a simple power-sharing technique, whereby the transmitter power is appropriately allocated between pure information transmission and state amplification.

A stock market game where one player (the investor) plays against another (the market) with payoff given by the ratio of the investor's wealth (at time n) to the market wealth given by the performance of the best constant rebalanced portfolio in hindsight on the market sequence is analysed. This paper consider markets in which no stock underperforms the average by a given amount, and consider portfolio strategies that allow both short selling and margin. The possibility of universal portfolios in the market which do as well against any specific stock sequence. Putting a constraint /spl alpha/ on stock performance creates the opportunity for short selling and margin. This increases the relative performance of the universal portfolio.

We show that the duality between channel capacity and data compression is retained when state information is available to the sender, to the receiver, to both, or to neither. We present a unified theory for eight special cases of channel capacity and rate distortion with state information, which also extends existing results to arbitrary pairs of independent and identically distributed (i.i.d.) correlated state information (S/sub 1/, S/sub 2/) available at the sender and at the receiver, respectively. In particular, the resulting general formula for channel capacity C = max/sub p/(u,x|s/sub 1/) [I(U; S/sub 2/, Y) I(U; S/sub 1/)] assumes the same form as the generalized Wyner-Ziv (1976) rate distortion function R(D) = min/sub p/(u|x, s/sub 1/)p(x/spl I.cap/|u, s/sub 2/) [I(U; S/sub 1/, X) 1(U; S/sub 2/)].

The maximum entropy noise under a lag p autocorrelation constraint is known by Burg's theorem to be the pth order Gauss-Markov process satisfying these constraints. The question is, what is the worst additive noise for a communication channel given these constraints? Is it the maximum entropy noise? The problem becomes one of extremizing the mutual information over all noise processes with covariances satisfying the correlation constraints R/sub 0/,..., R/sub p/. For high signal powers, the worst additive noise is Gauss-Markov of order p as expected. But for low powers, the worst additive noise is Gaussian with a covariance matrix in a convex set which depends on the signal power.

We formulate the problem of growth optimal investment in horse race markets with proportional costs and study growth optimal strategies both for stochastic horse races as well as races where one does not make any distributional assumptions. Our results extend all known results for frictionless horse race markets to their natural analog in markets with costs.

The key ideas in the theory of broadcast channels are illustrated by discussing some of the progress toward finding the capacity region. The capacity region is still unknown.

We investigate how the description of a correlated information V improves the investment in the stock market X. The objective is to maximize the growth rate of wealth in repeated investments, We find a single-letter characterization of the incremental growth rate /spl Delta/(R), the maximum increase in growth rate when V is described to the investor at rate R. The incremental growth rate specialized to the horse race market is related to source coding with side information of Wyner and Ahlswede-Kormer. We provide two horse race examples: jointly binary and jointly Gaussian. The initial efficiency /spl Delta/'(0) is the maximum possible increase in the growth rate per bit of description, We show that the initial efficiency is related to the dependency between V and the market. In particular, for the horse race market, the initial efficiency is the square of the Hirschfeld-Gebelein-Renyi maximal correlation between V and X. This provides a connection with the hypercontraction of the Markov operator of Ahlswede and Gacs. For the general market the initial efficiency is 1 when the side information V is equal to the stock market outcome X.

We solve the problem of tracking the best constant rebalanced portfolio computed in hindsight in a max-min optimal sense and relate our results to the pricing of a new derivative security which might be called the hindsight allocation option. This option pays the return of one dollar invested in the best constant rebalanced portfolio computed in hindsight.

We find an on-line portfolio selection strategy which minimizes the worst case regret with respect to the growth rate of wealth achieved by the best off-line optimized constant rebalanced portfolio.The resulting regret is compared to that of the infinite horizon Dirichlet-weighted universal portfolio.Both strategies track the performance of the best off-line constant rebalanced portfolio to first order in the exponent.1

The authors consider universal data compression, universal portfolio selection (online portfolio algorithms) and the relationship of both to information theory. Apparently the fundamental minimax redundancy game in data compression and the minimax regret game for the growth rate of wealth in investment have the same answer. There is also a duality between entropy rate and the growth rate of wealth.

We observe a training set Q composed of l labeled samples {(X/sub 1/,/spl theta//sub 1/),...,(X/sub l/, /spl theta//sub l/)} and u unlabeled samples {X/sub 1/',...,X/sub u/'}. The labels /spl theta//sub i/ are independent random variables satisfying Pr{/spl theta//sub i/=1}=/spl eta/, Pr{/spl theta//sub i/=2}=1-/spl eta/. The labeled observations X/sub i/ are independently distributed with conditional density f/sub /spl theta/i/(/spl middot/) given /spl theta//sub i/. Let (X/sub 0/,/spl theta//sub 0/) be a new sample, independently distributed as the samples in the training set. We observe X/sub 0/ and we wish to infer the classification /spl theta//sub 0/. In this paper we first assume that the distributions f/sub 1/(/spl middot/) and f/sub 2/(/spl middot/) are given and that the mixing parameter is unknown. We show that the relative value of labeled and unlabeled samples in reducing the risk of optimal classifiers is the ratio of the Fisher informations they carry about the parameter /spl eta/. We then assume that two densities g/sub 1/(/spl middot/) and g/sub 2/(/spl middot/) are given, but we do not know whether g/sub 1/(/spl middot/)=f/sub 1/(/spl middot/) and g/sub 2/(/spl middot/)=f/sub 2/(/spl middot/) or if the opposite holds, nor do we know /spl eta/. Thus the learning problem consists of both estimating the optimum partition of the observation space and assigning the classifications to the decision regions. Here, we show that labeled samples are necessary to construct a classification rule and that they are exponentially more valuable than unlabeled samples.

We present a sequential investment algorithm, the /spl mu/-weighted universal portfolio with side information, which achieves, to first order in the exponent, the same wealth as the best side-information dependent investment strategy (the best state-constant rebalanced portfolio) determined in hindsight from observed market and side-information outcomes. This is an individual sequence result which shows the difference between the exponential growth wealth of the best state-constant rebalanced portfolio and the universal portfolio with side information is uniformly less than (d/(2n))log (n+1)+(k/n)log 2 for every stock market and side-information sequence and for all time n. Here d=k(m-1) is the number of degrees of freedom in the state-constant rebalanced portfolio with k states of side information and m stocks. The proof of this result establishes a close connection between universal investment and universal data compression.

Consider the problem of classifying a sample X0 into one of two classes, using a training set Q. Let Q be composed of l labeled samples {(X1, θ1), …, (Xl, θl)} and u unlabeled samples {X′1, …, X′u}, where the labels θi are i.i.d. Bernoulli(η) random variables over the set {1, 2}, the observations {Xi}i=1l are distributed according to fθi(·) and the unlabeled observations {X′j}j=1u are independently distributed according to the mixture density fX′(·) = ηf1(·) + (1−η)f2(·). We assume that f1(·),f2(·) and η are all unknown. Let f1(·) and f2(·) belong to a known family F, and assume that the mixtures of elements of F are identifiable. Even when the number of unlabeled samples is infinite and the decision regions can therefore be identified, one still needs labeled samples to label the decision regions with the correct classification. Letting R(l, u) denote the optimal probability of error for l labeled and u unlabeled samples, and assuming that the pairwise mixtures of F are identifiable, we obtain the obvious statements R(0, u) = R(0, ∞) = 12, R(1, 0) ⪕ 2ηη, R(∞, u) = R∗, and then prove R(1, ∞) = 2R∗(1−R∗), where R∗ is the Bayes probability of error, and R(l, ∞) = R∗ + exp{ −αl + o(l)}, where the exponent α is given by −log(2√ηη∫ √f1(x)f2(x) dx). Thus the first labeled sample reduces the risk from 12 to 2R∗(1−R∗) and subsequent labeled samples in the training set reduce the probability of error exponentially fast to the Bayes risk.

Investigates the maximization of the differential entropy h(X+Y) of arbitrary dependent random variables X and Y under the constraints of fixed equal marginal densities for X and Y. We show that max[h(X+Y)]=h(2X), under the constraints that X and Y have the same fixed marginal density f, if and only if f is log-concave. The maximum is achieved when X=Y. If f is not log-concave, the maximum is strictly greater than h(2X). As an example, identically distributed Gaussian random variables have log-concave densities and satisfy max[h(X+Y)]=h(2X) with X=Y. More general inequalities in this direction should lead to capacity bounds for additive noise channels with feedback.>

Although feedback does not increase the capacity of an additive white noise Gaussian channel, it enables prediction of the noise for non-white additive Gaussian noise channels and results in an improvement of capacity, but at most by a factor of 2 (Pinsker, Ebert, Pombra, and Cover). Although the capacity of white noise channels cannot be increased by feedback, multiple access white noise channels have a capacity increase due to the cooperation induced by feedback. Thomas has shown that the total capacity (sum of the rates of all the senders) of an m-user Gaussian white noise multiple access channel with feedback is less than twice the total capacity without feedback. The present authors show that this factor of 2 bound holds even when cooperation and prediction are combined, by proving that feedback increases the total capacity of an m-user multiple access channel with non-white additive Gaussian noise by at most a factor of 2.>

The idea of thermodynamic depth put forth by S. Lloyd and H. Pagels (1988) requires the computation of the entropy of Markov trajectories. Toward this end, the authors consider an irreducible finite state Markov chain with transition matrix P and associated entropy rate H(X)=- Sigma /sub i,j/ mu /sub i/P/sub ij/ log P/sub ij/ where mu is the stationary distribution given by the solution of mu = mu P. A trajectory T/sub ij/ of the Markov chain is a path with initial state i, final state j, and no intervening states equal to j. It is shown that the entropy H(T/sub ii/) of the random trajectory originating and terminating in state i is given by H(T/sub ii/)=H(X)/ mu /sub i/. Thus the entropy of the random trajectory T/sub ii/ is the product of the expected number of steps 1/ mu /sub i/ to return to state i and the entropy rate H(X) per step for the stationary Markov chain. A general closed form solution for the entropies H(T/sub ij/) is given by H=K-K+H/sub Delta /, where H is the matrix of trajectory entropies H/sub ij/=H(T/sub ij/); K=(I-P+A)/sup -1/ (H*-H/sub Delta /); K is a matrix in which the ijth element K/sub ij/ equals the diagonal element K/sub jj/ of K; A is the matrix of stationary probabilities with entries A/sub ij/= mu /sub j/; H* is the matrix of single-step entropies with entries H*/sub ij/=H(P/sub i/)=- Sigma /sub k/ P/sub ik/ log P/sub ik/; and H/sub Delta / is a diagonal matrix with entries (H/sub Delta /)/sub ii/=H(X)/ mu /sub i/.>

The authors introduce an index of resolvability that is proved to bound the rate of convergence of minimum complexity density estimators as well as the information-theoretic redundancy of the corresponding total description length. The results on the index of resolvability demonstrate the statistical effectiveness of the minimum description-length principle as a method of inference. The minimum complexity estimator converges to true density nearly as fast as an estimator based on prior knowledge of the true subclass of densities. Interpretations and basic properties of minimum complexity estimators are discussed. Some regression and classification problems that can be examined from the minimum description-length framework are considered.>

Let X be a discrete random variable drawn according to a probability mass function p(x), and suppose p(x), is dyadic, i.e., log(1/p(x)) is an integer for each x. It is shown that the binary code length assignment l(x)=log(1/p(x)) dominates any other uniquely decodable assignment l'(x) in expected length in the sense that El(X)Pr(l (X)>l'(X)), which indicates l is also optimal in the short run. In general, if p is not dyadic then l=(log 1/p) dominates l'+1 in expected length and competitivity dominates l'+1, where l' is any other uniquely decodable code.>

The role of inequalities in information theory is reviewed, and the relationship of these inequalities to inequalities in other branches of mathematics is developed. The simple inequalities for differential entropy are applied to the standard multivariate normal to furnish new and simpler proofs of the major determinant inequalities in classical mathematics. The authors discuss differential entropy inequalities for random subsets of samples. These inequalities when specialized to multivariate normal variables provide the determinant inequalities that are presented. The authors focus on the entropy power inequality (including the related Brunn-Minkowski, Young's, and Fisher information inequalities) and address various uncertainty principles and their interrelations.>

A Wald-like equation is proved for the entropy of a randomly stopped sequence of independent identically distributed discrete random variables X/sub 1/, X/sub 2/. . ., with a nonanticipating stopping time N. The authors first define a general stopping time and the associated stopped sequence, and then present the two main theorems for the entropy of a stopped sequence. The formal proofs of the lemmas necessary for the proof of the theorems are given. The randomness in the stopped sequence X/sup N/ is the expected number of calls for X times the entropy per call plus the residual randomness in the stopping time conditioned on the unstopped sequence X/sup infinity /.>

The successive refinement of information consists of first approximating data using a few bits of information, then iteratively improving the approximation as more and more information is supplied. The goal is to achieve an optimal description at each stage. In general, an ongoing description which is rate-distortion optimal whenever it is interrupted is sought. It is shown that in order to achieve optimal successive refinement the necessary and sufficient conditions are that the solutions of the rate distortion problem can be written as a Markov chain. In particular, all finite alphabet signals with Hamming distortion satisfy these requirements. It is also shown that the same is true for Gaussian signals with squared error distortion and for Laplacian signals with absolute error distortion. A simple counterexample with absolute error distortion and a symmetric source distribution which shows that successive refinement is not always achievable is presented.>

The capacity of time-varying additive Gaussian noise channels with feedback is characterized. Toward this end, an asymptotic equipartition theorem for nonstationary Gaussian processes is proved. Then, with the aid of certain matrix inequalities, it is proved that the feedback capacity C/sub FB/ in bits per transmission and the nonfeedback capacity C satisfy C>

It is shown that each bit of information at most doubles the resulting wealth in the general stock-market setup. This information bound on the growth of wealth is actually attained for certain probability distributions on the market investigated by J. Kelly (1956). The bound is shown to be a special case of the result that the increase in exponential growth of wealth achieved with true knowledge of the stock market distribution F over that achieved with incorrect knowledge G is bounded above by the entropy of F relative to G.>

LetX_{1},X_{2},\cdotsbe independent identically distributed random variables taking values in a finite setXand consider the conditional joint distribution of the first m elements of the sampleX_{1},\cdots , X_{n}on the condition thatX_{1}=x_{1}and the sliding block sample average of a functionh(\cdot , \cdot)defined onX^{2}exceeds a threshold\alpha > Eh(X_{1}, X_{2}). Formfixed andn \rightarrow \infty, this conditional joint distribution is shown to converge m them-step joint distribution of a Markov chain started inx_{1}which is closest toX_{l}, X_{2}, \cdotsin Kullback-Leibler information divergence among all Markov chains whose two-dimensional stationary distributionP(\cdot , \cdot)satisfies\sum P(x, y)h(x, y)\geq \alpha, provided some distributionPonX_{2}having equal marginals does satisfy this constraint with strict inequality. Similar conditional limit theorems are obtained whenX_{1}, X_{2},\cdotsis an arbitrary finite-order Markov chain and more general conditioning is allowed.

A set of n pattern vectors are given in d-space and classified arbitrarily into two sets. The sets of patterns are said to be linearly separable if there exists a hyperplane that separates them. We ask whether translation of one of these sets in an arbitrary direction helps separability. Sometimes yes and sometimes no, but yes on the average. The average is taken over all classifications of the patterns into two sets. In fact, we prove that the probability of separability increases as the translation increases. Thus, we conclude that if points are drawn equiprobably from densities fo(x) and f1(x) = fo(x + tw) then the probability of linear separability is minimum at t = 0 and increases with t for t > 0.

The entropy power inequality states that the effective variance (entropy power) of the sum of two independent random variables is greater than the sum of their effective variances. The Brunn-Minkowski inequality states that the effective radius of the set sum of two sets is greater than the sum of their effective radii. Both these inequalities are recast in a form that enhances their similarity. In spite of this similarity, there is as yet no common proof of the inequalities. Nevertheless, their intriguing similarity suggests that new results relating to entropies from known results in geometry and vice versa may be found. Two applications of this reasoning are presented. First, an isoperimetric inequality for entropy is proved that shows that the spherical normal distribution minimizes the trace of the Fisher information matrix given an entropy constraint--just as a sphere minimizes the surface area given a volume constraint. Second, a theorem involving the effective radii of growing convex sets is proved.

Let the random (stock market) vectorX \geq 0be drawn according to a known distribution functionF(x), x \in R^{m}. A log-optimal portfoliob^{\ast}is any portfoliobachieving maximal expected\logreturnW^{\ast}=\sup_{b} E \ln b^{t}X, where the supremum is over the simplexb \geq 0, \sum_{i=1}^{m} b_{i} = 1. An algorithm is presented for findingb^{\ast}. The algorithm consists of replacing the portfoliobby the expected portfoliob^{'}, b_{i}^{'} = E(b_{i}X_{i}/b^{t}X), corresponding to the expected proportion of holdings in each stock after one market period. The improvement inW(b)after each iteration is lower-bounded by the Kullback-Leibler information numberD(b^{'}\|b)between the current and updated portfolios. Thus the algorithm monotonically improves the returnW. An upper bound onW^{\ast}is given in terms of the current portfolio and the gradient, and the convergence of the algorithm is established.

Hadamard's inequality follows immediately from inspection of both sides of the entropy inequalityh(X_{1}, X_{2},, \cdots, X_{n})\leq \sum h(X_{i}), when(X_{l}, X_{2},\cdots, X_{n})is multivariate normal.

An algorithm is derived which performs optimal symbol-by-symbol detection of a pulse amplitude modulated sequence. The algorithm is similar to the Viterbi algorithm with the optimality criterion optimal symbol detection rather than optimal sequence detection. A salient common feature is the merge phenomenon which allows common decisions to be made before the entire sequence is received.

Consider a sequence of independent identically distributed (i.i.d.) random variablesX_{l},X_{2}, \cdots, X_{n}and a distortion measured(X_{i},X̂_{i})on the estimatesX̂_{i}ofX_{i}. Two descriptionsi(X)\in \{1,2, \cdots ,2^{nR_{1}\}andj(X)\in \{1,2, \cdots,2^{nR_{2}\}are given of the sequenceX=(X_{1}, X_{2}, \cdots ,X_{n}). From these two descriptions, three estimates(i(X)), X2(j(X)), and\hat{X}_{O}(i(X),j(X))are formed, with resulting expected distortionsE \frac{1/n} \sum^{n}_{k=1} d(X_{k}, \hat{X}_{mk})=D_{m}, m=0,1,2.We find that the distortion constraintsD_{0}, D_{1}, D_{2}are achievable if there exists a probability mass distributionp(x)p(\hat{x}_{1},\hat{x}_{2},\hat{x}_{0}|x)withEd(X,\hat{x}_{m})\leq D_{m}such thatR_{1}>I(X;\hat{X}_{1}),R_{2}>I(X;\hat{X}_{2}),whereI(\cdot)denotes Shannon mutual information. These rates are shown to be optimal for deterministic distortion measures.

It is well-known that maximum entropy distributions, subject to appropriate moment constraints, arise in physics and mathematics. In an attempt to find a physical reason for the appearance of maximum entropy distributions, the following theorem is offered. The conditional distribution ofX_{l}given the empirical observation(1/n)\sum^{n}_{i}=_{l}h(X_{i})=\alpha, whereX_{1},X_{2}, \cdotsare independent identically distributed random variables with common densitygconverges tof_{\lambda}(x)=e^{\lambda^{t}h(X)}g(x)(Suitably normalized), where\lambdais chosen to satisfy\int f_{lambda}(x)h(x)dx= \alpha. Thus the conditional distribution of a given random variableXis the (normalized) product of the maximum entropy distribution and the initial distribution. This distribution is the maximum entropy distribution whengis uniform. The proof of this and related results relies heavily on the work of Zabell and Lanford.

An achievable rate regionR_{1} \leq I(X_{1};Y|X_{2},U), R_{2} \leq I(X_{2}; Y|X_{1},U), R_{1}+R_{2} \leq I(X_{1}, X_{2};Y), wherep(u,x_{l},x_{2},y)= p(u)p(x_{l}|u)p(x_{2}|u)p(y|x_{l},x_{2}), is established for the multiple-access channel with feedback. Time sharing of these achievable rates yields the rate region of this paper. This region generally exceeds the achievable rate region without feedback and exceeds the rate point found by Gaarder and Wolf for the binary erasure multiple-access channel with feedback. The presence of feedback allows the independent transmitters to understand each other's intended transmissions before the receiver has sufficient information to achieve the desired decoding. This allows the transmitters to cooperate in the transmission of information that resolves the residual uncertainty of the receiver. At the same time, independent information from the transmitters is superimposed on the cooperative correction information. The proof involves list codes and block Markov encoding.

The capacity region for the discrete memoryless multiple-access channel without time synchronization at the transmitters and receivers is shown to be the same as the known capacity region for the ordinary multiple-access channel. The proof utilizes time sharing of two optimal codes for the ordinary multiple-access channel and uses maximum likelihood decoding over shifts of the hypothesized transmitter words.

In the so-called "twin paradox" of relativity theory, one spaceship leaves another at velocity v = ftc and returns to find that the other ship has aged more by a factor\gamma=(1- \beta^{2})^{-1/2}. The asymmetry is first isolated in order to resolve the paradox. Then the principle of relativity is used to derive the relative aging factor\gammaand the relativistic Doppler shift. Using the Doppler factor, asymmetries in information transmission between moving spaceships are investigated. An additive white Gaussian noise channel with Shannon capacityC = W \log(l+P/NW)is considered. After accounting for the effect of the relativistic Doppler shift on signal power and bandwidth, it is found that for a given transmission rate and bandwidth, the traveler needs\gammatimes the energy of the stationary spaceship to transmit1/ \gammatimes as much information. The asymmetry in efficiency is thus\gamma^{2}. A simple proof is given that the round trip asymmetry in efficiency for constant-rate transmission is always the square of the relative aging factor for all trajectories regardless of accelerations and the presence of gravitational fields.

Let\{(U_{i},V_{i})\}_{i=1}^{n}be a source of independent identically distributed (i.i.d.) discrete random variables with joint probability mass functionp(u,v)and common partw=f(u)=g(v)in the sense of Witsenhausen, Gacs, and Körner. It is shown that such a source can be sent with arbitrarily small probability of error over a multiple access channel (MAC)\{\cal X_{1} \times \cal X_{2},\cal Y,p(y|x_{1},x_{2})\},with allowed codes\{x_{l}(u), x_{2}(v)\}if there exist probability mass functionsp(s), p(x_{1}|s,u),p(x_{2}|s,v), such thatH(U|V)<I(X_{1}; Y|X_{2},V,S),H(V|U )<I(X_{2};Y|X_{1},U,S),H(U,V|W)<I(X_{1},X_{2};Y|W,S),H(U,V)

A relay channel consists of an inputx_{l}, a relay outputy_{1}, a channel outputy, and a relay senderx_{2}(whose transmission is allowed to depend on the past symbolsy_{1}. The dependence of the received symbols upon the inputs is given byp(y,y_{1}|x_{1},x_{2}). The channel is assumed to be memoryless. In this paper the following capacity theorems are proved. 1)Ifyis a degraded form ofy_{1}, thenC \: = \: \max \!_{p(x_{1},x_{2})} \min \,{I(X_{1},X_{2};Y), I(X_{1}; Y_{1}|X_{2})}. 2)Ify_{1}is a degraded form ofy, thenC \: = \: \max \!_{p(x_{1})} \max_{x_{2}} I(X_{1};Y|x_{2}). 3)Ifp(y,y_{1}|x_{1},x_{2})is an arbitrary relay channel with feedback from(y,y_{1})to bothx_{1} \and x_{2}, thenC\: = \: \max_{p(x_{1},x_{2})} \min \,{I(X_{1},X_{2};Y),I \,(X_{1};Y,Y_{1}|X_{2})}. 4)For a general relay channel,C \: \leq \: \max_{p(x_{1},x_{2})} \min \,{I \,(X_{1}, X_{2};Y),I(X_{1};Y,Y_{1}|X_{2}). Superposition block Markov encoding is used to show achievability ofC, and converses are established. The capacities of the Gaussian relay channel and certain discrete relay channels are evaluated. Finally, an achievable lower bound to the capacity of the general relay channel is established.

In his original paper on the subject, Shannon found upper and lower bounds for the entropy of printed English based on the number of trials required for a subject to guess subsequent symbols in a given text. The guessing approach precludes asymptotic consistency of either the upper or lower bounds except for degenerate ergodic processes. Shannon's technique of guessing the next symbol is altered by having the subject place sequential bets on the next symbol of text. IfS_{n}denotes the subject's capital afternbets at27for1odds, and if it is assumed that the subject knows the underlying probability distribution for the processX, then the entropy estimate is\hat{H}_{n}(X)=(1-(1/n) \log_{27}S_{n}) \log_{2} 27bits/symbol. If the subject does not know the true probability distribution for the stochastic process, then\hat{H}_{n}(X)is an asymptotic upper bound for the true entropy. IfXis stationary,E\hat{H}_{n}(X)\rightarrowH(X), H(X)being the true entropy of the process. Moreover, if X is ergodic, then by the Shannon-McMillan-Breiman theorem\hat{H}_{n}(X)\rightarrowH(X)with probability one. Preliminary indications are that English text has an entropy of approximately1.3bits/symbol, which agrees well with Shannon's estimate. In his original paper on the subject, Shannon found upper and lower bounds for the entropy of printed English based on the number of trials required for a subject to guess subsequent symbols in a given text. The guessing approach precludes asymptotic consistency of either the upper or lower bounds except for degenerate ergodic processes. Shannon's technique of guessing the next symbol is altered by having the subject place sequential bets on the next symbol of text. IfS_{n}denotes the subject's capital afternbets at27for1odds, and if it is assumed that the subject knows the underlying probability distribution for the processX, then the entropy estimate is\hat{H}_{n}(X)=(1-(1/n) \log_{27}S_{n}) \log_{2} 27bits/symbol. If the subject does not know the true probability distribution for the stochastic process, then\hat{H}_{n}(X)is an asymptotic upper bound for the true entropy. IfXis stationary,E\hat{H}_{n}(X)\rightarrowH(X), H(X)being the true entropy of the process. Moreover, if X is ergodic, then by the Shannon-McMillan-Breiman theorem\hat{H}_{n}(X)\rightarrowH(X)with probability one. Preliminary indications are that English text has an entropy of approximately1.3bits/symbol, which agrees well with Shannon's estimate. In his original paper on the subject, Shannon found upper and lower bounds for the entropy of printed English based on the number of trials required for a subject to guess subsequent symbols in a given text. The guessing approach precludes asymptotic consistency of either the upper or lower bounds except for degenerate ergodic processes. Shannon's technique of guessing the next symbol is altered by having the subject place sequential bets on the next symbol of text. IfS_{n}denotes the subject's capital afternbets at27for1odds, and if it is assumed that the subject knows the underlying probability distribution for the processX, then the entropy estimate is\hat{H}_{n}(X)=(1-(1/n) \log_{27}S_{n}) \log_{2} 27bits/symbol. If the subject does not know the true probability distribution for the stochastic process, then\hat{H}_{n}(X)is an asymptotic upper bound for the true entropy. IfXis stationary,E\hat{H}_{n}(X)\rightarrowH(X), H(X)being the true entropy of the process.Moreover, if X is ergodic, then by the Shannon-McMillan-Breiman theorem\hat{H}_{n}(X)\rightarrowH(X)with probability one. Preliminary indications are that English text has an entropy of approximately1.3bits/symbol, which agrees well with Shannon's estimate. In his original paper on the subject, Shannon found upper and lower bounds for the entropy of printed English based on the number of trials required for a subject to guess subsequent symbols in a given text. The guessing approach precludes asymptotic consistency of either the upper or lower bounds except for degenerate ergodic processes. Shannon's technique of guessing the next symbol is altered by having the subject place sequential bets on the next symbol of text. IfS_{n}denotes the subject's capital afternbets at27for1odds, and if it is assumed that the subject knows the underlying probability distribution for the processX, then the entropy estimate is\hat{H}_{n}(X)=(1-(1/n) \log_{27}S_{n}) \log_{2} 27bits/symbol. If the subject does not know the true probability distribution for the stochastic process, then\hat{H}_{n}(X)is an asymptotic upper bound for the true entropy. IfXis stationary,E\hat{H}_{n}(X)\rightarrowH(X), H(X)being the true entropy of the process. Moreover, if X is ergodic, then by the Shannon-McMillan-Breiman theorem\hat{H}_{n}(X)\rightarrowH(X)with probability one. Preliminary indications are that English text has an entropy of approximately1.3bits/symbol, which agrees well with Shannon's estimate.

It is known that the expected codeword lengthL_{UD}of the best uniquely decodable (UD) code satisfiesH(X)\leqL_{UD}

An aspect of the measurement selection problem-the existence of anomalous orderings on the probability of error obtained by selected subsets of measurements-is discussed. It is shown that for any ordering on the probability of error as a function of the subset of measurements (subject to an obvious set monotonicity condition), there exists a multivariate normal two-hypothesis problem N(μ,K) versus N(μ,K) that exhibits this ordering. Thus no known nonexhaustive sequential k-measurement selection procedure is optimal, even for jointly normal measurements.

Sequential predictors for binary sequences with no assumptions upon the existence of an underlying process are discussed. The rule offered here induces an expected proportion of errors which differs by 0(n-½) from the Bayes envelope with respect to the observed kth order Markov structure. This extends the compound sequential Bayes work of Robbins, Hannan and Blackwell from sequences with perceived 0th order structure to sequences with perceived kth order structure. The proof follows immediately from applying the 0th order theory to 2k separate subsequences. These results show the essential robustness of procedures which play Bayes with respect to (a perhaps randomized) version of an estimate of the distribution of the past. Such procedures still have asymptotically good properties even when the underlying assumptions for which they were originally developed no longer hold.

If\{(X_i, Y_i)\}_{i=1}^{\infty}is a sequence of independent identically distributed discrete random pairs with(X_i, Y_i) ~ p(x,y), Slepian and Wolf have shown that theXprocess and theYprocess can be separately described to a common receiver at ratesR_XandR_Yhits per symbol ifR_X + R_Y > H(X,Y), R_X > H(X\midY), R_Y > H(Y\midX). A simpler proof of this result will be given. As a consequence it is established that the Slepian-Wolf theorem is true without change for arbitrary ergodic processes\{(X_i,Y_i)\}_{i=1}^{\infty}and countably infinite alphabets. The extension to an arbitrary number of processes is immediate.

Letp(y_1, y_2 \mid x)denote a discrete memoryless channel with a single sourceXand two independent receiversY_1andY_2. We exhibit an achievable region of rates(R_{11},R_{12},R_{22})at which independent information can be sent, respectively, to receiver 1, to both receivers 1 and 2, and to receiver 2. The achievability of the region is shown by using a version of the asymptotic equipartition property involving many simultaneous "typicality" constraints. These results immediately generalize to yield an achievable rate region for them-sendern-receiver channel in terms of standard mutual information quantities.

This paper shows that several transmitters operating in an additive white Gaussian noise environment can send at rates strictly dominating time-multiplex and frequency-multiplex rates by use of a superposition scheme that pools the time, bandwidth, and power allocations of the transmitters. This pooling can be achieved without cooperative action, except for agreement on the actual rate of transmission each transmitter will allow itself. The superposition scheme involves subtraction from the received signal of the estimated signals sent by the other transmitters, followed by decoding of the intended signal. This scheme has been shown to be optimal. We conclude that present methods of allocating different frequency bands to different transmitters are necessarily suboptimal.

Consider an item that belongs to one of two classes, θ = 0 or θ = 1, with equal probability. Suppose also that there are two measurement experiments E1and E2that can be performed, and suppose that the outcomes are independent (given θ). Let Eídenote an independent performance of experiment EI. Let Pe(E) denote the probability of error resulting from the performance of experiment E. Elashoff [1] gives an example of three experiments E1,E2,E3such that Pe(E1)e(E2)e(E3), but Pe(E1,E3)e(E1,E2). Toussaint [2] exhibits binary valued experiments satisfying Pe(E1)e(E2)e(E3), such that Pe(E2,E3)e(E1,E3)e(E1,E2). We shall give an example of binary valued experiments E1and E2such that Pe(E1)e(E2), but Pe(E2,E2')e(E1,E2)e(E1,E1'). Thus if one observation is allowed, E1is the best experiment. If two observations are allowed, then two independent copies of the ''worst'' experiment E2are preferred. This is true despite the conditional independence of the observations.

LetSbe a given subset of binary n-sequences. We provide an explicit scheme for calculating the index of any sequence inSaccording to its position in the lexicographic ordering ofS. A simple inverse algorithm is also given. Particularly nice formulas arise whenSis the set of alln-sequences of weightkand also whenSis the set of all sequences having a given empirical Markov property. Schalkwijk and Lynch have investigated the former case. The envisioned use of this indexing scheme is to transmit or store the index rather than the sequence, thus resulting in a data compression of(\log\midS\mid)/n.

We introduce the problem of a single source attempting to communicate information simultaneously to several receivers. The intent is to model the situation of a broadcaster with multiple receivers or a lecturer with many listeners. Thus several different channels with a common input alphabet are specified. We shall determine the families of simultaneously achievable transmission rates for many extreme classes of channels. Upper and lower bounds on the capacity region will be found, and it will be shown that the family of theoretically achievable rates dominates the family of rates achievable by previously known time-sharing and maximin procedures. This improvement is gained by superimposing high-rate information on low-rate information. All of these results lead to a new approach to the compound channels problem.

Huffman coding provides optimal source encoding for events of specified source probabilities. Gilbert has proposed a scheme for source encoding when these source probabilities are imperfectly known. This correspondence shows that Gilbert's scheme is a Bayes scheme against a certain natural prior distribution on the source probabilities. Consequently, since this prior distribution has nonzero mass everywhere, Gilbert's scheme is admissible in the sense that no source encoding has lower average code length for every choice of source probabilities.

This paper solves the classical two-armed-bandit problem under the finite-memory constraint described below. Given are probability densitiesp_0andp_1, and two experimentsAandB. It is not known which density is associated with which experiment. Thus the experimental outcomeYof experimentAis as likely to be distributed according top_0as it is to be distributed according top_1. It is desired to sequentially choose an experiment to be performed on the basis of past observations according to the algorithmT_n = f(T_{n-1}, e_n, Y_n), e_n = e(T_{n-1}), whereT_n \in \{1, 2, \cdots, m\}is the state of memory at timen, e_n \in \{A, B\}is the choice of experiment, andY_n, is the random variable observation. The goal is to maximize the asymptotic proportionrof uses of the experiment associated with densityp_0. Letl(y) = p_0 (y) / p_1 (y), and let\bar{l}and\bar{\bar{l}}denote the almost everywhere greatest lower bound and least upper bound onl(y). Let1 = \max {\bar{\bar{l}}, 1/\bar{l}}. Then the optimal value ofr, over allm-state algorithms(f, e), will be shown to bel^{m-1} / (l^{m-1} + 1). Ane-optimal family ofm-state algorithms will be demonstrated. In general, optimal algorithms do not exist, ande-optimal algorithms require artificial randomization.

LetR^{\ast}denote the Bayes risk (minimum expected loss) for the problem of estimating\theta \varepsilon \Theta, given an observed random variablex, joint probability distributionF(x,\theta), and loss functionL. Consider the problem in which the only knowledge ofFis that which can be inferred from samples(x_{1},\theta_{1}),(x_{2},\theta_{2}), \cdots ,(x_{n}, \theta_{n}), where the(x_{i}, \theta_{i})'sare independently identically distributed according toF. Let the nearest neighbor estimate of the parameter\thetaassociated with an observationxbe defined to be the parameter\theta_{n}^{'}associated with the nearest neighborx_{n}^{'}tox. Let R be the large sample risk of the nearest neighbor rule. It will be shown, for a wide range of probability distributions, thatR \leq 2R^{\ast}for metric loss functions andR = 2R^{\ast}for squared-error loss functions. A simple estimator using the nearestkneighbors yieldsR = R^{\ast} (1 + 1/k)in the squared-error loss case. In this sense, it can be said that at least haft the information in the infinite training set is contained in the nearest neighbor. This paper is an extension of earlier work[q from the problem of classification by the nearest neighbor rule to that of estimation. However, the unbounded loss functions in the estimation problem introduce additional problems concerning the convergence of the unconditional risk. Thus some work is devoted to the investigation of natural conditions on the underlying distribution assuring the desired convergence.

The nearest neighbor decision rule assigns to an unclassified sample point the classification of the nearest of a set of previously classified points. This rule is independent of the underlying joint distribution on the sample points and their classifications, and hence the probability of errorRof such a rule must be at least as great as the Bayes probability of errorR^{\ast}--the minimum probability of error over all decision rules taking underlying probability structure into account. However, in a large sample analysis, we will show in theM-category case thatR^{\ast} \leq R \leq R^{\ast}(2 --MR^{\ast}/(M-1)), where these bounds are the tightest possible, for all suitably smooth underlying distributions. Thus for any number of categories, the probability of error of the nearest neighbor rule is bounded above by twice the Bayes probability of error. In this sense, it may be said that half the classification information in an infinite sample set is contained in the nearest neighbor.

This paper develops the separating capacities of families of nonlinear decision surfaces by a direct application of a theorem in classical combinatorial geometry. It is shown that a family of surfaces having d degrees of freedom has a natural separating capacity of 2d pattern vectors, thus extending and unifying results of Winder and others on the pattern-separating capacity of hyperplanes. Applying these ideas to the vertices of a binary n-cube yields bounds on the number of spherically, quadratically, and, in general, nonlinearly separable Boolean functions of n variables. It is shown that the set of all surfaces which separate a dichotomy of an infinite, random, separable set of pattern vectors can be characterized, on the average, by a subset of only 2d extreme pattern vectors. In addition, the problem of generalizing the classifications on a labeled set of pattern points to the classification of a new point is defined, and it is found that the probability of ambiguous generalization is large unless the number of training patterns exceeds the capacity of the set of separating surfaces.