Skip to main content
tiny rephrasings
Source Link
Tom Leinster
  • 27.7k
  • 5
  • 109
  • 159

I don't have Hobson's book, but I do have a paper by Hobson in which he proves the theorem that Wikipedia is presumably referring to:

Arthur Hobson, A new theorem in information theory. Journal of Statistical Physics 1 (1969), 383-391.

(What a title. Long gone are the days when you could get away with that!)

Here's Hobson's theorem. Let $I(p; q)$ be defined for any pair of probability distributions $p, q$ on a finite set. Suppose it satisfies the properties below. Then $I$ is a constant multiple of relative entropy.

Before I list the properties, let me make a comment: the phrasing "let ... be defined" is his. He's not quite precise about the domain or codomain of the function $I$. I see no mention of the fact that relative entropy can be infinite, and it may be tacitly assumed that $I(p; q)$ is always nonnegative.

His properties:

  • $I$ is a continuous function of its $2n$ variables. (Again, I don't know how/whether he handles infinities. As John and Tobias make clear in their paper, continuity as relative entropy tends to $\infty$ is actually a tricky point.)

  • $I$ is permutation-invariant (doing the same permutation to both arguments). Actually, he only states invariance under a single transposition, but obviously that's equivalent.

  • $I(p; p) = 0$ for all $p$.

  • $I((1/m, \ldots, 1/m, 0, \ldots, 0); (1/n, \ldots, 1/n))$ is an increasing function of $n$ and a decreasing function of $m$, for all $n \geq m \geq 1$. (I don't know whether he means increasing and decreasing in the strict or weak sense.)

  • We have \begin{align*} & I((p_1, \ldots, p_m, p_{m + 1}, \ldots, p_n); (q_1, \ldots, q_m, q_{m + 1}, \ldots, q_n)) \\ & = I((P, P'); (Q; Q')) + P\cdot I((p_1/P, \ldots, p_m/P); (q_1/Q, \ldots, q_m/Q))\\ & \quad + P'\cdot I((p_{m + 1}/P', \ldots, p_n/P'); (q_{m + 1}/Q', \ldots, q_n/Q')) \end{align*} for all probability distributions $p$ and $q$ and all $m \in \{1, \ldots, n\}$, where we have put $P = p_1 + \cdots + p_m$, $P' = 1 - P$, $Q = q_1 + \cdots + q_m$, and $Q' = 1 - Q$. (Although he divides by $P$, $P'$, $Q$ and $Q'$ here, he doesn't seem to say what to do if they're zero.)

This theorem is weaker than the result in my earlier answer. In that other answer, his continuity axiom is replaced by measurability, the permutation-invariance and vanishing axioms are the same, and his fourth axiom (about increasing/decreasing) just isn't there. The last axioms in both lists look different, but are actually equivalent. This takes a bit of explanation, as follows.

As usul points out, most theorems characterizing entropies involve one axiom looking like these ones. In fact, both Hobson's last axiom and the last axiom in my earlier answer are special cases of the following general axiom, which I'm told is known as the "chain rule".

To state it, let me introduce some notation. Given probability distributions $\mathbf{w}$ on $n$ elements, $\mathbf{p}^1$ on $k_1$ elements, ..., $\mathbf{p}^n$ on $k_n$ elements, we get a distribution $$ \mathbf{w} \circ (\mathbf{p}^1, \ldots, \mathbf{p}^n) = (w_1 p^1_1, \ldots, w_1 p^1_{k_1}, \ \ldots, \ w_n p^n_1, \ldots, w_n p^n_{k_n}) $$ on $k_1 + \cdots + k_n$. Using that notation, the chain rule for relative entropy states that $$ D\bigl(\mathbf{w} \circ (\mathbf{p}^1, \ldots, \mathbf{p}^n) \,\|\, \tilde{\mathbf{w}} \circ (\tilde{\mathbf{p}}^1, \ldots, \tilde{\mathbf{p}}^n)\bigr) = D(\mathbf{w} \,\|\, \tilde{\mathbf{w}}) + \sum_{i = 1}^n p_i D(\mathbf{p}^i \,\|\, \tilde{\mathbf{p}}^i). $$ It's easy to see that both Hobson's last axiom and the last axiom in my earlier answer are special cases of this general rule. But by simple inductive arguments, either one of these special cases implies the general case. That's why I say they're equivalent.

Whether you find the general case or one of the special cases more appealing is a matter of taste.

I don't have Hobson's book, but I do have a paper by Hobson in which he proves the theorem that Wikipedia is presumably referring to:

Arthur Hobson, A new theorem in information theory. Journal of Statistical Physics 1 (1969), 383-391.

(What a title. Long gone are the days when you could get away with that!)

Here's Hobson's theorem. Let $I(p; q)$ be defined for any pair of probability distributions $p, q$ on a finite set. Suppose it satisfies the properties below. Then $I$ is a constant multiple of relative entropy.

Before I list the properties, let me make a comment: the phrasing "let ... be defined" is his. He's not quite precise about the domain or codomain of the function $I$. I see no mention of the fact that relative entropy can be infinite, and it may be tacitly assumed that $I(p; q)$ is always nonnegative.

His properties:

  • $I$ is a continuous function of its $2n$ variables. (Again, I don't know/whether he handles infinities. As John and Tobias make clear in their paper, continuity as relative entropy tends to $\infty$ is actually a tricky point.)

  • $I$ is permutation-invariant (doing the same permutation to both arguments). Actually, he only states invariance under a single transposition, but obviously that's equivalent.

  • $I(p; p) = 0$ for all $p$.

  • $I((1/m, \ldots, 1/m, 0, \ldots, 0); (1/n, \ldots, 1/n))$ is an increasing function of $n$ and a decreasing function of $m$, for all $n \geq m \geq 1$. (I don't know whether he means increasing and decreasing in the strict or weak sense.)

  • We have \begin{align*} & I((p_1, \ldots, p_m, p_{m + 1}, \ldots, p_n); (q_1, \ldots, q_m, q_{m + 1}, \ldots, q_n)) \\ & = I((P, P'); (Q; Q')) + P\cdot I((p_1/P, \ldots, p_m/P); (q_1/Q, \ldots, q_m/Q))\\ & \quad + P'\cdot I((p_{m + 1}/P', \ldots, p_n/P'); (q_{m + 1}/Q', \ldots, q_n/Q')) \end{align*} for all probability distributions $p$ and $q$ and all $m \in \{1, \ldots, n\}$, where we have put $P = p_1 + \cdots + p_m$, $P' = 1 - P$, $Q = q_1 + \cdots + q_m$, and $Q' = 1 - Q$. (Although he divides by $P$, $P'$, $Q$ and $Q'$ here, he doesn't seem to say what to do if they're zero.)

This is weaker than the result in my earlier answer. In that other answer, his continuity axiom is replaced by measurability, the permutation-invariance and vanishing axioms are the same, and his fourth axiom (about increasing/decreasing) just isn't there. The last axioms in both lists look different, but are actually equivalent. This takes a bit of explanation, as follows.

As usul points out, most theorems characterizing entropies involve one axiom looking like these ones. In fact, both Hobson's last axiom and the last axiom in my earlier answer are special cases of the following general axiom, which I'm told is known as the "chain rule".

To state it, let me introduce some notation. Given probability distributions $\mathbf{w}$ on $n$ elements, $\mathbf{p}^1$ on $k_1$ elements, ..., $\mathbf{p}^n$ on $k_n$ elements, we get a distribution $$ \mathbf{w} \circ (\mathbf{p}^1, \ldots, \mathbf{p}^n) = (w_1 p^1_1, \ldots, w_1 p^1_{k_1}, \ \ldots, \ w_n p^n_1, \ldots, w_n p^n_{k_n}) $$ on $k_1 + \cdots + k_n$. Using that notation, the chain rule for relative entropy states that $$ D\bigl(\mathbf{w} \circ (\mathbf{p}^1, \ldots, \mathbf{p}^n) \,\|\, \tilde{\mathbf{w}} \circ (\tilde{\mathbf{p}}^1, \ldots, \tilde{\mathbf{p}}^n)\bigr) = D(\mathbf{w} \,\|\, \tilde{\mathbf{w}}) + \sum_{i = 1}^n p_i D(\mathbf{p}^i \,\|\, \tilde{\mathbf{p}}^i). $$ It's easy to see that both Hobson's last axiom and the last axiom in my earlier answer are special cases of this general rule. But by simple inductive arguments, either one of these special cases implies the general case. That's why I say they're equivalent.

Whether you find the general case or one of the special cases more appealing is a matter of taste.

I don't have Hobson's book, but I do have a paper by Hobson in which he proves the theorem that Wikipedia is presumably referring to:

Arthur Hobson, A new theorem in information theory. Journal of Statistical Physics 1 (1969), 383-391.

(What a title. Long gone are the days when you could get away with that!)

Here's Hobson's theorem. Let $I(p; q)$ be defined for any pair of probability distributions $p, q$ on a finite set. Suppose it satisfies the properties below. Then $I$ is a constant multiple of relative entropy.

Before I list the properties, let me make a comment: the phrasing "let ... be defined" is his. He's not precise about the codomain of the function $I$. I see no mention of the fact that relative entropy can be infinite, and it may be tacitly assumed that $I(p; q)$ is always nonnegative.

His properties:

  • $I$ is a continuous function of its $2n$ variables. (Again, I don't know how/whether he handles infinities. As John and Tobias make clear in their paper, continuity as relative entropy tends to $\infty$ is actually a tricky point.)

  • $I$ is permutation-invariant (doing the same permutation to both arguments). Actually, he only states invariance under a single transposition, but obviously that's equivalent.

  • $I(p; p) = 0$ for all $p$.

  • $I((1/m, \ldots, 1/m, 0, \ldots, 0); (1/n, \ldots, 1/n))$ is an increasing function of $n$ and a decreasing function of $m$, for all $n \geq m \geq 1$. (I don't know whether he means increasing and decreasing in the strict or weak sense.)

  • We have \begin{align*} & I((p_1, \ldots, p_m, p_{m + 1}, \ldots, p_n); (q_1, \ldots, q_m, q_{m + 1}, \ldots, q_n)) \\ & = I((P, P'); (Q; Q')) + P\cdot I((p_1/P, \ldots, p_m/P); (q_1/Q, \ldots, q_m/Q))\\ & \quad + P'\cdot I((p_{m + 1}/P', \ldots, p_n/P'); (q_{m + 1}/Q', \ldots, q_n/Q')) \end{align*} for all probability distributions $p$ and $q$ and all $m \in \{1, \ldots, n\}$, where we have put $P = p_1 + \cdots + p_m$, $P' = 1 - P$, $Q = q_1 + \cdots + q_m$, and $Q' = 1 - Q$. (Although he divides by $P$, $P'$, $Q$ and $Q'$ here, he doesn't seem to say what to do if they're zero.)

This theorem is weaker than the result in my earlier answer. In that other answer, his continuity axiom is replaced by measurability, the permutation-invariance and vanishing axioms are the same, and his fourth axiom (about increasing/decreasing) just isn't there. The last axioms in both lists look different, but are actually equivalent. This takes a bit of explanation, as follows.

As usul points out, most theorems characterizing entropies involve one axiom looking like these ones. In fact, both Hobson's last axiom and the last axiom in my earlier answer are special cases of the following general axiom, which I'm told is known as the "chain rule".

To state it, let me introduce some notation. Given probability distributions $\mathbf{w}$ on $n$ elements, $\mathbf{p}^1$ on $k_1$ elements, ..., $\mathbf{p}^n$ on $k_n$ elements, we get a distribution $$ \mathbf{w} \circ (\mathbf{p}^1, \ldots, \mathbf{p}^n) = (w_1 p^1_1, \ldots, w_1 p^1_{k_1}, \ \ldots, \ w_n p^n_1, \ldots, w_n p^n_{k_n}) $$ on $k_1 + \cdots + k_n$. Using that notation, the chain rule for relative entropy states that $$ D\bigl(\mathbf{w} \circ (\mathbf{p}^1, \ldots, \mathbf{p}^n) \,\|\, \tilde{\mathbf{w}} \circ (\tilde{\mathbf{p}}^1, \ldots, \tilde{\mathbf{p}}^n)\bigr) = D(\mathbf{w} \,\|\, \tilde{\mathbf{w}}) + \sum_{i = 1}^n p_i D(\mathbf{p}^i \,\|\, \tilde{\mathbf{p}}^i). $$ It's easy to see that both Hobson's last axiom and the last axiom in my earlier answer are special cases of this general rule. But by simple inductive arguments, either one of these special cases implies the general case. That's why I say they're equivalent.

Whether you find the general case or one of the special cases more appealing is a matter of taste.

Source Link
Tom Leinster
  • 27.7k
  • 5
  • 109
  • 159

I don't have Hobson's book, but I do have a paper by Hobson in which he proves the theorem that Wikipedia is presumably referring to:

Arthur Hobson, A new theorem in information theory. Journal of Statistical Physics 1 (1969), 383-391.

(What a title. Long gone are the days when you could get away with that!)

Here's Hobson's theorem. Let $I(p; q)$ be defined for any pair of probability distributions $p, q$ on a finite set. Suppose it satisfies the properties below. Then $I$ is a constant multiple of relative entropy.

Before I list the properties, let me make a comment: the phrasing "let ... be defined" is his. He's not quite precise about the domain or codomain of the function $I$. I see no mention of the fact that relative entropy can be infinite, and it may be tacitly assumed that $I(p; q)$ is always nonnegative.

His properties:

  • $I$ is a continuous function of its $2n$ variables. (Again, I don't know/whether he handles infinities. As John and Tobias make clear in their paper, continuity as relative entropy tends to $\infty$ is actually a tricky point.)

  • $I$ is permutation-invariant (doing the same permutation to both arguments). Actually, he only states invariance under a single transposition, but obviously that's equivalent.

  • $I(p; p) = 0$ for all $p$.

  • $I((1/m, \ldots, 1/m, 0, \ldots, 0); (1/n, \ldots, 1/n))$ is an increasing function of $n$ and a decreasing function of $m$, for all $n \geq m \geq 1$. (I don't know whether he means increasing and decreasing in the strict or weak sense.)

  • We have \begin{align*} & I((p_1, \ldots, p_m, p_{m + 1}, \ldots, p_n); (q_1, \ldots, q_m, q_{m + 1}, \ldots, q_n)) \\ & = I((P, P'); (Q; Q')) + P\cdot I((p_1/P, \ldots, p_m/P); (q_1/Q, \ldots, q_m/Q))\\ & \quad + P'\cdot I((p_{m + 1}/P', \ldots, p_n/P'); (q_{m + 1}/Q', \ldots, q_n/Q')) \end{align*} for all probability distributions $p$ and $q$ and all $m \in \{1, \ldots, n\}$, where we have put $P = p_1 + \cdots + p_m$, $P' = 1 - P$, $Q = q_1 + \cdots + q_m$, and $Q' = 1 - Q$. (Although he divides by $P$, $P'$, $Q$ and $Q'$ here, he doesn't seem to say what to do if they're zero.)

This is weaker than the result in my earlier answer. In that other answer, his continuity axiom is replaced by measurability, the permutation-invariance and vanishing axioms are the same, and his fourth axiom (about increasing/decreasing) just isn't there. The last axioms in both lists look different, but are actually equivalent. This takes a bit of explanation, as follows.

As usul points out, most theorems characterizing entropies involve one axiom looking like these ones. In fact, both Hobson's last axiom and the last axiom in my earlier answer are special cases of the following general axiom, which I'm told is known as the "chain rule".

To state it, let me introduce some notation. Given probability distributions $\mathbf{w}$ on $n$ elements, $\mathbf{p}^1$ on $k_1$ elements, ..., $\mathbf{p}^n$ on $k_n$ elements, we get a distribution $$ \mathbf{w} \circ (\mathbf{p}^1, \ldots, \mathbf{p}^n) = (w_1 p^1_1, \ldots, w_1 p^1_{k_1}, \ \ldots, \ w_n p^n_1, \ldots, w_n p^n_{k_n}) $$ on $k_1 + \cdots + k_n$. Using that notation, the chain rule for relative entropy states that $$ D\bigl(\mathbf{w} \circ (\mathbf{p}^1, \ldots, \mathbf{p}^n) \,\|\, \tilde{\mathbf{w}} \circ (\tilde{\mathbf{p}}^1, \ldots, \tilde{\mathbf{p}}^n)\bigr) = D(\mathbf{w} \,\|\, \tilde{\mathbf{w}}) + \sum_{i = 1}^n p_i D(\mathbf{p}^i \,\|\, \tilde{\mathbf{p}}^i). $$ It's easy to see that both Hobson's last axiom and the last axiom in my earlier answer are special cases of this general rule. But by simple inductive arguments, either one of these special cases implies the general case. That's why I say they're equivalent.

Whether you find the general case or one of the special cases more appealing is a matter of taste.