The McMillan Theorem for Colored Branching Processes and Dimensions of Random Fractals

Abstract

For the simplest colored branching process, we prove an analog to the McMillan theorem and calculate the Hausdorff dimensions of random fractals defined in terms of the limit behavior of empirical measures generated by finite genetic lines. In this setting, the role of Shannon’s entropy is played by the Kullback–Leibler divergence, and the Hausdorff dimensions are computed by means of the so-called Billingsley–Kullback entropy, defined in the paper.

1. Introduction

Let us fix a finite set Ω = {1,…, r}, whose elements denote different colors, and consider a finite random set X containing a random number of elements of colors 1, …, r. The simplest colored branching process can be defined as an evolution of a population in which all individuals live the same fixed time, and then, when the lifetime ends, each individual generates (independently of others) a random set of “children” containing individuals of different colors and distributed as X. We will assume that the evolution starts with a unique initial individual. It is suitable to represent this process as a random genealogical tree with individuals as vertices and each vertex connected with its “children” by edges. Denote by X_n the set of all genetic lines of length n starting from the initial individual. The colored branching process can degenerate (when, starting from some n, all of the sets X_n are empty) or, otherwise, evolve endlessly. Every genetic line x = (x₁, …, x_n) ∈ X_n generates an empirical measure δ_x,n on the set of colors Ω in accordance with the following rule: for each i ∈ Ω, the value of δ_x,n(i) is the quota in the string (x₁, …, x_n) of all elements having the color i.

Denote by μ(i), where i ∈ Ω, the expectation of the number of all elements x ∈ X having the color i. Let ν be an arbitrary probability measure on Ω. An analog to the McMillan theorem that will be proven below (see Theorem 11) asserts that under the condition of non-degeneracy of the colored branching process, the cardinality of the set {x ∈ X_n | δ_x,n ≈ ν} almost surely (i.e., with probability one) has asymptotics (up to the logarithmic equivalence) of order e^{−nρ(ν,μ)}, where:

$$\rho (\nu ,\mu )={\displaystyle \sum _{i\in \mathrm{\Omega }}\nu (i)\ln \frac{\nu (i)}{\mu (i)}}.$$

(1)

Formally, the value of ρ(ν, μ) coincides with the usual Kullback–Leibler divergence and differs from it only in the fact that in our setting, the measure μ is not a probability, and so ρ(ν, μ) can be negative.

This is the first main result of the paper. It generalizes the usual McMillan theorem, which deals with Ωⁿ, rather than Xⁿ. Its proof is based essentially on the Legendre duality between the Kullback–Leibler divergence and the so-called spectral potential, which was introduced first in [1] and then investigated profoundly in [2,3].

We investigate also Hausdorff dimensions of random fractals defined in terms of the limit behavior of the sequence of empirical measures δ_x,n. Let X_∞ be the set of all infinite genetic lines. Fix an arbitrary vector θ = (θ(1), …, θ(r)) ∈ (0, 1)^r and define the following metric on X_∞:

$$\text{dist}(x,y)={\displaystyle \prod _{t=1}^n\theta (x_t),}\text{where}n=\inf \{t|x_t\ne y_t\}-1.$$

Denote by V any set of probability measures on Ω. The second main result of the paper (concerning Hausdorff dimensions of random fractals) is the following: under the condition of non-degeneracy of the colored branching process,

$${\dim }_H\{x\in X_{\infty }|{\delta }_{x,n}\succ V\}=\underset{\nu \in V}{\sup }d(\nu ,\mu ,\theta )$$

(2)

almost surely, where δ_x,n ≻ V means that the sequence δ_x,n has at least one limit point in V and d(ν, μ, θ) is the Billingsley–Kullback entropy defined as:

$$d(\nu ,\mu ,\theta )=\frac{\rho (\nu ,\mu )}{{\displaystyle {\sum }_{i=1}^r\nu }(i)\ln \theta (i)}=\frac{{\displaystyle {\sum }_{i=1}^r\nu }(i)\ln \frac{\nu (i)}{\mu (i)}}{{\displaystyle {\sum }_{i=1}^r\nu }(i)\ln \theta (i)}$$

(3)

Moreover, almost surely:

$${\dim }_H\{x\in X_{\infty }|{\delta }_{x,n}\to \nu \}=d(\nu ,\mu ,\theta ).$$

(4)

These results are the essence of Theorems 12 and 17 below.

The systematic study of random self-similar fractals was initiated in the works by Falconer [4], Mauldin, Williams [5] and Graf [6]. They considered the attractor K of a random version of an iterated function system (IFS) in ℝⁿ, letting the scaling factors θ(i) ∈ [0, 1) be independent and identically distributed (i.i.d.) random variables. The main result proven in [4–6] is the following: if the open set condition holds and ${\displaystyle {\sum }_i\theta (i)>1}$, then K ≠ ∅ with positive probability, and with the same probability (i.e., almost surely, provided K ≠ ∅), its Hausdorff dimension s is a unique solution to the equation ${\displaystyle {\sum }_i\mathrm{⋿}\theta }{(i)}^s=1$. Recently, the research was extended to the case of random self-affine fractals in ℝⁿ (see [7,8]) and random affine code tree fractals [9].

On the other hand, Billingsley in [10,11] considered fractals in the space of infinite sequences Ω^ℕ, where Ω is a finite set, defined in terms of the limit behavior of empirical measures. He investigated Hausdorff dimensions of such fractals and, in particular, obtained formulas analogous to Formulars (2) and (4) (with Ω^ℕ instead of X_∞ and μ(i) ≡ 1). Afterwards, Billingsley’s ideas and methods were transferred to strange attractors of dynamical systems in ℝⁿ (see [12,13]).

The present research combines both features of random self-similar fractals and subsets of nonrandom self-similar fractals defined in terms of the limit behavior of empirical measures. This combination provides its novelty.

The paper can be divided into two parts. The first one (Sections 3–7) contains preliminary information necessary for our research. All theorems in this part are known and supplied with appropriate references; however, some of them are modified in a certain way for the sake of convenience in further usage. Most of them are proven for completeness of presentation and the reader’s convenience. The second part (Sections 2 and 8–11) contains essentially new results, which have been briefly formulated above.

2. Examples and Discussion

Example 1. Suppose that Ω = {1, 2}, and the random set X ⊂ Ω contains the elements 1, 2 with probabilities p(1), p(2), respectively. Obviously, for i = 1, 2, the expectation of the number of elements in X that are equal to i is p(i). Therefore, in the notation of the previous section, μ(i) = p(i).

Let us define a sequence of random sets X_n ⊂ Ωⁿ in the following way: each X_n contains each of 2ⁿ strings x = (x₁, …, x_n) ∈ Ωⁿ with probability p(x₁) ⋯ p(x_n). In other words, under the condition (x₁, …, x_n) ∈ X_n, the set X_n+1 contains the string (x₁, …, x_n, 1) with probability p(1) and the string (x₁, …, x_n, 2) with probability p(2). In particular, X_n+1 contains both with probability p(1)p(2) and contains neither of them with probability (1 − p(1))(1 − p(2)).

Let ν be the probability distribution on Ω, such that ν(1) = 1/3 and ν(2) = 2/3. Question: how many strings (x₁, …, x_n) in which the quota of elements that equal one is close to 1/3 and the quota of elements that equal two is close to 2/3 are there in the random set X_n? According to Formula (1), under the condition of non-degeneracy of the stochastic process X₁, X₂, X₃, …, the number of those strings with probability one has an asymptotics of order e^{−nρ(ν,μ)}, where:

$$\rho (\nu ,\mu )={\displaystyle \sum _{i\in \mathrm{\Omega }}\nu (i)\ln \frac{\nu (i)}{\mu (i)}=\frac{1}{3}\ln \frac{1/3}{p(1)}+\frac{2}{3}\ln \frac{2/3}{p(2)}.}$$

In particular, if p(1) = p(2) = 2/3, then $\rho (\nu ,\mu )=-\frac{1}{3}\ln 2$ and, respectively, e^{−nρ(ν,μ)} = 2^n/3. On the other hand, if p(1) = 1 and p(2) = 1/3, then $\rho (\nu ,\mu )=\frac{1}{3}\ln \frac{4}{3}$ and e^{−nρ(ν,μ)} = (3/4)^n/3. The latter means that for all large enough n, there are no strings x = (x₁, …, x_n) in the random set X_n, such that δ_x,n(1) ≈ 1/3 and δ_x,n(2) ≈ 2/3.

Example 2. (random Cantor dust). To each string x = (x₁, …, x_n) ∈ X_n from Example 1, let us put in correspondence a line segment I(x) ⊂ ℝ as follows:

$$\begin{array}{c}I(\varnothing )=[0,1],\\ I(1)=[0,1/4],I(2)=[1/2,1],\\ I(1,1)=[0,1/16],I(1,2)=[1/8,1/4],I(2,1)=[1/2,5/8],I(2,2)=[3/4,1],\end{array}$$

and so on. If a certain segment I(x) = I(x₁, …, x_n) has already been defined, then I(x₁, …, x_n, 1) and I(x₁, …, x_n, 2) are the left quarter and the right half of I(x), respectively. The random Cantor dust C_∞ is defined as:

$$C_{\infty }=\underset{n=1}{\overset{\infty }{\cap }}{C}_n,\text{where}{C}_n=\underset{x\in X_n}{\cup }I(x).$$

Put θ(1) = 1/4 and θ(2) = 1/2. Let the distance function on the random set of infinite strings X_∞ be defined as:

$$\text{dist}(x,y)={\displaystyle \prod _{t=1}^n\theta (x_t)},\text{where}n=\inf \{t|x_t\ne y_t\}-1.$$

Consider the mapping π: X_∞ → C_∞ that takes any infinite string x = (x₁, x₂,…) ∈ X_∞ to the point π(x) = ∩_n I(x₁, …, x_n). Obviously, this mapping is bi-Lipschitz, and hence, the Hausdorff dimensions of any subset A ⊂ X_∞ and its image π(A) ⊂ ℝ are the same. Question: what is the Hausdorff dimension of the set π(A), where:

$$A=\{x\in X_{\infty }|{\delta }_{x,n}(1)\to 1/3,{\delta }_{x,n}(2)\to 2/3\}?$$

(5)

The answer is given by Formulas (3) and (4). For example, if for each segment I(x₁, …, x_n), the “probabilities of survival” of its left quarter I(x₁, …, x_n, 1) and its right half I(x₁, …, x_n, 2) are p(1) = p(2) = 2/3, then under the condition π(A) ≠ ∅ with probability one, we have:

$${\dim }_H\pi (A)=d(\nu ,\mu ,\theta )=\frac{{\displaystyle {\sum }_{i=1}^2\nu (i)}\ln \frac{\nu (i)}{\mu (i)}}{{\displaystyle {\sum }_{i=1}^2\nu (i)}\ln \theta (i)}=\frac{\frac{1}{3}\ln \frac{1/3}{2/3}+\frac{2}{3}\ln \frac{2/3}{2/3}}{\frac{1}{3}\ln \frac{1}{4}+\frac{2}{3}\ln \frac{1}{2}}=\frac{1}{4}.$$

As far as I know, no theorem proven or published previously gives answers to the questions put in Examples 1 and 2. On the other hand, if, in the setting of Example 2, one replaces the set π(A) by the whole of π(X_∞), then dim_H π(X_∞) is computed, for instance, in [4–6] and Theorem 15.2 in [14]. The answer is given there as a solution to the so-called Bowen equation. Moreover, in those papers, dim_H π(X_∞) was computed in a more general setting when the scaling factors θ(i) ∈ [0, 1) are random.

Therefore, the following problem arises naturally: how can one compute dim_H A and dim_H π(A) for the set A defined in Formula (5) in the case of random scaling factors θ(i)? The present work does not solve this problem.

