Renewal Theorems and Their Application in Fractal Geometry

Abstract

A selection of probabilistic renewal theorems and renewal theorems in symbolic dynamics are presented. The selected renewal theorems have been widely applied. Here, we will show how they can be utilised to solve problems in fractal geometry with particular focus on counting problems and the question of Minkowski measurability. The fractal sets we consider include self-similar and self-conformal sets as well as limit sets of graph-directed systems consisting of similarities and conformal mappings.

1 Introduction

Renewal theorems have found wide applicability in various areas of mathematics (such as fractal and hyperbolic geometry), economics (such as queuing, insurance and ruin problems) and biology (such as population dynamics). Classically, they describe the asymptotic behaviour of waiting times in-between occurrences of a repetitive pattern connected with repeated trials of a stochastic experiment. These probabilistic renewal theorems have been extended and generalised in several ways, resulting in an even broader applicability.

The purpose of this article is to provide an overview of a selection of renewal theorems and to highlight in which situation which renewal theorem is natural to be applied. This will be done by considering two questions in fractal geometry in different settings. These motivating questions will be stated in Sect. 2. Subsequently, a selection of probabilistic renewal theorems is introduced in Sect. 3 and applied to obtain answers to the previously raised questions in the setting of similarities. In Sect. 4 renewal theorems in symbolic dynamics are presented and applied to solve the questions raised in Sect. 2 in more general settings. Additionally, in an Appendix we provide background material and address the relationships between the mentioned renewal theorems.

2 Some Questions in Fractal Geometry

In fractal geometry various notions of dimension such as Minkowski-, Hausdorff- and packing dimension are well-established tools to describe the fractal nature of a given set. Characterising sets beyond their dimension is one of the many applications of renewal theorems. In Sect. 2.1 we raise two questions which we answer by means of renewal theory in Sects. 3 and 4 for the classes of sets that we introduce in Sect. 2.2.

2.1 Characterising Sets Beyond Dimension

Our first question relates to counting problems. The most basic counting problems associated with fractal sets E arise in the situation when E is a subset of [0, 1]. Letting {I _ℓ}_{ℓ ∈ L} denote the family of connected components of [0, 1] ∖ E a natural question is:

Question 2.1

What is the asymptotic behaviour as r → 0 of the number of intervals I _ℓ whose lengths lie in the interval [r, rh) for some h > 1, i. e. of

$$\displaystyle \begin{aligned} N_{\log h}(r):= \#\{ \ell\in L\mid r h>|I_{\ell}|\geq r \}? \end{aligned} $$

Here # denotes cardinality and |I _ℓ| denotes the length of the interval I _ℓ.

An example of a more advanced counting problem is to count the number of closed geodesics on manifolds related to Schottky groups that do not exceed a given length. This problem can also be treated by means of renewal theory. We refer the interested reader to [28].

Before addressing how the answer to Question 2.1 helps our understanding of the fine geometric structure of a set in Remark 2.3 we turn to the second question, which relates to the asymptotic behaviour of the volume function.

For arbitrary $d\in \mathbb N$ the d-dimensional Lebesgue measure shall be denoted by λ _d. Further, for r > 0 we let $E_{r}: =\{ x\in \mathbb R^d\mid \operatorname {\mathrm {dist}}(x,E) \leq r \}$ denote the r-parallel set of $E\subset \mathbb R^d$, where $\operatorname {\mathrm {dist}}(x,E): = \inf _{y\in E}\lvert x-y\rvert$ denotes the distance of x to E with respect to the euclidean metric $\lvert \cdot \rvert$ on $\mathbb R^d$.

Question 2.2

What is the asymptotic behaviour as r → 0 of the volume of the r-parallel set of E, i. e. of

$$\displaystyle \begin{aligned} \lambda_d(E_r)\quad \text{as}\ r\to 0? \end{aligned} $$

Supposing that the Minkowski dimension$\dim _M(E): = d-\lim _{r\to 0}\frac {\log \lambda _d(E_r)}{\log r}$ of E exists, the above question can be reformulated as follows. How does the function $f\colon (0,\infty )\to \mathbb R$, $f(r): = r^{\dim _M(E)-d}\lambda _d(E_r)$ behave as r → 0? If lim_r→0 f(r) exists, we call the limit the Minkowski content of E and denote it by $\mathcal M(E)$. If lim_r→0 f(r) exists, is positive and finite, then we say that E is Minkowski measurable. In recent years the question of Minkowski measurability of a given set has attracted much attention and is for instance related to the question ‘Can you hear the shape of a drum with fractal boundary?’, see for instance [29].

Remark 2.3

Knowledge of the asymptotic behaviour of $N_{\log h}(r)$ and λ _d(E _r) as r → 0 provides insight to the fine structure of E and can for instance be used to describe the lacunarity of E. The word lacunarity originates from the Latin word lacuna which means gap. According to [33] ‘a fractal is to be called lacunar if its gaps tend to be large, in the sense that they include large intervals (discs or balls)’. A nice exposition of lacunarity, its geometric meaning and its relationship to the above introduced counting function and asymptotic behaviour of λ _d(E _r) is provided in [33], see also [24]. We will provide further insight to the geometric meaning of the Minkowski content in Remark 3.6.

2.2 Classes of Fractal Sets

We address the above questions for the following classes of fractal sets.

2.2.1 Self-Similar and Self-Conformal Sets

Let Φ:= {ϕ ₁, …, ϕ _M} denote an IFS of M ≥ 2 contracting maps ϕ _i: X → X acting on a compact subset X of $\mathbb R^d$. The famous Hutchinson-Hata Theorem states that there exists a unique, non-empty and compact subset J ⊂ X, which is invariant under Φ, that is $J=\bigcup _{i=1}^M \phi _i(J)$. If all the maps ϕ _i are similarities, i. e. there exist r _i ∈ (0, 1) such that $\lvert \phi _i(x)-\phi _i(y)\rvert =r_i\lvert x-y\rvert$ for any x, y ∈ X, then the invariant set J is called self-similar. If all the maps ϕ _i extend to conformal maps on an open neighbourhood U of X, i. e. ϕ _i: U → U is a C ¹-diffeomorphism whose total derivative at every point is a similarity, then the invariant set J is called self-conformal. For background we refer the reader to [15].

Below, self-similar and self-conformal sets appear as special cases if A _i,j = 1 for all i, j ∈ Σ and all ϕ _i are similarities resp. extend to conformal maps.

2.2.2 Limit Sets of Graph-Directed Systems

Here, we restrict to a special class of graph-directed systems, namely those which arise from iterated function systems (IFS) by forbidding certain transitions. However, the results presented below are not limited to this special class but also hold for general graph-directed systems as defined in [36]. We will provide references at the appropriate places.

Let Φ:= {ϕ ₁, …, ϕ _M} denote an IFS of finitely many contracting maps ϕ _i: X → X acting on a compact subset X of $\mathbb R^d$. Further, let A be an irreducibleM × M matrix of zeros and ones, i. e. for each pair i, j ∈ Σ:= {1, …, M} there exists $n\in \mathbb N$ such that (A ⁿ)_i,j > 0. We allow to concatenate ϕ _i ∘ ϕ _j if and only if A _i,j = 1. Let $\Sigma _A^n: =\{ (\omega _1,\ldots ,\omega _n)\in \Sigma ^{n}\mid A_{\omega _i,\omega _{i+1}}=1\ \forall \, i\in \{1,\ldots ,n-1 \} \}$. The limit set of this type of graph-directed system is defined to be

$$\displaystyle \begin{aligned} J:= \bigcap_{n\in\mathbb N} \bigcup_{\omega\in\Sigma_A^n} \phi_{\omega}(X), \end{aligned} $$

where $\phi _{\omega }: = \phi _{\omega _1}\circ \cdots \circ \phi _{\omega _n}$ for ω = (ω ₁, …, ω _n). We in particular study the cases in which all the maps ϕ _i are similarities, and in which all the maps ϕ _i extend to conformal maps on an open neighbourhood U of X.

3 Probabilistic Renewal Theorems and Their Applications to Questions 2.1 and 2.2 for Self-Similar Sets and Limit Sets of Graph-Directed Systems of Similarities

Probabilistic renewal theory is concerned with waiting times in-between occurrences of a repetitive pattern connected with repeated trials of a stochastic experiment. In classical renewal theory, it is assumed that after each occurrence of the pattern, the trials start from scratch. This means that the trials which follow an occurrence of the pattern form a replica of the whole stochastic experiment. In other words, the waiting times in-between successive occurrences of the pattern, also called inter-arrival times, are assumed to be mutually independent random variables with the same distribution (see [16, Ch. XIII] and [17]). The classical renewal theorems have been extended in various ways and to various different settings. One such extension, which we focus on here is given by Markov renewal theory, where the independence condition is weakened. The literature on classical and Markov renewal theory is vast. Therefore, we abstain from presenting a complete list of references but instead refer the reader to the following monographs and fundamental articles, where further references can be found: [1, 2, 10, 16, 17, 34].

