Let \(S\) be a finite nonempty set, let \((\Omega ,\mu )\) be a measure space, and let \(X\colon \Omega \to S\) be a random variable. If \(N\) is a natural number with \(\left\lvert S\right\rvert \le N\), then the Shannon entropy of \(X\) satisfies

Let \(S\) be a finite nonempty set and let \(X\) be a random variable on a probability space \(\Omega \) (equipped with a measure \(\mu \)) taking values in \(S\). If the number of elements of \(S\) is at most \(2^c\) for some natural number \(c\), then the Shannon entropy of \(X\) satisfies

where the logarithm is natural (so the entropy is measured in nats).

Let \(X\) and \(Y\) be measurable random variables on a measure space \((\Omega ,\mu )\), taking values in countable measurable spaces and each attaining only finitely many values, and suppose \(\mu \) is either the zero measure or a probability measure. Then the mutual information between \(X\) and \(Y\) is at most the Shannon entropy of \(X\):

Let \(X \colon \Omega \to S\) and \(Y \colon \Omega \to T\) be measurable random variables, each taking only finitely many values, defined on a space \(\Omega \) equipped with a measure \(\mu \) that is either the zero measure or a probability measure. Writing \(H[Y;\mu ]\) for the Shannon entropy of \(Y\) and \(I[X:Y;\mu ]\) for the mutual information between \(X\) and \(Y\), one has

Let \((\Omega , \mu )\) be a measured space and let \(S\) and \(T\) be countable measurable spaces. Suppose \(X, X' \colon \Omega \to S\) and \(Y, Y' \colon \Omega \to T\) are maps with \(X\) and \(Y\) measurable, and that \(X = X'\) and \(Y = Y'\) hold \(\mu \)-almost everywhere. Then the mutual information is unchanged, \(I[X : Y \, ;\, \mu ] = I[X' : Y' \, ;\, \mu ]\).

Let \(X\colon \Omega \to S\) and \(Y\colon \Omega \to T\) be measurable random variables on a probability space \((\Omega ,\mu )\) (allowing also \(\mu \) to be the zero measure), where \(S\) and \(T\) are countable and each of \(X\) and \(Y\) takes only finitely many values. If \(f\colon T\to V\) is a measurable injection into a countable space \(V\), then passing \(Y\) through \(f\) leaves the mutual information with \(X\) unchanged:

Let \(\mu \) be a probability measure (or the zero measure) on a sample space \(\Omega \), and let \(X\colon \Omega \to S\) and \(Y\colon \Omega \to T\) be measurable random variables taking countably many values, each with finite range. If there is a constant \(c\in S\) such that \(X=c\) holds \(\mu \)-almost everywhere, then the mutual information between \(X\) and \(Y\) vanishes: \(I[X:Y;\mu ]=0\).

Let \(X \colon \Omega \to S\) and \(Y \colon \Omega \to T\) be measurable random variables taking values in countable spaces, defined on a space \(\Omega \) carrying a probability measure \(\mu \) (or the zero measure), and suppose each of \(X\) and \(Y\) takes only finitely many values. If \(Y\) is \(\mu \)-almost-surely equal to a fixed constant \(c \in T\), then the mutual information between \(X\) and \(Y\) vanishes:

Let \(\mu \) be a probability measure on a sample space \(\Omega \) (or the zero measure), and let \(X\), \(Y\), \(Z\) be measurable random variables on \(\Omega \) taking finitely many values in the countable sets \(S\), \(T\), \(U\) respectively. If there is a constant \(c \in S\) with \(X = c\) holding \(\mu \)-almost everywhere, then the conditional mutual information of \(X\) and \(Y\) given \(Z\) vanishes:

Let \(X\), \(Y\), and \(Z\) be discrete random variables on a probability space \((\Omega , \mu )\) — where \(\mu \) is either the zero measure or a probability measure — taking values in countable measurable spaces \(S\), \(T\), and \(U\) respectively, with each of \(X\), \(Y\), \(Z\) almost surely taking only finitely many values, and with \(X\) and \(Y\) measurable. If there is a constant \(c \in T\) such that \(Y = c\) \(\mu \)-almost everywhere, then the conditional mutual information satisfies \(I[X : Y \mid Z; \mu ] = 0\).

Let \(\mu \) be a finite measure on a measurable space \(\Omega \), and let \(S\) and \(T\) be finite sets. Let \(X : \Omega \to S\) and \(Y : \Omega \to T\) be measurable maps such that, for every \(x \in S\) and \(y \in T\),

