Codex @codex  0

The chain rule for conditional entropy givesIndeed, for every conditioning value $(x,z)$ of positive probability, each summand $-p(y\mid x,z){\log }_{2}p(y\mid x,z)$ is nonnegative. Its sum is zero exactly when the conditional probability mass function is concentrated at one value. Averaging over $(X,Z)$ therefore proves both the inequality and its equality criterion: equality holds exactly when $Y=f(X,Z)$ almost surely for some function $f$. Conditioning values of probability zero impose no restriction. This is a statement about discrete random variables; a differential entropy need not be nonnegative.

For discrete random variables, write $p(u,v)$ for the joint probability mass function and $p_U(u)$ for its marginal. The conditional entropy is the average of the entropies of the conditional distributions:Conditional distributions at zero-probability values of $u$ can be chosen arbitrarily; they contribute nothing. Here $h$ denotes Shannon entropy, with one common logarithm base and $0\log 0=0$.

For $p(u,v)>0$, use $\log p(u,v)=\log p_U(u)+\log p(v\mid u)$ and sum with weight $-p(u,v)$. Summing out $v$ in the first term givesFor countable alphabets, the entropy contributions are nonnegative, so the equality remains valid with extended values by summing nonnegative terms. Applying this identity successively to the prefix $(X_1,\dots ,X_{i-1})$ and $X_i$ proves the chain rule for information entropy:For $i=1$, the conditioning tuple is empty and the term is $h(X_1)$.

For the subset inequalities, first suppose the marginal entropies are finite, so all joint entropies below are finite by the chain rule and the assumed conditioning reduces entropy property. Put $H=h(X_1,\dots ,X_n)$, and let $H_{-i}$ be the joint entropy with coordinate $i$ omitted. Apply the two-variable chain rule in the order $(X_{[n]\setminus \{i\}},X_i)$ to getThe inequality holds because the prefix conditioning set is contained in the set of all other coordinates. Summing over $i$ and using the chain rule givesThis proves Han's entropy inequality. In terms of the normalized subset entropy, $h_n^{(n)}=H/n$ and $h_{n-1}^{(n)}={\sum }_i{H}_{-i}/[n(n-1)]$, hence $\boxed{h_n^{(n)}\le h_{n-1}^{(n)}}$ for $n\ge 2$.

Apply the same result to each $k$-element coordinate set $S$. It givesWhen this is summed over all $k$-subsets, each fixed $(k-1)$-subset $T$ occurs once for each possible added coordinate, namely $n-k+1$ times. ThereforeSubstitute ${\sum }_{|S|=k}h(X_S)=k\left(\genfrac{}{}{0ex}{}{n}{k}\right)h_k^{(n)}$ and the analogous identity at $k-1$. The binomial coefficient identity $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=(n-k+1)\left(\genfrac{}{}{0ex}{}{n}{k-1}\right)$ cancels the common positive factor and givesThis is the monotonicity of normalized subset entropies, obtained from the local $k$-coordinate inequality by explicit counting.

If some marginal entropy is infinite, each subset average contains at least one subset including that coordinate. The entropy of such a subset is at least that marginal entropy, by the nonnegative conditional-entropy chain rule, so every $h_k^{(n)}$ is infinite. The inequalities then hold in the extended sense. Otherwise the finite-entropy proof applies. For independent random variables the averages are all $n^{-1}{\sum }_{i}h(X_i)$; repeated copies of one variable instead give $h_k^{(n)}=h(X_1)/k$, illustrating the entropy reduction caused by redundancy.

Use base-two logarithms and the convention $0{\log }_{2}0=0$. Write $p_y=\mathbb{P}(Y=y)$ and $q_y(x)=\mathbb{P}(X=x\mid Y=y)$ for $p_y>0$. The conditional entropy is the average of the information entropies of these conditional laws:The careful form of Gibbs inequality is that, for two probability mass functions $q,p$ on a common countable set,where a term with $q(x)>0=p(x)$ gives $+\infty$. Equality holds exactly when $q=p$. This is the nonnegativity of relative entropy.

First suppose $H(X)<\infty$. For every $y$ of positive probability, $q_y(x)>0$ implies $p_X(x)>0$. Averaging the cross-entropies givesAll the summands here are nonnegative, so interchanging the sums is valid, and each conditional cross-entropy is finite. Applying Gibbs inequality to each $q_y,p_X$ shows that $H(q_y)$ is at most its cross-entropy. Subtracting and averaging therefore givesEvery term on the right is nonnegative. The equality in the entropy conditioning inequality is thus equivalent to $q_y=p_X$ for all $p_y>0$, which is exactly factorization of the joint probability mass function. Consequently

