Misère End Play is a two-person constant sum game with perfect information. The game uses a deck of cards that consists of a single totally ordered suit of $2n$ cards. To begin play, the deck is divided into two hands of n cards each, held by players Left and Right, with one player designated as having the lead. The player on lead plays one of his cards, and the other player, after seeing it, plays one of his cards. The player with the higher card wins a “trick” and obtains the lead. The cards in the trick are removed and play continues until all cards are played. In Misère End Play each player's goal is to take as few tricks as possible. Misère End Play is shown to have a simple optimal strategy.

A simple (combinatorial) special case of the generalized Lloyd-Max (or quantization) problem is shown to be nondeterministic polynomial (NP)-complete. {\em A fortiori}, the general problem of communication theory, in its combinatorial forms, has at least that complexity.

From its very beginning, information theory has been pervaded by convexity arguments. Much of the necessary background was developed on an ad hoc basis without reference to the knowledge available from the mathematical study of convex sets and functions. Yet explicit use shown by examples.

The output of a source, the first of the two arguments of a distortion function, is seen by an encoder through a noisy channel. A decoder sees the encoder's signal through the usual communication channel. The second argument of the distortion function is obtained from the decoder's output via another noisy channel. The Dobrushin-Tsybakov reduction of this problem to a direct one is shown to follow at once from a "disconnection principle" for conditional expectations. The same principle applies to more general situations such as i) dependence between the noise variables acting in the input and output channels and ii) side information available only at the decoder.

A discrete random variableXis to be transmitted by means of a discrete signal. The receiver has prior knowledge of a discrete random variableYjointly distributed withX. The probability of error must be exactly zero, and the problem is to minimize the signal's alphabet size. In the case where the transmitter also has access to the value ofY, the problem is trivial and no advantage can be obtained by block coding over independent repetitions. If, however,Yis not known at the transmitter then the problem is equivalent to the chromatic number problem for graphs, and block coding may produce savings.

LetX, Ybe a pair of discrete random variables with a given joint probability distribution. For0 \leq x \leq H(X), the entropy ofX, define the functionF(x)as the infimum ofH(Y\mid W), the conditional entropy ofYgivenW, with respect to all discrete random variablesWsuch that a)H(X\mid W) = x, and b)WandYare conditionally independent givenX. This paper concerns the functionF, its properties, its calculation, and its applications to several problems in information theory.

The sharp lower boundf(x)on the per-symbol output entropy for a given per-symbol input entropyxis determined for stationary discrete memoryless channels; it is the lower convex envelope of the boundg(x)for a single channel use. The bounds agree for all noiseless channels and all binary channels. However, for nonbinary channels,gis not generally convex so that the bounds differ. Such is the case for the Hamming channels that generalize the binary symmetric channels. The bounds are of interest in connection with multiple-user communication, as exemplified by Wyner's applications of "Mrs. Gerber's lemma" (the bound for binary symmetric channels first obtained by Wyner and Ziv). These applications extend from the binary symmetric case to the. Hamming case. Doubly stochastic channels are characterized by the property of never decreasing entropy.

Without special assumptions as to the values of coefficients, the simplifications due to central symmetry in worst case estimation, for linear systems with convex constraints, can be obtained only in the case of (generalized) energy constraints.