where each measure is taken as a real number. Then \(X\) and \(Y\) are independent under \(\mu \).

Let \(X\), \(Y\), and \(Z\) be random variables on a probability space \((\Omega , \mu )\), taking values in countable measurable spaces, and assume each takes only finitely many values (with positive probability). Then the conditional mutual information of \(X\) and \(Y\) given \(Z\) is at most the conditional entropy of \(X\) given \(Z\):

Here \(\mu \) is allowed to be either a probability measure or the zero measure.

Let \(X\), \(Y\), and \(Z\) be measurable random variables on a common probability space \((\Omega , \mu )\), each taking values in a countable measurable space and each having finite range, and suppose \(\mu \) is either the zero measure or a probability measure. Then the conditional mutual information of \(X\) and \(Y\) given \(Z\) is at most the conditional entropy of \(Y\) given \(Z\):

Let \(X\), \(Y\), and \(Z\) be measurable random variables on a probability space \((\Omega , \mu )\), taking values in countable spaces and each attaining only finitely many values. Then the conditional mutual information of \(X\) and \(Y\) given \(Z\) is bounded above by the Shannon entropy of \(X\):

(The bound also holds trivially when \(\mu \) is the zero measure.)

Let \(X\), \(Y\), and \(Z\) be random variables on a probability space \((\Omega , \mu )\), taking values in countable measurable spaces and each attaining only finitely many values. Then the mutual information between \(X\) and \(Y\) conditioned on \(Z\) is at most the Shannon entropy of \(Y\):

Let \(X\), \(Y\), and \(Z\) be random variables on a probability space \((\Omega , \mu )\), taking values in countable measurable spaces \(S\), \(T\), and \(U\) respectively, each measurable and of finite range. For any function \(f \colon U \times S \to V\) into a countable measurable space \(V\), form the postprocessed variable \(W(\omega ) = f\bigl(Z(\omega ), X(\omega )\bigr)\), obtained by applying to \(X\) a map that may itself depend on the conditioning value \(Z\). Then the conditional mutual information satisfies

Let \(X\colon \Omega \to S\), \(Y\colon \Omega \to T\), and \(Z\colon \Omega \to U\) be measurable random variables on a probability space \((\Omega ,\mu )\), each taking only countably many values and having finite range, where \(S\), \(T\), and \(U\) are countable measurable spaces. Let \(f\colon U\times T\to V\) be a measurable map into a countable measurable space \(V\), and define \(W(\omega )=f\big(Z(\omega ),Y(\omega )\big)\). Then the conditional mutual information satisfies

That is, replacing \(Y\) by any function of \(Y\) that is also permitted to depend on the conditioning variable \(Z\) cannot increase the conditional mutual information with \(X\).

Let \(X\), \(Y\), and \(Z\) be discrete random variables on a probability space \((\Omega , \mu )\), each taking values in a countable set and attaining only finitely many values, and let \(f\) be an arbitrary function defined on the range of \(Z\). Then the conditional mutual information of \(X\) and \(Y\) given the augmented variable \((Z, f(Z))\) equals the conditional mutual information of \(X\) and \(Y\) given \(Z\) alone:

Let \(X\), \(Y\), \(Z\) be random variables on a probability space \((\Omega ,\mu )\) (where \(\mu \) is allowed to be the zero measure), taking values in countable measurable spaces \(S\), \(T\), \(U\) respectively, and assume each of \(X\), \(Y\), \(Z\) is measurable with finite range. Let \(V\) be a further countable measurable space and let \(f\colon U\times S\to V\) be measurable, and write \(f(Z,X)\) for the random variable \(\omega \mapsto f\bigl(Z(\omega ),X(\omega )\bigr)\). Then conditioning additionally on \(f(Z,X)\) cannot increase the conditional mutual information of \(X\) and \(Y\) given \(Z\):

Let \(X\), \(Y\), \(Z\) be random variables on a probability space \((\Omega , \mu )\), taking values in countable measurable spaces, each measurable and with finite range. Let \(f\) be a measurable function of two arguments, and write \(f(Z, Y)\) for the random variable \(\omega \mapsto f\bigl(Z(\omega ), Y(\omega )\bigr)\). Then conditioning on the pair \(\bigl(Z, f(Z, Y)\bigr)\) — that is, refining the conditioning variable \(Z\) by a deterministic function of \(Z\) and \(Y\) — cannot increase the conditional mutual information between \(X\) and \(Y\):