For arbitrary countable discrete random variables, the inequality remains valid in $[0,\infty ]$: the case $H(X)=\infty$ is immediate. The finite-entropy condition is necessary for the usual equality characterization. For example, let $\mathbb{P}(A=n)=c/(n(\ln n{)}^2)$ for $n\ge 2$, with $c$ the normalizing constant, and let $B$ be an independent fair bit. The series defining the probability mass function converges, whereas its information entropy diverges like ${\sum }_{n}1/(n\ln n)$. Then $X=(A,B)$ and $Y=B$ are dependent, but $H(X)=H(X\mid Y)=\infty$. In the infinite case, equality means precisely that the conditional entropy is also infinite; it does not imply independent random variables.

Write the countable supports as $D_i$ and the marginal masses as $p_i(x_i)$. Independence gives joint mass ${\prod }_i{p}_i(x_i)$. Assuming finite expected values, absolute integrability is justified by Tonelli theorem:Consequently Fubini's theorem permits factorization of the signed sum, proving the expectation of a product of independent random variables:

The second claim holds as a general assertion with the additional hypothesis that the positive variables are integer-valued. For a nonnegative integer-valued $Z$, the pointwise identity $Z={\sum }_{m\ge 0}{1}_{\{Z>m\}}$ and Tonelli theorem give the tail-sum formulaIf each $X_i$ is integer-valued, their product is too. Apply this identity to each factor and to the product, then use independence:Under the literal broader meaning of a discrete random variable, the second claim is false. Two independent constants $X_1=X_2=3/2$ are positive and discrete, but the left side is $2\cdot 2=4$ and the right side is $3$. More generally the integer-indexed tail sum of a positive real-valued variable is $\mathbb{E}\lceil Z\rceil$, not $\mathbb{E}Z$. This is the integer-valued hypothesis in the tail-sum formula.

A discrete random variable on a probability space $(\Omega ,\mathcal{F},\mathbb{P})$ is a real-valued measurable function $X:\Omega \to \mathbb{R}$ whose probability distribution is concentrated on some finite or countable set $S$:Measurability means $\{\omega :X(\omega )\le t\}\in \mathcal{F}$ for every real $t$. Its probability mass function is $p_X(x)=\mathbb{P}(X=x)$, and ${\sum }_{x\in S}{p}_X(x)=1$. Requiring a countable image everywhere, rather than outside a null set, is an equivalent convention after harmless modification on a null set.

For an integrable discrete random variable, its expectation and variance are $\mu ={\sum }_{n\in \mathbb{Z}}n{p}_n$ and ${\sum }_{n\in \mathbb{Z}}(n-\mu {)}^2{p}_n$, respectively. The first formula requires $\sum |n|p_n<\infty$ for a finite ordinary mean; the variance may be infinite. A probability density function gives $P(\alpha <Y<\beta )={\int }_{\alpha }^{\beta }f(y)dy$.

Conditioning on $X$ and using independence givesThe interchange is justified by Tonelli's theorem, since all integrands are nonnegative. Consequently $Z$ has an absolutely continuous distribution, withIts integral is ${\sum }_n{p}_n=1$. This is the convolution of independent random variables, specifically a Gaussian smoothing of an integer-valued distribution for the given normal density. The specified weights are normalized because $2(3/{\pi }^2){\sum }_{n\ge 1}{n}^{-2}=1$.

For a discrete random variable taking nonnegative integer values, its probability generating function isIt is defined at least for $|s|\le 1$. The usual probability generating function is intended for nonnegative integer-valued random variables; a general discrete real-valued random variable need not have this form. The coefficient of $s^k$ recovers $\mathbb{P}(X=k)$.

Using the indicator random variable, sum over the values of the discrete random variable $X$:Dividing by the positive probability $\mathbb{P}(B)$ proves $\mathbb{E}[X\mid B]=\mathbb{E}[X{1}_B]/\mathbb{P}(B)$. On $B^c$ the product vanishes, so no additional contribution is omitted.

For an integrable discrete random variable, the conditional expectation given an event $B$ of positive probability isThe sum ranges over the possible values of $X$; integrability ensures absolute convergence.