Falconer and Miao started the investigation of random self-affine fractals [7]. They considered a random iterated function system (RIFS) generated by a finite collection of contracting affine maps S_i: ℝⁿ → ℝⁿ and encoded by a random tree T_∞ that is defined exactly in the same manner as the random set of infinite genetic lines X_∞ above. It turned out that under the condition of non-degeneracy T_∞ ≠ ∅ and some additional assumptions, the attractor of RIFS with probability one has a constant dimension (Hausdorff and box-counting), which can be found as a solution to a certain equation. Recently, analogous results were obtained for random affine code tree fractals [9] and for uniformly random self-similar fractals [8]. Thereby, the natural problem arises: is it possible to compute almost sure Hausdorff dimensions for subsets of random fractals like in [7–9], provided the subsets are defined in terms of the limit behavior of the corresponding empirical measures (say, as in Formula (5))?

One more possible direction to generalize the results of the paper is the case when the distribution ν, empirical measures δ_x,n and/or the scaling factors θ(i) are defined not on the set of colors Ω, but on the whole set of infinite strings Ω^ℕ.

3. The Spectral Potential

The notion of spectral potential was introduced in [1–3]. It was defined there as a logarithm of the spectral radius of a weighted shift or transfer operator. We will use below a simplified version of the spectral potential that corresponds to an operator of weighted integration.

Let X be an arbitrary finite set. Denote by B(X) the space of all real-valued functions on X, by M(X) the set of all positive measures on X and by M₁(X) the set of all probability distributions on X.

Every measure μ ∈ M(X) defines a linear functional on B(X) of the form:

$$\mu [f]={\displaystyle {\int }_{X}fd\mu ={\displaystyle \sum _{x\in X}f(x)\mu (x)}}.$$

It is easily seen that this functional is positive (i.e., it takes nonnegative values on nonnegative functions). If, in addition, the measure μ is a probability, then this functional is normalized (i.e., μ[1] = 1).

Consider the nonlinear functional:

$$\lambda (\phi ,\mu )=\ln \mu [e^{\phi }],$$

(6)

where φ ∈ B(X) and μ ∈ M(X). We will call it the spectral potential. It is monotone (if φ ≥ ψ then λ(φ, μ) ≥ λ(ψ, μ)), additively homogeneous (that is, λ(φ + t, μ) = λ(φ, μ) + t for each constant t) and analytic in φ.

Define a family of probability measures μ_φ on X, depending on the functional parameter φ ∈ B(X), by means of the formula:

$${\mu }_{\phi }[f]=\frac{\mu [e^{\phi }f]}{\mu [e^{\phi }]},f\in B(X).$$

Evidently, each measure μ_φ is equivalent to μ and has the density e^{φ−λ(φ,μ)} with respect to μ.

Let us compute the first two derivatives of the spectral potential with respect to the argument φ. We introduce the notation:

$${{\lambda }^{\prime }(\phi ,\mu )[f]=\frac{d\lambda (\phi +tf,\mu )}{dt}|}_{t=0}.$$

This is nothing else than the derivative of the spectral potential in the direction f at the point φ. An elementary computation shows that:

$${{\lambda }^{\prime }(\phi ,\mu )[f]=\frac{d\ln \mu [e^{\phi +tf}]}{dt}|}_{t=0}=\frac{\mu [e^{\phi }f]}{\mu [e^{\phi }]}={\mu }_{\phi }[f].$$

(7)

In other words, the derivative λ′(φ, μ) coincides with the probability measure μ_φ. Now, put:

$${{\lambda }^{″}(\phi ,\mu )[f,g]=\frac{{\partial }^2\lambda (\phi +tf+sg,\mu )}{\partial s\partial t}|}_{s,t=0s}$$

and compute this derivative using the just obtained Formula (7):

$$\begin{array}{c}{{\lambda }^{″}(\phi ,\mu )[f,g]=\frac{\partial }{\partial s}\left(\frac{\mu [e^{\phi +sg}f]}{\mu [e^{\phi +sg}]}\right)|}_{s=0}=\frac{\mu [e^{\phi }fg]}{\mu [e^{\phi }]}-\frac{\mu [e^{\phi }f]\mu [e^{\phi }g]}{{(\mu [e^{\phi }])}^2}\\ ={\mu }_{\phi }[fg]-{\mu }_{\phi }[f]{\mu }_{\phi }[g].\end{array}$$

In probability theory, the expression μ_φ[f] is usually called the expectation of a random variable f with respect to the probability distribution μ_φ, and the expression μ_φ[fg] − μ_φ[f]μ_φ[g] is called the covariance of random variables f and g. In particular, the second derivative:

$${\frac{d^2\lambda (\phi +tf,\mu )}{d{t}^2}|}_{t=0}={\mu }_{\phi }[f^2]-{\mu }_{\phi }{[f]}^2={\mu }_{\phi }[{(f-{\mu }_{\phi }[f])}^2]$$

is equal to the variance of the random variable f with respect to the distribution μ_φ. Since the variance is nonnegative, it follows that the spectral potential is convex in φ.

4. The Kullback Action

Denote by B^∗(X) the space of all linear functionals on B(X). Obviously,

$$M_1(X)\subset M(X)\subset B^{*}(X).$$

For any measure μ ∈ M(X) and nonnegative function φ ∈ B(X), define a product φμ ∈ M(X) by means of the formula (φμ)(x) = φ(x)μ(x).

The Kullback action is the following functional of two arguments ν ∈ B^∗(X) and μ ∈ M(X):

