Introduce a selector with Bernoulli distribution of parameter , and construct by taking its conditional law given to be , and its conditional law given to be . No prescribed joint law of is needed. Summing over the selector gives the desired mixture probability mass function. The conditional entropy is
Since conditioning cannot increase information entropy,
This proves the concavity of information entropy. The argument also covers infinite information entropies with the convention that a zero mixing weight contributes zero. At or , the mixture is the corresponding original law and equality is immediate.
For , the Poisson distribution gives
This information entropy is finite: for integer , while .
Fix . Take independent random variables and . Their convolution is
by the binomial theorem. Thus has Poisson distribution with parameter . Conditioning on only translates , so . The entropy monotonicity under independent addition yields .
In fact the inequality is strict. The covariance is positive, so and are not independent random variables. Their information entropies are finite, and the equality criterion from part (a) excludes equality. Therefore the Poisson entropy monotonicity gives the stronger conclusion
Use base-two logarithms and put , with . Zero-probability letters can be omitted. The random variables are self-information values, are IID, and have finite mean because the alphabet is finite. Independence gives
For an arbitrary , define the typical set
The weak law of large numbers implies . Every string in this set satisfies
This is the asymptotic equipartition property for the given finite IID source, here obtained directly from the weak law of large numbers.
For the upper bound, summing the lower bound on typical-string probabilities yields . For sufficiently large , its probability is at least , so it is an admissible set in the definition of . Hence
For the lower bound, let be any admissible set and write . Then
Each member of this intersection has probability at most . Therefore, for all sufficiently large ,
This applies in particular to a minimum-size admissible set, giving a liminf at least . Letting proves both existence and the value of the minimal high-probability source-set exponent:
For a deterministic source, and , consistent with the formula.
For coding, label the strings in an admissible set with distinct binary indices of length . A decoder reconstructs those strings exactly and may fail outside the set. Thus asymptotically bits per source symbol describe any fixed fraction of the probability mass. More strongly, every rate permits block codes with error tending to zero: choose , encode the typical strings individually and reserve one index for all other strings. The required number of indices is at most for large .
Conversely, a block encoder with at most outputs can reconstruct at most that many distinct input strings correctly. If , choose . Its success probability is at most
This gives the strong converse for fixed-rate source coding. It is the operational significance of the information entropy limit for reliable source encoding at a rate. The allowance of a small reconstruction error matters: a fixed-length code that must encode every possible string without error generally needs the larger rate .
We give the bounds for an alphabet of size , including the binary case . Let be a length- code with codewords and minimum Hamming distance at least , where . Write for the maximum code size at a given distance and
for the number of words in a Hamming ball of radius . The th term chooses the changed coordinates and the alternative symbols in each.
For the Hamming bound, put . Balls of radius around distinct codewords are disjoint: a common point would, by the triangle inequality, make their distance at most . Counting those balls inside the ambient words proves
No linearity is needed. For a linear code of dimension over , replace by .
For the Gilbert–Varshamov bound, construct a code greedily, adding any word at distance at least from all previously selected words, until none remains. The process terminates because the space is finite. Its maximality implies that the radius- balls around its codewords cover the whole space: an uncovered word could have been added. These balls may overlap, but the size of their union is at most the sum of their sizes. Hence the constructed code has , proving the existence bound
One may take the ceiling on the right because code size is integral.
For completeness, the sharper linear version is the Varshamov bound for linear codes. When is a prime power and , an linear code exists provided
Set and choose columns of an parity-check matrix in order. When choosing column , exclude all combinations of at most earlier columns, including the zero combination. There are at most forbidden vectors, smaller than by the assumed inequality. A column can therefore be chosen. Inductively every set of at most chosen columns is independent: a relation involving the newest one would express it as a combination of at most earlier columns. The kernel has dimension at least and minimum Hamming distance at least , since a low-weight kernel vector would be such a column relation. If its dimension is larger than , take a -dimensional subspace. This proves the stated linear existence claim; it does not assume the greedy nonlinear code was linear.
To derive the asymptotic bounds, define the q-ary entropy
with the continuous endpoint conventions. Its derivative is , so it is increasing on and has maximum one at . Stirling's formula gives, uniformly for integer ,
The sum defining is between its largest summand and times that summand. For radius fractions tending to , monotonicity of makes the largest exponent tend to . Consequently the Hamming ball volume exponent is
For , the exponent is one: use a radius fraction just below for a lower bound and for an upper bound.
Set and define the asymptotic rate-distance function by
The code rate is and the relative minimum distance is . A limsup suffices; no unproved existence of a limit for optimal code sizes is required. The packing radii have fraction tending to , so the finite Hamming bound and the volume exponent give the asymptotic Hamming bound
The covering radii have fraction tending to , giving the asymptotic Gilbert–Varshamov bound
For larger , this covering argument gives only the trivial lower bound zero, not the expression obtained by extending the decreasing information entropy function beyond its maximum.
The asymptotic lower bound is also achievable by linear codes over a finite field. For and sufficiently large , take redundancy , so . The linear existence condition produces dimension at least ; its rate has liminf at least . At , use the whole space, of rate one. In particular, for binary codes the bounds reduce to
where is the binary entropy function.
For each , choose a proper coloring minimizing its color information entropy , so its coloring entropy weight is . A minimizing coloring exists: up to relabeling there are only finitely many partitions of its finite vertex set into color classes. Use independent dummy colors with the same marginal law as before. The marginal and conditional-entropy calculations in part (i) remain valid for any number of colors. Also any pair of vertices is joined in some covering graph and hence receives different forced colors there, so the full color vector still determines . Thus
Choose uniformly among the vertices. For each covering graph use a proper binary coloring, and fill the color of an absent vertex with an independent random color having the same law as the color of a uniform vertex of that graph, as in the question's construction. Write for that color information entropy, so . The marginal distribution of is precisely this color law, and the variables are conditionally independent given : present colors are deterministic and absent colors use independent dummy draws. Therefore
Any two distinct vertices are joined in some and have different forced colors there. They cannot both be compatible with the same observed color vector, so . The mutual information identity now gives
and hence .
Let be the number of independent sets of the biregular graph . Choose one such set uniformly and write . All information entropies below use logarithms to base two, so
We will prove .
We state and justify the entropy facts used. For a finite-valued random variable , with . Its conditional entropy is the mean of this quantity over the conditioning variable. Factoring the joint probabilities proves the chain rule for information entropy, . Conditioning reduces entropy: . To see this, condition on and use concavity of to compare the mixture of the conditional distributions given with their mean entropy.
The precise Shearer inequality needed here is: if subsets of the indices of a finite random vector cover every index at least times, then . To prove it, order the indices. The chain rule for information entropy expands
The inequality is conditioning reduces entropy. Summing over counts each nonnegative conditional term at least times and proves the assertion.
For every , its vertex neighbourhood has vertices. Every lies in exactly of these neighbourhoods. Hence Shearer inequality gives
Let , the probability that no neighbour of is selected. Conditional on a particular selected subset of , a vertex with a selected neighbour is forbidden, and all other vertices of are available. Because there are no edges within , every subset of the available vertices is a valid completion. Uniform choice of makes these completions equally likely. The available coordinates are therefore independent fair binary choices, each of entropy one, and the forbidden coordinates are zero. Averaging their number gives
By the chain rule for information entropy,
It remains to bound each bracket. Let , a binary vector of length , with distribution on , and put . Assign weight to the all-zero vector and weight to every nonzero vector. Then
The first inequality is Jensen's inequality for the concave logarithm; the weights sum to . This explicitly handles zero probabilities and does not assume the neighbourhood indicators are independent.
There are right vertices, so combining the bounds and using gives
Exponentiating proves the required independent-set bound for biregular graphs. The proof uses both degree constraints: supplies the neighbourhood-cover multiplicity and the conditional-completion weight, while determines the number of neighbourhood patterns.
For separate binary observations, the saturated model fits each outcome exactly and has maximized log-likelihood zero. With , the residual deviance is therefore
Use the identity in part (b) to replace by in its first term:
Thus the deviance is twice the sum of the fitted binary information entropies. A deviance goodness-of-fit test against is unreliable for individual ungrouped binary observations: there is only one trial per saturated-model parameter, so the usual large-cell-count approximation fails. Deviance differences between fixed-dimensional nested logistic regression models can still support a likelihood-ratio test, subject to its usual regularity assumptions.
The three tree models are respectively , , and , with independent Bernoulli random variables conditional on the covariates. Testing the additional severity effect gives
Under , its reference distribution is asymptotically . The -value is approximately , giving overwhelming evidence that severity improves the fitted model. Holding severity fixed, doubling increases by one and multiplies the odds by
This is an odds ratio, not a multiplication of the event probability itself.
The empty family satisfies the bound, so assume is nonempty and choose a graph according to the uniform distribution on a finite set . Let be its random vector of edge indicators, indexed by . Then its information entropy is .
For each vertex , put , so records the graph neighbourhood of . The possible graph neighbourhoods form an intersecting family of subsets of : the graph intersection of any two members of has no isolated vertex at . A subset and its complement cannot both occur. Pairing the subsets into complementary pairs gives at most possible graph neighbourhoods. The maximum entropy on a finite alphabet therefore gives
This argument applies for . For the assumed nonempty family cannot exist, since its only possible graph has an isolated vertex.
Each edge belongs to exactly two of the sets . To obtain the needed instance of Shearer inequality directly from the preceding compression argument, repeatedly apply a union-intersection compression to incomparable members of the multiset . Each such step strictly increases , by
The potential is bounded and integer-valued, so the process terminates in a chain under inclusion. Coordinate multiplicities stay equal to two, so, for , the terminal chain consists of two copies of and empty sets. The compression of an entropy sum now gives
Exponentiating proves the entropy bound for graphs with isolated-vertex-free intersections:
An elementary union-intersection compression replaces two occurrences in a multiset by . By entropy submodularity, this changes the sum of information entropies by
A compression of an entropy sum is obtained by iterating these elementary union-intersection compressions. Summing the inequalities over the sequence, with repetitions counted according to their multiset multiplicities, proves the required monotonicity:
Neither the number of occurrences of an individual coordinate nor the total number of sets changes under union-intersection compression.
Take information entropy in bits and put . Write , , and . The chain rule for information entropy gives
The last line uses nonnegativity of conditional mutual information, equivalently the conditional version of conditioning reduces entropy. All random variables are finite-valued, so every conditional entropy here is finite. Therefore the entropy set function is a submodular set function:
This is entropy submodularity, with equality precisely when and satisfy conditional independence given .
On a probability measure-preserving system, for a finite measurable partition , the entropy of a finite measurable partition is
Use natural logarithms, so information entropy is measured in nats; another fixed logarithm base rescales all answers. The join of measurable partitions is their common refinement, and write , with an empty join the trivial partition. The entropy rate of a measurable partition and Kolmogorov-Sinai entropy are respectively
The block entropies form a subadditive sequence, so the first limit exists by the Fekete lemma. For finite partitions the conditional entropy of finite measurable partitions is .
Put and for . The chain rule for information entropy, applied from the last coordinate backwards, and measure preservation give
The second equality uses invariance of the joint partition atom probabilities under the common pullback ; invertibility is unnecessary. Since conditioning reduces entropy, decreases to a nonnegative limit . The Cesaro convergence of a sequence of this convergent sequence has the same limit. Therefore
Equivalently , where . Here conditional entropy of a countable measurable partition conditioned on a sigma-algebra is computed using conditional partition atom probabilities; the martingale convergence theorem gives continuity under increasing conditioning sigma-algebras. This is the infinite-future formula for partition entropy rate.
The Kolmogorov-Sinai generator theorem states that if a finite or countable measurable partition has finite entropy of a countable measurable partition and its iterates generate the whole completed sigma-algebra modulo null sets, then . For an invertible system, generating means modulo null sets. For a noninvertible system a one-sided generator, using , suffices. The two-sided and one-sided versions must not be confused.
For a Bernoulli shift with discrete symbol probabilities , the coordinate-zero measurable partition has independent coordinate iterates. Thus
For a finite alphabet the coordinate partition is a generator of finite entropy of a finite measurable partition; on the two-sided sequence space use all integer coordinate iterates, and on the one-sided space use the nonnegative ones. The Kolmogorov-Sinai generator theorem proves the displayed answer in both cases. The same calculation applies to countably many symbols when their Shannon entropy is finite, using the countable finite-entropy version of the theorem. If the Shannon entropy is infinite, merge all but the first symbols into one cell. These finite coordinate partitions have entropy rate , so the system entropy is infinite. Zero-probability symbols contribute zero. In particular a fair -symbol shift has entropy .
For the final assertion, let and complete it modulo null sets. The approximation property forces modulo null sets. Indeed for each , choose approximating sets from finite blocks with error tending to zero. Their indicators approach in , and is a closed vector subspace, so is -measurable modulo a null set.
Invertibility now gives modulo null sets. In particular the present partition is measurable with respect to its entire future, so . The infinite-future formula gives . Since the given one-sided generator is also a two-sided generator, the Kolmogorov-Sinai generator theorem finishes the proof:
This is finite one-sided generator of an invertible system forces zero entropy. Invertibility is essential: a fair binary one-sided Bernoulli shift has a finite one-sided generator and Kolmogorov-Sinai entropy .
Take every logarithm in base two. The information entropy of is
with . If the codeword has length , then its expected codeword length is
For any decipherable code, the Kraft inequality gives
Define the probability distribution . By Gibbs inequality,
Since ,
Conversely, choose the integer lengths
Then , so their Kraft sum is at most one and the converse part of Kraft's inequality supplies a binary prefix code. Moreover,
Thus the minimum expected length satisfies the Shannon noiseless coding theorem
For a decipherable code with arbitrary lengths , apply the lower bound to the uniform source . Its entropy is and its expected length is . Hence
the total length lower bound for a decipherable binary code.
Now consider the cumulative construction. Since
and cannot have the same first binary digits: numbers sharing those digits lie in one half-open dyadic interval of length . Also, implies . Therefore no earlier codeword is a prefix of a later one, and no later, weakly longer codeword can be a prefix of an earlier one. The cumulative Shannon code is thus a prefix code, hence decipherable.
An optimal code minimizes expected codeword length over all decipherable codes for the specified source probabilities. The cumulative construction need not be optimal. For example, if
then and the construction gives codewords and , with expected length . The prefix code has expected length , so the constructed code is not optimal. In general, Huffman coding produces an optimal prefix code.
Because and are independent random variables, conditioning on merely translates . The conditional entropy under a deterministic change of variables and the fact that conditioning reduces entropy therefore give
Interchanging and similarly gives , and hence
The proof applies to countable alphabets whenever the displayed information entropies are finite.
On , part b gives . Hence the information entropy of the conditional law satisfies
Parts d and e imply
Exponentiation proves .
The source is reliably encodable at rate if, for each block length , there are an encoder with at most outputs and a decoder such that the block error probability
tends to zero as .
Its information rate is the limiting information entropy per source symbol,
when this limit exists.
The unicity distance is the least ciphertext length for which the key is determined, or in the usual approximation the length at which the expected number of spurious keys falls to about zero. Assume equiprobable keys, a stationary plaintext source of information entropy rate , and ciphertext symbols that are approximately uniform on . The language redundancy per symbol is
The key equivocation is then approximated by
Hence the classical closed-form estimate is
The axioms for information entropy give the formula and hence the chain rule for information entropy
Because conditioning reduces entropy, , and therefore
This is subadditivity of information entropy.
For the entropy submodularity rule, apply the chain rule for information entropy twice:
The last quantity is conditional mutual information, whose nonnegativity again expresses that conditioning reduces entropy.
Let be the set of valid quintuples and choose uniformly from . Then
Apply Shearer's inequality to the ten pairs . Every index occurs in four pairs, so
Put . Since , it has cardinality . For each element of , its membership bits in are one of ; outside they are forced to be . Thus at most ordered pairs have any prescribed union. The chain rule for information entropy, conditional entropy, and the support bound for information entropy give
because every belongs to . There are ten pairs, hence
Exponentiating proves
which is the five-variable case of the entropy bound for pairwise-union tuples.
For feasible mass functions at distortion levels , the mixture has nonzero-symbol mass at most . Concavity of information entropy gives
Taking maximizing sequences proves