The aim of this section is to present the afore-mentioned renewal theorems and to demonstrate to which question in which setting the respective renewal theorems are natural to apply. We will present a solution to a selection of the problems, focus on the ideas and provide references for the details. More precisely, we study the fundamental setting of renewal theory in Sects. 3.1 and 3.3 and show how its results can be utilised to answer Questions 2.1 and 2.2 for self-similar sets in Sects. 3.2 and 3.4. Subsequently, in Sect. 3.5 we turn to Markov renewal theory and apply Markov renewal theorems to answer Questions 2.1 and 2.2 for limit sets of graph-directed systems of similarities in Sect. 3.6.

3.1 Expected Number of Renewals—Blackwell’s Renewal Theorem

In the afore-mentioned setting it is of interest how many occurrences of the pattern (renewals) are expected in a given time interval, if the process has been going on for a long time.

Let W, W ₁, W ₂, … denote independent identically distributed (i. i. d.) non-negative random variables on a common probability space $(\Omega ,\mathcal A,\mathbb P)$. We interpret W _i as the waiting time between the (i − 1)-st and the i-th occurrence of the pattern and set W ₀:= 0. For $n\in \mathbb N_0: =\mathbb N\cup \{0\}$ define $S_n: = \sum _{i=0}^{n} W_i$, which is the epoch of the (n + 1)-st occurrence of a renewal, the origin counting as a renewal epoch. Further, introduce the renewal function$N\colon [0,\infty )\times (0,\infty )\to \mathbb R\cup \{\infty \}$ by

(3.1)

where denotes expectation. Thus, N(t, h) gives the expected number of renewals in the time interval (t − h, t].

The asymptotic behaviour of N(t, h) as t →∞ depends on whether the common distribution F of the W _i is lattice or non-lattice. Recall that a distribution function is called lattice if its set of discontinuities lies in a discrete subgroup of $\mathbb R$, i. e. in $a\mathbb Z$ for some a > 0. If a is maximal as such, we say that the distribution is a-lattice. If no such a exists, then it is called non-lattice.

Intuitively, in the non-lattice situation we would expect h renewals in a time interval of length if the process has been going for a long while. Thus, in a time interval of length h intuition yields to be the expected number of renewals. In the a-lattice situation the same is plausible with h replaced by a.

This intuition was made rigorous in a series of publications, in which different situations were covered, see [5, 6, 12, 17, 23] and references therein, resulting in the following renewal theorem, which sometimes is referred to as Blackwell’s renewal theorem.

We say that $f,g\colon \mathbb R\to (0,\infty )$ are asymptotic and write f(t) ∼ g(t) as t →∞ if lim_t→∞ f(t)∕g(t) = 1.

Theorem 3.1

Suppose the setting of the current subsection. In particular, assume that F is supported on [0, ∞). Further, interpretas 0 if.

• (i) If F is a-lattice then

  

• (ii) If F is non-lattice then

  

  for any h > 0.

3.2 Question 2.1 for Self-Similar Sets—Application of Blackwell’s Renewal Theorem

We fix the following notation. Φ:= {ϕ ₁, …, ϕ _M} shall denote an IFS of finitely many contracting similarities ϕ _i with similarity ratio r _i acting on [0, 1] with invariant set E ⊂ [0, 1]. For ease of exposition, we assume that {0, 1}⊂ E and that $\phi _i([0,1])\cap \phi _j([0,1])=\varnothing$ for distinct i, j, however, note that the open set condition is sufficient. (If we assume the milder open set condition to be satisfied with a bounded feasible open set O, i. e. $\phi _iO\cap \phi _jO=\varnothing$ for i ≠ j and ϕ _i O ⊆ O for all i, then we would consider the connected components of $O\setminus \bigcup _{i=1}^M\phi _i O$ below, of which there might be infinitely many.)

Let G ₁, …, G _q denote the connected components of $[0,1]\setminus \bigcup _{i=1}^M \phi _i([0,1])$. Then the connected components of [0, 1] ∖ E are precisely the intervals ϕ _ω(G _j). Recall, $\phi _{\omega }: = \phi _{\omega _1}\circ \cdots \circ \phi _{\omega _n}$ and $r_{\omega }: = r_{\omega _1}\cdots r_{\omega _n}$ for ω = (ω ₁, …, ω _n). Thus,

$$\displaystyle \begin{aligned} N_{\log h}(r) = \sum_{j=1}^q \sum_{n=0}^{\infty}\#\{ \omega\in\Sigma^n\mid hr> r_{\omega}\lvert G_j\rvert \geq r\} = \sum_{j=1}^q M_{\log h}\left(\tfrac{r}{\lvert G_j\rvert}\right), \end{aligned} $$

(3.2)

where Σ:= {1, …, M}, $M_{\log h}(r): = \sum _{n=0}^{\infty }\#\{ \omega \in \Sigma ^n\mid hr> r_{\omega } \geq r\}$ and $\Sigma ^0: =\{\varnothing \}$, with $\varnothing$ denoting the empty word and $r_{\varnothing }: = 1$. For applying Blackwell’s renewal theorem, we introduce random variables W _i in the following. By the Moran-Hutchinson formula, $1=\sum _{i=1}^M r_i^{D}$ where D is the Hausdorff dimension of E. Thus, for i ∈ Σ defines the distribution of a non-negative random variable W. With W, W ₁, W ₂, … being i.i.d. the distribution of S _n:= W ₁ + ⋯ + W _n is given by for t > 0. With this notation

$$\displaystyle \begin{aligned} \mbox{e}^{-Dt}M_{\log h}(\mbox{e}^{-t}) =\mathbb{E}\left( \sum_{n=0}^{\infty} z(t-S_n) \right), \end{aligned} $$

(3.3)

where $z\colon \mathbb R\to \mathbb R$, .

3.2.1 The Lattice Case

If $-\log r_1,\ldots ,-\log r_M$ lie in the discrete subgroup $a\mathbb Z$ of $\mathbb R$ with a > 0 maximal as such, then W is a-lattice. As $-\log r_{\omega }\in a\mathbb Z$ for each ω, it follows that $t-a <-\log r_{\omega }\leq t$ is equivalent to $-\log r_{\omega }/a = \lfloor t/a\rfloor : =\max \{ k\in \mathbb Z\mid k\leq t/a \}$. Whence, Theorem 3.1 implies for t →∞

yielding

$$\displaystyle \begin{aligned} N_{a}(\mathrm{e}^{-t}) \sim \frac{a}{-\sum_{i=1}^M r_i^{D}\log r_i} \sum_{j=1}^q \mathrm{e}^{a D\lfloor (t+\log\lvert G_j\rvert)/a\rfloor} \quad \text{as}\quad t\to\infty. \end{aligned} $$

3.2.2 The Non-lattice Case

If $-\log r_1,\ldots ,-\log r_M$ do not generate a discrete subgroup of $\mathbb R$ then W is non-lattice. Let h > 0 be arbitrary. Theorem 3.1 implies for t →∞

We abstain from gaining the precise asymptotics here as these can be easily deduced from the key renewal theorem, see Remark 3.8.

3.3 The Key Renewal Theorem

The considerations of Sect. 3.1 are intimately related to the asymptotic behaviour of the solution $Z\colon \mathbb R\to \mathbb R$ of the renewal equation

$$\displaystyle \begin{aligned} Z(t) = z(t) + \int_{-\infty}^{\infty} Z(t-y)\,\mbox{d}F(y) = (z + F\star Z)(t) \end{aligned} $$

(3.4)

with given $z\colon \mathbb R\to \mathbb R$, where ⋆ denotes convolution and F is a distribution on $\mathbb R$.

For obtaining statements on the uniqueness and on the asymptotic behaviour of Z(t) as t →∞ it is required that z be directly Riemann integrable.

Definition 3.2

For a function $f\colon \mathbb R\to \mathbb R$, h > 0 and $k\in \mathbb Z$ set

$$\displaystyle \begin{aligned} \underline{m}_k(f,h)&:=\inf\{f(t)\mid (k-1)h\leq t<kh\}\qquad \text{and}\\ \overline{m}_k(f,h)&:=\sup\{f(t)\mid (k-1)h\leq t<kh\}. \end{aligned} $$

The function f is called directly Riemann integrable (d. R. i.) if for some sufficiently small h > 0

$$\displaystyle \begin{aligned} \underline{R}(f,h):=\sum_{k\in\mathbb Z}h\cdot\underline{m}_k(f,h)\qquad \text{and}\qquad \overline{R}(f,h):=\sum_{k\in\mathbb Z}h\cdot\overline{m}_k(f,h) \end{aligned} $$

are finite and tend to the same limit, denoted by $\int f(T)\,\mbox{d}T$, as h → 0.

Direct Riemann integrability excludes wild oscillations of the function at infinity and is stronger than Riemann integrability. For further insights into this notion we refer the reader to [17, Ch. XI] and [2, Ch. B.V].

As before, W, W ₁, W ₂, … shall denote i. i. d. random variables with common distribution F. Note that here the W _i are not necessary non-negative. Recall that $S_n: = \sum _{i=0}^n W_i$ with W ₀:= 0.

Lemma 3.3 ([1, Ch. 3.2])

If z is d.R.i. then the function $Z\colon \mathbb R\to \mathbb R$ given by

(3.5)

is the unique solution of the renewal equation (3.4) that satisfies lim_t→−∞ Z(t) = 0.