$$\rho (\nu ,\mu )=\{\begin{array}{ll}\mu [\phi \ln \phi ]=\nu [\ln \phi ],& \text{if}\nu \in M_1(X)\text{and}\nu =\phi \mu ,\\ +\infty & \text{in all of the other cases}.\end{array}$$

(8)

To be more precise, “all of the other cases” fit into at least one of the three categories: (1) probability measures ν, such that ν(x₀) > 0 and μ(x₀) = 0 for a certain x₀ ∈ X; (2) non-normalized functionals ν; and (3) nonpositive functionals ν.

As far as we know, in the literature, this functional was defined only for probability measures ν and μ. Different authors call it differently: the relative entropy, the deviation function, the Kullback–Leibler information function and the Kullback–Leibler divergence.

When ν is a probability measure, the Kullback action can be defined by the explicit formula:

$$\rho (\nu ,\mu )={\displaystyle \sum _{x\in X}\nu (x)\ln \frac{\nu (x)}{\mu (x)}}.$$

(9)

In particular, if μ(x) ≡ 1, then the Kullback action differs only in sign from Shannon’s entropy:

$$H(\nu )=-{\displaystyle \sum _{x\in X}\nu (x)\ln \nu (x)}.$$

(10)

In the case of a probability measure μ, the Kullback action is nonnegative and vanishes only if ν = μ. Indeed, if the functional ν is not a probability measure that is absolutely continuous with respect to μ, then ρ(ν, μ) = +∞. Otherwise, if ν is a probability measure of the form ν = φμ, then Jensen’s inequality and strong convexity of the function f(x) = x ln x imply:

$$\rho (\nu ,\mu )=\mu [f(\phi )]\ge f(\mu [\phi ])=0$$

(since μ[φ] = ν[1] = 1) and the equality ρ(ν, μ) = 0 holds if and only if φ is constant almost everywhere, and therefore, ν coincides with μ.

Every measure μ ∈ M(X) can be written in the form μ = cμ₁, where c = μ[1] and μ₁ ∈ M₁(X). If ν ∈ M₁(X), then Formula (9) implies:

$$\rho (\nu ,\mu )=\rho (\nu ,{\mu }_1)-\ln c\ge -\ln \mu [1].$$

(11)

In case ν ∉ M₁(X), this inequality holds, as well, since the Kullback action is infinite.

Theorem 1. The spectral potential and the Kullback action satisfy the Young inequality:

$$\rho (\nu ,\mu )\ge \nu [\psi ]-\lambda (\psi ,\mu ),$$

(12)

that turns into equality if and only if ν = μ_ψ.

Proof. If ρ(ν, μ) = +∞, then the Young inequality is trivial. If ρ(ν, μ) < +∞, then by definition of the Kullback action, the functional ν is an absolutely continuous probability measure of the form ν = φμ, where φ is a nonnegative density. In this case:

$$\begin{array}{c}\lambda (\psi ,\mu )=\ln \mu [e^{\psi }]\ge \ln {\displaystyle \sum _{\phi (x)>0}{e}^{\psi (x)}\mu (x)=\ln {\displaystyle \sum _{\phi (x)>0}{e}^{\psi (x)-\ln \phi (x)}\nu (x)}}\\ =\ln \nu [e^{\psi -\ln \phi }]\ge \nu [\psi -\ln \phi ]\end{array}$$

(where at the last step, we have used Jensen’s inequality and concavity of the logarithm function). Since ρ(ν, μ) = ν[ln φ], this formula implies inequality (12).

Recall that μ_ψ = e^{ψ−λ(ψ,μ)}μ. Therefore, if ν = μ_ψ, then by definition:

$$\rho (\nu ,\mu )=\nu [\psi -\lambda (\psi ,\mu )]=\nu [\psi ]-\lambda (\psi ,\mu ).$$

Vice versa, suppose that ρ(ν, μ) = ν[ψ] − λ(ψ, μ). Then, subtracting from the above equality the Young inequality ρ(ν, μ) ≥ ν[φ] − λ(φ, μ), one obtains:

$$\lambda (\phi ,\mu )-\lambda (\psi ,\mu )\ge \nu [\phi -\psi ]$$

which implies that ν = λ′(ψ, μ). Finally, λ′(ψ, μ) coincides with μ_ψ.

Theorem 2. The Kullback action ρ(ν, μ) is the Legendre transform of the spectral potential:

$$\rho (\nu ,\mu )=\underset{\psi \in B(X)}{\sup }\{\nu [\psi ]-\lambda (\psi ,\mu )\},\nu \in B^{*}(X),\mu \in M(X).$$

(13)

Proof. By the Young inequality, the left-hand side of Formula (13) is not less than the right-hand one. Therefore, it is enough to associate with any functional ν ∈ B^∗(X) a family of functions ψ_t, depending on the real-valued parameter t, on which the equality in Formula (13) is attained.

Suppose first that ν is a probability measure that is absolutely continuous with respect to μ. Therefore, ν has the form ν = φμ, where φ is a nonnegative density. Consider the family of functions:

$${\psi }_t(x)=\{\begin{array}{ll}\ln \phi (x),& \text{if}\phi (x)>0,\\ -t,& \text{if}\phi (x)=0.\end{array}$$

When t → +∞, we have the following relations:

$$\begin{array}{c}\mu [e^{{\psi }_t}]={\displaystyle \sum _{\phi (x)>0}\phi (x)}\mu (x)+{\displaystyle \sum _{\phi (x)=0}{e}^{-t}}\mu (x)\to {\displaystyle \sum _{x\in X}\phi }(x)\mu (x)=1,\\ \nu [{\psi }_t]={\displaystyle \sum _{\phi (x)>0}\phi (x)\ln }\phi (x)\mu (x)-{\displaystyle \sum _{\phi (x)=0}t\phi (x)\mu (x)}=\mu [\phi \ln \phi ],\\ \nu [{\psi }_t]-\lambda ({\psi }_t,\mu )=\nu [{\psi }_t]-\ln \mu [e^{{\psi }_t}]\to \mu [\phi \ln \phi ]=\rho (\nu ,\mu ),\end{array}$$

and so, Formula (13) is proven.

In all other cases, when ν is not an absolutely continuous probability measure, by definition, we have ρ(ν, μ) = +∞. Let us consider these cases one after another.

If ν is a probability measure, which is singular with respect to μ, then there exists x₀ ∈ X, such that μ(x₀) = 0 and ν(x₀) > 0. In this case, consider the family of functions:

$${\psi }_t(x)=\{\begin{array}{cc}t,& \text{if}x=x_0,\\ 0,& \text{if}x\ne x_0.\end{array}$$

It is easily seen that:

$$\nu [{\psi }_t]-\lambda ({\psi }_t,\mu )\ge t\nu (x_0)-\ln \mu [e^{{\psi }_t}]\ge t\nu (x_0)-\ln \mu [1].$$

The right-hand side of the above formula goes to +∞, while t increases, and so, Formula (13) holds.

If the functional ν is not normalized, then put ψ_t(x) ≡ t. In this case, the expression:

$$\nu [{\psi }_t]-\lambda ({\psi }_t,\mu )=\nu [t]-\ln \mu [e^t]=t(\nu [1]-1)-\ln \mu [1]$$

is unbounded from above, and hence, Formula (13) is still valid.

Finally, if the functional ν is not positive, then there exists a nonnegative function φ, such that ν[φ] < 0. Consider the family ψ_t = −tφ, where t > 0. For this family:

$$\nu [{\psi }_t]-\lambda ({\psi }_t,\mu )\ge -t\nu [\phi ]-\lambda (0,\mu )\to +\infty$$

as t → +∞, and Formula (13) still remains in force. □

Corollary 1. The functional ρ(⋅, μ) is convex and lower semicontinuous on the space B^∗(X).

Proof. These are properties of the Legendre transform. □

5. The Local Large Deviations Principle and the McMillan Theorem

As above, we keep the following notation: X is a finite set; B(X) stands for the space of real-valued functions on X; B^∗(X) is the space of linear functionals on B(X); M₁(X) is the set of all probability measures on X; and M(X) is the set of all positive measures on X.

With each finite sequence x = (x₁,…, x_n) ∈ Xⁿ, we associate an empirical measure δ_x,n ∈ M₁(X), which is supported on the set {x₁,…, x_n} and assigns to every point x_i the measure 1/n. The integral of any function f with respect to δ_x,n looks like:

$${\delta }_{x,n}[f]=\frac{f(x_1)+\cdots +f(x_n)}{n}.$$

For any measure μ ∈ M(X), we denote by μⁿ its Cartesian power, which is defined on Xⁿ.

Theorem 3 (The local large deviations principle). For any positive measure μ ∈ M(X), functional ν ∈ B^∗(X) and ε > 0, there exists a neighborhood O(ν), such that:

$${\mu }^n\{x\in X^n|{\delta }_{x,n}\in O(\nu )\}\le e^{-n(\rho (\nu ,\mu )-\epsilon )}.$$

(14)

On the other hand, for any ε > 0 and any neighborhood O(ν), the following asymptotic estimate holds:

$${\mu }^n\{x\in X^n|{\delta }_{x,n}\in O(\nu )\}\ge e^{-n(\rho (\nu ,\mu )\epsilon )},n\to \infty .$$

(15)

If ρ(ν, μ) = +∞, then by the difference ρ(ν, μ) − ε in Formula (14), we mean an arbitrary positive number.

In the case of probability measure μ, Theorem 3 is a partial case of Varadhan’s large deviations principle (the explicit formulation of which can be found, e.g., in [15,16]). Therefore, this theorem can be deduced from Varadhan’s large deviations principle by means of mere renormalization of μ. Nevertheless, we will prove it independently for the sake of completeness.

Proof. By Theorem 2, for any ε > 0, there exists ψ ∈ B(X), such that:

$$\rho (\nu ,\mu )-\epsilon /2<\nu [\psi ]-\lambda (\psi ,\mu ).$$

(16)

Consider the probability measure μ_ψ = e^{ψ−λ(ψ,μ)}μ. Obviously,

$$\frac{{\mu }^n(x)}{{\mu }_{\psi }^n(x)}={\displaystyle \prod _{i=1}^n\frac{\mu (x_i)}{{\mu }_{\psi }(x_i)}={\displaystyle \prod _{i=1}^n{e}^{\lambda (\psi ,\mu )-\psi (x_i)}}=e^{n(\lambda (\psi ,\mu )-{\delta }_{x,n}[\psi ])}}.$$

(17)

Define a neighborhood of the functional ν as follows:

$$O(\nu )=\{\delta \in B*(X)|\delta [\psi ]>\nu [\psi ]-\epsilon /2\}.$$

Then, it follows from Formulas (17) and (16) that under the condition δ_x,n ∈ O(ν),

$$\frac{{\mu }^n(x)}{{\mu }_{\psi }^n(x)}<e^{n(\lambda (\psi ,\mu )-\nu [\psi ]+\epsilon /2)}<e^{n(-\rho (\nu ,\mu )+\epsilon )}.$$

Consequently,

$$\begin{array}{c}{\mu }^n\{x\in X^n|{\delta }_{x,n}\in O(\nu )\}={\displaystyle \sum _{{\delta }_{x,n}\in O(\nu )}{\mu }^n(x)}\le {\displaystyle \sum _{{\delta }_{x,n}\in O(\nu )}{e}^{n(-\rho (\nu ,\mu )+\epsilon )}{\mu }_{\psi }^n(x)}\\ \le e^{-n(\rho (\nu ,\mu )-\epsilon )}.\end{array}$$

Thus, the first part of Theorem 3 is proven.

If ρ(ν, μ) = +∞, then estimating Formula (15) is trivial. Therefore, it is enough to prove it only for the case when ν is a probability measure of the form ν = φμ, and the Kullback action ρ(ν, μ) = ν[ln φ] is finite. Fix any number ε > 0 and any neighborhood O(ν). Define the sets:

$$Y_n=\{x\in X^n|{\delta }_{x,n}\in O(\nu ),|{\delta }_{x,n}[\ln \phi ]-\nu [\ln \phi ]|<\epsilon /2\}$$

(the last inequality in the braces implies that φ(x_i) > 0 at each point of the sequence x = (x₁,…,x_n)). Note that for x ∈ Y_n,

$$\frac{{\mu }^n(x)}{{\nu }^n(x)}={\displaystyle \prod _{i=1}^{n}s\frac{\mu (x_i)}{\nu (x_i)}={\displaystyle \prod _{i=1}^n\frac{1}{\phi (x_i)}=e^{-n{\delta }_{x,n}[\ln \phi ]}>e^{-n(\nu [\ln \phi ]+\epsilon /2)}.}}$$

Consequently,

$${\mu }^n(Y_n)={\displaystyle \sum _{x\in Yn}{\mu }^n(x)}\ge {\displaystyle \sum _{x\in Yn}{e}^{-n(\nu [\ln \phi ]+\epsilon /2)}{\nu }^n(x)=e^{-n\rho (\nu ,\mu )-n\epsilon /2)}{\nu }^n(Y_n)}.$$

(18)

By the Law of large numbers νⁿ(Y_n) → 1. Hence, Formula (18) implies Formula (15).

Corollary 2 (The McMillan theorem). For any probability measure ν ∈ M₁(X) and ε > 0, there exists a neighborhood O(ν), such that:

$$\#\{x=(x_1,\dots ,x_n)\in X^n|{\delta }_{x,n}\in O(\nu )\}\le e^{n(H(\nu )+\epsilon )}.$$

On the other hand, for any neighborhood O(ν) and ε > 0:

$$\#\{x\in X^n|{\delta }_{x,n}\in O(\nu )\}\ge e^{n(H(\nu )-\epsilon )}asn\to \infty .$$

Here, H(ν) denotes Shannon’s entropy defined in Formula (10).

Proof. This follows from Formulas (9) and (10) and Theorem 3 if we set μ(x) = 1 for all x ∈ X.

6. Hausdorff Dimension and the Maximal Dimension Principle

Let us define the Hausdorff dimension of an arbitrary metric space Ω.

Suppose that Ω is covered by at most a countable collection of sets U = {U_i}. Denote by |U| the diameter of this covering: |U| = sup |U_i|, where |U_i| is the diameter of U_i. For every α ∈ ℝ, put:

$$\text{mes}(\mathcal{U},\alpha )={\displaystyle \sum _i|U_i{|}^{\alpha }}.$$

The Hausdorff measure (of dimension α) of the metric space Ω is:

$$\text{mes}(\mathrm{\Omega },\alpha )=\underset{\left|\mathcal{U}\right|\to 0}{\lim \inf }\text{mes}(\mathcal{U},\alpha ),$$

where U is at most a countable covering of Ω. Obviously,

$$\text{mes}(\mathcal{U},\beta )\le (\mathcal{U},\alpha )|\mathcal{U}{|}^{\beta -\alpha }\text{if}\beta \ge \alpha .$$

This implies the basic property of the Hausdorff measure: if mes(Ω, α) < ∞ for some α, then mes(Ω, β) = 0 for all β > α.

The Hausdorff dimension of the space Ω is the number:

$${\text{dim}}_H\mathrm{\Omega }=\text{inf}\left\{\alpha \right|\text{mes}(\mathrm{\Omega },\alpha )=0\}.$$

(19)

In other words, dim_H Ω = α₀ if mes(Ω, α) = 0 for all α > α₀ and mes(Ω, α) = ∞ for all α < α₀.

Note that, according to this definition, we obtain dim_H Ω = −∞ when Ω = ∅ and dim_H Ω = 0 when Ω is nonempty finite or countable.

Below, we will consider the space of sequences:

$$X^{\mathrm{\mathbb{N}}}=\{x=(x_1,x_2,x_3,\dots )\},x_i\in X=\{1,\dots ,r\}.$$

Let x = (x₁, x₂, …) ∈ X^ℕ. Denote by Z_n(x) the set of all sequences y = (y₁, y₂,…) whose first n coordinates coincide with the same coordinates of x. This set will be called a cylinder of rank n. In particular, Z₀(x) = X^ℕ. All cylinders generate the Tychonoff topology on the space X^ℕ and the cylinder σ-algebra of subsets in X^ℕ.

On the set of all cylinders, we fix an arbitrary positive function η that possesses the following two properties: first, if Z_n(x) ⊂ Z_m(y), then η(Z_n(x)) ≤ η(Z_m(y)) and, second, η(Z_n(x)) 0 → as n → ∞ at each point x ∈ X^ℕ. Define the cylindrical metric on X^ℕ by means of the formula:

$$\text{dist}(x,y)=\eta (Z_n(x)),\text{where}n=max\left\{m\right|Z_m(x)=Z_m(y)\}.$$

(20)

Evidently, the diameter of Z_n(x) in this metric coincides with η(Z_n(x)).

Suppose that in addition to cylindrical metric (20) on X^ℕ, there is given a Borel measure μ on X^ℕ. The function:

$$d_{\mu }(x)=\underset{n\to \infty }{\lim \inf }\frac{\ln \mu (Z_n(x))}{\ln |Z_n(x)|}$$

is called the (lower) pointwise dimension of the measure μ.

The next theorem provides an effective tool for computing the Hausdorff dimensions of various subsets of X^ℕ.

Theorem 4. Suppose A ⊂ X^ℕ. If there exists a finite Borel measure μ on X^ℕ, such that d_μ(x) ≤ d for each point x ∈ A, then dim_H A ≤ d. On the contrary, if d_μ(x) ≥ d for each x ∈ A and the outer measure μ^∗(A) is positive, then dim_H A ≥ d.

It follows that if d_μ(x) ≡ d on the whole of the subset A ⊂ X^ℕ, then its dimension is equal to d.

A weakened version of the second part of Theorem 4 in which the condition d_μ(x) ≥ d is replaced by a more strong one μ(Z_n(x)) ≤ |Z_n(x)|^d is usually called the mass distribution principle.

Theorem 4 was first proven by Billingsley in the case when the function η in Formula (20) is a probability measure on X^ℕ (see Theorems 2.1 and 2.2 in [11]). An analog to this theorem for subsets A ⊂ R^r was proven in works [12,13].

Proof. Every cylinder Z_n(x) is, in fact, a ball in metric (20), whose radius equals its diameter, and vice versa, any ball in this metric coincides with a cylinder. Besides, any two cylinders Z_n(x) and Z_m(y) either have an empty intersection or one of them is embedded in the other. Therefore, while computing the Hausdorff measure and the dimension of a subset A ⊂ X^ℕ, it is enough to operate only with disjoint coverings of A by cylinders.

Suppose first that d_μ(x) < α for all points x ∈ A. Then, for each x ∈ A, there exist arbitrarily small cylinders Z_n(x) satisfying the condition |Z_n(x)|^α < μ(Z_n(x)). Using cylinders of this kind, we can arrange a disjoint covering U of the set A of arbitrarily small diameter. For this covering, we have:

$$\text{mes}(\mathcal{U},\alpha )={\displaystyle \sum _{Z_n(x)\in \mathcal{U}}|Z_n(x){|}^{\alpha }}\le {\displaystyle \sum _{Z_n(x)\in \mathcal{U}}\mu }(Z_n(x))\le \mu (X^{\mathrm{\mathbb{N}}}),$$

and hence, dim_H A ≤ α. Thus, the first part of the theorem is proven.

Suppose now that d_μ(x) > α for all points x ∈ A. Define the sets:

$$A_{\epsilon }=\left\{x\in A|\right|Z_n(x){|}^{\alpha }>\mu (Z_n(x))\text{whenever}|Z_n(x)|<\epsilon \}.$$

Obviously, A = ∪_ε>0 A_ε. Hence, there exists an ε, such that μ^∗(A_ε) > 0. Let U be a disjoint covering of A by cylinders of diameters less than ε. From the definition of A_ε, it follows that mes(U, α) ≥ μ^∗(A_ε). Therefore, dim_H A ≥ α, and thus, the second part of the theorem is proven.

Each point x = (x₁, x₂, …) ∈ X^ℕ generates a sequence of empirical measures δ_x,n on the set X:

$${\delta }_{x,n}(i)=\frac{\#\left\{t\right|x_t=i,t\le n\left|\right\}}{n},i\in X.$$

In other words, δ_x,n(i) is the fraction of coordinates of the vector (x₁,…, x_n) coinciding with i.

For every probability measure ν ∈ M₁(X), let us define its basin B(ν) as the set of all points x ∈ X^ℕ, such that δ_x,n converges to ν:

$$B(v)=\{x\in X^{\mathrm{\mathbb{N}}}|{\delta }_{x,n}\to v\}.$$

Evidently, basins different measures do not intersect each other and are nonempty. If x ∈ B(ν) and y ∈ X^ℕ differs from x in only finite number of coordinates, then y ∈ B(ν). This implies the density of each basin in X^ℕ.

Every measure ν ∈ M₁(X) generates the Bernoulli distribution P_ν = ν^ℕ on X^ℕ. By the strong law of large numbers, the basin B(ν) has probability one with respect to Bernoulli distribution P_ν, and its complement has zero probability P_ν. In particular, any basin different from B(ν) has zero probability.

Points that do not belong to the union of all basins will be called irregular. The set or irregular points has zero probability with respect to any distribution P_ν, where ν ∈ M₁(X). As a result, X^ℕ turns out to be decomposed into the disjoint union of different basins and the set of irregular points.

Let us fix some numbers θ(i) ∈ (0, 1) for all elements i ∈ X = {1,…, r} and define a cylindrical θ-metric on X^ℕ by the rule:

$$\text{dist}(x,y)={\displaystyle \prod _{t=1}^n\theta (x_t),n=\inf \{t|x_t\ne y_t\}-1.}$$

(21)

It is a partial case of cylindrical metric (20).

For each measure ν ∈ M₁(X) and θ-metric (21), define the quantity:

$$S(v,\theta )=\frac{{\sum }_{i=1}^{r}v(i)\ln v(i)}{{\sum }_{i=1}^{r}v(i)\ln \theta (i)}.$$

(22)

We will call it the Billingsley entropy, because he was the first who wrote down this formula and applied it for the computation of the Hausdorff dimensions [10]. He also expressed this quantity in terms of Shannon’s entropy and the Kullback action:

$$S(v,\theta )=\frac{H(v)}{H(v)+\rho (v,\theta )}.$$

Theorem 5. The Hausdorff dimension of any basin B(ν) with respect to θ-metric (21) is equal to the Billingsley entropy S(ν, θ).

A partial case of this theorem, in which θ(1) = ⋯ = θ(r) = 1/r, was first proven by Eggleston [17]. In the complete form, this theorem and its generalizations were proven by Billingsley [10,11].

Proof. Assume first that ν(i) > 0 for every i = 1,…, r. Obviously,

$$\frac{\ln P_v(Z_n(x))}{\ln |Z_n(x)|}=\frac{{\sum }_{t=1}^n\ln v(x_t)}{{\sum }_{t=1}^n\ln \theta (x_t)}=\frac{{\sum }_{i=1}^{r}n{\delta }_{x,n}(i)\ln v(i)}{{\sum }_{i=1}^{r}n{\delta }_{x,n}(i)\ln \theta (i)}.$$

Hence, for each point x ∈ B(ν), we have:

$$d_{P_v}(x)=\underset{x\to \infty }{\lim \inf }\frac{\ln P_v(Z_n(x))}{\ln |Z_n(x)|}=\frac{{\sum }_{i=1}^{r}v(i)\ln v(i)}{{\sum }_{i=1}^{r}v(i)\ln \theta (i)}=S(v,\theta ).$$

(23)

Applying Theorem 4 to the set A = B(ν) and measure μ = P_ν, we obtain the statement of Theorem 5.

In the general case, the same argument provides only the lower bound $d_{P_{\nu }}(x)\ge S(\nu ,\theta )$, which implies the lower bound dim_H B(ν) ≥ S(ν, θ). The inverse inequality is provided by the next lemma.

Lemma 1. Suppose that X^ℕ is equipped with metric (21). Then, for any measure ν ∈ M₁(X) and ε > 0, there exists a neighborhood O(ν), such that the Hausdorff dimension of the set:

$$A=\{x\in X^{\mathrm{\mathbb{N}}}|\forall N\exists n>N:{\delta }_{x,n}\in O(v)\}$$

does not exceed S(ν, θ) + ε.

Proof. Fix a measure ν ∈ M₁(X) and an arbitrary positive number x. By McMillan’s theorem, there exists a neighborhood O(ν), such that for each positive integer n:

$$\#\{Z_n(x)|{\delta }_{x,n}\in O(v)\}\le e^{n(H(v)+x)}.$$

(24)

Decrease this neighborhood in such a way that, in addition to Formula (24), for every measure δ ∈ O(ν), the next inequality holds:

$${\displaystyle \sum _{i=1}^r\delta (i)\ln \theta (i)}<{\displaystyle \sum _{i=1}^{r}v}(i)\ln \theta (i)+x.$$

Then, for every cylinder Z_n(x) satisfying the condition δ_x,n ∈ O(ν), we have the estimate:

$$\begin{array}{c}|Z_n(x)|={\displaystyle \prod _{t=1}^n\theta }(x_t)=\exp \left\{{\displaystyle \sum _{t=1}^n\ln \theta (x_t)}\right\}=\exp \left\{n{\displaystyle \sum _{i=1}^r{\delta }_{x,n}}(i)\ln \theta (i)\right\}\\ <\exp \left\{n{\displaystyle \sum _{i=1}^{r}v}(i)\ln \theta (i)+nx\right\}.\end{array}$$

(25)

For any positive integer N, the set A is covered by the collection of cylinders:

$${\mathcal{U}}_N={\displaystyle \underset{n=N}{\overset{\infty }{\cup }}\{Z_n}(x)|{\delta }_{x,n}\in O(v)\}.$$

Evidently, the diameter of this covering goes to zero when N increases. Now, we can evaluate mes(U_N, α) by means of Formulas (24) and (25):

$$\begin{array}{c}\text{mes}({\mathcal{U}}_N,\alpha )={\displaystyle \sum _{Z_n(x)\in {\mathcal{U}}_N}|Z_n(x){|}^{\alpha }}\\ \le {\displaystyle \sum _{n=N}^{\infty }{e}^{n(H(v)+x)}}\exp \left\{\alpha n{\displaystyle \sum _{i=1}^{r}v(i)\ln }\theta (i)+\alpha nx\right\}\\ ={\displaystyle \sum _{n=N}^{\infty }\exp }\left\{n\left(-{\displaystyle \sum _{i=1}^{r}v}(i)\ln v(i)+\alpha {\displaystyle \sum _{i=1}^{r}v(i)\ln }\theta (i)+x+\alpha x\right)\right\}.\end{array}$$

(26)

If α > S(ν, θ), then we can choose κ > 0 so small that the exponent in braces in Formula (26) is negative, and all of the sum in Formula (26) goes to zero as N → ∞. Therefore, the Hausdorff measure (of dimension α) of the set A is zero, and hence, dim_H A does not exceed α.

We will say that a sequence of empirical measures δ_x,n condenses on a subset V ⊂ M₁(X) (notation: δ_x,n ≻ V) if it has at least one limit point in V.

Similar to the known large deviations principle by Varadhan [15,16], it is natural to call the next theorem the maximal dimension principle.

Theorem 6. Let the space X^ℕ be equipped with cylindrical θ-metric (21). Then, for any nonempty subset V ⊂ M₁(X):

$${\dim }_H\{x\in X^{\mathrm{\mathbb{N}}}|{\delta }_{x,n}\succ V\}=\underset{v\in V}{\sup }S(v,\theta ).$$

(27)

Proof. The set A = {x ∈ X^ℕ | δ_x,n ≻ V} contains basins of all measures ν ∈ V. Therefore, by Theorem 5, its dimension is not less than the right-hand side of Formula (27).

It is easily seen from the definition (22) of the Billingsly entropy S(ν, θ) that it depends continuously on the measure ν ∈ M₁(X). Consider the closure $\overline{V}$ of V. Obviously, it is compact. Fix any ε > 0. By Lemma 1 for any measure $v\in \overline{V}$, there exists a neighborhood O(ν), such that:

$${\dim }_H\{x\in X^{\mathrm{\mathbb{N}}}|{\delta }_{x,n}\succ O(v)\}\le S(v,\theta )+\epsilon \le \underset{v\in V}{\sup }S(v,\theta )+\epsilon .$$

(28)

Let us take a finite covering of $\overline{V}$ composed of neighborhoods of this sort. Then, the set A = {x ∈ X^ℕ | δ_x,n ≻ V} will be covered by a finite collection of sets of the form {x ∈ X^ℕ | δ_x,n ≻ O(ν)} satisfying inequality Formula (28). By the arbitrariness of ε, this implies the statement of Theorem 6.

A result very similar to Theorem 6 was proven by Billingsley in Theorem 7.1 in [10].

7. Branching Processes

First, let us recall the basic notions about the simplest Galton–Watson branching process.

Suppose that a random variable Z takes nonnegative values k ∈ Z₊ with probabilities p_k. The Galton–Watson branching process is a sequence of random variables Z₀, Z₁, Z₂,…, such that Z₀ ≡ 1, Z₁ = Z, and further, each Z_n+1 is defined as the sum of Z_n independent counterparts of the random variable Z. In particular, if Z_n = 0, then Z_n+1 = 0, as well. Usually, Z_n is understood as the total number of descendants in the n-th generation of a unique common ancestor under the condition that each descendant independently of the others gives birth to Z children.

It is known that in some cases, the posterity of the initial ancestor may degenerate (when starting from a certain n, all Z_n are zeros), and in other cases, it can “flourish” (when Z_n grows exponentially). The type of behavior of a branching process depends on the mean number of children of any individual:

$$m=\mathrm{⋿}Z={\displaystyle \sum _{k=0}^{\infty }k{p}_k}$$

and on the generating function of that number:

$$f(s)=f_1(s)={\displaystyle \sum _{k=0}^{\infty }{p}_k{s}^k.}$$

Obviously, the restriction of the function f(s) to the segment [0, 1] is nonnegative, nondecreasing, convex and satisfies f(1) = 1 and f′(1) = m.

In the theory of branching processes (see, for instance, [18,19]), the following statements were proven.

Theorem 7. The generating functions of the number of descendants in the n-th generation:

$$f_n(s)={\displaystyle \sum _{k=0}^{\infty }\mathrm{P}}\{Z_n=k\}{s}^k$$

satisfy the recursion relation f_n+1(s) = f(f_n(s)).

Theorem 8. If m ≤ 1, then the branching process degenerates almost surely (except the case when each individual gives birth to exactly one child). If m > 1, then the probability of degeneration q is less than one and coincides with a unique non-unit root of the equation f(s) = s on the segment [0, 1].

Theorem 9. If m > 1 and EZ² < ∞, then the sequence W_n = Z _n/mⁿ converges almost surely to a random variable W, such that P{W > 0} = 1 − q. If m > 1 and EZ² = ∞, then, for any number m⁰ < m, with probability 1 − q:

$$\begin{array}{cc}\underset{n\to \infty }{\lim }{Z}_n/m^n<\infty ,& \underset{n\to \infty }{\lim }{Z}_n/{(m^{\prime })}^n=\infty \end{array}$$

(here, q is the probability of degeneration of the branching process).

Thereby, in the case m > 1, there is an alternative for the total number of descendants Z_n: either it vanishes at a certain moment n₀ (with probability q < 1) or it is asymptotically equivalent to Wmⁿ (with the complementary probability 1 − q), where the random variable W > 0 does not depend on n (except the case EZ² = ∞, when only the logarithmic equivalence ln Z_n ∼ ln mⁿ is guaranteed). All of the other types of behavior of descendants’ totality have zero probability.

We will exploit these theorems in the study of colored branching processes.

Suppose now that each individual may give birth to children of r different colors (or r different genders, if one likes). We will assume that the posterity of each individual in the first generation is a random set X containing a random number k₁ of children of the first color, a random number k₂ of children of the second color, and so on, up to a random number k_r of children of color r. All of the elements of X (including elements of the same color) are treated as different. The ordered array $k=\left(k_1,\dots ,k_r\right)\in {\mathbb{Z}}_{+}^r$ will be called the color structure of the set X of children. Denote by p_k the probability of the birth of the set X with color structure k = (k₁, k₂,…, k_r). Naturally, all of the probabilities p_k are nonnegative and:

$${\displaystyle \sum _{k\in {\mathbb{Z}}_{+}^r}{p}_k=1.}$$

If an individual x₁ gave birth to x₂, then x₂ gave birth to x₃, and so on, up to an individual x_n, then the sequence x = (x₁,…, x_n) will be called a genetic line of length n.

Let us construct a new branching process taking into account not only the total number of descendants, but also the color of each individual and all its upward and downward lineal relations. This process may be treated as a random genealogical tree with a common ancestor in the root and all its descendants in the vertices, where each parent is linked with all its children. In the case of a degenerating population, its genealogical tree is finite, and in the case of a “flourishing” one, the tree is infinite.

Formally, it is convenient to define such a process as a sequence of random sets X_n containing all genetic lines of length n. As the first set X₁, we take X. The subsequent sets X_n are built by induction: if X_n is already known, then for all genetic lines (x₁,…, x_n) ∈ X_n, one defines disjoint independent random sets of children X(x₁,…, x_n), each with a color structure distribution as in X, and X_n+1 is given by:

$$X_{n+1}=\{(x_1,\dots ,x_n,x_{n+1})|(x_1,\dots ,x_n)\in X_n,x_{n+1}\in X(x_1,\dots ,x_n)\}.$$

The stochastic process X₁, X₂, X₃,… built in this way will be referred to as a colored branching process (or unconditional colored branching process, if one wishes to emphasize that the posterity of any individual is independent of its color and genealogy).

8. The McMillan Theorem for Colored Branching Processes

Consider a colored branching process X₁, X₂, X₃,… with a given finite collection of colors Ω = {1,…, r} and a probability distribution $\{p_k|k\in {\mathbb{Z}}_{+}^r\}$, where k = (k₁,…, k_r) is the color structure of each individual’s set of children X. We will always assume that X₁ = X is generated by a unique initial individual.

For any genetic line x = (x₁,…, x_n) ∈ X_n, define the spectrum δ_x,n as the corresponding empirical measure on Ω given by the rule:

$$\begin{array}{cc}{\delta }_{x,n}(i)=\frac{\#\left\{t\right|g(x_t)=i\}}{n},& i\in \mathrm{\Omega },\end{array}$$

(29)

where g(x_t) denotes the color of x_t. In other words, δ_x,n(i) is the fraction of individuals of color i in the genetic line x. Our next goal is to obtain asymptotical estimates for cardinalities of the random sets:

$$\{x=(x_1,\dots ,x_n)\in X_n|{\delta }_{x,n}\in O(\nu )\},$$

where O(ν) is a small neighborhood of the distribution ν on the set of colors Ω.

Denote by μ(i) the expectation of members of color i in X:

$$\begin{array}{cc}\mu (i)={\displaystyle \sum _{k\in {\mathbb{Z}}_{+}^r}{k}_i{p}_k},& i=1,\dots ,r.\end{array}$$

(30)

Provided all μ(i) are finite, the vector μ = (μ(1),…, μ(r)) can be regarded as a measure on the set of colors Ω. This measure generates the measure μⁿ on Ωⁿ as a Cartesian product.

Define a mapping G : X_n → Ωⁿ by means of the formula:

$$G(x_1,\dots ,x_n)=(g(x_1),\dots ,g(x_n)),$$

where g(x_t) is the color of x_t.

Lemma 2. For any$\omega =({\omega }_1,\dots ,{\omega }_n)\in {\mathrm{\Omega }}^n$, we have:

$$\mathrm{⋿}\#\{x\in X_n|G(x)=\omega \}={\displaystyle \prod _{t==1}^n\mu ({\omega }_t)={\mu }^n(\omega ).}$$

(31)

Proof. Discard the last coordinate in ω, and let ${\omega }^{\prime }=({\omega }_1,\dots ,{\omega }_{n-1})$. For every genetic line (x₁,…, x_n−1) ∈ X_n−1, by virtue of the definition of unconditional colored branching process, we have:

$$\mathrm{⋿}\#\{x_n\in X(x_1,\dots ,x_{n-1})|g(x_n)={\omega }_n\}=\mu ({\omega }_n).$$

Evidently, this expression does not depend on x′ = (x₁,…, x_n−1). Therefore,

$$\mathrm{⋿}\#\{x_n\in X_n|G(x)=\omega \}=\mathrm{⋿}\#\{x^{\prime }\in X_{n-1}|G(x^{\prime })={\omega }^{\prime }\}=\mu ({\omega }_n).$$

Repeated application of the latter equality gives Formula (31).

For the measure μ from Formula (30), let us define the Kullback action:

$$\begin{array}{cc}\rho (\nu ,\mu )={\displaystyle \sum _{i\in \mathrm{\Omega }}\nu (i)\ln \frac{\nu (i)}{\mu (i)},}& \nu \in M_1(\mathrm{\Omega })\end{array},$$

where M₁(Ω) is the set of all probability measures on Ω. This formula is a copy of Formula (9).

Theorem 10. Suppose X₁, X₂, X₃,… is an unconditional colored branching process with a finite collection of colors Ω. Then, for any ε > 0 and probability measure ν ∈ M₁(Ω), there exists a neighborhood O(ν) ⊂ M₁(Ω), such that for all natural n:

$$\mathrm{⋿}\#\{x\in X_n|{\delta }_{x,n}\in O(\nu )\}\le e^n{}^{(-\rho (\nu ,\mu )+\epsilon )}.$$

(32)

On the other hand, for any ε > 0 and any neighborhood O(ν):

$$\begin{array}{cc}\mathrm{⋿}\#\{x\in X_n|{\delta }_{x,n}\in O(\nu )\}\le e^n{}^{(-\rho (\nu ,\mu )+\epsilon )}& asn\to \infty \end{array}.$$

(33)

If ρ(ν, μ) = +∞, the expression −ρ(ν, μ) + ε in Formula (32) should be treated as an arbitrary negative real number.

Proof. It follows from Formula (29) that, for every genetic line x ∈ X_n, its spectrum δ_x,n coincides with the empirical measure δ_ω,n, where ω = G(x). Therefore,

$$\begin{array}{cc}\#\{x\in X_n|{\delta }_{x,n}\in O(\nu )\}=& {\displaystyle \sum _{\omega \in {\mathrm{\Omega }}^n:{\delta }_{\omega ,n}\in O(\nu )}\#\{x\in X_n|G(x)=\omega \}}.\end{array}$$

(34)

It follows from Formulas (31) and (34) that:

$$\mathrm{⋿}\#\{x\in X_n|{\delta }_{x,n}\in O(\nu )\}={\mu }^n\{\omega \in {\mathrm{\Omega }}^n|{\delta }_{\omega ,n}\in O(\nu )\}.$$

The latter equality converts estimate Formulas (32) and (33) into already proven estimate Formulas (14) and (15) from the large deviations principle.

It is remarkable that the last reference to the large deviations principle serves as a unique “umbilical cord” linking the first three Sections of the paper with the others.

Now, we are ready to state an analog of the McMillan theorem for colored branching processes. Let q^∗ be the probability of degeneration of the process (the probability of the event when starting from a certain number n all of the sets X_n turn out to be empty).

Theorem 11. Suppose that X₁, X₂,… is an unconditional colored branching process with a finite collection of colors Ω. Then, for any ε > 0 and any probability measure ν ∈ M₁(Ω), there exists a neighborhood O(ν) ⊂ M₁(Ω), such that almost surely:

$$\begin{array}{cc}\#\{x\in X_n|{\delta }_{x,n}\in O(\nu )\}=<e^{n(-\rho (\nu ,\mu )+\epsilon )}& asn\to \infty \end{array}.$$

(35)

On the other hand, if ρ(ν, μ) < 0, then, for any neighborhood O(ν) and positive ε, the estimate:

$$\begin{array}{cc}\#\{x\in X_n|{\delta }_{x,n}\in O(\nu )\}=<e^{n(-\rho (\nu ,\mu )-\epsilon )}& asn\to \infty \end{array}.$$

(36)

holds with probability 1 − q^∗ (or almost surely under the condition that our branching process does not degenerate).

Proof. The application of Chebyshev’s inequality to Formula (32) gives:

$$\mathrm{P}\{\#\{x\in X_n|{\delta }_{x,n}\in O(\nu )\}\ge e^{n(-\rho (\nu ,\mu )+2\epsilon )}\}\le e^{-n\epsilon }.$$

Summing up these inequalities over all n ≥ N, one obtains:

$$\mathrm{P}\{\exists n\ge N:\#\{x\in X_n|{\delta }_{x,n}\in O(\nu )\}\ge e^{n(-\rho (\nu ,\mu )+2\epsilon )}\}\le \frac{e^{-N\epsilon }}{1-e^{-\epsilon }}.$$

This implies Formula (35) with constant 2ε instead of ε, which does not change its sense.

Now, we proceed to the second part of the theorem. Let x = −ρ(ν, μ) − ε and, at the same time, the number ε be so small that x > 0. By the second part of Theorem 10, for any neighborhood O(ν), there exists N, such that:

$$\mathrm{⋿}\#\{x\in X_N|{\delta }_{x,N}\in O(\nu )\}>e^{Nx}.$$

Without loss of generality, we may assume that O(ν) is convex.

Now, we wish to construct a Galton–Watson branching process Z₁, Z₂,… satisfying the conditions:

$$Z_1=\#\{x\in X_N|{\delta }_{x,N}\in O(\nu )\},$$

(37)

$$\begin{array}{cc}{Z}_n\le \#\{x\in X_{nN}|{\delta }_{x,nN}\in O(\nu )\},& n=2,3,\dots \end{array}$$

(38)

Let the random variable Z₁ be defined by Formula (37). For n > 1, set Z_n to be the total number of genetic lines:

$$(x_1,\dots ,x_n,\dots ,x_{(n-1)N+1,\dots ,x{n}_N})\in X_{nN}$$

such that the spectrum of each segment (x_kN+1,…, x_(k+1)N) belongs to O(ν). In other words, we treat as “individuals” of the process Z₁, Z₂, Z₃,… those segments (x_kN+1,…, x_(k+1)N) of genetic lines of the initial process whose spectrum lies in O(ν). Now, Formula (38) follows from convexity of O(ν); and from the unconditionality of the initial colored branching process, it can be concluded that the sequence Z₁, Z₂,… in fact forms a Galton–Watson branching process.

By construction, one has EZ₁ > e^Nx. In this setting, Theorem 9 asserts that there is an alternative for the sequence Z_n: either it tends to zero with a certain probability q < 1 or it grows faster than e^nNx with probability 1 − q. In the second case, Formula (38) implies:

$$\begin{array}{cc}\#\{x\in X_{nN}|{\delta }_{x,nN}\in O(\nu )\}{e}^{-nNx}\to \infty ,& n\to \infty \end{array}.$$

(39)

To finish the proof, we have to do two things: verify that Formula (39) is valid with probability 1 − q^∗ and get rid of the multiplier N there. To do this, we will exploit two ideas. First, if the colored branching process X₁, X₂,… had been generated by m initial individuals instead of a unique one, then Formula (39) would be valid with a probability of at least 1 − q^m. Second, if one genetic line is a part of another one and the ratio of their lengths is close to one, then their spectra are close to each other, as well.

Obviously, the total number of individuals in the n-th generation of the initial branching process X₁, X₂, X₃,… equals |X_n|. The sequence of random variables |X_n| forms a Galton–Watson branching process with the probability of degeneration q^∗, that does not exceed q. Therefore, the sequence |X_n| grows exponentially with probability 1 − q^∗.

Consider the colored branching process X_k+1, X_k+2, X_k+3,… obtained from the initial one by truncation of the first k generations. It can be thought of as a union of |X_k| independent branching processes generated by all individuals of k-th generation. Therefore, it satisfies Formula (39) with probability at least $1-q^{|X_k|}$. Hence, for the initial process with even greater probability, we obtain the condition:

$$\begin{array}{cc}\#\{x\in X_{k+nN}|{\delta }_{x,k+nN}\in O*(\nu )\}{e}^{-nNx}\to \infty ,& n\to \infty \end{array}.$$

(40)

where O^∗(ν) is an arbitrary neighborhood of ν containing the closure of O(ν).

Suppose that the sequence |X_n| grows exponentially. For every m ∈ ℕ, we set the numbers:

$$\begin{array}{cc}{k}_i=min\{k:|X_k|\ge m,k=i\mathrm{mod}N\},& i=0,1,\dots N-1\end{array}.$$

For each k = k_i, condition (40) holds with probability at least 1 − q^m, and together, they give the estimate:

$$\begin{array}{cc}\#\{x\in X_n|{\delta }_{x,n}\in O*(\nu )\}{e}^{nx},& n\to \infty \end{array},$$

with probability at least 1 − Nq^m. By the arbitrariness of m, this estimate is valid almost surely (under the condition |X_n| → ∞, which takes place with probability 1−q^∗). It is equivalent to Formula (36).

9. Dimensions of Random Fractals (Upper Bounds)

Here, we continue the investigation of a colored branching process X₁, X₂,… with a finite collection of colors Ω = {1,…, r}. Let us consider the corresponding set of infinite genetic lines:

$$X_{\infty }=\{x=(x_1,x_2,x_3,\dots )|(x_1,\dots ,x_n)\in X_n\forall n\in \mathbb{N}\}.$$

Define the cylindrical θ-metric on X_∞:

$$\begin{array}{cc}\text{dist}(x,y)={\displaystyle \prod _{t=1}^n\theta (x_t)},& n=\inf \{t|x_t\ne y_t\}\end{array}-1,$$

(41)

where the numbers θ(1),…, θ(r) are taken from (0, 1).

We will be interested in the Hausdorff dimensions of both the space X_∞ and its various subsets, defined in terms of the partial limits of empirical measures on Ω (we call these measures spectra; see Formula (29), and denote by δ_x,n). If the colored branching process degenerates, then X_∞ = ∅. Therefore, the only case of interest is when m = E|X₁| > 1, and the cardinality of X_n increases with a rate of order mⁿ.

As before, we denote by μ(i), where i ∈ Ω, the expectation of individuals of color i in the random set X₁. It will be always assumed that μ(i) < ∞. Consider any probability measure ν ∈ M₁(Ω). It will be proven below that the dimension of the set {x ∈ X_∞ | δ_x,n → ν} can be computed by means of the function:

$$d(\nu ,\mu ,\theta )=\frac{\rho (\nu ,\mu )}{{\displaystyle {\sum }_{i=1}^r\nu (i)\ln \theta (i)}}=\frac{{\displaystyle {\sum }_{i=1}^r\nu (i)\ln \frac{\nu (i)}{\mu (i)}}}{{\displaystyle {\sum }_{i=1}^r\nu (i)\ln \theta (i)}}.$$

(42)

We will call it the Billingsley–Kullback entropy.

The numerator in Formula (42) is the Kullback action, and the denominator is negative. If μ is a probability measure on Ω, then the Kullback action is nonnegative. However, in our setting, this is not the case, since m = μ(1) + ⋯ + μ(r) > 1. In particular, if μ(i) > ν(i), for all i ∈ Ω, then the Kullback action is negative, and the Billingsley–Kullback entropy is positive. Note, in addition, that if μ(1) = ⋯ = μ(r) = 1, then −ρ(ν, μ) is equal to Shannon’s entropy H(ν), and the Billingsley–Kullback entropy turns into the Billingsley entropy (22).

Lemma 3. Let the space X_∞ of infinite genetic lines be equipped with metric (41). Then, for any probability measure ν ∈ M₁(Ω) and any ε > 0, there exists a neighborhood O(ν), such that the Hausdorff dimension of the set:

$$A=\{x\in X_{\infty }|\forall N\exists n>N:{\delta }_{x,n}\in O(\nu )\}$$

does not exceed d(ν, μ, θ) + ε almost surely.

The proof is carried out in the same manner as in Lemma 1. Take any x > 0. By Theorem 32, there exists a neighborhood O(ν), such that almost surely:

$$\begin{array}{cc}\#\{x\in X_n|{\delta }_{x,n}\in O(\nu )\}\le e^{-n(-\rho (\nu ,\mu )+x)},& \text{as}n\to \infty \end{array}.$$

(43)

Let us reduce this neighborhood in such a way that in addition to Formula (43), for all δ ∈ O(ν),

$${\displaystyle \sum _{i=1}^r\delta (i)\ln \theta (i)<}{\displaystyle \sum _{i=1}^r\nu (i)\ln \theta (i)+x.}$$

Then, for each cylinder Z_n(x) satisfying the condition δ_x,n ∈ O(ν), the following estimate holds:

$$\begin{array}{c}|Z_n(x)|={\displaystyle \prod _{i=1}^n\theta (x_t)=\exp \left\{{\displaystyle \sum _{t=1}^n\ln \theta (x_t)}\right\}=\exp \left\{n{\displaystyle \sum _{t=1}^n{\delta }_{x,n}(i)\ln \theta (i)}\right\}}\\ <\exp \left\{n{\displaystyle \sum _{t=1}^n\nu (i)\ln \theta (i)+nx}\right\}.\end{array}$$

(44)

For every natural N, the set A is covered by the collection of cylinders:

$${\mathcal{U}}_N={\displaystyle \underset{n=N}{\overset{\infty }{\cup }}\{Z_n(x)|{\delta }_{x,n}\in O(\nu )\}}.$$

Evidently, the diameter of this covering tends to zero as N → ∞. Hence, $\text{mes}({\mathcal{U}}_{N,\alpha })$ can be estimated by means of Formulas (43) and (44):

$$\begin{array}{c}\text{mes}({\mathcal{U}}_{N,\alpha })={\displaystyle \sum _{Z_n(x)\in {\mathcal{U}}_N}|Z_n(x){|}^{\alpha }}\\ \le {\displaystyle \sum _{n=N}^{\infty }{e}^{n(-\rho (\nu ,\mu )+x)}}\exp \left\{an{\displaystyle \sum _{i=1}^r\nu (i)\ln \theta (i)+anx}\right\}\\ ={\displaystyle \sum _{n=N}^{\infty }\exp \left\{n\left(-{\displaystyle \sum _{i=1}^r\nu (i)\ln \frac{\nu (i)}{\mu (i)}+a{\displaystyle \sum _{i=1}^r\nu (i)\ln \theta (i)+x+ax}}\right)\right\}}.\end{array}$$

(45)

If α > d(ν, μ, θ), then x can be chosen so small, that the last exponent in braces is negative, and all of the sum (45) tends to zero as N → ∞. Thus, the Hausdorff measure (of dimension α) of the set A is zero, and its dimension does not exceed α.

As before, we say that a sequence of empirical measures δ_x,n condenses on a subset V ⊂ M₁(Ω) $(\text{notation}{\delta }_{x,n}\succ V)$ if it has a limit point in V.

Theorem 12. Let X₁, X₂,… be an unconditional colored branching process with a finite set of colors Ω, and let the set X_∞ of all infinite genetic lines be equipped with a cylindrical θ-metric (41). Then, for any subset V ⊂ M₁(Ω), almost surely:

$${\dim }_H\{x\in X_{\infty }|{\delta }_{x,n}\succ V\}\le \underset{\nu \in V}{\sup }d(\nu ,\mu ,\theta ).$$

(46)

In particular, dim_H X_∞ ≤ s almost surely, where s is a unique root of the “Bowen equation”:

$${\displaystyle \sum _{i=1}^r\mu (i)\theta {(i)}^s=1}.$$

(47)

Proof. It follows from the definition of the Billingsley–Kullback entropy d(ν, μ, θ) that it depends continuously on the measure ν ∈ M₁(Ω). Let $\overline{V}$ be the closure of V. Obviously, it is compact. Take an arbitrary ε > 0. By Lemma 3, for any measure $\nu \in \overline{V}$, there exists a neighborhood O(ν), such that almost surely:

$${\dim }_H\{x\in X_{\infty }|{\delta }_{x,n}\succ O(\nu )\}\le d(\nu ,\mu ,\theta )+\epsilon \le \underset{\nu \in V}{\sup }d(\nu ,\mu ,\theta )+\epsilon .$$

(48)

Choose a finite covering of the set $\overline{V}$ by neighborhoods of this kind. Then, the set $\{x\in X_{\infty }|{\delta }_{x,n}\succ V\}$ will be covered by a finite collection of sets of the form $\{x\in X_{\infty }|{\delta }_{x,n}\succ O(\nu )\}$ satisfying Formula (48). By the arbitrariness of ε, this implies the first statement of Theorem 12.

Let s be a solution to Equation (47). Note that for any ν ∈ M₁(Ω), the concavity of the logarithm function implies that:

$$\begin{array}{c}s{\displaystyle \sum _{i=1}^r\nu (i)\ln \theta (i)-}{\displaystyle \sum _{i=1}^r\nu (i)\ln \frac{\nu (i)}{\mu (i)}=}{\displaystyle \sum _{i=1}^r\nu (i)\ln \frac{\mu (i)\theta {(i)}^s}{\nu (i)}}\\ \le \ln \left\{{\displaystyle \sum _{\nu (i)>0}^r\nu (i)\ln \frac{\mu (i)\theta {(i)}^s}{\nu (i)}}\right\}\le 0.\end{array}$$

Consequently, d(ν, μ, θ) ≤ s. Now, the second part of the theorem follows from the first one if we take V = M₁(Ω).

Remark. Usually, the term “Bowen equation” is used for the equation P (sφ) = 0, where P (sφ) is the topological pressure of a weight function sφ in some dynamical system (more detailed explanations can be found in [13]). If we replace the topological pressure P (sφ) by the spectral potential:

$$\begin{array}{cc}\lambda \left(s\phi ,\mu \right)=\ln {\displaystyle \sum _{i=1}^r{e}^{s\phi (i)}}\mu (i),& \text{where}\phi (i)=\ln \theta (i)\end{array},$$

then the Bowen equation turns into the equation λ(sφ, μ) = 0, which is equivalent to Formula (47).

10. Block Selections of Colored Branching Processes

Let ξ₁, ξ₂, ξ₃,… be a sequence of independent identically distributed random variables taking values of zero or one (independent Bernoulli trials).

Lemma 4. If 0 < p′ < p < 1 and P{ξ_i = 1} ≥ p, then:

$$\begin{array}{cc}\mathrm{P}\{{\xi }_1+\cdots +{\xi }_k\ge p^{\prime }k\}\to 1& ask\to \infty \end{array}$$

(49)

uniformly with respect to the probability$\mathrm{P}\{{\xi }_i=1\}\ge p$.

Proof. In the case P{ξ_i = 1} = p, this follows from the law of large numbers. If P{ξ_i = 1} increases, then the probability in the left-hand side of Formula (49) increases, as well.

Consider a colored branching process X₁, X₂,… with a finite set of colors Ω = {1,…, r}. Each X_n consists of genetic lines (x₁, x₂,…, x_n) of length n, in which every subsequent individual is born by the previous one. Fix a (large enough) natural N. We will split genetic lines of length divisible by N into blocks of length N:

$$\begin{array}{cc}\left(x_1,x_2,\dots ,x_{nN}\right)=\left(y_1,\dots ,y_n\right),& \text{where}{y}_k=\left(x_{(k-1)N+1,\dots ,x{k}_N}\right)\end{array}.$$

Each block y_k generates an empirical measure ${\delta }_{y_k}$ (spectrum) on Ω by the rule:

$${\delta }_{y_k}(i)=\frac{\begin{array}{cc}\#\left\{t\right|g(x_t)=i,& (k-1)N<t\le kN\}\end{array}}{N},$$

where g(x_t) denotes the color of x_t.

A block selection of order N from a colored branching process X₁, X₂,… is any sequence of random subsets Y_n ⊂ X_nN with the following property: if (y₁,…, y_n+1) ∈ Y_n+1, then (y₁,…, y_n) ∈ Y_n. In this case, the sequence of blocks (y₁,…, y_n+1) will be called a prolongation of the sequence (y₁,…, y_n).

As above (see Formula (30)), denote by μ(i) the expectation of children of color i born by each individual and by μ the corresponding measure on Ω.

Theorem 13. Let X₁, X₂,… be an unconditional colored branching process with a finite set of colors Ω and the probability of degeneration q^∗ < 1. If a measure ν ∈ M₁(Ω) satisfies the condition ρ(ν, μ) < 0, then for any neighborhood O(ν) ⊂ M₁(Ω) and any number ε > 0 with probability 1 − q^∗, one can extract from the branching process a block selection Y₁, Y₂,… of an order N, such that each sequence of blocks (y₁,…, y_n) ∈ Y_n has at least l(N) prolongations in Y_n+1, where:

$$l(N)=e^{N(-\rho (\nu ,\mu )-\epsilon )},$$

(50)

and the spectra of all blocks belong to O(ν).

Proof. Fix any numbers p and ε satisfying the conditions:

$$\begin{array}{cc}0<p<p+\epsilon <1-q*,& \rho (\nu ,\mu )+\epsilon <0.\end{array}$$

By the second part of Theorem 11 for all large enough N, we have:

$$\mathrm{P}\{\#\{x\in X_N|{\delta }_{x,N}\in O(\nu )\}\ge e^{N(-\rho (\nu ,\mu )-\epsilon /2)}\}\ge p+\epsilon .$$

(51)

Further, we will consider finite sequences of random sets X₁,…, X_nN and extract from them block selections Y₁,…, Y_n of order N, such that the spectra of all of their blocks belong to O(ν) and each sequence of blocks (y₁,…, y_k) ∈ Y_k has at least l(N) prolongations in Y_k+1. Denote by A_n the event of the existence of a block selection with these properties. Define one more event A by the condition:

$$\#\{x\in X_N|{\delta }_{x,N}\in O(\nu )\}>l(N)e^{N\epsilon /2}.$$

It follows from Formulas (50) and (51) that P(A) ≥ p + ε. Evidently, A ⊂ A₁. Therefore, P(A₁) ≥ p + ε. Now, we are going to prove by induction that P(A_n) ≥ p whenever the order N of our block selection is large enough. Let us perform the step of induction. Suppose that P(A_n) ≥ p is valid for some n. Consider the conditional probability P(A_n+1|A). By the definition of events A_n+1 and A, it cannot be less than the probability of the following event: there are at least l(N) wins in a sequence of $\left[l(N)e^{N_{\epsilon }/2}\right]$ independent Bernoulli trials with the probability of win P(A_n) in each. Choosing N large enough and using Lemma 4 (with p′ = p/2 and $k=[l(N)e^{N\epsilon /2}]$, one can make this probability greater than 1 − ε. Then,

$$\mathrm{P}(A_{n+1})\ge \mathrm{P}(A)\mathrm{P}(A_{n+1}|A)>(p+\epsilon )(1-\epsilon )>p.$$

Thus, the inequality P(A_n) > p is proven for all n.

This means that with probability greater than p, one can extract from the sequence X₁,…, X_nN a block selection Y₁,…, Y_n of order N, such that the spectra of all blocks belong to the neighborhood O(ν) and each sequence of blocks (y₁,…, y_k) ∈ Y_k has at least l(N) prolongations in Y_k+1.

To obtain a block selection of infinite length with the same properties, we will construct finite block selections Y₁,…, Y_n in the following manner. Initially, suppose that every Y_k, where k ≤ n, consists of all of the sequences of blocks (y₁,…, y_k) ∈ X_kN, such that the spectrum of each block lies in O(ν). At the first step, we exclude from Y_n−1 all of the sequences of blocks having less than l(N) prolongations in Y_n and then exclude from Y_n all prolongations of the sequences that were excluded from Y_n−1. At the second step, we exclude from Y_n−2 all of the sequences of blocks having after the first step less than l(N) prolongations in the modified Y_n−1, and then, exclude from Y_n−1 and Y_n all prolongations of the sequences that were excluded from Y_n−2. Proceeding further in the same manner, after n steps, we will obtain a block selection Y₁,…, Y_n, such that each sequence of blocks from any Y_k has at least l(N) prolongations in Y_k+1. Evidently, this selection will be the maximal one among all of the selections of order N having the mentioned “l(N)-prolongations” property. Therefore, with probability at least p, all of the sets Y_k are nonempty.

For every n, let us construct, as is described above, the maximal block selection $Y_1^{(n)},\dots ,Y_n^{(n)}$ possessing the mentioned “l(N)-prolongations” property. From the maximality of these selections, it follows that:

$$Y_n^{(n)}\supset Y_n^{(n+1)}\supset Y_n^{(n+2)}\supset \dots$$

Define the sets $Y_n={\cap }_{k\ge n}{Y}_n^{(k)}$. Then, with probability at least p, all of them are nonempty and compose an infinite block selection from Theorem 13. Since p may be chosen arbitrarily close to 1 – q*, such selections do exist with probability 1 – q*.

Theorem 13 can be strengthened by taking several measures in place of a unique measure ν ∈ M₁(Ω).

Theorem 14. Let X₁, X₂, X₃,… be an unconditional colored branching process with a finite set of colors Ω and probability of degeneration q* < 1. If a finite collection of measures ν_i ∈ M₁(Ω), where i = 1,…, k, satisfy the inequalities ρ(ν_i, μ) < 0, then for any neighborhoods O(ν_i) ∈ M₁(Ω) and any ε > 0 with probability 1 – q*, one can extract from the branching process a block selection Y₁, Y₂,… of an order N, such that for every i = 1,…, k, each sequence of blocks (y₁,…, y_n) ∈ Y_n has at least:

$$l_i(N)=e^{N(-\rho ({\nu }_i,\mu )-\epsilon )}$$

prolongations (y₁,…, y_n, y) ∈ Y_n+1 with the property δ_y ∈ O(ν_i).

It can be proven in the same manner as the previous one. Here, the event A_n should be understood as the existence of a finite block selection Y₁,…, Y_n satisfying the conclusion of Theorem 14, and the event A should be defined by the system of inequalities:

$$\begin{array}{cc}\#\{x\in X_N|{\delta }_{x,N}\in O({\nu }_i)\}>l_i(N)e^{N\epsilon /2},& i=1,\dots ,k.\end{array}$$

We leave the details to the reader.

11. Dimensions of Random Fractals (Lower Bounds)

Now, we continue the investigation of the space of infinite genetic lines:

$$X_{\infty }=\{x=(x_1,x_2,x_3,\dots )|(x_1,\dots ,x_n)\in X_n\forall n\in \mathbb{N}\},$$

which is generated by an unconditional colored branching process X₁, X₂,… with a finite set of colors Ω = {1,…, r}. It is assumed that there is a measure:

$$\mu =\left(\mu \left(1\right),\dots ,\mu \left(r\right)\right)$$

on Ω, where μ(i) denote the expectation of children of color i born by each individual, and X_∞ is equipped with cylindrical θ-metric (41).

Theorem 15. Let X₁, X₂, X₃,… be an unconditional colored branching process with a finite set of colors Ω and probability of degeneration q* < 1. If a measure ν ∈ M₁(Ω) satisfies the condition d(ν, μ, θ) > 0, then with probability 1 – q* for any neighborhood O(ν), we have the lower bound:

$${\dim }_H\{x\in X_{\infty }|\exists N\forall n>N{\delta }_{x,n}\in O(\nu )\}\le d(\nu ,\mu ,\theta ).$$

(52)

Proof. Let us fix any number α < d(ν, μ, θ) and ε > 0 so small that:

$$d\left(\nu ,\mu ,\theta \right)=\frac{\rho (\nu ,\mu )}{{\displaystyle {\sum }_{i=1}^r\nu (i)\ln \theta (i)}}>\frac{\rho (\nu ,\mu )+2\epsilon }{{\displaystyle {\sum }_{i=1}^r\nu (i)\ln \theta (i)}-\epsilon }>\alpha .$$

(53)

Then, we choose a convex neighborhood O*(ν), whose closure lies in O(ν) and such that, for any measure δ ∈ O*(ν):

$${\displaystyle \sum _{i=1}^r\delta (i)\ln \theta (i)>}{\displaystyle \sum _{i=1}^r\nu (i)\ln \theta (i)-\epsilon .}$$

(54)

By Theorem 13 with probability 1 – q*, one can extract from the branching process under consideration a block selection Y₁, Y₂,… of an order N, such that any sequence of blocks (y₁,…, y_n) from Y_n has at least l(N) prolongations in Y_n+1, where:

$$l(N)=e^{N(-\rho (\nu ,\mu )-\epsilon )},$$

and for each block $y_k=(x_{(k-1)N+1,\dots ,}{x}_{kN})$, the corresponding empirical measure δ_yk (spectrum) belongs to O*(ν). Let us exclude from this selection a certain part of genetic lines in such a way that each of the remaining sequences of blocks (y₁,…, y_n) ∈ Y_n has exactly [l(N)] prolongations in Y_n+1.

Define the random set:

$$Y_{\infty }=\{y=(y_1,y_2,\dots )|(y_1,\dots ,y_n)\in Y_n,n=1,2,\dots \}.$$

Any sequence y = (y₁, y₂,…) ∈ Y_∞ consists of blocks of length N. Writing down in order the elements of all of these blocks, we obtain from y an infinite genetic line x = (x₁, x₂,…) ∈ X_∞. Denote it as π(y). By the definition of Y_∞, the spectrum of each block y_k belongs to O*(ν). For every point x = π(y), where y ∈ Y_∞, the empirical measure δ_x,nN is the arithmetical mean of the empirical measures corresponding to the first n blocks of y, and so, it belongs to O*(ν), as well. It follows that:

$$\pi (Y_{\infty })\subset \{x\in X_{\infty }|\exists N\forall n>N{\delta }_{x,n}\in O(\nu )\}.$$

(55)

The family of all cylinders of the form Z_nN(x), where x ∈ π(Y_∞), generates some σ-algebra on π(Y_∞). Define a probability measure P on this σ-algebra, such that:

$$P\left(Z_{nN}(x)\right)={\left[l(N)\right]}^{-n}.$$

Then, for all large enough N, all x ∈ π(Y_∞) and all natural n:

$$P\left(Z_{nN}(x)\right)\le e^{nN(\rho (\nu ,\mu )+2\epsilon )}.$$

On the other hand, by Formula (54):

$$\begin{array}{c}\left|Z_{nN}(x)\right|={\displaystyle \prod _{t=1}^{nN}\theta (x_t)=\exp \left\{{\displaystyle \sum _{t=1}^{nN}\ln \theta (x_t)}\right\}=\exp \left\{{\displaystyle \sum _{i=1}^{r}nN{\delta }_{x,nN}(i)\ln \theta (i)}\right\}}\\ \ge \exp \left\{nN\left({\displaystyle \sum _{i=1}^r\nu (i)\ln \theta (i)}-\epsilon \right)\right\}.\end{array}$$

It follows from the last two formulas and Formula (53) that:

$$\begin{array}{c}{\left|Z_{nN}(x)\right|}^{\alpha }\ge \exp \left\{nN\alpha \left({\displaystyle \sum _{i=1}^r\nu (i)\ln \theta (i)}-\epsilon \right)\right\}\\ \ge e^{nN(\rho (\nu ,\mu )+2\epsilon )}\ge P(Z_{nN}(x)).\end{array}$$

Now, we are ready to compute the Hausdorff measure of dimension α of the set π(Y_∞). If, while computing the Hausdorff measure, we used coverings of π(Y_∞) not by arbitrary cylinders, but only by cylinders of orders divisible by N, then the last formula would imply that such a measure is not less than P (π(Y_∞)) = 1. Any cylinder can be embedded in a cylinder of order divisible by N, such that the difference of their orders is less than N and the ratio of their diameters greater than min θ(i)^ℕ. Therefore,

$$\text{mes}\left(\pi (Y_{\infty }),\alpha \right)\ge min\theta {(i)}^{N\alpha }$$

and hence, dim_H π(Y_∞) ≥ α.

The set defined in the right-hand part of Formula (55) contains π(Y_∞). Thus, its dimension is at least α. Recall that we have proven this fact by means of a block selection that exists with probability 1 – q*. By the arbitrariness of α < d(ν, μ, θ), this implies the desired bound (52) with the same probability.

Theorem 16. Let s be a root to the “Bowen equation”:

$${\displaystyle \sum _{i=1}^r\mu (i)\theta {(i)}^s=1}.$$

If s ≤ 0, then X_∞ = ∅ almost surely. Otherwise, if s > 0, then X_∞ is nonempty with a positive probability, and with the same probability, its dimension equals s.

We note that a more general version of Theorem 16, in which the similarity coefficients θ(i) are random, is proven in [4–6,14].

Proof. The expectation of the total number of children born by each individual in the branching process generating the set X_∞ is equal to m = μ(1) + ⋯ + μ(r). If s ≤ 0, then m ≤ 1. In this case, by Theorem 8, our branching process degenerates almost surely, and X_∞ = ∅.

If s > 0, then m > 1. In this case, by Theorem 8, our branching process does not degenerate with a positive probability, and X_∞ is nonempty. Define a measure ν ∈ M₁(Ω) by means of the equality:

$$\begin{array}{cc}\nu (i)=\mu (i)\theta {(i)}^s,& i\in \mathrm{\Omega }.\end{array}$$

Then, evidently, d(ν, μ, θ) = s. By the previous theorem, dim_H X_∞ ≥ s with the same probability with which X_∞ ≠ ∅. On the other hand, by Theorem 12, the inverse inequality holds almost surely.

For every probability measure ν ∈ M₁(Ω), we define its basin B(ν) ⊂ X_∞ as the set of all infinite genetic lines x = (x₁, x₂, x₃,…), such that the corresponding sequence of empirical measures δ_x,n converges to ν. What is the dimension of B(ν)? By Theorem 12, it does not exceed the Billingsley–Kullback entropy d(ν, μ, θ) with probability one. On the other hand, the inverse inequality does not follow from the previous results (and, in particular, from Theorem 15). To obtain it, we ought to enhance the machinery of block selections.

Lemma 5. Let$Q_1,\dots ,Q_{2^r}$ be the vertices of a cube in ℝ^r. Then, there exists a law of choice i: ℝ^r → {1,…, 2^r}, such that if neighborhoods O(Q_i) are small enough, and sequences:

$${\delta }_n\in ℝand{\mathrm{\Delta }}_n=\frac{{\delta }_1+\cdots +{\delta }_n}{n}$$

satisfy the conditions${\delta }_{n+1}\in O(Q_{i({\mathrm{\Delta }}_n)})$ and ${\delta }_1\in O(Q_1)\cup \cdots \cup O(Q_{2^r})$, then the sequence Δ_n converges to the center of the cube.

Proof. First, we consider the case r = 1, when the cube is a segment. Let, for definiteness, Q₁ = −1 and Q₂ = 1. Set:

$$i(\mathrm{\Delta })=\{\begin{array}{cc}1,& \text{if}\mathrm{\Delta }\ge 0,\\ 2,& \text{if}\mathrm{\Delta }<0.\end{array}$$

(56)

Take any neighborhoods O(Q₁) and O(Q₂)with radii at most one. Then, for any sequence δ_n satisfying the conditions ${\delta }_{n+1}\in O(Q_{i({\mathrm{\Delta }}_n)})$ and |δ₁| < 2, we have the estimate |∆_n| < 2/n. It may be easily proven by induction. Thus, in the one-dimensional case, the lemma is proven. To prove it in the multidimensional case, one should choose a coordinate system with the origin at the center of the cube and the axes parallel to its edges and apply the law of choice (56) to each of the coordinates independently.

Theorem 17. Let X₁, X₂, X₃,… be an unconditional colored branching process with a finite set of colors Ω and probability of degeneration q* < 1. If a measure ν ∈ M₁(Ω) satisfies the condition d(ν, μ, θ) > 0, then with probability 1 – q*:

$${\dim }_{H}B(\nu )=d(\nu ,\mu ,\theta ).$$

Proof. Fix any number α < d(ν, μ, θ) and ε > 0 so small, that:

$$d(\nu ,\mu ,\theta )=\frac{\rho (\nu ,\mu )}{{\displaystyle {\sum }_{i=1}^r\nu (i)\ln \theta (i)}}>\frac{\rho (\nu ,\mu )+3\epsilon }{{\displaystyle {\sum }_{i=1}^r\nu (i)\ln \theta (i)-}\epsilon }>\alpha .$$

The set M₁(Ω) is, in fact, a simplex of dimension r − 1, where r = |Ω|. Suppose first that ν is an inner point of this simplex (in other words, ν(i) > 0 for all i ∈ Ω). Take a small convex neighborhood O(ν) ⊂ M₁(Ω), such that for any measure δ ∈ O(ν):

$$\begin{array}{c}\rho (\delta ,\mu )<\rho (\nu ,\mu )+\epsilon ,\\ {\displaystyle \sum _{i=1}^r\delta (i)\ln \theta (i)>}{\displaystyle \sum _{i=1}^r\nu (i)\ln \theta (i)-\epsilon .}\end{array}$$

Let $Q_1,\dots ,Q_{2^{r-1}}$ be the vertices of some cube in O(ν) with the center at ν. Define for them small neighborhoods O(Q_i) ⊂ O(ν) as in Lemma 5. By Theorem 14 with probability 1 – q*, one can extract from the colored branching process X₁, X₂,… a block selection Y₁, Y₂,… of an order N, such that for every i ≤ 2^r−1, each sequence of blocks (y₁,…, y_n) ∈ Y_n has at least:

$$l(N)=e^{N(-\rho (\nu ,\mu )-2\epsilon )}$$

prolongations (y₁,…, y_n, y) ∈ Y_n+1 possessing the property δ_y ∈ O(Q_i).

We exclude from this block selection a certain part of the genetic lines, so that each of the remaining sequences of blocks (y₁,…, y_n) ∈ Y_n has exactly [l(N)] prolongations (y₁,…, y_n, y) ∈ Y_n+1, and all of these prolongations satisfy the law of choice from Lemma 5, namely,

$$\begin{array}{cc}{\delta }_y\in O(Q_{i({\mathrm{\Delta }}_n)}),& \text{where}{\mathrm{\Delta }}_n\end{array}=\frac{{\delta }_{y_1}+\dots +{\delta }_{y_n}}{n}.$$

Let π(Y_∞) be the set of all infinite genetic lines (x₁, x₂,…) ∈ X_∞ for which every initial segment of length nN, being partitioned into blocks of length N, turns into an element of Y_n. Then, by Lemma 5, we have the inclusion π(Y_∞) ⊂ B(ν).

Reproducing the reasoning from the proof of Theorem 15, one can verify that the dimension of π(Y_∞) is greater than α. Since α can be taken arbitrarily close to d(ν, μ, θ), we obtain the lower bound dim_H B(ν) ≥ d(ν, μ, θ). The inverse inequality, as was mentioned above, follows from Theorem 12. Thus, in the case of an inner point ν ∈ M₁(Ω), the theorem is proven.

If the measure ν belongs to the boundary of the simplex M₁(Ω), then one should exclude from Ω all elements i with ν(i) = 0 and consider the set:

$${\mathrm{\Omega }}^{\prime }=\{i\in \mathrm{\Omega }|\nu (i)>0\}.$$

Let us exclude from the branching process X₁, X₂,… all of the genetic lines containing elements of colors not in Ω⁰ and denote by ${X^{\prime }}_1,{X^{\prime }}_2\dots$ the resulting branching process (with the set of colors Ω′). The corresponding set of infinite genetic lines ${X^{\prime }}_{\infty }$ is contained in X_∞. It follows from the definition of the Billingsley–Kullback entropy d(ν, μ, θ) that it is the same for the sets of colors Ω and Ω′. Besides, the measure ν lies in the interior of the simplex M₁(Ω′). Therefore, ${\dim }_{H}B(\nu )\cap {X^{\prime }}_{\infty }=d(\nu ,\mu ,\theta )$ with the same probability as the probability of the event ${X^{\prime }}_{\infty }\ne \varnothing$.

The theorem would be completely proven if the probability of the event ${X^{\prime }}_{\infty }\ne \varnothing$ was equal to 1 – q*. However, it may be less than 1 – q*. This obstacle can be overcome as follows.

Let $m^{\prime }={\displaystyle {\sum }_{i\in {\mathrm{\Omega }}^{\prime }}\mu (i)}$. This is nothing else than the expectation of each individual’s number of children in the branching process ${X^{\prime }}_1,{X^{\prime }}_2\dots$ If m′ ≤ 1, then Formula (11) implies the inequality ρ(ν, μ) ≥ 0, which contradicts the condition d(ν, μ, θ) > 0 of our theorem. Therefore, m′ > 1, and respectively, the probability of the event ${X^{\prime }}_{\infty }\ne \varnothing$ is strictly less than one. Let us denote it by q′.

If the branching process ${X^{\prime }}_1,{X^{\prime }}_2\dots$ was generated not by a unique initial element, but by k initial elements, then the probability of the event ${X^{\prime }}_{\infty }\ne \varnothing$ would be equal to (q′)^k. Recall that the cardinality of X_n grows exponentially with probability 1 – q*. If this is the case, one can first wait for the event |X_n| ≥ k and then consider separately |X_n| independent counterparts of the branching process ${X^{\prime }}_1,{X^{\prime }}_2\dots$ generated by different elements of X_n. This trick allows one to obtain the bound dim_H B(ν) ≥ d(ν, μ, θ) with conditional probability at least 1 − (q′)^k under the condition |X_n| → ∞. Since k is arbitrary, the above-mentioned conditional probability is, in fact, equal to one, and the complete probability cannot be less than 1 – q*.