At an interior tree node write $A,B$ for the total masses in its two children, and $S=A+B$. Counting path lengths and telescoping the Shannon entropy over the binary decisions givesIndeed each symbol contributes its probability once per ancestral interior node to the first sum. In the second sum, expanding $Sh(A/S)=S{\log }_{2}S-A{\log }_{2}A-B{\log }_{2}B$ cancels the interior terms and leaves the source Shannon entropy. The supplied inequality now bounds redundancy byConsider the cut between adjacent symbols $k,k+1$ made at one node. If its left side is heavier, moving its last symbol to the right must not improve the chosen cut. Writing $\Delta =A-B\ge 0$, this says $|\Delta -2p_k|\ge \Delta$, which implies $\Delta \le p_k$; when the left side is a singleton the same bound is immediate. If the right side is heavier, the corresponding argument gives $|A-B|\le p_{k+1}$. In all casesRecursive subdivision of contiguous blocks uses each original gap exactly once. Summing over the $m-1$ gaps therefore givesproving $\bar{s}<H(X)+2$. If probabilities are already nonincreasing, each maximum is $p_k$ and the improved bound is $\bar{s}-H(X)\le 1-p_m<1$. Thus the sorted version has expected length less than $H(X)+1$, although it need not be optimal. For one symbol the assertions hold directly. This is the Fano slice code redundancy bound.

Work on the source support, so its listed probabilities are positive; zero-probability symbols may be omitted. An optimal binary prefix code minimizes the expected codeword length for that distribution. The same optimal expected length is attained when optimization is over uniquely decipherable codes, by the converse and existence parts of Kraft–McMillan inequality.

Choose Shannon lengths ${\ell }_k=\lceil -{\log }_2{p}_k\rceil$. They satisfy $2^{-{\ell }_k}\le p_k$, so the preceding existence theorem gives a prefix code with those lengths. Also ${\ell }_k<-{\log }_2{p}_k+1$ for every symbol, including the integer cases. Thus its expected length is less than $H(X)+1$. An optimal code cannot have a larger expected length, provingFor a deterministic one-symbol source the empty word has length zero, consistent with this bound.

A binary prefix code assigns distinct finite binary strings to the source symbols, with no assigned string a prefix of another. It is instantaneous because a complete codeword is recognized without needing the next word's bits.

Associate a word of length $\ell$ with its dyadic subinterval of $[0,1)$ of length $2^{-\ell }$. A prefix relation corresponds to interval containment. Prefix-free words therefore give disjoint intervals, whose total length is at most one. This proves necessity of Kraft inequality.

For sufficiency, sort the requested nonnegative integer lengths increasingly and construct a code greedily in a binary tree. At depth ${\ell }_j$, the preceding codewords forbid exactly ${\sum }_{i<j}{2}^{{\ell }_j-{\ell }_i}$ nodes. The assumed inequality, retaining the positive contribution of the present word, bounds this integer by $2^{{\ell }_j}-1$. Thus at least one node is available; choose it. It is not below an earlier codeword, and the nondecreasing lengths prevent it from being a proper ancestor of an earlier word. Continue to obtain a prefix code of all the required lengths. Hence

Independence gives $P(X=Y)={\sum }_r{p}_r{q}_r={\mathbb{E}}_p[2^{{\log }_2{q}_X}]$. The given exponential convexity inequality therefore yieldsTaking complementary probabilities provesThe strict positivity of the entries of $q$ makes all logarithms appearing in this finite expectation well defined.

Conditional entropy is $H(U\mid V)={\sum }_{v}P(V=v)H(U\mid V=v)$. Factor the joint probabilities as $P(U=u,V=v)=P(V=v)P(U=u\mid V=v)$ and expand their logarithms. This gives $H(X,Y)=H(Y)+H(X\mid Y)$. Applying the same identity within each conditional law given $Z=z$ and averaging gives $H(X,Y\mid Z)=H(X\mid Z)+H(Y\mid X,Z)$.

Put $E=1_{\{X\ne Y\}}$ and $\epsilon =P(E=1)$. Since $E$ is a function of $X,Y$, the conditional chain rule givesBy Gibbs inequality, the first term is at most $h(\epsilon )\le 1$. When $E=0$, $Y$ determines $X$. When $E=1$, there are at most $n-1$ possibilities for $X$ given $Y$, so its conditional entropy is at most ${\log }_2(n-1)$. ThereforeFor $n>2$, rearrangement provesThe printed division presupposes $n>2$. For $n=2$ its denominator is zero, and the meaningful statement is the stronger undivided inequality $H(X\mid Y)\le h(\epsilon )$. For $n=1$ the variables agree surely.