Being a solution of the renewal equation (3.4), Z from (3.5) is called renewal function. Setting and assuming that F is concentrated on [0, ∞) we recover the renewal function N(⋅, h) of Sect. 3.1, see Eq. (3.1). Thus, it is apparent that the present setting is much more general than that of Sect. 3.1.

Theorem 3.4 ([1, Satz 3.2.2])

Denote by$z\colon \mathbb R\to \mathbb R$a d.R.i. function. Let F be a distribution supported on$\mathbb R$with positive mean and let Z be the unique solution (3.5) of the renewal equation (3.4) which satisfies lim_t→−∞ Z(t) = 0. Then the following hold.

• (i) If F is non-lattice, then as t →∞

  

• (ii) If F is a-lattice, then as t →∞

  

Notice, direct Riemann integrability of z ensures convergence of the series $\sum _{\ell =-\infty }^{\infty } z(a \ell +t)$ in the above theorem, which can be seen as follows. If $m\in \mathbb N$ is minimal such that $\overline {R}(z,a/m)<\infty$ then $\overline {R}(z,a)\leq m \overline {R}(z,a/m)<\infty$. Thus, m = 1 and we are done.

Remark 3.5

A nice exposition of the key renewal theorem tailored to fractal geometry can be found in [14, Ch. 7], where it is applied to obtain results on the asymptotic behaviour of the covering number of a self-similar subset of $\mathbb R^d$, and to Questions 2.1 and 2.2 for self-similar subsets of $\mathbb R$.

3.4 Questions 2.1 and 2.2 for Self-Similar Sets—Application of the Key Renewal Theorem

In the setting of self-similar sets both Questions 2.1 and 2.2 can be solved by means of the key renewal theorem and the ideas below stem from [40]. We focus on the solution to Question 2.2 and briefly discuss Question 2.1 in Remark 3.8. We fix the following notation. Φ:= {ϕ ₁, …, ϕ _M} shall denote an IFS of finitely many contracting similarities ϕ _i with similarity ratio r _i acting on $X\subset \mathbb R^d$ with invariant set E. We suppose that the open set condition (OSC) is satisfied and that O is a feasible open set for Φ, i. e. ϕ _i(O) ⊂ O and $\phi _i(O)\cap \phi _j(O)=\varnothing$ for i ≠ j. Assume w. l. o. g. that O is bounded.

Often, depending on the shape of O, the expression λ _d(E _r ∖ O) is very easy to determine. For the Sierpiński carpet E for instance, (i.e. for the invariant set E of the IFS $\{x\mapsto x/3 + (i/3,j/3)\}_{i,j\in \{0,1,2\}^2\setminus \{(1,1)\}}$ acting on X = [0, 1]²) one can choose O = (0, 1)², giving λ _d(E _r ∖ O) = 4r + πr ². Moreover, it is known that $\lambda _d(E_r\setminus O)=\mathfrak {o}(r^{d-\dim _M(E)})$ as r → 0 for general self-similar sets E under the OSC with the little Landau symbol $\mathfrak o$, see [40]. (For functions $f,g\colon \mathbb R\to \mathbb R$ we write $f=\mathfrak {o}(g)$ as t →∞ if lim_t→∞ f(t)∕g(t) = 0.) Therefore, we consider λ _d(E _r ∩ O) and let Γ:= O ∖ Φ(O), where the action of Φ on a subset U of X is defined via $\Phi (U) : = \bigcup _{i=1}^M \phi _i(U)$. Then O can be decomposed as

$$\displaystyle \begin{aligned} O=\bigcup_{n=0}^{\infty}\bigcup_{\omega\in\Sigma^n}\phi_{\omega}\Gamma\cup\bigcap_{n=0}^{\infty}\Phi^n O, \end{aligned}$$

where the unions are disjoint. We have $\Phi \left (\overline {\bigcap _{n=0}^{\infty }\Phi ^n O}\right )=\overline {\bigcap _{n=0}^{\infty }\Phi ^n O}$. Thus, $\overline {\bigcap _{n=0}^{\infty }\Phi ^n O}$ is either empty or coincides with E by uniqueness of the self-similar set. Therefore, $\lambda _d\left (\bigcap _{n=0}^{\infty }\Phi ^n O\right )\leq \lambda _d(E)$. Let D denote the Minkowski dimension of E. If D < d then λ _d(E) = 0 and whence $\lambda _d\left (\bigcap _{n=0}^{\infty }\Phi ^n O\right )=0$. Suppose that O is chosen in such a way that E _r ∩ ϕ _ω Γ = (ϕ _ω E)_r ∩ ϕ _ω Γ for each ω. This condition is known as the locality property and it is shown in [40] that to each IFS of similarities satisfying the OSC there is a feasible open set O which satisfies the locality property, namely the central open set as introduced in [3]. Thus,

$$\displaystyle \begin{aligned} \lambda_d(E_{\mathrm{e}^{-t}}\cap O) &= \sum_{n=0}^{\infty}\sum_{\omega\in\Sigma^n}\lambda_d(E_{\mathrm{e}^{-t}}\cap \phi_{\omega}\Gamma)\\ &= \sum_{n=0}^{\infty}\sum_{\omega\in\Sigma^n} \lambda_d((\phi_{\omega}E)_{\mathrm{e}^{-t}}\cap \phi_{\omega}\Gamma)\\ &= \sum_{n=0}^{\infty}\sum_{\omega\in\Sigma^n} r_{\omega}^d\lambda_d(E_{\mathrm{e}^{-t-\log r_{\omega}}}\cap \Gamma). \end{aligned} $$

Let W, W ₁, W ₂, … denote i. i. d. random variables with common distribution given by as in Sect. 3.1. In [40] it is shown that $t\mapsto z(t): = \mathrm {e}^{-t(D-d)}\lambda _d(E_{\mathrm {e}^{-t}}\cap \Gamma )$ is d. R. i., which allows to apply the key renewal theorem to

3.4.1 The Lattice Case

If $-\log r_1,\ldots ,-\log r_M$ lie in the discrete subgroup $a\mathbb Z$ of $\mathbb R$ with a > 0 maximal as such, then W is a-lattice. Thus, Theorem 3.4 yields for t →∞

(3.6)

Note that g(t) is periodic in t with period a. In general it is not known whether g is strictly periodic (implying that E is not Minkowski-measurable) or constant (implying Minkowski-measurability of E). For self-similar subsets of $\mathbb R$ arising from lattice IFS E being not Minkowski measurable has been shown in [26], building on [20, 27, 30]. In the higher dimensional setting the analogue statement has been verified under further assumptions in various works, see [27] and references therein.

3.4.2 The Non-lattice Case

If $-\log r_1,\ldots ,-\log r_M$ do not generate a discrete subgroup of $\mathbb R$ then W is non-lattice and Theorem 3.4 gives for t →∞

(3.7)

Thus, (3.7) implies that E is Minkowski measurable in the non-lattice setting. Furthermore, the Minkowski content of E is given by the right hand side of (3.7).

Remark 3.6

Just like there is a variety of sets of the same topological dimension, e.g. 3-dimensional balls and cubes, there are various distinct fractal sets of the same Minkowski dimension. The formula in (3.7) shows that we can use the Minkowski content to distinguish between such sets. The value that the Minkowski content takes highly depends on the geometric structure of Γ. Equation (3.7) shows that if Γ includes large intervals (discs or balls), i.e. is highly lacunar, then $\mathcal M(E)$ will be relatively small, compared to the case when Γ is made up of several connected components of smaller size. We refer the interested reader to [24, 33] for further details.

Remark 3.7

In the setting of self-similar sets, Question 2.2 has been studied by various authors. References include [11, 13, 18, 29, 31, 32, 40] and several related articles by the same authors. Related to the Minkowski measurability question is the question of existence of fractal curvature measures, see e.g. [8, 37, 41].

Remark 3.8

Combining the methods presented above with those of Sect. 3.2 leads to an answer of Question 2.1 in the setting of Sect. 3.2: combining (3.2) with (3.3) gives

$$\displaystyle \begin{aligned} \mathrm{e}^{-Dt}N_{\log h}(\mathrm{e}^{-t}) =\sum_{j=1}^q \lvert G_j\rvert^D \mathbb{E}\left( \sum_{n=0}^{\infty} z(t+\log\lvert G_j\rvert-S_n) \right) \end{aligned} $$

with $z\colon \mathbb R\to \mathbb R$, . In the a-lattice situation an application of the key renewal theorem leads to

$$\displaystyle \begin{aligned} \mathrm{e}^{-Dt} N_{a}(\mathrm{e}^{-t}) \sim \frac{a}{-\sum_{i=1}^M r_i^D\log r_i}\sum_{j=1}^q \lvert G_j\rvert^D \mathrm{e}^{a D\{ (t+\log \lvert G_j\rvert)/a \}}, \end{aligned} $$

where $\{x\}: = x-\lvert x\rvert \in [0,1)$ for $x\in \mathbb R$. In the non-lattice situation an application of the key renewal theorem yields

