Results on entropy at a scale and on self-similar measures, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• The inequality of Gibbs — Lemma 1.1. For laws p, q on a finite set with q_a > 0 where p_a > 0: sum p_a log(p_a/q_a) >= 0, with equality only for p = q.
• Bounds for the entropy of a finite random variable — Proposition 1.2. A random variable with at most N values has entropy between 0 and log N; 0 exactly if it is almost surely constant, log N exactly if it is uniform on N values.
• The chain rule and the effect of conditioning on entropy — Proposition 2.1. H(Y, Z) = H(Y) + H(Z | Y); 0 <= H(Z | Y) <= H(Z) with the cases of equality; H(f(Z)) <= H(Z); H(Z | Y, W) <= H(Z | Y).
• Mutual information: nonnegativity, chain rule, functions — Proposition 3.1. I(Z; Y) = H(Z) + H(Y) - H(Z, Y) >= 0 and I(Z; Y | W) >= 0; I(J; (Z, W)) = I(J; W) + I(J; Z | W); I(J; f(Z)) <= I(J; Z); I(J; Z) <= I(J; Z | W) + H(W).
• The entropy of a mixture — Proposition 4.1. For laws P_i on a finite set and weights lambda: sum lambda_i H(P_i) <= H(sum lambda_i P_i) <= sum lambda_i H(P_i) + H(lambda).
• The binary entropy is at most 3 sqrt(u) — Lemma 5.1. h_2(u) <= 3 sqrt(u) for 0 <= u <= 1, with entropy in bits.
• Strong concavity of the binary entropy — Lemma 5.2. h_2((a + b)/2) - h_2(a)/2 - h_2(b)/2 >= (a - b)^2 / (2 ln 2) for a, b in [0, 1], with entropy in bits.
• Averaged grid entropy under translation and scaling — Lemma 1.1. For a bounded real random variable X: H_s(X + b) = H_s(X) and H_s(aX) = H_{s/|a|}(X) for a not zero, where H_s is the entropy of the cell of X in a grid of length s, averaged over the shifts of the grid.
• Comparison of the averaged entropies at two scales — Proposition 1.3. For z >= s: H_s - log(z/s + 2) <= H_z <= H_s + 1; the averaged entropy and the entropy for a fixed grid of the same length differ by at most 1.
• The entropy between two scales with an integer ratio — Proposition 2.1. G_{s,Ns} = H_s - H_{Ns} is the mean over shifts of the conditional entropy of the fine cell given the coarse cell; 0 <= G_{s,Ns} <= log N.
• Jensen's inequality for a concave function on a simplex — Lemma 2.2. For a continuous concave function Psi on the laws on a finite set and a measurable map p into these laws: Psi(mean of p) >= mean of Psi(p).
• Concavity and the convolution inequality for the entropy between two scales — Proposition 2.4. For an integer N, G_{s,Ns} of the mean of a measurable family of laws is at least the mean of G_{s,Ns}; G_{s,Ns}(X + Y) >= G_{s,Ns}(X) for independent bounded X, Y; Delta_s = 1 - G_{s,2s} is convex.
• Uniform steps change the scale — Proposition 3.1. For U uniform on {0, ..., K-1} and independent of X: H_v(X + vU) = H_{Kv}(X) + log K.
• The one-bit deficit as mutual information — Corollary 3.2. log K - G_{v,Kv}(X) is the mean over shifts of I(U; F_u + U), where F_u is the cell of X; in particular Delta_v(X) = H_v(X + vJ) - H_v(X) is the mean of I(J; F_u + J) for a fair bit J.
• Existence and uniqueness of the self-similar measure — Proposition 1.2. For maps phi_i(x) = r_i x + t_i with 0 < |r_i| < 1 and positive weights p_i, the law of the coding limit is the only Borel probability measure mu with mu = sum p_i (phi_i)_* mu; it is supported in a bounded interval.
• A self-similar measure as a mixture of copies at a given scale — Lemma 1.3. For 0 < rho < 1, mu = sum over the words w with |r_w| <= rho < |r of the word without its last letter| of p_w (phi_w)_* mu, and these words have rho a_* < |r_w| <= rho.
• Entropy at small scales of an exact-dimensional law — Proposition 2.2. For a bounded exact-dimensional law of dimension d, limsup of max(H_s, H^0_s) / log(1/s) as s -> 0 is at most d.
• A small one-bit deficit forces almost full entropy over K steps — Proposition 3.3. For a bounded X, v > 0 and an integer K >= 2: log K - G_{v,Kv}(X) <= (K(K-1)/2) log K sqrt(2 ln 2 Delta_v(X)).
• Uniform nonsaturation of self-similar measures of dimension less than one — Theorem 3.5. If a self-similar measure on the line is exact dimensional with dimension d < 1, then inf over v > 0 of Delta_v(mu) is positive.
• The two-point gain — Theorem 1.2. For a bounded X, an independent fair bit J and 0 < s < v < t: G_{s,t}(X + vJ) - G_{s,t}(X) >= Delta_v(X) - s/v - v/t; the same for any independent fair two-point law of size v.
• Pair capacities of a finite law — Definition 2.1. c_l(nu) is the largest total weight of fair pairs with sizes in [2^-l, 2^(1-l)) whose weighted sum is at most nu at every point; 0 <= c_l(nu) <= 1.
• The gain of a convolution from the fair pairs of one factor — Theorem 2.3. For t = Ns with an integer N >= 2, a finite law nu with weights w_e on pairs of sizes v_e in (s, t) such that half the weights at every point is at most its mass, and a bounded law lambda: G_{s,t}(nu * lambda) >= G_{s,t}(lambda) + sum of w_e (Delta_{v_e}(lambda) - s/v_e - v_e/t).
• The pair bound for a finite law — Theorem 1.1. For an integer k >= 1, a law nu with finite support F on the line and rho > 0: k (H(nu) - H^0_rho(nu)) <= log |kF| + 53760 k^4 times the sum of the pair capacities c_l(nu) over the l with 2^-l <= 2 rho.
• Entropy of a refinement of cells when the sum is known — Lemma 4.1. For independent X_i in cells A_i, each cut into at most eight children, with means m_i, a the least distance from a mean to a cut of its cell and p_i = P(|X_i - m_i| >= a/(4k)): the entropy of the tuple of children given the sum is at most 9k times the sum of the p_i.
• The coupling of a partition and the pair capacities — Lemma 5.2. For a partition into cells of length at most 2r, the law of two independent points of a random cell has marginals nu, gives each dyadic distance band a mass of at most c_l(nu), and has mean distance at most 2 times the sum of 2^-l c_l(nu) over 2^-l <= 2r.
• The entropy rate of the walk of maps — Proposition 1.2. For G_n the composition of n independent maps of a finite family of contracting affine maps of the line, H(G_n)/n converges to its infimum h, with 0 <= h <= H(p); without exact overlaps h = H(p).
• Entropy at small scales of an exact-dimensional law: the limit — Proposition 2.1. For a bounded exact-dimensional law of dimension d, the averaged and the fixed-grid entropy at scale s divided by log(1/s) converge to d as s -> 0; in particular 0 <= d <= 1.
• Upper bound for the dimension of a self-similar measure on the line — Theorem 3.3. If a self-similar measure on the line is exact dimensional with dimension d, then d <= min(1, h/chi), where h is the entropy rate of the walk of maps and chi = - sum p_i log |r_i|.
• Entropy of the translations of block maps given the block types — Proposition 4.1. For a self-similar measure on the line that is exact dimensional with d chi < h, and the parameters b, A, A', gamma of the lesson: E H(nu_Omega) = H(G_bn | Omega_n) >= n h_b; E H^0_s(nu_Omega) <= H^0_s(mu) + 1; and for large n the mean of 1_{E_n} (H(nu_Omega) - H^0_{rho_n}(nu_Omega)) is at least (gamma/4) n.
• Sumsets of the supports of the laws of translations for given types — Lemma 5.1. For a tuple of n block types with blocks of length b over m symbols, the support F of the law of the translations satisfies log |kF| <= n m^b log(k+1) for every k >= 1.
• Pair capacity of order n in a finite range of fine scales — Theorem 5.1. Under d chi < h there are c > 0 and n_0 such that for n >= n_0 there is an integer B_n >= a_n with E[1_{E_n} sum over l from a_n to B_n of c_l(nu_Omega)] >= c n.
• Gain of entropy in a window of scales from the pairs of a stretch of blocks — Proposition 3.1. Under d < 1 and d chi < h: the mean, over the later types, of g_j - g_{j+n} is at least (delta/2) times the pair capacity c_{L - ceil(sigma_j)} of the law of translations of the blocks j to j+n-1.
• The dimension formula for self-similar measures on the line — Theorem 5.1. A self-similar measure on the line (maps r_i x + t_i with 0 < |r_i| < 1, positive weights, no separation assumption) that is exact dimensional with dimension d has d = min(1, h/chi), where h is the entropy rate of the walk of maps and chi = - sum p_i log |r_i|.
• Exact overlaps of words of different lengths — Lemma 6.1. If two different nonempty words of contracting affine maps of the line give the same map, then two different words of the same length give the same map.
• The dimension formula without exact overlaps — Corollary 6.2. An exact-dimensional self-similar measure on the line whose maps have no exact overlaps has d = min(1, H(p)/chi).

Reading order

Eight lessons with a complete proof of the dimension formula d = min(1, h/chi) for self-similar measures on the line, assuming exact dimensionality (the named hypothesis (ED), a theorem of Feng and Hu that the course does not prove): the rules of entropy for finite random variables; the entropy of a law at a scale; uniform nonsaturation; the gain of entropy from pairs of points; the pair bound for a finite law; the walk of maps and the upper bound; block types and the pair capacity at fine scales; disjoint windows and the formula, with the case without exact overlaps.