imported>Jacobolus: base of a logarithm is a better target than base (exponentiation)

2025-01-28T07:06:22Z

base of a logarithm is a better target than base (exponentiation)

New page

The '''Hartley function''' is a measure of [[uncertainty]], introduced by [[Ralph Hartley]] in 1928. If a sample from a finite set ''A'' uniformly at random is picked, the information revealed after the outcome is known is given by the Hartley function
: <math> H_0(A) := \mathrm{log}_b \vert A \vert ,</math>
where {{abs|''A''}} denotes the [[cardinality]] of ''A''.

If the [[base of a logarithm|base of the logarithm]] is 2, then the unit of uncertainty is the [[Shannon (unit)|shannon]] (more commonly known as [[bit]]). If it is the [[natural logarithm]], then the unit is the [[Nat (unit)|nat]]. Hartley used a [[base-ten logarithm]], and with this base, the unit of information is called the [[Hartley (unit)|hartley]] (aka [[Hartley (unit)|ban]] or [[Hartley (unit)|dit]]) in his honor. It is also known as the Hartley entropy or max-entropy.

== Hartley function, Shannon entropy, and Rényi entropy ==
The Hartley function coincides with the [[Shannon entropy]] (as well as with the Rényi entropies of all orders) in the case of a uniform probability distribution. It is a special case of the [[Rényi entropy]] since:
:<math>H_0(X) = \frac 1 {1-0} \log \sum_{i=1}^{|\mathcal{X}|} p_i^0 = \log |\mathcal{X}|.</math>

But it can also be viewed as a primitive construction, since, as emphasized by Kolmogorov and Rényi, the Hartley function can be defined without introducing any notions of probability (see ''Uncertainty and information'' by George J. Klir, p. 423).

== Characterization of the Hartley function ==
The Hartley function only depends on the number of elements in a set, and hence can be viewed as a function on natural numbers. Rényi showed that the Hartley function in base 2 is the only function mapping natural numbers to real numbers that satisfies

# <math>H(mn) = H(m)+H(n)</math> (additivity)
# <math>H(m) \leq H(m+1)</math> (monotonicity)
# <math>H(2)=1</math> (normalization)

Condition 1 says that the uncertainty of the Cartesian product of two finite sets ''A'' and ''B'' is the sum of uncertainties of ''A'' and ''B''. Condition 2 says that a larger set has larger uncertainty.

== Derivation of the Hartley function ==
We want to show that the Hartley function, log<sub>2</sub>(''n''), is the only function mapping natural numbers to real numbers that satisfies
# <math>H(mn) = H(m)+H(n)\,</math> (additivity)
# <math>H(m) \leq H(m+1)\,</math> (monotonicity)
# <math>H(2)=1\,</math> (normalization)

Let ''f'' be a function on positive integers that satisfies the above three properties. From the additive property, we can show that for any integer ''n'' and ''k'',
: <math>f(n^k) = kf(n).\,</math>

Let ''a'', ''b'', and ''t'' be any positive integers. There is a unique integer ''s'' determined by
: <math>a^s \leq b^t \leq a^{s+1}. \qquad(1)</math>

Therefore,
: <math>s \log_2 a\leq t \log_2 b \leq (s+1) \log_2 a \, </math>
and
: <math>\frac{s}{t} \leq \frac{\log_2 b}{\log_2 a} \leq \frac{s+1}{t}.</math>

On the other hand, by monotonicity,
: <math>f(a^s) \leq f(b^t) \leq f(a^{s+1}). \, </math>

Using equation (1), one gets
: <math>s f(a) \leq t f(b) \leq (s+1) f(a),\,</math>
and
: <math>\frac{s}{t} \leq \frac{f(b)}{f(a)} \leq \frac{s+1}{t}.</math>

Hence,
: <math>\left\vert \frac{f(b)}{f(a)} - \frac{\log_2(b)}{\log_2(a)} \right\vert \leq \frac{1}{t}.</math>

Since ''t'' can be arbitrarily large, the difference on the left hand side of the above inequality must be zero,
: <math>\frac{f(b)}{f(a)} = \frac{\log_2(b)}{\log_2(a)}.</math>

So,
: <math>f(a) = \mu \log_2(a)\,</math>
for some constant ''μ'', which must be equal to 1 by the normalization property.

== See also ==
* [[Rényi entropy]]
* [[Min-entropy]]

== References ==
{{reflist}}
* {{PlanetMath attribution|id=6070|title=Hartley function}}
* {{PlanetMath attribution|id=6082|title=Derivation of Hartley function}}

[[Category:Information theory]]

Hartley function - Revision history

imported>Jacobolus: base of a logarithm is a better target than base (exponentiation)