$$\displaystyle \begin{aligned} \mathrm{e}^{-Dt}N_{\log h}(\mathrm{e}^{-t}) \sim \frac{1-h^{-D}}{D\sum_{i=1}^M r_i^D\log r_i}\sum_{j=1}^q\lvert G_j\rvert^D. \end{aligned} $$

3.5 Markov Renewal Theory

In Markov renewal theory one is concerned with the asymptotic behaviour of solutions of the Markov renewal equation, which is a system of coupled renewal equations that we will introduce momentarily. Before, let us allude to the stochastic motivation.

By a Markov random walk, we understand a point process for which the inter-arrival times W ₀, W ₁, … are not necessarily i. i. d. (as in the preceding subsections), but Markov dependent on a Markov chain $(X_n)_{n\in \mathbb N_0}$ with finite or countable state space Σ. This means that W _n is sampled according to the current and proximate values X _n, X _n+1 but is independent of the past values X _n−1, …, X ₀ of the underlying Markov chain. Thus, $(X_{n+1},W_n)_{n\in \mathbb N_0}$ has an interpretation as a stochastic process with state space $\Sigma \times \mathbb R$ and transition kernel $U\colon \Sigma \times (\mathcal P(\Sigma )\otimes \mathfrak B(\mathbb R))\to \mathbb R$ given by

$$\displaystyle \begin{aligned} U(i,\{j\}\times(-\infty,t]) := \mathbb P(X_{n+1}=j,W_n\leq t\mid X_n=i) =: F_{i,j}(t). \end{aligned} $$

(3.8)

Here $\mathcal P(\Sigma )$ denotes the power set of Σ and $\mathfrak B(\mathbb R)$ denotes the Borel σ-algebra on $\mathbb R$ and F _i,j defines a distribution function of a finite measure with total mass for given i, j ∈ Σ.

The system of equations

$$\displaystyle \begin{aligned} N(t,i) &=f_i(t)+\sum_{j\in\Sigma} \int_{-\infty}^{\infty}N(t- u,j)F_{i,j}(\mbox{d}u), \end{aligned} $$

(3.9)

for varying i ∈ Σ and given $f_i\colon \mathbb R\to \mathbb R$ is called a Markov renewal equation, multivariate renewal equation or system of coupled renewal equations. This system of equations is a direct analogue of (3.4) to the current setting, taking the Markov dependence into account.

The Laplace transform of F _i,j at $s\in \mathbb R$ is given by

$$\displaystyle \begin{aligned} B_{i,j}(s) := (\mathcal L F_{i,j})(s) := \int_{-\infty}^{\infty}\mathrm{e}^{-sT}\mbox{d} F_{i,j}(T). \end{aligned}$$

Setting B(s):= (B _ij(s))_{i,j ∈ Σ}, and assuming that Σ is of finite cardinality, the Perron-Frobenius theorem for matrices yields a unique s for which B(s) has spectral radius one.

Theorem 3.9 (A Markov Renewal Theorem)

Let M ≥ 2 be an integer and assume that Σ = {1, …, M}. For i, j ∈ Σ let F _i,j(t) be as in (3.8) and suppose that F:= (∥F _i,j∥_∞)_{i,j ∈ Σ}is irreducible. Let δ > 0 denote the unique positive real number for which the matrix B(δ) given by$B_{i,j}(\delta ): =\int \mathrm {e}^{-\delta u}F_{i,j}(\mathit{\mbox{d}}u)$has spectral radius one. For i ∈ Σ let$f_i\colon \mathbb R\to \mathbb R$denote d.R.i. functions. Suppose that there exist C, s > 0 such that$\mathrm {e}^{-\delta t}\lvert f_i(t)\rvert \leq C\mathrm {e}^{st}$for t < 0 and i ∈ Σ. Choose vectors ν, h with νB(δ) = ν, B(δ)h = h and ν _i, h _i > 0 for i ∈ Σ. Let N(t, i) for i ∈ Σ solve the Markov renewal equation (3.9).

• (i) If F _i,jis non-lattice for some (i, j) ∈ Σ ², then

  $$\displaystyle \begin{aligned} \mathrm{e}^{-\delta t}N(t,i) \sim \frac{h_i\sum_{j=1}^M\nu_j\int\mathrm{e}^{-\delta T}f_j(T)\mathit{\mbox{d}}T}{\sum_{k,j=1}^M\nu_kh_j\int T\mathrm{e}^{-\delta T}F_{k,j}(\mathit{\mbox{d}}T)} =: G(i). \end{aligned}$$

• (ii) We always have

  $$\displaystyle \begin{aligned} \lim_{t\to\infty} t^{-1}\int_{0}^t\mathrm{e}^{-T\delta}N(T,i)\mathit{\mbox{d}}T=G(i). \end{aligned}$$

A statement for the lattice situation, i. e. when all F _i,j are lattice, can be deduced from Theorem 4.2.

Remark 3.10

The above theorem is presented in a similar form in [2, VII. Thm. 4.6]. More general versions of Markov renewal theorems can be found in the literature (see e.g. [1]). The precise version of Theorem 3.9 is a direct consequence of the more general Renewal Theorem 4.2, which we present in the next section. In Appendix B.2 we allude to how Theorem 3.9 can be deduced from Theorem 4.2.

3.6 Questions 2.1 and 2.2 for Limit Sets of Graph-Directed Systems of Similarities—Application of Markov Renewal Theory

We demonstrate how to apply Markov renewal theory by considering the following example. Let X:= [0, 1] and let ϕ ₁, ϕ ₂, ϕ ₃: X → X be given by

$$\displaystyle \begin{aligned} \phi_1(x)=\frac{x}{4},\quad \phi_2(x)=\frac{x}{6} + \frac{5}{12},\quad \phi_3(x)=\frac{x}{4} + \frac{3}{4}\qquad \text{and}\qquad A=\left( \begin{array}{ccc} 1& 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 1 \end{array} \right). \end{aligned}$$

Further, let J denote the limit set of Φ:= {ϕ ₁, ϕ ₂, ϕ ₃} associated with A. The first two steps in the construction of J are depicted in Fig. 1.

Fig. 1

First two steps in the construction of the limit set of the graph-directed system studied in Sect. 3.6

For a given h > 1 let N ₁(r), N ₂(r), N ₃(r) respectively denote the number of connected components of [0, 1∕4] ∖ J, [5∕12, 7∕12] ∖ J, [3∕4, 1] ∖ J of lengths between r and rh. We have that

Setting

we see that $N(t,i)=f_i(t)+\sum _{j\in \Sigma } \int _{-\infty }^{\infty }N(t- u,j)F_{i,j}(\mbox{d}u)$ for i ∈ Σ. Thus, the system of coupled renewal equations (3.9) is satisfied. As we are in the non-lattice situation and all hypotheses of Theorem 3.9 are clearly satisfied, Theorem 3.9 thus yields

$$\displaystyle \begin{aligned} \mathrm{e}^{-\delta t} N(t,1) &= \mathrm{e}^{-\delta t} N(t,3) \sim \frac{(1-h^{-\delta})(1+2^{-\delta})}{2\delta[\log 4(1+6^{\delta})+\log 6]} =: G \quad \text{and}\\ \mathrm{e}^{-\delta t} N(t,2) &\sim 6^{-\delta} G \end{aligned} $$

as t →∞, where δ ≈ 0.6853. Now the asymptotics of the total number of complementary intervals of lengths between e^−t and he^−t can be obtained from the above through evaluating

There is nothing particular about this example and the general setting, assuming $\phi _i(\mbox{int}(X))\cap \phi _j(\mbox{int}(X))=\varnothing$ for i ≠ j, can be treated analogously. Here, int(X) denotes the topological interior of X.

The author is not aware that this approach has been carried out in the literature. However, general results in the current setting were obtained in [20] for the more general class of limit sets of conformal graph-directed systems, by means of the renewal theorems that we turn to in the following section.

4 Renewal Theory in Symbolic Dynamics

The renewal theorem which is presented in the current section was developed in [25] and extended to the setting of infinite state space in [21]. Here, the focus lies on the situation of finite state space.

Now, the assumption of the previous section that $(X_n)_{n\in \mathbb N_0}$ is a Markov chain and that W _n is Markov dependent on $(X_n)_{n\in \mathbb N_0}$ is dropped. Instead, we consider a time-homogeneous (i.e. stationary increments) stochastic process $(X_n)_{n\in \mathbb Z}$ with finite state space Σ = {1, …, M} and time-set $\mathbb Z$ and extend to the setting that W _n may depend on the current values X _n+1, X _n as well as on the whole past X _n−1, X _n−2, … of the stochastic process $(X_n)_{n\in \mathbb Z}$.

In this situation it is of interest to study the limiting behaviour as t →∞ of the renewal function $N\colon \mathbb R \times \Delta \to \mathbb R$ given by

$$\displaystyle \begin{aligned} N(t,x) := \mathbb E_x\left[\sum_{n=0}^{\infty}f_{X_n\cdots X_1 x}\left(t-\sum_{k=0}^{n-1}W_k\right)\right], \end{aligned} $$

(4.1)

