Random recursive sets have been used to model a wide range of fractal phenomena, but they can be slow and difficult to generate. V-variability address this problem by allowing these sets at most V distinct shapes at each level of magnification. The formulae for the almost sure Hausdorff dimension of both classes is known, and it has been conjectured that (under mild assumptions) the V-variable dimension converges to the random recursive dimension as V→∞. We prove this conjecture.
Introduction
Iterated function systems (IFSs) are a popular method for constructing fractals exhibiting self-similarity, and there is a rich and growing literature studying their attractor’s dynamics and dimension. Random iterated function systems generalise classical IFSs by introducing randomness into the construction of the attractor over a family of IFSs. Well studied cases include the random homogeneous model, whereby a single IFS is randomly chosen at each level and applied uniformly across that level, and the random recursive model, where an IFS is chosen independently for each piece at every level of the construction (see [5, 8]). V-variable sets were introduced by Barnsley, Hutchinson, and Stenflo to interpolate between these two models by requiring there to be at most V distinct local patterns at each level of magnification [2, 3], with V=1 the random homogeneous case and V=∞ the random recursive case.
For random systems made up of similarities and satisfying an open set condition, the Hausdorff dimension of almost every random homogeneous and recursive set can be readily calculated as a probabilistic version of the classical similarity dimension. The case for V-variable sets however relies on calculating the Lyapunov exponent of the decision trees [4]. Methods for such dimension calculations have since been researched and extended to more general settings, see for example [7, 10]. Nevertheless, it has remained a folklore conjecture since 2012, supported by the computational results in [4], that the dimension of a typical V-variable set approaches the dimension of a typical random recursive set as V→∞. This is explicitly formulated in [Tro21], which further conjectures the almost sure dimension as a function of V is strictly increasing (provided its endpoint values are distinct). We prove the first of these conjectures by piecing together techniques in [3, 4] and [GMW88].
Date: November 20, 2026
The author would like to thank Jonathan Fraser for conversations regarding the problem, Antti Käenmäki for an inspiring minicourse on fractal geometric applications of subadditivity, and Johannes Livengood van Vliet for revisions. The author was financially supported by a PhD studentship provided by the University of St Andrews in associated with the EPSRC Open Fellowship (EP/Z533440/1) held by Jonathan Fraser.
V-variable fractals
We will first precisely define the construction of V-variable iterated function systems.
Random Iterated Function Systems
Definition 2.1. Let F={Fλ={fi,λ}}λ∈Λ be a family of IFSs consisting of contracting similitudes on Rd, each with Nλ maps and associated contraction factors ri,λ. Let μ be a probability measure on the (possibly infinite) indexing set Λ. We say the pair (F,μ) is a random iterated function system (RIFS). We make the following assumptions:
As mentioned in the introduction, the goal of an RIFS is to apply different function sets at each iteration depth. The choices of such IFSs can be written as a tree. Let [N]∗ be the set of finite words (including the empty word ∅) where [n]:={1,2,…,n}, let [N]n denote the length n words, and let ∣v∣ denote the length of v∈[N]∗. For 0≤m<n and v∈[N]n, we write v∣m=v1v2⋯vm for truncation, and for v,w∈[N]∗ we will write vw for their concatenation. We will also view [N]∗ as the rooted N-ary tree, where ∅ is the root, the children of any v∈[N]∗ are v1,v2,…,vN, and [N]n is the n-th level of the tree. A subtree of [N]∗ is a nonempty subset τ⊂[N]∗ such that v∈τ implies v∣k∈τ for all k<∣v∣. We will write τn for the n-th level of τ and τ∣v for the subtree rooted at v. We will consider coloured subtrees of [N]∗ defined inductively by associating Λ-colourings to nodes at each level.
Definition 2.2. We say τ is a Λ-coloured tree for an RIFS (F,μ) if it is a subtree of [N]∗ constructed in the following way: for every n∈N0 and node v at level n of the partially constructed tree,
Colour v with some λ∈Λ,
Build level n+1 nodes v1,v2,…,vNλ.
Abusing notation, let τ denote both the constructed coloured tree as well as the colouring map which determined it (i.e. the partial function τ:[N]∗⇀Λ). Let Ω denote the collection of such trees. For k∈N and v,w∈τk, we say the two coloured trees τ∣v and τ∣w are isomorphic if vu∈τ⟺wu∈τ and τ(vu)=τ(wu) for every u∈[N]∗, and say τ is V-variable if there are at most V isomorphism classes of coloured subtrees rooted at level k, for every k∈N0. Let ΩV denote the set of such trees, so Ω∞=Ω.
Definition 2.3. The attractor for the RIFS (F,μ) with respect to τ is
with respect to the Hausdorff metric, independent of the choice of non-empty compact set K⊆Rd. We assume F satisfies the Uniform Open Set Condition (UOSC), that is there exists an open set U⊆Rd such that fi,λ(U)⊆U and fi,λ(U)∩fj,λ(U)=∅ for every λ∈Λ and 1≤i=j≤Nλ. Further, set
Note our assumption on Nλ≥2 implies Eλ∼μ(logSλ0)>0 and S0>1.
Theorem 2.4.[5 GMW88] The Hausdorff dimension of a typical random homogenous attractor is the unique s such that Eλ∼μ(logSλs)=0, and the Hausdorff dimension of a typical random recursive attractor is the unique s such that Ss=1.
Another perspective of trees
Definition 2.2 constructs arbitrarily coloured trees, but does not impose V-variability. Our aim in this section is to introduce an alternative tree construction which guarantees the property by tracking the isomorphism class information of each subtree at each level and encoding it in their root vertices. To motivate a formal definition, we will demonstrate a conversion procedure using a tree constructed by our current definition.
Choose some τ∈ΩV. Fix some λ0∈Λ and i0∈[V], these will act as ‘default’ choices for colour and isomorphism class. For every n∈N0, let Vn denote the number of isomorphism classes of subtrees at level n, index them 1,2,…,Vn, and let vi(n) denote the root word of the i-th isomorphism class representative. Now build the V-tuple
and a V×N matrix J(n), setting its ij-th element to be the unique k such that τ∣vi(n)=τ∣vk(n+1) for j≤Nλi(n) and i0 otherwise, i.e. the index of the isomorphism class which the j-th child of vi(n) belongs to. So the tuple an=(λ(n),J(n)) records the root node colour of each subtree at the n-th level, and determines the isomorphism class index of each subtree at the (n+1)-th level in τ’s construction. Moreover, the sequence (an)n∈N determines the tree. One should note we assigned constants in redundant situations, and chose a specific ordering of the isomorphism classes at each level, so the assignment of the sequence (an)n∈N0 to τ is many-to-one. We remark this information can be turned into a V-tuple of attractors (see [1]), but that isn’t relevant to the work in this paper.
Definition 2.5. Let AV=ΛV×[V]V×N, and fix some i∈[V] and
a=(λ(0),J(0))(λ(1),J(1))⋯∈AVN0,
where λ(n)=(λ1(n),λ2(n),…,λV(n)), J(n)=(Jij(n)).
Define the Λ-coloured tree τa,i and isomorphism class indexing function ι:τa,i→[V] the following way: for each n∈N0, each v∈[N]n will already be assigned some index ι(v) (with initialisation ι(∅)=i), so
For each v at level n of the partially constructed tree,
(i) Set the colour τa,i(v) of v to λι(v)(n) and
(ii) Build nodes v1,v2,…,vNτa,i(v)
(2) For each v∈[N]n and j∈[N], let ι(vj)=(J(n))ι(v)j.
We will write τa:=τa,1 (i.e. giving the root node the sensible isomorphism class indexing). With UV the uniform probability measure on [V] for V∈N, let
PVμ:=(μ⊗V⊗UV⊗VN)⊗N0
be the canonical measure (with respect to μ and UV) on the product space AVN0. Note PVμ is invariant under σ and permutation of [V]. Finally, let BV=B(AVN0) be the Borel σ-algebra generated by cylinder sets, and Bn,V⊂BV be the σ-algebra generated by cylinder sets of words up to length n (i.e. the smallest σ-algebra which makes projections onto the k-th coordinate of the string a0a1…, for k<n, measurable).
Remark 1. We will similarly let the probability measure on Ω, denoted P∞μ, be the push-forward of μ[N]∗ under the mapping Λ[N]∗→Ω. Let B∞ be the σ-algebra generated by sets {τ∈Ω∣v∈τ,τ(v)∈Λ′} for v∈[N]∗ and μ-measurable Λ′⊂Λ, and Bn,∞⊂B∞ be the σ-algebra generated by such sets with ∣v∣<n. Additionally one can note that, denoting σ the left shift on AVN0, for v∈τna,i
τa,i∣v=τσn(a),ι(v).(2)
Flows on trees
We can now define the flow of IFS s-mass between two subtrees rooted at different levels belonging to different isomorphism classes and use it to calculate the dimension of V-variable sets.
Definition 2.6. The V×V flow matrix Ma for some a=(λ,J)∈AV is given by
(Ma(s))ij=k=1∑Nλi{rk,λis∣Jik=j},(3)
and for a∈AVN0 write Ma∣n(s)=Ma0(s)Ma1(s)⋯Man−1(s). Let ∥M∥=∑i,jMi,j.
Theorem 2.7 ([4 Main Theorem]). Let (F,μ) be a RIFS. The Lyapunov exponent of a V-variable system is equal to
γV(s)=n→∞limEa∼PVμ(n1log∥Ma∣n(s)∥),(4)
and is monotonically decreasing in s. Additionally, for almost every a∈AVN0, the Hausdorff dimension of Fτa is the unique zero of γV(s), so define the function D:N∪{∞}→R+ by
D(V)=a.s.-dimH(Fτa),D(∞)=the unique s such that Ss=1.
Proof of the dimension limit
Properties of flows
In [4 §5], they look at the sum over the i-th row of the finite product of matrices in the definition of γV(s), however this direct definition can only be discussed in the V-variable setting. We will look at an object studied in [GMW88] for the V=∞ case which extends the aforementioned notion and contains results similar to Lemma 3.1 and Proposition 3.6. For K∈N0, s≥0 and τ∈Ω, let
F(K,s,τ):=v∈τK∑k<K∏rvk+1,τ(v∣k)s(5)
be the total flow of IFS s-mass over the first K levels of τ. We will first note the recursive nature of this definition, then relate this flow to the product of matrices in Equation (4).
Lemma 3.1. For all K∈N0, s≥0 and τ∈Ω,
F(K+1,s,τ)=i=1∑Nτ(∅)ri,τ(∅)sF(K,s,τ∣i)(6)
and
(Ss)K≤F(K,s,τ)≤(Ss)K.(7)
Proof. We can isolate the first or last term in the product in Eq. (5). The former gives
Additionally, (Ma(s)1)i=Sλis for any a∈AV, so Proposition 3.2 gives the first equality. Additionally, since the colouring of the root is independent to the colouring of the rest of the tree with respect to P∞μ, we get the second equality by taking the expectation of both sides in (6) and iterating.
Expectation results
By Corollary 3.3, it suffices to work with these flows when studying γV(s). We will first adapt [3 Theorem 49] to our setting of flows. For a fixed s we will write
Proof. Fix K, V and s. For any a∈AVN0 and τ∈Ω, by Eq. (7)
(SsSs)−K≤F(K,s,τ)F(K,s,τa)≤(SsSs)K,
so taking the logarithm of both sides and dividing by K gives the general bound
∣Φ(τa)−Φ(τ)∣≤logSsSs.(10)
For NK≥V this immediately implies Eq. (9), so assume NK<V. Then there exist a∈AVN0 such that ι is injective on [N]k for k<K; let E∈BK,V denote the collection of such a. For all k≤K, note: (a) ι∣[N]k is only determined by J(l) for l<k and so is independent of λ, and (b) the injectivity of ι∣[N]k implies the colouring λι(v)(k) of each v∈[N]k is chosen i.i.d. Since F(K,s,τ) only sees the first K levels of τ, then
Ea∼PVμ(Φ(τa)∣E)=Eτ∼P∞μ(Φ(τ)),(11)
So expanding the left hand side of Eq. (9) and applying Eq. (11), we get
where the second inequality is a result of applying the general bound Eq. (10). Finally, for an a∈Ec there is a least k<K such that two vertices at level k are labelled the same isomorphism class index. By minimality of k, this is equivalent to there being two distinct entries of J(k−1) which have equal value. Since entries are chosen i.i.d., the probability a fixed pair agrees is 1/V, and since there are fewer than (2Nk) choices of pairs at each level, then
PVμ(Ec)≤V1k=0∑K−1(2Nk)≤VN2K.
Thus the difference between the expected log-normed flow to a fixed level of a V-variable and random tree shrinks to zero as V→∞. We now want to find a Lyapunov exponent representation for RIFS systems equivalent to Eq. (4).
Proposition 3.6. For any s such that S2s<(Ss)2,
Eτ∼P∞μ(ΦK(τ))K→∞log(Ss).
Proof. Let F(K,s,τ):=F(K,s,τ)/(Ss)K denote the normalised flow. We claim its second moment is uniformly bounded in K. By (6) and the independence of the colouring of the root to the rest of the tree with respect to P∞μ,
where we let ri,λ=0 for Nλ<i≤N, and use Corollary 3.4 for the third equality. Also note F(1,s,τ)<∞ for every τ∈Ω, so by our assumption on s this completes the claim, and moreover shows supK∥F(K,s,τ)∥2<∞. Now notice that Eτ∼P∞μ(F(K,s,τ))=1 for every K, and further
Eτ∼P∞μ(F(K+1,s,τ)∣BK,∞)=F(K,s,τ),
so the sequence (τ↦F(K,s,τ))K∈N is a martingale adapted to (BK,∞)K∈N, and converges P∞μ-a.e. and in L2, to some F(s,τ) by the Martingale Convergence Theorem [9].
This has two consequences. First, the convergence paired with uniform boundedness implies that Eτ∼P∞μ(F(s,τ))=1. Second, dividing both sides of (6) by (Ss)K+1 and taking the limit as K→∞ gives
F(s,τ)=Ss1i=1∑Nτ(∅)ri,τ(∅)sF(s,τ∣i)P∞μ-a.e.,
so F(s,τ)=0 if and only if F(s,τ∣i)=0 for all 1≤i≤Nτ(∅). Moreover,
P∞μ(F(s,τ)=0)=Eλ∼μ(P∞μ(F(s,τ)=0)Nλ).
By our assumption that Nλ≥2, then P∞μ(F(s,τ)=0)∈{0,1}. The first consequence rules out the latter option, so F(s,τ)>0 almost surely, and logF(s,τ)∈(−∞,∞). Thus
ΦK(τ)=logSs+K1logF(K,s,τ)K→∞logSsP∞μ-a.e.
Finally by Eq. (7), ∣ΦK(τ)∣ is bounded by a constant, so by the Dominated Convergence Theorem
where the equality comes from Corollary 3.4. Thus as K→∞ the first term vanishes and Corollary 3.3 gives us the upper bound.
To show the lower bound, letting xK:=Ea∼PVμlogS(K,s,τa) we claim (xK)K∈N is superadditive. By isolating the K terms of the product in Eq. (5), for any τ∈Ω we get
where the second term was achieved by splitting the possible evaluations of ι(v). By the independence of data between the first K levels and the rest, as well as the invariance of PVμ under permutation of [V], we have
Theorem 3.11. Let (F,μ) be a RIFS. Then D(V)V→∞D(∞).
Proof. Let s∗=D(∞). By setting s=D(V) and t=s∗−D(V) (which is non-negative by Corollary 3.10), Lemma 3.9 gives
s∗−D(V)≤−logrmax−1γV(s∗).
Finally, by our assumption that S0>1 then s∗>0, so by definition of s∗ we have S2s∗<Ss∗=1=(Ss∗)2. Thus by Corollary 3.7 and Proposition 3.8, the Squeeze theorem gives
γV(s∗)V→∞logSs∗=0.
C. de Wit, School of Mathematics and Statistics, University of St Andrews, St Andrews, KY16 9SS, United Kingdom.
[1]Michael Barnsley. Superfractals. Cambridge University Press, Cambridge, United Kingdom, 2006.
[2]Michael Barnsley, John E. Hutchinson, and Örjan Stenflo. A fractal valued random iteration algorithm and fractal hierarchy. Fractals, 13(2):111–146, 2005.DOI
[3]Michael Barnsley, John E. Hutchinson, and Örjan Stenflo. V-variable fractals: Fractals with partial self similarity. Advances in Mathematics, 218:2051–2088, 2008.arxiv.org/abs/0802.0064
[4]Michael Barnsley, John E. Hutchinson, and Örjan Stenflo. V-variable fractals: dimension results. Forum Math., 24(3):445–470, 2012.
[5]Kenneth J. Falconer. Random fractals. Math. Proc. Cambridge Philos. Soc., 100:559–582, 1986.DOI
[7]Esa Järvenpää, Maarit Järvenpää, Antti Käenmäki, Henna Koivusalo, Örjan Stenflo, and Ville Suomala. Dimensions of random affine code tree fractals. Ergodic Theory and Dynamical Systems, 34(3):854–875, 2014.DOI
[8]R. Daniel Mauldin and S. C. Williams. Random recursive constructions: Asymptotic geometric and topological properties. Trans. Am. Math. Soc., 295(1):325–346, 1986.DOI
[9]Karl R. Stromberg. Probability for Analysts. Chapman & Hall, New York, USA, 1994.
[10]Sascha Troscheit. On the dimensions of attractors of random self-similar graph directed iterated function systems. Journal of Fractal Geometry, 4(3):257–303, 2017.DOI