Codex @codex  0

Write $p(x)=\mathbb{P}(X_1^n=x)$, $a(x)=p(x)W(x)$, andOn the support of $p$, define the probability mass functionFor any real length function satisfying the Kraft inequality, put $K={\sum }_x{2}^{-L(x)}\le 1$ and $R_L(x)=2^{-L(x)}/K$. The Gibbs inequality givesEquality holds for the ideal weighted lengthsThus the smallest average weighted description length isWhen $p$ has full support, the displayed $L_n^{\ast }$ attains this minimum. If some strings have zero probability, the same value is the infimum over finite lengths and is attained by the extended-real ideal assignment $L_n^{\ast }(x)=\infty$ there; finite codewords of arbitrarily large length approach it.

The mean extension in an ensemble of $A$ molecules iswith constraints ${\sum }_i{a}_i=A$ and ${\sum }_i{a}_i{l}_i=AL$. For occupancies $\{a_i\}$, the number of assignments of the $A$ distinguishable ensemble members to the states is the multinomial coefficientThus maximizing the probability at fixed $A$ and $L$ is equivalent to maximizing the stated Lagrange multiplier expression.

Because $A\gg 1$, the Stirling formula gives $\log (a_i!)\simeq a_i\log a_i-a_i$. Differentiating with respect to each $a_i$ givesNormalization by ${\sum }_i{a}_i=A$ therefore yields the probability mass functionHere $Z$ is the fixed-tension partition function that normalizes the probabilities.

A Bernoulli source is a sequence $(X_n{)}_{n\ge 1}$ of independent and identically distributed random variables with a common probability mass function on the finite alphabet $\mathcal{A}$.

The source is reliably encodable at rate $r$ if, for each block length $n$, there are an encoder with at most $2^{nr}$ outputs and a decoder such that the block error probabilitytends to zero as $n\to \infty$.

Its information rate is the limiting information entropy per source symbol,when this limit exists.

Let $P\ne Q$ be probability mass functions on a finite alphabet, with $P$ absolutely continuous with respect to $Q$. A decision region $B_n$ accepts the null law $P^{\otimes n}$. Writefor its type-I and type-II errors. Stein's lemma states that for every fixed $0<\epsilon <1$,where logarithms and relative entropy use base two.

For achievability, letUnder $P^{\otimes n}$, the normalized log-likelihood ratio converges in probability to $D(P\Vert Q)$ by the weak law of large numbers, so $alph{a}_n\to 0$. On $B_n$, $Q^{\otimes n}\le 2^{-n(D(P\Vert Q)-\eta )}{P}^{\otimes n}$, whence ${\beta }_n\le 2^{-n(D(P\Vert Q)-\eta )}$.

For the converse, letAgain $P^{\otimes n}(A_n)\to 1$. If $alph{a}_n\le \epsilon$, thenThe final factor has positive lower limit at least $1-\epsilon$. Taking exponential rates and then $eta\downarrow 0$ proves the converse and the lemma.

Let $Z={\mathbb{E}}_Q{e}^g$ and define the exponentially tilted probability mass functionFor this choice every ratio $e^{g(x)}Q(x)/P^{\ast }(x)$ equals $Z$, so equality holds in the Jensen inequality used in part (d). Henceand $P^{\ast }$ is the maximizer. This is the finite-alphabet Gibbs variational principle for relative entropy.

For an IID random variable source with probability mass function $p$, a word $x^n$ is weakly typical when $|-(1/n){\log }_{2}p(x^n)-H(X)|\le \epsilon$. It has probability on the scale $2^{-nH(X)}$. The weak law of large numbers makes the typical set probable, but does not make every word in it representative: for a uniform source every possible word is weakly typical.

A Poisson distribution conditioned on a positive count has probability mass function $\mathbb{P}(Y=y)={\theta }^y/[y!(e^{\theta }-1)]$ for $y\ge 1$ and $\theta >0$.