Let \(X\), \(Y\), and \(W\) be random variables on a probability space \((\Omega ,\mu )\), taking values in countable measurable spaces and each attaining only finitely many values, and let \(f\) be a measurable map defined on the range of \(W\). Suppose the conditional mutual information \(I[X : W \mid f\circ W;\mu ]\) vanishes, so that \(X\) and \(W\) are conditionally independent given the coarsened variable \(f\circ W\). Then

Let \(X\), \(W\), \(Y\), and \(Z\) be random variables on a measure space \((\Omega ,\mu )\), each valued in a countable measurable space and each attaining only finitely many values, and suppose \(\mu \) is either the zero measure or a probability measure. Writing \(I[U : V \mid T;\mu ]\) for the mutual information of \(U\) and \(V\) conditioned on \(T\), the pair \((X,W)\) obeys the chain rule

Let \(X\), \(Y\), \(Z\), and \(W\) be measurable functions on a probability space \((\Omega , \mu )\), where \(\mu \) is either the zero measure or a probability measure, each taking values in a countable measurable space and attaining only finitely many values. Write \(I(X ; Y \mid Z)\) for the conditional mutual information between \(X\) and \(Y\) given \(Z\). Then the conditional mutual information between \(X\) and the pair \((Y, W)\) given \(Z\) satisfies

Let \(X\), \(Y\), \(W\), and \(Z\) be measurable functions on a probability space \((\Omega , \mu )\), taking values in countable measurable spaces and each having finite range. Then the conditional mutual information satisfies

where \((Y, W)\) denotes the joint random variable \(\omega \mapsto (Y(\omega ), W(\omega ))\).

Let \(Y\) and \(Z\) be random variables on a probability space \((\Omega , \mu )\) (allowing also the zero measure), each taking countably many values with finite range, and let \(X : \Omega \to (\{ 0,1\} ^m)\) be a random boolean vector; assume \(X\), \(Y\), and \(Z\) are measurable. Writing \(X_i(\omega ) = X(\omega )(i)\) for the \(i\)-th coordinate and \(X_{\lt i}(\omega )\) for the strict prefix consisting of coordinates \(0, 1, \ldots , i-1\), the conditional mutual information of \(X\) and \(Y\) given \(Z\) decomposes as

Let \(\mu \) be a finite measure on a measurable space, and let \(F \subseteq A\) be measurable sets. Then conditioning \(\mu \) on \(A\) and afterwards on \(F\) gives the same measure as conditioning \(\mu \) on \(F\) directly:

Let \(\mu \) be a finite measure on a measurable space \(\Omega \), let \(A\) be a measurable set, and let \(F \subseteq A\). Writing \(\mu (\, \cdot \mid A)\) for the conditional measure obtained by restricting \(\mu \) to \(A\) and normalising by \(\mu (A)\), and taking all masses as real numbers, one has

Let \((\Omega ,\mu )\) be a finite measure space, and let \(X\), \(Y\), \(K\), and \(Z\) be measurable functions on \(\Omega \) taking values in countable spaces, with \(X\) and \(Y\) each having finite range, \(K\) taking values in a finite set \(A\), and \(Z\) taking values in a finite space. Then the mutual information of \(X\) and \(Y\) conditioned on the pair \((K,Z)\) decomposes as the \(\mu \)-weighted average, over the values of \(K\), of the mutual information of \(X\) and \(Y\) conditioned on \(Z\) alone:

where \(\mu (K^{-1}\{ k\} )\) denotes the (real-valued) measure of the event \(\{ K = k\} \) and \(\mu [\, \cdot \mid K = k\, ]\) denotes \(\mu \) conditioned on that event.

Let \(X\), \(Y\), and \(Z\) be random variables of finite range on a probability space \((\Omega , \mu )\), taking values in countable measurable spaces, and let \(A = Z^{-1}(B)\) be the event that \(Z\) lands in a measurable set \(B\). Writing \(I[X : Y \mid Z;\, \nu ]\) for the conditional mutual information of \(X\) and \(Y\) given \(Z\) computed under a measure \(\nu \), and \(\mu [\, \cdot \mid A]\) for \(\mu \) conditioned on the event \(A\), one has

Let \(X\), \(Y\), and \(W\) be measurable random variables on a probability space \((\Omega , \mu )\), taking values in countable measurable spaces, and suppose each of \(X\), \(Y\), \(W\) takes only finitely many values almost surely. Then the mutual information between \(X\) and the pair \((Y, W)\) decomposes as

where \(I(X : W \mid Y)\) is the mutual information of \(X\) and \(W\) conditioned on \(Y\). (If \(\mu \) is the zero measure rather than a probability measure, both sides are \(0\).)