where $\{f_y\colon \mathbb R\to \mathbb R\mid y\in \Delta \}$ is a family of functions, $\mathbb E_x$ is the conditional expectation given X ₀ X ₋₁⋯ = x, for n = 0 we interpret $f_{X_n\cdots X_1 x}(t-\sum _{k=0}^{n-1}W_k)$ to be f _x(t), and Δ is a subset of $\Sigma ^{\mathbb N}$. For instance, if , then N(t, x) gives the expected number of renewals in the time-interval (0, t] given X ₀ X ₋₁⋯ = x.

In view of the questions in fractal geometry that we raised in Sect. 2 we impose some assumptions, which turn the renewal function from (4.1) into a deterministic one. For this, well-known terminology and theorems from symbolic dynamics are used. For convenience, these are introduced in Appendix A and referred to at the appropriate places.

4.1 Setting

The admissible transitions of the stochastic process $(X_n)_{n\in \mathbb N_0}$ are assumed to be governed by an irreducible (M × M)- incidence matrix A of zeros and ones. Hence infinite paths of the process are encoded by elements of the code space $\Sigma _A: = \{x\in \Sigma ^{\mathbb N}\mid A_{x_k,x_{k+1}}=1\ \forall \, k\in \mathbb N\}$, see Sect. A.1. Thus, we consider the renewal function $N\colon \mathbb R\times \Sigma _A\to \mathbb R$ from (4.1) acting on $\mathbb R\times \Sigma _A$.

A natural assumption in applications is that the recent history of $(X_n)_{n\in \mathbb N_0}$ has more influence on which state will be visited next than the earlier history. This is reflected in the assumption that the function $\eta \colon \Sigma _A\to \mathbb R$ given by

$$\displaystyle \begin{aligned} \eta(ix) := \log\mathbb P_x(X_{1}=i) \end{aligned}$$

belongs to the class $\mathcal F_{\alpha }(\Sigma _A)$ of real-valued α-Hölder continuous functions on Σ_A for some α ∈ (0, 1), see Sect. A.2. Here, i ∈ Σ and $\mathbb P_x$ is the distribution corresponding to $\mathbb E_x$. Note that $\mathbb P_x(X_1=i): = \mathbb P(X_1=i\mid X_0X_{-1}\cdots =x)>0$ if ix ∈ Σ_A by the definition of Σ_A. Similarly, it is assumed that the dependence of W _n on X _n+1, X _n, … is described by a Hölder continuous function. That is we assume existence of $\xi \in \mathcal F_{\alpha }(\Sigma _A)$ with

$$\displaystyle \begin{aligned} W_n=\xi(X_{n+1}X_nX_{n-1}\cdots). \end{aligned}$$

This notation allows us to evaluate the conditional expectation and express N(t, x) in a deterministic way. Let σ denote the left-shift on Σ_A and S _n the n-th Birkhoff sum, see Sects. A.1 and A.3. Since $\sum _{k=0}^{n-1} W_k=S_n\xi (X_{n}X_{n-1}\cdots )$ and, for x, y ∈ Σ_A with σ ⁿ y = x, we have $\mathbb P(X_nX_{n-1}\cdots =y\mid X_0X_{-1}\cdots =x)=\exp (S_n\eta (y))$ it follows that

$$\displaystyle \begin{aligned} N(t,x) =\sum_{n=0}^{\infty}\sum_{y\in\Sigma_A:\sigma^n y=x}f_y(t-S_n\xi(y))\mathrm{e}^{S_n\eta(y)}. \end{aligned} $$

(4.2)

From this, one can deduce the renewal-type equation

$$\displaystyle \begin{aligned} N(t,x) =\sum_{y\in\Sigma_A:\sigma y=x} N(t-\xi(y),y)\mathrm{e}^{\eta(y)}+f_x(t), \end{aligned} $$

which justifies calling N a renewal function. Intuitively, inter-arrival times are non-negative and probabilities take values in [0, 1]. However, when considering the deterministic form (4.2), ξ is allowed to take negative values, provided there exists $n\in \mathbb N$ for which S _n ξ is strictly positive. Note that this condition is equivalent to ξ being co-homologous (see Definition A.2) to a strictly positive function, see [25, Rem. 2.1]. Moreover, η is allowed to be chosen freely from the class $\mathcal F_{\alpha }(\Sigma _A)$.

4.2 The Renewal Theorem

For y ∈ Σ_A and $t\in \mathbb R$ write

$$\displaystyle \begin{aligned} f_y(t)=\chi(y)\cdot g_y(t) \end{aligned}$$

with non-negative but not identically zero $\chi \in \mathcal {F}_{\alpha }(\Sigma _A)$, where $g_y\colon \mathbb R\to \mathbb R$, for y ∈ Σ_A, need to satisfy a regularity condition, which is related to the direct Riemann integrability assumption of the classical key renewal theorem (see Sect. 3.3), and which we introduce next.

Definition 4.1

A family of functions $\{f_x\colon \mathbb R\to \mathbb R \mid x\in I\}$ with some index set I is called equi directly Riemann integrable (equi d. R. i.) if f _x is d. R. i. for all x ∈ I (see Definition 3.2) and if

$$\displaystyle \begin{aligned} \sum_{k\in\mathbb Z} h\cdot\sup_{x\in I}\Big{(}\underline{m}_k(f_x,h)-\overline{m}_k(f_x,h)\Big{)} \end{aligned}$$

tends to zero as h → 0.

For the following, fix ξ and η as in Sect. 4.1 and let $\mathcal {C}(\Sigma _A)$ denote the space of real-valued continuous functions on Σ_A, see Sect. A.2.

Theorem 4.2 (Renewal Theorem in Symbolic Dynamics, [25, Thm. 3.1] and [21, Thm. 3.1])

Let A be irreducible, fix x ∈ Σ _Aand take α ∈ (0, 1). Further, let$\xi ,\eta \in \mathcal {F}_{\alpha }(\Sigma _A)$be so that S _n ξ is strictly positive on Σ _Afor some$n\in \mathbb N$ . Let δ > 0 denote the unique real for which P(η − δξ) = 0, where P denotes the topological pressure function (see Sect. A.3). Assume that x↦g _x(t) is α-Hölder continuous for any$t\in \mathbb R$ , that$\{ t\mapsto \mathrm {e}^{-t\delta }\lvert g_x(t)\rvert \mid x\in \Sigma _A \}$is equi d.R.i. and that there exist C, s > 0 such that$\mathrm {e}^{-t\delta }\lvert g_x(t)\rvert \leq C\mathrm {e}^{st}$for t < 0 and x ∈ Σ _A.

• (i) If ξ is non-lattice (see DefinitionA.2) then there exists$G(x)\in \mathbb R$ , explicitly stated in Sect. A.5 , such that

  $$\displaystyle \begin{aligned} N(t,x)\sim\mathrm{e}^{t\delta} G(x) \end{aligned}$$

  as t →∞, uniformly for x ∈ Σ _A.

• (ii) Assume that ξ is lattice (see DefinitionA.2) and let$\zeta ,\psi \in \mathcal {C}(\Sigma _A)$satisfy the relation

  $$\displaystyle \begin{aligned} \xi-\zeta=\psi-\psi\circ\sigma, \end{aligned}$$

  where$\zeta (\Sigma _A)\subseteq a\mathbb Z$for some a > 0. Suppose that ξ is not co-homologous to any function with values in a proper subgroup of$a\mathbb Z$ , see DefinitionA.2 . Then

  $$\displaystyle \begin{aligned} N(t,x) \sim \mathrm{e}^{t\delta}\widetilde{G}_x(t) \end{aligned} $$

  as t →∞, uniformly for x ∈ Σ _A . Here$\widetilde {G}_x$is periodic with period a and explicitly stated in Sect. A.5.

• (iii) We always have

  $$\displaystyle \begin{aligned} \lim_{t\to\infty}t^{-1}\int_0^{t}\mathrm{e}^{-T\delta}N(T,x)\mathit{\mbox{d}}T=G(x). \end{aligned}$$

Remark 4.3

• (i) In [25] it is shown that weaker assumptions than $\{ t\mapsto \mathrm {e}^{-t\delta }\lvert g_x(t)\rvert \mid x\in \Sigma _A \}$ being equi d.R.i. suffice, see [25, Sec. 3, (A)–(D)].

• (ii) In [28] the case that η is the constant zero-function in conjunction with for every x ∈ Σ_A is addressed. With these restrictions, [25, Sec. 3, (A) and (Da)] are immediate and [25, Sec. 3, (B) and (C)] are shown in [28, Lemma 8.1]. The renewal function from (4.2) becomes

  

  which is a counting function. [25, Thm. 3.1] provides its asymptotic behaviour as t →∞, recovering [28, Thms. 1 to 3].

• (iii) Notice, in [25] the above theorem was obtained under the stronger assumption of A being primitive. This was weakened to A being irreducible in [21], where additionally Theorem 4.2 was extended to the setting of Σ being countably infinite.

In Appendix B we show how versions of the probabilistic renewal theorems, which we stated in Sect. 3, can be deduced from the renewal theorems in symbolic dynamics presented above.

4.3 Questions 2.1 and 2.2 for Limit Sets of Graph-Directed Systems of Conformal Maps, Including Self-conformal Sets—Application of the Renewal Theorems in Symbolic Dynamics

