Minimum Information (IMIN)

What is Minimum Information?

IMIN quantifies the irreducible, length-only part of information in a dataset when content carries no diversity or structure to exploit. In a self-delimiting setting (where the decoder must be told when the sequence ends), the only degree of freedom left is the sequence length. IMIN measures the idealized number of bits needed to single out one termination position among all possible ones.

Formally, if a dataset has length n, then the Minimum Information is defined as the base-2 logarithm of the number of admissible termination positions (from 0 up to n), i.e. n + 1 possibilities. The measure symbol is \(I_{\mathrm{IMIN}}\); see the definition below.

\[ I_{\mathrm{IMIN}}(n) \;=\; \log_2\!\bigl(n+1\bigr), \qquad n \in \mathbb{N}. \]

This matches the provided implementation: empty input yields 0; length 1 yields 1; otherwise it follows the same closed form for all n via \(\log_2(n+1)\).

Short history

The idea behind IMIN is rooted in early coding theory and later formalized through self-delimiting descriptions in algorithmic information theory. When only the end position must be identified, an optimal fixed-length index among n+1 choices calls for \(\log_2(n+1)\) bits. Closely related developments include universal, self-delimiting integer codes (e.g., Elias codes) that describe lengths with nearly minimal overhead.

\[ \ell_{\mathrm{Elias}}(n) \;=\; \log_2 n \;+\; 2\,\log_2\!\bigl(\log_2 n\bigr) \;+\; O(1), \quad n \ge 2. \]

Physical meaning

IMIN captures the information of counting identical quanta. If the symbol content is perfectly homogeneous (or known in advance), the only uncertainty is how many items are present. Picking a unique termination among n+1 candidates requires the number of bits shown below, which grows logarithmically with the count.

\[ \text{Termination choices} = n+1 \;\;\Longrightarrow\;\; \text{bits} = \log_2(n+1). \]

Mathematical properties

Domain & codomain. IMIN is defined for non-negative integers and returns non-negative real values.

\[ I_{\mathrm{IMIN}} \colon \mathbb{N} \to \mathbb{R}_{\ge 0}, \qquad I_{\mathrm{IMIN}}(0) = 0. \]

Monotonicity. IMIN is strictly increasing in the sequence length.

\[ 0 \le n_1 \lt n_2 \;\Longrightarrow\; I_{\mathrm{IMIN}}(n_1) \lt I_{\mathrm{IMIN}}(n_2). \]

Concavity (continuous extension). Extending \(I_{\mathrm{IMIN}}\) to real \(n \ge 0\) yields a concave function; marginal information gained by one extra item decreases with larger \(n\).

\[ \frac{d}{dn} I_{\mathrm{IMIN}}(n) = \frac{1}{(n+1)\ln 2}, \qquad \frac{d^2}{dn^2} I_{\mathrm{IMIN}}(n) = -\,\frac{1}{(n+1)^2 \ln 2} \le 0. \]

Subadditivity. IMIN is subadditive with respect to concatenation of lengths: the information to mark the end of a combined sequence does not exceed the sum of the separate end markers.

\[ I_{\mathrm{IMIN}}(n+m) \;=\; \log_2(n+m+1) \;\le\; \log_2\!\bigl((n+1)(m+1)\bigr) \;=\; I_{\mathrm{IMIN}}(n) + I_{\mathrm{IMIN}}(m). \]

Asymptotics. IMIN grows logarithmically with length, reflecting the diminishing cost of each additional identical item.

\[ I_{\mathrm{IMIN}}(n) \;=\; \Theta\!\bigl(\log_2 n\bigr) \quad \text{as } n \to \infty. \]

Content invariance. IMIN depends only on the number of elements. It is invariant to permutations and ignores actual symbol values and frequencies.

Relation to Kolmogorov complexity

For fully homogeneous data (e.g., the same byte repeated n times) when the repeated symbol is known to the decoder, the Kolmogorov complexity of the dataset is essentially the description length of the integer n plus a constant for the generation rule. Here, IMIN acts as a tight baseline for that integer’s description, up to small, well-known self-delimiting overheads.

\[ K(a^n) \;\le\; I_{\mathrm{IMIN}}(n) \;+\; 2\,\log_2\!\bigl(\log_2(n+1)\bigr) \;+\; L_{\mathrm{side}}(a) \;+\; c_U. \]

In words: a short program can “repeat symbol a for n steps,” where the dominant term to specify is n. IMIN approximates this dominant term. For arbitrary, structured data, Kolmogorov complexity can be much larger; IMIN does not lower-bound \(K(x)\) in general—it is a length-only baseline, most informative for the simplest (highly regular) cases.

Limitations and remarks

Model dependence. IMIN assumes a self-delimiting communication model. If the container or protocol already conveys length out of band, the length component does not need to be encoded again, and IMIN overestimates the cost.

Content blindness. IMIN completely ignores symbol diversity, distribution, and structure. It cannot detect patterns, correlations, or randomness—only how many items there are.

Comparability. Because IMIN depends only on length, comparing datasets of very different sizes can be misleading. It is best used alongside content-aware measures (e.g., IS, IHUFF, IGZIP) to bracket possible information ranges.

Pseudocode

The following pseudocode mirrors the implementation: it returns \(\log_2(n+1)\) for input length n, with null and empty handled as zero.

function IMIN_value(sequence):
    if sequence is null:
        return 0
    n := length(sequence)
    if n == 0:
        return 0
    # Unified closed form covers all n ≥ 0:
    return log2(n + 1)

Note on Gutenberg safety: All mathematical expressions are placed in dedicated MathML blocks; no inline formulas are used. Any inequality signs inside formulas are written as \(\le\) and \(\lt\) to avoid raw angle brackets in the LaTeX content.