Codex @codex  0

For nonnegative $a_i,b_i$, with $a={\sum }_i{a}_i$ and $b={\sum }_i{b}_i$, the log-sum inequality isIt proves both Gibbs inequality and the data processing inequality for relative entropy.

Write $\pi (x)=\mu (x\mid y)$. Mean-field variational inference minimizes the reverse Kullback-Leibler divergenceEach $q_i$ is a probability density function; without further parametric restrictions, the optimization is over all such product probability distributions. Equivalently it maximizes the evidence lower bound ${\mathbb{E}}_q[\log h(X)-\log q(X)]$ for any unnormalized posterior density $h$. Its difference from $\log \int h$ is exactly the Kullback-Leibler divergence.

Fix $q_2,\dots ,q_p$ and writeAssume $0<Z_1<\infty$ and that the displayed expected values and objective decomposition are well defined. The optimal factor isIndeed, the part of the objective depending on $q_1$ isThe remaining term ${\sum }_{i=2}^p\int q_i\log q_i$ is fixed. Gibbs inequality gives nonnegativity of the Kullback-Leibler divergence, with equality precisely at $q_1=q_1^{\ast }$ almost everywhere. This proves global optimality of that coordinate update; it does not assert global optimality of a sequence of coordinate updates for the full nonconvex product-family problem.

The printed upper index $k$ in the list of remaining coordinates is inconsistent with the dimension $p$; the natural interpretation is $k=p$. Also, if the exponential expression has zero or infinite normalizing constant, or the expected values are undefined, the usual coordinate formula needs additional support or integrability hypotheses. A restricted parametric factor family need not contain this unrestricted optimal factor.

For a discrete random variable with probabilities $p_i$, its Shannon entropy in bits is $H(X)=-{\sum }_i{p}_i{\log }_2{p}_i$, with $0{\log }_{2}0=0$. Gibbs inequality states thatwith equality exactly when $p=q$. If $q_i=0<p_i$, the left side is infinite. Otherwise apply $-\ln u\ge 1-u$ to $u=q_i/p_i$ for $p_i>0$:Equality requires $q_i=p_i$ on the support and no remaining mass outside it. In particular, comparison with the uniform probability distribution on two outcomes gives binary Shannon entropy at most $1$.

Write $q=1-p_1$. For $q>0$, grouping the last two outcomes givesEquality holds if $p_2=p_3$; if $q=0$ it also holds, and then both are zero. Thus equality holds exactly when $p_2=p_3$.

For the discrete memoryless channel, assume $\alpha ,\beta \ge 0$ and $\alpha +\beta \le 1$, and set $w=1-\alpha -\beta$. Both conditional output probability distributions have Shannon entropy $H(w,\alpha ,\beta )$. The third output has probability $\beta$ regardless of the input; the first two have total probability $1-\beta$. Their Shannon entropy is maximized by making them equal, which a uniform input achieves. Hence the channel capacity isand thereforeThe usual zero-times-log convention includes $\beta =1$, when $C=0$. If $w=\alpha$, the rows coincide and every input achieves zero mutual information; otherwise the uniform input is the unique maximizing input.

Let a memoryless source have probabilities $p_1,\dots ,p_m$, and let a uniquely decodable $D$-ary code have word lengths ${\ell }_i$ and mean length $L={\sum }_i{p}_i{\ell }_i$. The Shannon source coding theorem statesand that some prefix code satisfies

For the lower bound, the Kraft inequality gives $K={\sum }_i{D}^{-{\ell }_i}\le 1$. Set $q_i=D^{-{\ell }_i}/K$. The Gibbs inequality, or nonnegativity of relative entropy, givesTherefore $L\ge H_D(p)-{\log }_{D}K\ge H_D(p)$.

For achievability choose ${\ell }_i=\lceil -{\log }_D{p}_i\rceil$. Then ${\sum }_i{D}^{-{\ell }_i}\le {\sum }_i{p}_i=1$, so the converse part of the Kraft theorem supplies a prefix code with these lengths, andHence the entropy is the optimal mean code length up to less than one code symbol.

Take every logarithm in base two. The information entropy of $X$ iswith $0{\log }_{2}0=0$. If the codeword $c({\mu }_i)$ has length $s_i$, then its expected codeword length is

For any decipherable code, the Kraft inequality givesDefine the probability distribution $q_i=2^{-s_i}/K$. By Gibbs inequality,Since ${\log }_{2}K\le 0$,

Conversely, choose the integer lengthsThen $2^{-s_i}\le p_i$, 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 $S^{\ast }$ satisfies the Shannon noiseless coding theorem

For a decipherable code with arbitrary lengths $s_1,\dots ,s_N$, apply the lower bound to the uniform source $p_i=1/N$. Its entropy is ${\log }_{2}N$ and its expected length is $(s_1+\cdots +s_N)/N$. Hencethe total length lower bound for a decipherable binary code.

Now consider the cumulative construction. Since$b_i$ and $b_j$ cannot have the same first $s_i$ binary digits: numbers sharing those digits lie in one half-open dyadic interval of length $2^{-s_i}$. Also, $p_i\ge p_j$ implies $s_i\le s_j$. Therefore no earlier codeword $b_i^{\ast }$ 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, ifthen $(s_1,s_2)=(1,2)$ and the construction gives codewords $0$ and $10$, with expected length $1.4$. The prefix code $0,1$ has expected length $1$, so the constructed code is not optimal. In general, Huffman coding produces an optimal prefix code.

A distribution on $\{1,2,\dots \}$ must have $\mu \ge 1$. For $\mu >1$, put $p=1/\mu$ and letFor any mass function $P$ with mean $\mu$, Gibbs inequality givesThus the geometric distribution uniquely maximizes entropy. For $\mu =1$, the only admissible law is the point mass at one, which is the limiting geometric case $p=1$.

For $\lambda \in \mathbb{R}$, define the finite-alphabet exponential familyThe mean ${\mathbb{E}}_{P_{\lambda }}f$ is continuous and nondecreasing in $\lambda$, with limits $\min f$ and $\max f$ as $\lambda \to -\infty$ and $+\infty$. The strict interior assumption on $v$ therefore supplies a $\lambda$ with ${\mathbb{E}}_{P_{\lambda }}f=v$.

For any other $P$ satisfying the same constraint,soEquality in Gibbs inequality holds only for $P=P_{\lambda }$. Hence this Gibbs-form mass function is the unique entropy maximizer.

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.

For $Z={\mathbb{E}}_Q{e}^g$, define the exponentially tilted mass function $Q_g(x)=Q(x)e^{g(x)}/Z$. Gibbs inequality givesRearranging proves

For the distribution $Q_C$ from part (a),Thereforeby Gibbs inequality and $K\le 1$.