Both Questions 2.1 and 2.2 can be solved for limit sets of graph-directed systems of conformal maps by means of the Renewal theorems in symbolic dynamics. We will show how this is done for Question 2.2 below. Since the main ideas are similar we will not execute how to solve Question 2.1 in this setting. Moreover, we will focus on the case of self-conformal sets here and refer to [22] for the graph-directed case, where details are provided.

As in Sect. 3.4 assume that Φ satisfies the OSC with feasible open set O and w. l. o. g. that O is bounded. Recall from Sect. 3.4 that $\Gamma : = O\setminus \bigcup _{i=1}^M \phi _i O$ and that

$$\displaystyle \begin{aligned} \lambda_d(O) =\lambda_d\left(\bigcup_{n=0}^{\infty}\bigcup_{u\in\Sigma^n}\phi_u\Gamma\right), \end{aligned} $$

(4.3)

where the unions are disjoint. In the following we assume that O can be chosen so that $\lambda _d(E_{\mathrm {e}^{-t}}\cap \Gamma )=\mathfrak {o}(\mathrm {e}^{t(D-d)})$ as t →∞ with the little Landau symbol $\mathfrak o$, where E denotes the self-conformal set associated with Φ and D denote its Minkowski dimension. (For functions $f,g\colon \mathbb R\to \mathbb R$ we write $f=\mathfrak {o}(g)$ as t →∞ if lim_t→∞ f(t)∕g(t) = 0.) This is a mild condition, which is always satisfied for self-similar systems with any feasible open set O, see [40]. For D < d Eq. (4.3) thus gives

$$\displaystyle \begin{aligned} \lambda_d(E_{\mathrm{e}^{-t}}\cap O) &= \sum_{n=0}^{\infty}\sum_{u\in\Sigma^n}\lambda_d(E_{\mathrm{e}^{-t}}\cap\phi_u\Gamma)\\ &=\sum_{\omega\in\Sigma^m}\sum_{n=0}^{\infty}\sum_{u\in\Sigma^n}\lambda_d(E_{\mathrm{e}^{-t}}\cap\phi_u\phi_{\omega}\Gamma)+\mathfrak{o}(\mathrm{e}^{t(D-d)}) \end{aligned} $$

for any $m\in \mathbb N$. In the current setting we need to assume that $\lambda _d(E_{\mathrm {e}^{-t}}\cap \phi _u\phi _{\omega }\Gamma )=\lambda _d((\phi _uE)_{\mathrm {e}^{-t}}\cap \phi _u\phi _{\omega }\Gamma )$. As conformal maps locally behave like similarities the expression $\lambda _d((\phi _uE)_{\mathrm {e}^{-t}}\cap \phi _u\phi _{\omega }\Gamma )$ can be approximated by

$$\displaystyle \begin{aligned} \lvert\phi_u^{\prime}(\pi\sigma\omega x)\rvert^d\lambda_d(E_{\mathrm{e}^{-t}/\lvert\phi_u^{\prime}(\pi\sigma\omega x)\rvert}\cap\phi_{\omega}\Gamma) \end{aligned} $$

(4.4)

with an arbitrary $x\in \Sigma ^{\mathbb N}$. Here, $\pi \colon \Sigma ^{\mathbb N}\to E$ is the code map defined by $\{\pi (\omega )\}: =\bigcap _{n=0}^{\infty }\phi _{\omega \vert _n}(X)$. Introducing the geometric potential function$\xi \colon \Sigma ^{\mathbb N}\to \mathbb R$ associated with the IFS Φ by

$$\displaystyle \begin{aligned} \xi(\omega):=-\log\lvert\phi^{\prime}_{\omega_1}(\pi\sigma\omega)\rvert \end{aligned}$$

we obtain $\exp (-S_n\xi (u\omega x))=\lvert \phi _u^{\prime }(\pi \sigma \omega x)\rvert$. Thus, $\lambda _d(E_{\mathrm {e}^{-t}}\cap O)$ can be approximated by

$$\displaystyle \begin{aligned} \sum_{\omega\in\Sigma^m}\sum_{n=0}^{\infty}\sum_{u\in\Sigma^n}\mathrm{e}^{-dS_n\xi(u\omega x)} \lambda_d(E_{\mathrm{e}^{-t+S_n\xi(u\omega x)}}\cap\phi_{\omega}\Gamma)+\mathfrak{o}(\mathrm{e}^{t(D-d)}). \end{aligned}$$

Setting $f_y(t): =\lambda _d(E_{\mathrm {e}^{-t}}\cap \phi _{\omega }\Gamma )$ for $y\in \Sigma ^{\mathbb N}$, , η:= −dξ and assuming the condition of {e^−tδ f _y∣y ∈ Σ_A} being equi d.R.i. we can apply Thm. 4.2 and, if ξ is non-lattice, obtain

$$\displaystyle \begin{aligned} \sum_{n=0}^{\infty}\sum_{u\in\Sigma^n}\mathrm{e}^{-dS_n\xi(u\omega x)}& \lambda_d(E_{\mathrm{e}^{-t+S_n\xi(u\omega x)}}\cap\phi_{\omega}\Gamma) =N(t,\omega x)\\ &\sim \mathrm{e}^{t\delta}\frac{h_{-(d+\delta)\xi}(\omega x)}{\int\xi\mbox{d}\mu_{-(d+\delta)\xi}}\int_{-\infty}^{\infty}\mathrm{e}^{-T\delta}\lambda_d(E_{\mathrm{e}^{-T}}\cap\phi_{\omega}\Gamma)\mbox{d}T, \end{aligned} $$

where δ > 0 is the unique value for which P(−(d + δ)ξ) = 0, see Sect. A.3 and the terms appearing in the fraction are explained in Sect. A.3, see also Sect. A.5. It is proven in [4] that the Minkowski dimension D of E is the unique solution to P(−Dξ) = 0 thus, d + δ = D. Using the bounded distortion property [35, Lem. 2.3.1] this shows, in the non-lattice situation, that

$$\displaystyle \begin{aligned} \lambda_d(E_{\mathrm{e}^{-t}}\cap O) \sim\mathrm{e}^{t(D-d)}\hspace{-0.1cm}\lim_{m\to\infty}\hspace{-0.1cm}\sum_{\omega\in\Sigma^m}\frac{h_{-D\xi}(\omega x)}{\int\xi\mbox{d}\mu_{-D\xi}}\int_{-\infty}^{\infty}\hspace{-0.3cm}\mathrm{e}^{-T(D-d)}\lambda_d(E_{\mathrm{e}^{-T}}\cap\phi_{\omega}\Gamma)\mbox{d}T. \end{aligned} $$

The lattice case can be treated similarly.

Remark 4.4

Question 2.2 for self-conformal subsets of $\mathbb R$ and limit sets of graph-directed systems in $\mathbb R$, including Fuchsian groups of Schottky type, are treated in [19] and [20], where results of [28] were applied. The desire of obtaining an answer to Question 2.2 in the higher dimensional setting of limit sets of conformal graph-directed systems gave the motivation for developing the renewal theorem in symbolic dynamics that we stated in Theorem 4.2 in [25] and its generalisation to the infinite alphabet case in [21]. In [25] and [22] more details on the above can be found. Results on curvature measures are for instance provided in [7].

Acknowledgements

The author would like to thank the anonymous referee for their helpful and constructive suggestions.

Appendices

A Appendix: Symbolic Dynamics

Here, we provide some background from symbolic dynamics which we use in Sect. 4. Good references for the exposition below are [9, 38].

1.1 A.1 Sub-Shifts of Finite Type—Admissible Paths of a Random Walk Through Σ

Recall the following setting from Sect. 4. Σ = {1, …, M}, M ≥ 2 denotes the state space of the stochastic process $(X_n)_{n\in \mathbb N_0}$ and A denotes an irreducible (M × M)- incidence matrix of zeros and ones. The set of one-sided infinite admissible paths of $(X_n)_{n\in \mathbb N_0}$ through Σ consistent with A = (A _i,j)_{i,j ∈ Σ} is defined by

$$\displaystyle \begin{aligned} \Sigma_A:=\{x\in\Sigma^{\mathbb N}\mid A_{x_k,x_{k+1}}=1\ \forall\, k\in\mathbb N\}. \end{aligned}$$

Elements of Σ_A are interpreted as paths which describe the history of the process, supposing that the process has been going on forever.

The path of the process prior to the current time is described by σ(x), where σ: Σ_A → Σ_A denotes the (left) shift-map on Σ_A given by σ(ω ₁ ω ₂…):= ω ₂ ω ₃…. The set of admissible words of length$n\in \mathbb N$ is defined by

$$\displaystyle \begin{aligned} \Sigma_A^n:=\{\omega\in\Sigma^{n}\mid A_{\omega_k,\omega_{k+1}}=1\ \text{for}\ k\leq n-1\}. \end{aligned}$$

If ω has infinite length or length m ≥ n we define ω|_n:= ω ₁⋯ω _n to be the sub-path of length n. Further, [ω]:= {u ₁ u ₂⋯ ∈ Σ_A∣u _i = ω _i for i ≤ n} is the ω-cylinder set for $\omega \in \Sigma _A^n$.

1.2 A.2 (Hölder-)Continuous and (Non-)lattice Functions