Use the convention $0{\log }_{2}0=0$. On the positive support of $p$, the given logarithm inequality givesThe logarithm is strictly concave, so its supporting line at one has equality only there. More explicitly, the given global bound forces $c=1/{\log }_{e}2$ by differentiation at one, and $x-1-{\log }_{e}x$ vanishes only at one. Equality above therefore requires $p_r=q_r$ on the positive support, and no mass of $q$ outside it. Thus equality holds exactly when $p=q$.

For the uniform distribution $q_r=1/n$, the divergence is $D(p,q)={\log }_{2}n-H(p)$. Its nonnegativity gives $\boxed{H(p)\le {\log }_{2}n}$, with equality precisely for the uniform law.

A scalar Tonelli existence theorem states: if $f(x,y,p)$ is continuous, convex in $p$, and has a uniform superlinear lower bound $f(x,y,p)\ge \Theta (|p|)-C$ with $\Theta (r)/r\to \infty$, and at least one fixed-endpoint admissible absolutely continuous function has finite energy, then the energy attains its infimum in the fixed-endpoint $W^{1,1}$ class. One may take $\Theta$ nonnegative and convex. The lower bound makes derivatives uniformly integrable; endpoint control then gives uniform compactness of a minimizing sequence, and convexity supplies the required lower semicontinuity.

For the specified functional, the integrand is continuous, nonnegative, and convex in the derivative, withThe affine function $u_0(x)=2x-1$ has the required endpoints and finite energy. Thus a global minimizer exists. In fact any finite-energy minimizer belongs to $W^{1,52}$, since its derivative's 52nd power is integrable.

It is unique. The admissible class is convex, and the integrand is strictly convex in $(y,p)$: $|p{|}^{52}$ and $|y{|}^{2011}$ are strictly convex, with the latter multiplied by $e^x>0$. If two distinct admissible finite-energy functions minimized the energy, their midpoint would have strictly smaller energy. Distinct continuous representatives differ on a set of positive measure, so the strict integral inequality really applies. This contradiction proves uniqueness.

The variational terminology refers to the size of a neighborhood, rather than weak versus strong convergence in a Banach space. The definitions in the two numbered children giveThe second implication holds because smallness in $W^{1,\infty }$ implies smallness in the uniform norm. Reverse implications need not hold.

For differentiable $f$ in its slope variable, define the Weierstrass excess functionThe strengthened Weierstrass condition means that some $\delta >0$ givesIt requires support at nearby heights and nearby reference slopes, while the trial slope $q$ is arbitrary. Requiring this only exactly on the curve is the unstrengthened necessary condition.

A standard Weierstrass sufficient condition assumes the usual $C^2$ smoothness of $f$, $u\in \mathcal{A}\cap C^1$, the weak Euler-Lagrange equation, a coercively positive second variation, and the strengthened condition above. Explicitly, for some $c>0$,for zero-endpoint variations. Then $u$ is a strong local minimizer. If the excess is strictly positive for $q\ne p$ throughout the tube, the strong minimum is strict. The second-variation hypothesis supplies a neighboring field of extremals. Its slope $p(x,y)$ gives the comparison identityfor uniformly close admissible $v$. This explains how the condition controls competitors with large derivatives.

For the supporting inequality, assume first that $F$ is convex and fix $z,z_0$. For $0<t\le 1$,Subtract $F(z_0)$, divide by $t$ and let $t\downarrow 0$. Differentiability givesConversely assume this inequality for every pair. Put $w=(1-t)z_0+tz$ and apply it with base point $w$ to both $z_0$ and $z$. Multiply those two inequalities by $1-t$ and $t$ and add. The gradient terms cancel, proving $F(w)\le (1-t)F(z_0)+tF(z)$. Thus the supporting inequality characterizes a differentiable convex function.

For the integral inequality let $\bar{z}=|\Omega {|}^{-1}{\int }_{\Omega }u$. Apply the supporting inequality at $\bar{z}$ to $u(x)$ and integrate. Its affine term has integral $DF(\bar{z})\cdot ({\int }_{\Omega }u-|\Omega |\bar{z})=0$, yieldingThis is Jensen's inequality. Since $u$ is integrable, the supporting affine lower bound has integrable negative part, so the right side is well-defined as an extended real integral. If its positive part is infinite, the inequality remains valid.