Let \(X\), \(Y\), and \(W\) be random variables on a probability space \((\Omega ,\mu )\) (with \(\mu \) a probability measure, or else the zero measure), taking values in countable measurable spaces and each assuming only finitely many values. Write \(I[X : Y;\mu ]\) for the mutual information of \(X\) and \(Y\), and \(I[X : Y \mid W;\mu ]\) for their mutual information conditioned on \(W\). If conditioning on \(Y\) does not increase the mutual information between \(X\) and \(W\), that is,

then conditioning on \(W\) does not increase the mutual information between \(X\) and \(Y\):

Let \((\Omega ,\mu )\) be a probability space, and let \(X,X'\colon \Omega \to S\) and \(Y,Y'\colon \Omega \to T\) be measurable random variables valued in countable measurable spaces, each taking only finitely many values. If \(X = X'\) and \(Y = Y'\) hold \(\mu \)-almost everywhere, then the conditional Shannon entropies agree:

Let \(\mu \) be a probability measure on a sample space \(\Omega \), and let \(X, X' \colon \Omega \to S\), \(Y, Y' \colon \Omega \to T\), and \(Z \colon \Omega \to U\) be measurable maps into countable spaces, each taking only finitely many values \(\mu \)-almost surely. If \(X = X'\) and \(Y = Y'\) hold \(\mu \)-almost everywhere, then the conditional mutual informations agree:

Let \((\Omega ,\mu )\) be a probability space, and let \(X,X'\), \(Y,Y'\), and \(Z,Z'\) be measurable random variables on \(\Omega \) taking values in countable (discrete) measurable spaces, each attaining only finitely many values. If \(X = X'\), \(Y = Y'\), and \(Z = Z'\) hold \(\mu \)-almost everywhere, then the conditional mutual informations agree:

Let \(\mu \) be a probability measure on a finite sample space \(\Omega \) (with every subset measurable), and let \(X, X'\), \(Y, Y'\), and \(Z, Z'\) be random variables on \(\Omega \) taking values in the finite sets \(S\), \(T\), and \(U\) respectively. If \(X = X'\), \(Y = Y'\), and \(Z = Z'\) each hold \(\mu \)-almost everywhere, then the conditional mutual informations coincide:

Let \(X,Y,Z\) be measurable random variables on a probability space \((\Omega ,\mu )\) and let \(X',Y',Z'\) be measurable random variables on a probability space \((\Omega ',\mu ')\), all taking values in countable measurable spaces and each assuming only finitely many values. If the triples \((X,Y,Z)\) and \((X',Y',Z')\) are identically distributed, meaning they induce the same joint law on \(S\times T\times U\), then their conditional mutual informations agree:

Let \((\Omega ,\mu )\) and \((\Omega ',\mu ')\) be finite probability spaces, and let \(S\), \(T\), \(U\) be finite sets. Consider random variables \(X\colon \Omega \to S\), \(Y\colon \Omega \to T\), \(Z\colon \Omega \to U\) defined on the first space and \(X'\colon \Omega '\to S\), \(Y'\colon \Omega '\to T\), \(Z'\colon \Omega '\to U\) defined on the second. If the joint random vectors \((X,Y,Z)\) and \((X',Y',Z')\) are identically distributed — that is, they induce the same probability measure on \(S\times T\times U\) — then their conditional mutual informations agree:

Let \(\mu \) be a probability measure on a sample space \(\Omega \), and let \(X\), \(Y\), \(Z\) be measurable random variables on \(\Omega \), taking values in countable measurable spaces \(S\), \(T\), \(U\) respectively and each having finite range. Let \(f\colon T\to V\) and \(g\colon U\to W\) be measurable injections into countable measurable spaces. Then relabelling the second and conditioning variables by \(f\) and \(g\) leaves the conditional mutual information unchanged:

Let \(X, Y\) be measurable maps from a probability space \((\Omega , \mu )\) taking values in measurable spaces \(A\) and \(B\), and let \(X', Y'\) be measurable maps from a probability space \((\Omega ', \mu ')\) into the same spaces \(A\) and \(B\), with \(Y\) and \(Y'\) measurable. Suppose the pairs \((X, Y)\) and \((X', Y')\) are identically distributed, that is, they induce the same law on \(A \times B\) under \(\mu \) and \(\mu '\) respectively. Then for every measurable set \(s \subseteq B\), the maps \(X\) and \(X'\) are identically distributed with respect to the conditioned measures \(\mu [\, \cdot \mid Y^{-1}(s)]\) and \(\mu '[\, \cdot \mid Y'^{-1}(s)]\).