Equip $\Sigma ^{\mathbb N}$ with the product topology of the discrete topologies on Σ and equip $\Sigma _A\subset \Sigma ^{\mathbb N}$ with the subspace topology, i. e. the weakest topology with respect to which the canonical projections onto the coordinates are continuous. Denote by $\mathcal C(\Sigma _A)$ the space of continuous real-valued functions on Σ_A. Elements of $\mathcal C(\Sigma _A)$ are called potential functions.

Definition A.1

For $\xi \in \mathcal C(\Sigma _A)$, α ∈ (0, 1) and $n\in \mathbb N_0$ define

$$\displaystyle \begin{aligned} \text{var}_n(\xi)&:=\sup\{\lvert \xi(\omega)-\xi(u)\rvert\mid \omega, u\in\Sigma_A\ \text{and}\ \omega_i=u_i\ \text{for all}\ i\in\{1,\ldots,n\}\},\\ \lvert \xi\rvert_{\alpha}&:=\sup_{n\geq 0}\frac{\text{var}_n(\xi)}{\alpha^{n}}\ \text{and}\\ \mathcal F_{\alpha}(\Sigma_A)&:=\{\xi\in\mathcal C(\Sigma_A)\mid \lvert \xi\rvert_{\alpha}<\infty\}. \end{aligned} $$

Elements of $\mathcal F_{\alpha }(\Sigma _A)$ are called α-Hölder continuous functions on Σ_A.

Definition A.2

Functions $\xi _1,\xi _2\in \mathcal {C}(\Sigma _A)$ are called co-homologous, if there exists $\psi \in \mathcal {C}(\Sigma _A)$ such that ξ ₁ − ξ ₂ = ψ − ψ ∘ σ. A function $\xi \in \mathcal {C}(\Sigma _A)$ is said to be lattice, if it is co-homologous to a function whose range is contained in a discrete subgroup of $\mathbb R$. Otherwise, we say that ξ is non-lattice.

1.3 A.3 Topological Pressure Function and Gibbs Measures

The topological pressure function$P\colon \mathcal C(\Sigma _A)\to \mathbb R$ is given by the well-defined limit

$$\displaystyle \begin{aligned} P(\xi):=\lim_{n\to\infty}n^{-1}\log\sum_{\omega\in\Sigma_A^n}\exp\sup_{u\in[\omega]}S_n\xi(u). \end{aligned} $$

(A.1)

Here, $S_n\xi : =\sum _{k=0}^{n-1}\xi \circ \sigma ^k$ denotes the n-th Birkhoff sum of ξ with $n\in \mathbb N$ and S ₀ ξ:= 0.

Proposition A.3

Let$\xi ,\eta \in \mathcal C(\Sigma _A)$be so that S _n ξ is strictly positive on Σ _A , for some$n\in \mathbb N$ . Then s↦P(η + sξ) is continuous, strictly monotonically increasing and convex with lim_s→−∞ P(η + sξ) = −∞ and lim_s→∞ P(η + sξ) = ∞. Hence, there is a unique$\delta \in \mathbb R$for which P(η − δξ) = 0.

A finite Borel measure μ on Σ_A is said to be a Gibbs measure for $\xi \in \mathcal C(\Sigma _A)$ if there exists a constant c > 0 such that

$$\displaystyle \begin{aligned} c^{-1} \leq \frac{\mu([\omega\vert_n])}{\exp(S_n \xi(\omega)-n\cdot P(\xi))} \leq c \end{aligned} $$

(A.2)

for every ω ∈ Σ_A and $n\in \mathbb N$.

1.4 A.4 Ruelle’s Perron-Frobenius Theorem

The Ruelle-Perron-Frobenius operator to a potential function $\xi \in \mathcal C(\Sigma _A)$ is defined by $\mathcal L_{\xi }\colon \mathcal C(\Sigma _A)\to \mathcal C(\Sigma _A)$,

$$\displaystyle \begin{aligned} \mathcal L_{\xi} \chi(x):= \sum_{y\in\Sigma_A:\sigma y=x} \chi(y) \mathrm{e}^{\xi(y)}. \end{aligned} $$

(A.3)

The dual operator acting on the set of Borel probability measures supported on Σ_A, is denoted by $\mathcal L_{\xi }^*$.

By [39, Thm. 2.16, Cor. 2.17] and [9, Theorem 1.7], for each $\xi \in \mathcal F_{\alpha }(\Sigma _A)$, some α ∈ (0, 1), there exists a unique Borel probability measure ν _ξ on Σ_A satisfying $\mathcal L_{\xi }^*\nu _{\xi }=\gamma _{\xi }\nu _{\xi }$ for some γ _ξ > 0. This equation uniquely determines γ _ξ, which satisfies $\gamma _{\xi }=\exp (P(\xi ))$ and which coincides with the spectral radius of $\mathcal L_{\xi }$. Further, there exists a unique strictly positive eigenfunction $h_{\xi }\in \mathcal {C}(\Sigma _A)$ satisfying $\mathcal L_{\xi } h_{\xi }=\gamma _{\xi } h_{\xi }$ and $\int h_{\xi }\mbox{d}\nu _{\xi }=1$. Define μ _ξ by dμ _ξ∕dν _ξ = h _ξ. This is the unique σ-invariant Gibbs measure for the potential function ξ.

Proposition A.3 and the relation $\gamma _{\xi }=\exp (P(\xi ))$ imply the following.

Proposition A.4

Let$\xi ,\eta \in \mathcal C(\Sigma _A)$be such that for some$n\in \mathbb N$the n-th Birkhoff sum S _n ξ of ξ is strictly positive on Σ _A . Then s↦γ _η+sξis continuous, strictly monotonically increasing, log-convex in$s\in \mathbb R$with lim_s→−∞ γ _η+sξ = 0 and satisfies lim_s→∞ γ _η+sξ = ∞. The unique$\delta \in \mathbb R$from PropositionA.3is the unique$\delta \in \mathbb R$for which γ _η−δξ = 1.

1.5 A.5 The Constants in Theorem 4.2

Using the notation from Sect. A.3 we can explicitly state the form of G(x) and G _x(t) occurring in the Renewal Theorem 4.2. For this, write ⌊t⌋ for the largest integer $k\in \mathbb Z$ satisfying k ≤ t, where $t\in \mathbb R$. Moreover, set {t}:= t −⌊t⌋∈ [0, 1). Notice, for $t\in \mathbb R$ positive, ⌊t⌋ is the integer part and {t} is the fractional part of t.

$$\displaystyle \begin{aligned} G(x) &= \frac{h_{\eta-\delta \xi}(x)}{\int \xi\mbox{d}\mu_{\eta-\delta \xi}}\int_{\Sigma_A} \chi(y)\int_{-\infty}^{\infty}\mathrm{e}^{-T\delta}g_y(T)\,\mbox{d}T\mbox{d}\nu_{\eta-\delta \xi}(y)\quad \text{and}\\ \widetilde{G}_x(t) &= \int_{\Sigma_A}\chi(y) \sum_{l=-\infty}^{\infty}\mathrm{e}^{-a l\delta} g_y\left(a l+a\left\{\tfrac{t+\psi(x)}{a}\right\}-\psi(y)\right) \mbox{d}\nu_{\eta-\delta\zeta}(y)\\ &\qquad \times \mathrm{e}^{-a\big{\{}\frac{t+\psi(x)}{a}\big{\}}\delta} \frac{a\mathrm{e}^{\delta\psi(x)}}{\int\zeta\mbox{d}\mu_{\eta-\delta\zeta}}\cdot h_{\eta-\delta\zeta}(x). \end{aligned} $$

B Appendix: Relation to the Probabilistic Renewal Theorems

The setting of Sect. 4 extends and unifies the setting of established renewal theorems. In brief: in the context of classical renewal theory for finitely supported measures (in particular of the key renewal theorem), η and ξ only depend on the first coordinate. When η and ξ only depend on the first two coordinates, we are in the setting of Markov renewal theory. If η is the constant zero-function and , where $\chi \in \mathcal F_{\alpha }(\Sigma _A)$ is non-negative, we are precisely in the setting of [28], where renewal theorems for counting measures in symbolic dynamics were developed, see Remark 4.3. The results of the infinite alphabet case obtained in [21] even yield the respective cases for general discrete measures.

In the following we expand upon the above and let $N\colon \Sigma _A\times \mathbb R\to \mathbb R$ denote the renewal function given in (4.2).

1.1 B.1 The Key Renewal Theorem for Finitely Supported Measures

The special case of Theorem 4.2 that N is independent of Σ_A gives the classical key renewal theorem for measures on [0, ∞) that are finitely supported:

N being independent of Σ_A can be achieved by the following assumptions. First, $\Sigma _A=\Sigma ^{\mathbb N}$ (i. e. full shift). Second, g _x = f is independent of $x\in \Sigma ^{\mathbb N}$ implying that equi d. R. i. of $\{t\mapsto \mathrm {e}^{-t\delta } \lvert g_x(t)\rvert \mid x\in \Sigma _A\}$ is equivalent to $z\colon \mathbb R\to \mathbb R$ with z(t):= e^−δt f(t) being absolutely d. R. i. Third, . Fourth and most importantly, ξ and η are constant on cylinder sets of length one. To emphasise local constancy, write s _u:= S _n ξ(u ₁⋯u _n ω) and $p_{u}: =\exp \left [S_n(\eta -\delta \xi )(u_1\cdots u_n\omega )\right ]$ for u = u ₁⋯u _n ∈ Σⁿ and $\omega =\omega _1\omega _2\cdots \in \Sigma ^{\mathbb N}$. Setting Z(t):= e^−δt N(t) we obtain that

$$\displaystyle \begin{aligned} Z(t)=\sum_{n=0}^{\infty}\sum_{\omega\in\Sigma^n}z(t-s_{\omega})p_{\omega} \quad \text{and}\quad Z(t) =\sum_{i=1}^M Z(t - s_i)p_i+ z(t), \end{aligned} $$

(B.1)

for $t\in \mathbb R$. Notice, the latter equation of (B.1) is the classical renewal equation (3.4). The assumption S _n ξ > 0 for some $n\in \mathbb N$ implies s _i > 0 for all i ∈ Σ. Thus, the distribution F which assigns mass p _i to s _i is concentrated on (0, ∞). On the other hand, any vector (s ₁, …, s _M) with s ₁, …, s _M > 0 determines a strictly positive function $\xi \in \mathcal F_{\alpha }(\Sigma ^{\mathbb N})$ via $\xi (\omega _1\omega _2\cdots ): = s_{\omega _1}$. Furthermore, in the setting of Theorem 4.2, (p ₁, …, p _M) is a probability vector with p _i ∈ (0, 1) since

$$\displaystyle \begin{aligned} 0 =P(\eta-\delta\xi) =\lim_{n\to\infty}n^{-1}\log\bigg{(}\sum_{i\in\Sigma}p_i\bigg{)}^n =\log\sum_{i\in\Sigma}p_i \end{aligned}$$

by Proposition A.3. Thus, F is a probability distribution. On the other hand, any probability vector (p ₁, …, p _M) with p ₁, …, p _M ∈ (0, 1) determines $\eta \in \mathcal F_{\alpha }(\Sigma ^{\mathbb N})$ via $\eta (\omega _1\omega _2\cdots ): =\log (p_{\omega _1}\mathrm {e}^{\delta s_{\omega _1}})$.

Consequently, Theorem 4.2 provides the asymptotic behaviour of Z under the assumptions that (p ₁, …, p _M) is a probability vector and that s ₁, …, s _M > 0. In order to present the asymptotic term in a common form, observe that $\mathcal L_{\eta -\delta \xi }\mathbf {1}=\mathbf {1}(x)$ for any $x\in \Sigma ^{\mathbb N}$, where . Thus,

$$\displaystyle \begin{aligned} h_{\eta-\delta\xi}=\mathbf{1} \qquad \text{and} \qquad \mu_{\eta-\delta\xi}([i])=\nu_{\eta-\delta\xi}([i])= p_i, \end{aligned}$$

where the last equality follows by considering the dual operator of $\mathcal L_{\eta -\delta \xi }$. If ξ is lattice then the range of ξ itself lies in a discrete subgroup of $\mathbb R$: If there exist $\zeta ,\psi \in \mathcal C(\Sigma ^{\mathbb N})$ with ξ − ζ = ψ − ψ ∘ σ and $\zeta (\Sigma ^{\mathbb N})\subset a\mathbb Z$ for some a > 0, then ξ and ζ need to coincide on $\{\omega \in \Sigma ^{\mathbb N}\mid \omega =\sigma \omega \}$. As every cylinder set of length one contains a periodic word of period one the claim follows. Hence, we can choose ζ = ξ and ψ to be the constant zero-function. We deduced the key renewal theorem, Theorem 3.4 for finitely supported measures on [0, ∞) and f ≥ 0. In exactly the same way [21, Thm. 3.1] yields the key renewal theorem for discrete measures.

1.2 B.2 Relation to Markov Renewal Theorems

Suppose that we are in the setting of Sect. 4.

If we assume that η and ξ are constant on cylinder sets of length two, then the point process with inter-arrival times W ₀, W ₁, … becomes a Markov random walk: To see this, define $\widetilde {\eta },\widetilde {\xi }\colon \Sigma _A^2\to \mathbb R$ by $\widetilde {\eta }(ij): =\eta (ij\omega )$ and $\widetilde {\xi }(ij): =\xi (ij\omega )$ for any ω ∈ Σ_A for which ijω ∈ Σ_A. Then

$$\displaystyle \begin{aligned} \mathbb P(X_1=i\mid X_0X_{-1}\cdots=x) = \mathrm{e}^{\eta(ix)} &= \mathrm{e}^{\widetilde{\eta}(ix_1)} =\mathbb P(X_1=i\mid X_0=x_1). \end{aligned} $$

Thus, $(X_n)_{n\in \mathbb Z}$ is a Markov chain. Further, $W_n=\xi (X_{n+1}X_nX_{n-1}\cdots ) =\widetilde {\xi }(X_{n+1}X_n)$ implies that the inter-arrival times W ₀, W ₁, … are Markov dependent on $(X_n)_{n\in \mathbb Z}$. Applying Theorem 4.2 to such Markov random walks gives the Markov renewal theorem presented in Theorem 3.9. In order to state its conclusions in the form of Theorem 3.9 we present several simplifications and conversions in the following. Set

and define $F: =(\widetilde {F}_{ij})_{i,j\in \Sigma }$ to be the matrix with entries . Then, F is irreducible if and only if A is irreducible. Moreover, $\widetilde {F}_{ij}$ is a distribution function of a discrete measure. Thus, ξ is lattice if and only if $\widetilde {F}_{ij}$ is lattice for all i, j. For $s\in \mathbb R$ and i, j ∈ Σ we have

$$\displaystyle \begin{aligned} B_{i,j}(s) &:=\int\mathrm{e}^{-s T}\widetilde{F}_{i,j}(\mbox{d}T) =\begin{cases} \exp(\widetilde{\eta}(ji)-s\widetilde{\xi}(ji))&:\ ji\in\Sigma_A^2\\ 0&:\ \text{otherwise}. \end{cases} \end{aligned} $$

Setting B(s):= (B _ij(s))_{i,j ∈ Σ} we see that the action of B(−s) on vectors coincides with the action of the Ruelle-Perron-Frobenius operator $\mathcal L_{\eta +s\xi }$ on functions $g\colon \Sigma _A\to \mathbb R$ which are constant on cylinder sets of length one. That is, setting $\widetilde {g}_i: = g(ix)$, for x ∈ Σ_A with ix ∈ Σ_A, gives

$$\displaystyle \begin{aligned} \mathcal L_{\eta+s\xi}g(ix) =\sum_{j\in\Sigma,\,ji\in\Sigma_A^2}\mathrm{e}^{\widetilde{\eta}(ji)+s\widetilde{\xi}(ji)}\widetilde{g}_j =\sum_{j\in\Sigma} B_{ij}(-s)\widetilde{g}_j =(B(-s)\widetilde{g})_i. \end{aligned}$$

By the Perron-Frobenius theorem for matrices there is a unique s for which B(s) has spectral radius one. By the above this value coincides with the unique s for which $\mathcal L_{\eta -s\xi }$ has spectral radius one, which we denoted by δ in Proposition A.4. Similarly, h _η−δξ is constant on cylinder sets of length one. Thus, setting h _i:= h _η−δξ(ix) for x ∈ Σ_A with ix ∈ Σ_A we obtain a vector (h _i)_{i ∈ Σ} with strictly positive entries which satisfies B(δ)h = h, since

$$\displaystyle \begin{aligned} (B(\delta)h)_i =\mathcal L_{\eta-\delta\xi}h_{\eta-\delta\xi}(ix) =h_{\eta-\delta\xi}(ix) =h_i. \end{aligned}$$

Moreover, the vector ν given by ν _i:= ν _η−δξ([i]) satisfies ν _i > 0 for all i ∈ Σ and νB(δ) = ν, since $\mathcal L^{*}_{\eta -\delta \xi }\nu _{\eta -\delta \xi }=\nu _{\eta -\delta \xi }$. By the Perron-Frobenius theorem h and ν are unique with these properties. Additionally assuming and that f _x only depends on the first letter of x ∈ Σ_A it follows that N(t, x) only depends on the first letter of x. Thus, for i ∈ Σ write N(t, i):= N(t, ix) with x ∈ Σ_A for which ix ∈ Σ_A. Now, the renewal equation becomes

$$\displaystyle \begin{aligned} N(t,i) &=\sum_{j\in\Sigma,\ ji\in\Sigma_A^2} N(t-\widetilde{\xi}(ji),j)\mathrm{e}^{\widetilde{\eta}(ji)} + f_i(t)\\ &=\sum_{j\in\Sigma} \int_{-\infty}^{\infty}N(t- u,j)\widetilde{F}_{i,j}(\mbox{d}u)+ f_i(t), \end{aligned} $$

(B.2)

for i ∈ Σ, where f _i(t):= f _ix(t) for x ∈ Σ_A with ix ∈ Σ_A, compare (3.8). Using the above in conjunction with the constants provided in Sect. A.5 thus yields Theorem 3.9.