Gerold Alsmeyer

Bastien Mallein

A SIMPLE METHOD TO FIND ALL SOLUTIONS TO THE FUNCTIONAL EQUATION OF THE SMOOTHING TRANSFORM

Keywords: stochastic fixed-point equation, distributional fixed point, smoothing transform, branching random walk, multiplicative martingales, Choquet-Denytype lemma, fractal random measure, disintegration, many-to-one lemma

Given a nonincreasing null sequence T = (Tj) j 1 of nonnegative random variables satisfying some classical integrability assumptions and E( j T α j ) = 1 for some α > 0, we characterize the solutions of the well-known functional equation

related to the so-called smoothing transform and its min-type variant.

In order to do so within the class of nonnegative and nonincreasing functions, we provide a new three-step method whose merits are that (1) it simplifies earlier approaches in some relevant aspects, (2) it works under weaker, close to optimal conditions in the so-called boundary case when E j 1 T α j log Tj = 0, (3) it can be expected to work as well in more general setups like random environment.

At the end of this article, we also give a one-to-one correspondence between those solutions that are Laplace transforms and thus correspond to the fixed points of the smoothing transform and certain fractal random measures. The latter are defined on the boundary of a weighted tree related to an associated branching random walk.

1. Introduction. Given a nonincreasing null sequence T = (T j ) j 1 of nonnegative random variables, the mapping f → E j 1 f (tT j ) for suitable functions f : R → R with R = [0, ∞) is called the smoothing transform and any f satisfying

f (t) = E j 1 f (tT j )
a fixed point of this mapping. The problem of identifying all fixed points within certain function classes, here Laplace transforms of probability measures on R or, more generally, survival functions of nonnegative random variables, has been dealt with in a host of articles such as [START_REF] Durrett | Fixed points of the smoothing transformation[END_REF][START_REF] Liu | Fixed points of a generalized smoothing transformation and applications to the branching random walk[END_REF][START_REF]Fixed points of the smoothing transform: the boundary case[END_REF], with most general results obtained in [START_REF] Alsmeyer | The functional equation of the smoothing transform[END_REF]. The last reference should also be consulted for a more detailed account of the earlier literature and for further background information.

The existence of fixed points of the smoothing transform has been studied mostly under the following standard conditions which are also assumed throughout this article: First, (2)

E j 1 1 {T j >0} > 1,
which ensures that the product in (1) remains nonempty with positive probability upon iterating the fixed point equation; second, the existence of α > 0 such that (3) E We mention that nonnegative solutions to [START_REF] Biggins | Measure change in multitype branching[END_REF] may still exist if (3) for some α > 0 is weakened to (5) E The aim of this article is to introduce a new and simple method that provides the characterization of all fixed points of the smoothing transform within the framework just given and some extra integrability conditions. Not working under most general conditions as in [START_REF] Alsmeyer | The functional equation of the smoothing transform[END_REF] allows us to simplify and streamline the presentation of our method while, on the other hand, still being able to treat the so-called boundary case (see [START_REF] Kyprianou | Martingale convergence and the stopped branching random walk[END_REF]) under close to optimal conditions and to thus improve related earlier results in [START_REF]Fixed points of the smoothing transform: the boundary case[END_REF][START_REF] Alsmeyer | The functional equation of the smoothing transform[END_REF].

If f is the Laplace transform of a probability law ν on R , then it solves Eq. ( 1) iff ν is a distributional fixed point of the (homogeneous) smoothing transform S which maps ν to the law of the random variable j 1 T j X j , where X, X 1 , X 2 , . . . denote i.i.d. random variables with common law ν and independent of T . Hence, Eq. ( 1) corresponds to S(ν) = ν or, equivalently, [START_REF] Biggins | Measure change in multitype branching[END_REF])

X d = j 1
T j X j where d = means equality in distribution.

In the case when f is the (left continuous) survival function of a probability distribution ν on R , viz. f (t) = ν([t, ∞)) for t 0, the fixed-point property [START_REF] Aïdékon | Convergence in law of the minimum of a branching random walk[END_REF] corresponds to the distributional fixed-point equation [START_REF]Fixed points of the smoothing transform: the boundary case[END_REF] X d = inf{X j /T j : j 1 and T j > 0} with X, X 1 , X 2 , . . . as before. Here the infimum over the empty set is defined to be ∞.

As in [START_REF] Alsmeyer | The functional equation of the smoothing transform[END_REF], let S(M) denote the set of solutions to Eq. ( 1) within the class M = {f : R → [0, 1] : f is nonincreasing and left continuous, f (0) = f (0+) = 1 and 0 < f (t) < 1 for some t > 0} which comprises all survival functions on R as well as its subclass L of Laplace transforms of probability measures on R , ruling out only the trivial solutions f ≡ 1 and f = 1 {0} + q 1 R> , where q denotes the extinction probability of the associated branching random walk (BRW) described below. Note that the last fact entails S(L) ⊂ S(M). In order to determine S(M) (and thus S(L)), which has already been done in [START_REF] Alsmeyer | The functional equation of the smoothing transform[END_REF], we provide here a new approach that works under relaxed conditions on the random sequence T and also considerably simplifies some of the key arguments used in [START_REF] Alsmeyer | The functional equation of the smoothing transform[END_REF]. This novel approach consists of three steps that will be outlined further below, after the introduction of some necessary notation, further background information and the most important assumptions.

It is well-known that the fixed points of the smoothing transform satisfying [START_REF] Alsmeyer | The functional equation of the smoothing transform[END_REF] are intimately related to the essentially unique fixed-point of the modified smoothing transform

(8) X d = j 1 T α j Xj ,
where the Xj are i.i.d. copies of X (see also Remark 1.3 below). Here we work under conditions ensuring that X can be obtained as the limit of a martingale of an associated BRW that we describe next. Let V = n 0 N n be the Ulam-Harris tree of finite integer words, with the convention that N 0 = {∅} equals the set containing the empty word (and root of the tree).

As common, we use v 1 . . . v n as shorthand for v = (v 1 , . . . , v n ), |v| = n for its length, and uv for the concatenation of two vertices u, v ∈ V. The restriction of v to its first j coordinates, thus its ancestor at level j, is denoted v(j), thus v(j) = v 1 . . . v j . We set ∂V = N N , which represents the boundary of the tree V.

Now let (T v j ) j 1 be i.i.d. copies of T for any v ∈ V and define the multiplicative BRW (also called weighted branching process) as the random map

L : V → R , v → L(v) := |v| j=1 T v(j-1) v j .
Assumption (2) entails that L forms a supercritical BRW, thus with positive probability, for any n ∈ N there exists a vertex v ∈ V n := {u : |u| = n} such that L(v) > 0. This event is called the survival set of the BRW. Thinking of T v j as a weight attached to the edge connecting vertex v with its child vj, we see that L(v) equals the total weight of the unique shortest path from the root ∅ (with L(∅) := 1) to v obtained by multiplying the edge weights along this path. The natural filtration of the BRW, reflecting its genealogical structure, is defined by

F n = σ L(v), |v| n , n ∈ N 0 .
There is a deep and meaningful relationship between the fixed points of the smoothing transform and the BRW just introduced. This will be further explained in Section 6.

A second fundamental assumption for the existence of nontrivial solutions to (1), though not necessary as shown in [START_REF] Liu | Fixed points of a generalized smoothing transformation and applications to the branching random walk[END_REF] and already mentioned, is the existence of a minimal positive α, called characteristic exponent of T in [START_REF] Alsmeyer | The functional equation of the smoothing transform[END_REF], such that (3) holds. Then these solutions can be expressed in terms of an associated martingale limit. Namely, by the branching property of the BRW, the process [START_REF] Choquet | Sur l'équation de convolution µ = µ * σ[END_REF] W n := |v|=n L(v) α , n 0 constitutes a nonnegative martingale. It was shown by Biggins [START_REF] Biggins | Martingale convergence in the branching random walk[END_REF] (see also [START_REF] Lyons | A simple path to Biggins' martingale convergence for branching ranwalk, Classical and modern branching processes[END_REF] for a simpler proof of his result) that W n converges a.s. and in L 1 to a nondegenerate limit W provided that, additionally,

E j 1
T α j log T j < 0 [START_REF] Doney | The Martin boundary and ratio limit theorems for killed random walks[END_REF] and

E (W 1 log W 1 ) < ∞ (11)
hold. Alsmeyer and Iksanov [START_REF] Alsmeyer | A log-type moment result for perpetuities and its application to martingales in supercritical branching random walks[END_REF] further proved that these conditions are indeed necessary and sufficient whenever E j 1 T α j log T j is well-defined. The law of W forms the unique (up to scaling) solution to the SFPE (8).

Remark 1.1. Under more general conditions, for instance, when replacing (3) with (5), the a.s. limit of the martingale (W n ) n 0 may be 0, but yet a regularly varying sequence (a n ) n 0 , called Heyde-Seneta norming, exists such that a n W n converges a.s. to a non-degenerate solution of (8).

Condition [START_REF] Doney | The Martin boundary and ratio limit theorems for killed random walks[END_REF] is obviously more restrictive than Condition (4), for it requires E( j 1 T α j log T j ) to be strictly negative. We call this situation the regular case, as opposed to the more difficult boundary case, where this expectation is zero and which will be discussed further below. Assuming [START_REF] Doney | The Martin boundary and ratio limit theorems for killed random walks[END_REF] and [START_REF] Durrett | Fixed points of the smoothing transformation[END_REF] (naturally besides (2) and ( 3)) allows the construction of a natural solution to the SFPE. Moreover, we will see that under one more integrability condition, namely [START_REF] Gut | Stopped Random Walks[END_REF] E

j 1 T α j log T j > -∞,
the set S(M), and thus all fixed points of Eqs. ( 6) and [START_REF]Fixed points of the smoothing transform: the boundary case[END_REF], can be determined quite easily. The structure of the fixed points depends on the lattice-type of T . As in [START_REF] Alsmeyer | The functional equation of the smoothing transform[END_REF], T is called geometric with span r or r-geometric if r > 1 is the maximal number such that (13) P (T j ∈ {r n : n ∈ Z} for all j 1) = 1, and nongeometric if no such r exists. A function h : R → R > is called multiplicatively r-periodic if h(rt) = h(t) for all t 0. Given r > 1, let H r denote the set of all such functions such that t → h(t)t α is nondecreasing for α satisfying [START_REF] Alsmeyer | The functional equation of the smoothing transform[END_REF]. Let also H 1 be the the set of positive constant functions on R . In order to be able to describe S(L), we put P 1 = H 1 and denote by P r for r > 1 the set of h ∈ H r such that t α h(t) has a completely monotone derivative. When α = 1, the latter requirements force h to be constant, thus P r = P 1 . These classes were first introduced in [START_REF] Durrett | Fixed points of the smoothing transformation[END_REF].

Theorem 1.2. Let T satisfy (2), ( 3), [START_REF] Doney | The Martin boundary and ratio limit theorems for killed random walks[END_REF], [START_REF] Durrett | Fixed points of the smoothing transformation[END_REF], [START_REF] Gut | Stopped Random Walks[END_REF] and r 1 denote its span. Then the elements of S(M) are the functions

f (t) = E(exp(-h(t)t α W )), t 0
with left continuous h ∈ H r and W = lim n→∞ W n a.s. Moreover, S(L) is nonempty only if 0 < α 1 in which case it consists of all f ∈ S(M) with h ∈ P r .

This result was derived in [START_REF] Alsmeyer | The functional equation of the smoothing transform[END_REF] by first showing the slow variation of the function (1 -Ee -tW )/t at t = 0 (Thm. 3.1) and then, given any f ∈ S(M), the same property for (1 -f (t))/t α h(t) for a suitable h ∈ H r (Thms. 3.2 and 3.3). Our method of proof does not need these intermediate results, but rather replaces them by a simpler boundedness argument.

Remark 1.3. If α = 1, then Eq. ( 6) becomes Eq. ( 8), and the only fixed point, modulo positive multiplicative constants, is given by the limit W of the Biggins martingale defined in [START_REF] Choquet | Sur l'équation de convolution µ = µ * σ[END_REF]. This fixed point is endogenous in the sense of Aldous and Bandyopadhyay [START_REF] Aldous | A survey of max-type recursive distributional equations[END_REF] which means that W can be constructed as a measurable function of the BRW or, equivalently, that it is F ∞ -measurable, where F ∞ := σ(F n , n 0). If α < 1, there are no endogenous fixed points.

Remark 1.4. Although working here under conditions that ensure the convergence of the additive martingale, our method can be adapted to the case of Heyde-Seneta-type norming mentioned in Rem. 1.1. Then one has to replace the function t α by a suitable regularly varying function of index α in the proof of Theorem 1.2.

Nontrivial solutions to Eq. (1) also exist in the boundary case when [START_REF] Kyprianou | Martingale convergence and the stopped branching random walk[END_REF] E j 1

T α j log T j = 0, holds in the place of [START_REF] Doney | The Martin boundary and ratio limit theorems for killed random walks[END_REF]. In this case, the martingale limit W is a.s. zero. However, assuming [START_REF] Kyprianou | Martingale convergence and the stopped branching random walk[END_REF], the process

(15) Z n = |v|=n L(v) α (-log L(v)), n 0
is also a martingale, known as the derivative martingale. Quite general, but nonoptimal conditions for the almost sure convergence of Z n to a nonnegative and nondegenerate limit were provided by Biggins and Kyprianou [START_REF] Biggins | Measure change in multitype branching[END_REF].

Later Aïdékon [START_REF] Aïdékon | Convergence in law of the minimum of a branching random walk[END_REF] determined necessary conditions, that Chen [START_REF] Chen | A necessary and sufficient condition for the nontrivial limit of the derivative martingale in a branching random walk[END_REF] found sufficient. More precisely, if

(16) E j 1 T α j log 2 T j ∈ (0, ∞), EW 1 log 2 W 1 + E X log X < ∞,
where

X := j 1 T α j log + T j , then (17)
Z := lim n→∞ Z n a.s.
exists and is almost surely positive on the survival set of the BRW.

Biggins and Kyprianou [START_REF]Fixed points of the smoothing transform: the boundary case[END_REF] and Alsmeyer et al. [START_REF] Alsmeyer | The functional equation of the smoothing transform[END_REF] proved analogs of Theorem 1.2 in the boundary case, where the limit Z of the derivative martingale replaces the limit W of the additive martingale. Their proofs required some exponential integrability condition, see (A) in [START_REF]Fixed points of the smoothing transform: the boundary case[END_REF] and (A4b) in [START_REF] Alsmeyer | The functional equation of the smoothing transform[END_REF]. Using the same techniques as in the proof of Theorem 1.2, we can extend their results without any additional assumption other than those ensuring the nondegeneracy of the derivative martingale. This can be seen as a major advantage of our approach.

Theorem 1.5. Let T satisfy (2), ( 3), ( 14) and [START_REF] Lyons | A simple path to Biggins' martingale convergence for branching ranwalk, Classical and modern branching processes[END_REF]. Then all assertions of Theorem 1.2 remain valid when replacing W with Z in the definition of the solutions f . Remark 1.6. The following example shows that one can easily provide sequences (T n ) n 1 to which Theorem 1.5 applies but which are not covered by the corresponding result in [START_REF] Alsmeyer | The functional equation of the smoothing transform[END_REF] because they fail to satisfy the condition (A4b) in that article. Define T j = X(j/ log 3 (j + 1)) 1/α , j 1, and let X be any nonnegative random variable such that (3), ( 14) and ( 16) hold. Then we obviously have E( T β j ) = ∞ for all β < α.

Although the proofs of Theorems 1.2 and 1.5 need different estimates, they follow the same three-step scheme that we now outline (in the regular case) and believe to work also in more general situations. Given any solution f ∈ S(M), it is easily checked that, for each t 0,

M n (t) := |v|=n f (tL(v))
, n 0 constitutes a positive bounded product martingale whose limit

M (t) := lim n→∞ |v|=n f (tL(v))
exists a.s. and in L 1 . These martingales are called in [START_REF] Alsmeyer | The functional equation of the smoothing transform[END_REF] the disintegration of the fixed point f .

1. Tameness: Using the convergence of the disintegration along a sequence of stopping lines (see Section 2), the first step is to show that any nondegenerate fixed point f must satisfy

lim sup t→0 -log f (t) t α < ∞.

Harmonic analysis:

This property enables us to derive that -log M (t) is an integrable random variable with

F (t) := E(-log M (t)) = E |v|=1 F (tL(v)) Ct α
for all t > 0 and suitable C ∈ (0, ∞). The shown equality can be translated as follows: the function G(x) := e αx F (e -x ) defines a bounded harmonic function of a certain random walk associated with the BRW (see Section 2). By a Choquet-Deny-type lemma, we then deduce that G is constant on the subgroup generated by the walk. 3. Identification of M (t): It follows by the previous step that F is of the form F (t) = h(t)t α for some h ∈ H r , r the span of T . To find the value of M (t), we finally observe that log

M (t) = lim n→∞ E (log M (t)|F n ) = -lim n→∞ |v|=n F (tL(v)) = -h(t)t α W
and thus complete the proof of the main theorem as f (t) = Ee log M (t) .

In the boundary case, this three-step method requires the identification of a harmonic function of at most linear growth for a killed random walk. This is done in Proposition 4.1, where we prove that there is only one such function modulo scalars, namely the renewal function of a random walk. This result, which may also be of independent interest, forms a generalization of a result by Spitzer [START_REF] Spitzer | Principles of random walks[END_REF]Thm. E3,p. 332] and shows that the Martin boundary of a centered random walk with finite variance and conditioned to stay positive reduces to a single point.

We devote the next section to some classical BRW tools and then prove Theorem 1.2 in Section 3. Before turning to the more difficult proof of Theorem 1.5 in Section 5, we need to show in Section 4 a Choquet-Deny-type result asserting that any right-continuous and at most linearly growing harmonic function of a centered random walk killed upon entering R equals the Tanaka solution (see ( 34)) up to a constant, or a periodic function in the lattice case. Finally, in Section 6 we briefly describe a one-to-one connection between the solutions of ( 6) and certain fractal random measures on the boundary of the weighted tree related to the BRW.

Preliminary results for the classical branching random walk.

This section collects some well-known tools in the study of BRW's that will be needed later on, namely the many-to-one lemma and some facts about stopping lines.

The many-to-one lemma is a widely known result, which can be traced back at least to Peyrière [START_REF] Peyrière | Turbulence et dimension de Hausdorff[END_REF] and Kahane and Peyrière [START_REF] Kahane | Sur certaines martingales de Benoit Mandelbrot[END_REF]. It links additive moments of the BRW to random walk estimates. Consider a zero-delayed random walk (S n ) n 0 with increment distribution specified as [START_REF] Spitzer | Principles of random walks[END_REF] Eg(S 1 ) = E j 1

T α j g(-log T j ) .

for nonnegative measurable g.

Lemma 2.1 (Many-to-one lemma). For all n 0 and all nonnegative measurable functions g, we have

Eg(S 1 , . . . , S n ) = E |v|=n L(v) α g(-log L(v(j)), j n) .
The result can be thought of as a first step towards the spinal decomposition due to Lyons [START_REF] Lyons | A simple path to Biggins' martingale convergence for branching ranwalk, Classical and modern branching processes[END_REF] that describes the law of the BRW when size-biased by the martingale (W n ) n 0 as a BRW with a designated path, called spine, along which offspring particles have displacement law defined by [START_REF] Spitzer | Principles of random walks[END_REF].

As moments of functionals of the tL(u) will often be considered hereafter, it is convenient to define P t as the law of the above random walk (S n ) n 0 when its delay equals S 0 = -log t. In other words, the random walk is G. ALSMEYER AND B. MALLEIN starting from -log t under P t , and its laws under P and P 1 coincide. With this notation, Lemma 2.1 can be rewritten as [START_REF] Tanaka | Time reversal of random walks in one-dimension[END_REF] E |v|=n L(v) α g(tL(v(j)), j n) = E t g(e -S 1 , . . . , e -Sn ).

We now recall some facts about stopping lines, in fact so-called very simple stopping lines, a name coined by Biggins and Kyprianou [6, p. 557]. A line is a set L ⊂ V satisfying the two following assumptions:

∀u, v ∈ L : u v ⇒ u = v, ∀v ∈ ∂V : v(n) ∈ L for some n ∈ N. ( 20
)
In other words, a line is a minimal set separating the root ∅ from the boundary ∂V. In BRW's, stopping lines take the role of stopping times for random walks. In particular, a very simple stopping line is a random line such that for all v ∈ V,

(21) {v ∈ L} ∈ σ(L(v(j)), j |v|).
In other words, whether or not a vertex v belongs to the line depends only on the weights of the tree along the unique path from the root to v.

In this article, only the following first passage lines will be of interest. For all a > 0, we set (22) Υ a := {v ∈ V : L(v(j)) a for j < |v| and L(v) < a} .

Note that lim n→∞ sup |v|=n L(v) = 0 a.s. under the assumptions of our two theorems. Therefore, Υ a is a well-defined very simple stopping line for any a > 0 and consists of all particles entering the interval [0, a] for the first time. Biggins and Kyprianou [START_REF] Biggins | Measure change in multitype branching[END_REF] proved that a theorem similar to the optional stopping theorem holds for the additive martingale of the BRW. We state and use here a simplified version of their result. Further defining

G a := σ (L(v(j)), j |v|, v ∈ Υ a ) , (23)
note that (G e -t ) t 0 forms a filtration for the BRW. The following result is a version of the many-to-one lemma along the stopping lines Υ a and can also be found for example in [START_REF] Kyprianou | Martingale convergence and the stopped branching random walk[END_REF]. We give a proof here for sake of completeness. Lemma 2.2. For all a ∈ (0, 1] and all measurable nonnegative functions g, we have

E v∈Υa L(v) α g(L(v(j)), j |v|) = Eg e -S j , j σ(-log a) ,
where σ(b) := inf{n 0 : S n > b} and (S n ) n 0 equals the random walk with increment law defined by [START_REF] Spitzer | Principles of random walks[END_REF].

Proof. The result is obtained by a decomposing the cutting line generation-wise and the applying the many-to-one lemma, viz.

E v∈Υa L(v) α g(L(v(j)), j |v|) = n 0 E |v|=n 1 {v∈Υa} L(v) α g(L(v(j)), j n) = n 0
Eg(e -S 1 , . . . , e -Sn )1 {σ(-log a)=n} = Eg e -S j , j σ(-log a) .

This completes the proof.

3. The regular case: proof of Theorem 1.2. Given any solution f ∈ S(M), recall that, for each t 0, the disintegration

M n (t) := |v|=n f (tL(v))
, n 0 constitutes a positive bounded product martingale whose limit M (t) exists a.s. and in L 1 . We start by proving the tameness of any solution f ∈ S(M). Lemma 3.1. Under the assumptions of Theorem 1.2, any f ∈ S(M) satisfies

(24) sup 0<t 1 -log f (t) t α C for some 0 < C < ∞.
Proof. Assuming lim sup t→0

-log f (t) t α
= ∞, we will derive that for all t > 0 we have f (t) P(W = 0). Since P(W = 0) < 1, this contradicts the property f (0+) = 1.

By the stated assumption, there exists a decreasing null sequence (t n ) n 1 such that

-log f (t n ) t α n n 2 for all n 1.
Setting c n := n 1/α and observing that t → -log f (t) and t → t α are both nonnegative and nondecreasing functions, we find that

-log f (s) s α -log f (t n ) (c n t n ) α n for all s ∈ [t n , c n t n ].
Therefore, we can define decreasing null sequences (ϑ n ) n 1 and (ρ n

) n 1 such that (25) -log f (s) s α n for all s ∈ [ρ n ϑ n , ϑ n ].
We will now bound the conditional mean of M (t) given G ϑn/t , where (G ϑn/t ) n 1 is the first passage filtration defined in (23). By dominated convergence,

E M (t) G ϑn/t = lim m→∞ E M m (t) G ϑn/t ,
and the branching property of the BRW implies

E M m (t) G ϑn/t = exp v∈Υ ϑn/t |v| m log f (tL(v)) + |v|=m tL * (v) ϑn f (tL(v)) ,
where L * (v) := min 0 k |v| L(v(k)). Hence, using sup v∈Υ ϑn/t |v| < ∞ a.s., we infer upon letting m → ∞

E M (t) G ϑn/t = exp   v∈Υ ϑn/t log f (tL(v))   exp -n v∈Υ ϑn/t (tL(v)) α 1 {tL(v) ρnϑn} , (26)
where we have bounded -log f (tL(v)) by 0 if tL(v) ∈ [ρ n ϑ n , ϑ n ], and with the help of (25) otherwise.

On the other hand, by another use of the branching property of the BRW, we obtain, for all a > 0 and m ∈ N,

E (W m |G a ) = v∈Υa |v| m L(v) α + |v|=m L * (u)>a L(v) α a.s. and thus E (W |G a ) = v∈Υa L(v) α a.s. as m → ∞. Now let a → 0 and use F ∞ = a>0 G a to infer (27) lim a→0 v∈Υa L(v) α = W a.s.
Next, Lemma 2.2 provides us with

E   v∈Υ ϑn/t (tL(v)) α 1 {tL(v)<ρnϑn}   = t α P S σ(-log(ϑn/t)) > -log ρ n ϑ n t ,
where σ(a) = inf{n 0 : S n > a} should be recalled. Use [START_REF] Doney | The Martin boundary and ratio limit theorems for killed random walks[END_REF] and [START_REF] Gut | Stopped Random Walks[END_REF] to infer

ES 1 = -E j 1 T α j log T j ∈ (0, ∞).
As a consequence, the family {S σ(-log s) + log s : 0 < s 1} of overshoots of the random walk is tight (see e.g. Gut Finally using that E(M (t)|G ϑn/t ) n 0 forms a bounded martingale, we infer M (t) 1 {W =0} a.s. for all t > 0 and thereupon the announced contradiction f (t) = EM (t) P(W = 0) for all t > 0.

Remark 3.2. In the above proof, Assumption ( 12) is only needed for the conclusion that

v∈Υ ϑn/t (tL(v)) α 1 {tL(v) ρnϑn}
converges to a positive random variable with positive probability. We suspect that it can be replaced with a weaker assumption while keeping the assertions of Theorem 1.2.

With the help of Lemma 3.1, we can now identify the function defined by ( 28)

F (t) := E (-log M (t))
for a given f ∈ S(M). Doing so, we make use of the subsequent Choquet-Deny lemma, for convenience reformulated here in our setting, which identifies all bounded harmonic functions of the random walk.

Lemma 3.3. Let G : R → R be a right-continuous bounded function satisfying

(29) G(x) = EG(x + S 1 )
for all x ∈ R. Then G d-periodic if (S n ) n 0 is d-arithmetic, and it is constant everywhere if (S n ) n 0 is nonarithmetic.

Proof. Note that, possibly upon adding a constant, we can assume G to be nonnegative. We denote by ν the law of S 1 , and we let λ denote the measure with density G with respect to Lebesgue measure. Then (29) can be rewritten as λ = λ * ν.

The Choquet-Deny lemma [START_REF] Choquet | Sur l'équation de convolution µ = µ * σ[END_REF] entails that, for each a in the support of ν, the measure λ is a-periodic. In particular, G(x + a) = G(x) for Lebesgue almost all x ∈ R. Thus using the right-continuity of G, this equation in fact holds for all x ∈ R and a in the support of ν. The set of periods of a right-continuous function being a closed group, we deduce that G is d-periodic if (S n ) n 0 is d-arithmetic for some d > 0, and that G is constant otherwise.

We now turn to the identification of the function F .

Lemma 3.4. Given the assumptions of Theorem 1.2, let f ∈ S(M) with disintegration (M n (t)) n 0 . Then there exists a function h ∈ H r , r the span of T , such that (30)

F (t) = h(t)t α
for all t 0.

Proof. Since M (t) = lim n→∞ M n (t) a.s., we see that

lim n→∞ |v|=n -log f (tL(v)) = -log M (t) a.s.
Moreover, by Lemma 3.1, there exists C > 0 such that

|v|=n -log f (tL(u)) Ct α W n .
for all n so large that sup |v|=n L(v) 1. Hence, 0 -log M (t) Ct α W follows upon letting n → ∞. Since EW = 1 under the assumptions of Theorem 1.2, we infer

(31) 0 F (t) Ct α ,
where F is the function defined in (28) (for the given f ). One can readily check that F is nondecreasing and left continuous.

Put G(x) := e -αx F (e -x ) and use the branching property of the BRW to obtain, for any m ∈ N, (32)

M (t) = |u|=m M (u) (tL(u)),
where M (u) (s) = lim n→∞ |v|=n f (s L(uv) L(u) ) are i.i.d. copies of M and independent of F m for u ∈ V m . Equality in law is already enough to infer that

G(x) = e -αx E log M (e -x ) = e -αx E log |v|=1 M (v) (e -x L(v)) = E |v|=1 L(u) α G(x -log L(v)) = EG(x + S 1 ),
by the many-to-one lemma. Therefore, by (31), G is a bounded, nonnegative and right continuous harmonic function of the random walk (S n ) n 0 , and the latter is log r-arithmetic. It follows by Lemma 3.3, that G is log r-periodic, thus G(x + log r) = G(x) for all x ∈ R. Equivalently, (30) holds with h ∈ H r given by h(t) := G(log t) for t > 0.

Remark 3.5. The previous proof has also shown that, if [START_REF] Doney | The Martin boundary and ratio limit theorems for killed random walks[END_REF] and [START_REF] Durrett | Fixed points of the smoothing transformation[END_REF] fail and thus W n → 0 a.s., any solution f ∈ S(M) satisfying (24) must be trivial, i.e. f (t) = 1 for all t 0. In particular, no nontrivial solution f can satisfy (24) in the boundary case.

We are now ready to provide the proof of Theorem 1.2.

Proof of Theorem 1.2. Given any f ∈ S(M), we denote by M (t) its disintegration and put F (t) = E(-log M (t)). It folows from (32) that

E (-log M (t)|F n ) = |v|=n F (tL(v)) a.s.
for all n ∈ N. By letting → ∞ and an appeal to Lemma 3.4, we obtain

-log M (t) = lim n→∞ |v|=n F (tL(v)) = h(t)t α lim n→∞ W n = h(t)t α W a.s.
for some h ∈ H r , r the span of T , and then f (t) = EM (t) = Ee -h(t)t α W . If f ∈ S(L), we even infer h ∈ P r because f is a Laplace transform.

4. Harmonic functions of random walks on the positive halfline. We now turn to the proof of Theorem 1.5 and thus work under assumptions [START_REF] Kyprianou | Martingale convergence and the stopped branching random walk[END_REF] and [START_REF] Lyons | A simple path to Biggins' martingale convergence for branching ranwalk, Classical and modern branching processes[END_REF]. In this case, instead of using the Choquet-Deny lemma, we need to identify harmonic functions of a centered random walk with finite variance, killed upon entering the nonpositive halfline. This is the content of the present section.

We recall that (S n ) n 0 is the random walk associated with the BRW by the many-to-one lemma. Since ES 1 = 0 by [START_REF] Kyprianou | Martingale convergence and the stopped branching random walk[END_REF] and 0 < ES 2 1 < ∞ by ( 16), (S n ) n 0 is a centered random walk with finite variance. A harmonic function G of the walk, killed at the first time it leaves the positive halfline R > , is a function such that G(x) = 0 for x 0 and (33)

G(x) = EG(x + S 1 )1 {x+S 1 >0} = E x G(S 1 )1 {S 1 >0} .
for all x > 0.

Let us define τ (a) := inf{n 0 : S n a}, τ := τ (0), and recall that σ(a) := inf{n 0 : S n > a}, σ := σ(0), for a ∈ R. Further, put R a := S σ(a) -a, and let (τ n ) n 1 and (σ n ) n 1 denote the sequences of weakly descending and strictly ascending ladder epochs, respectively. Note that P x (τ (a) ∈ •) = P 0 (τ (a -x) ∈ •) for a 0 and x 0 and recall that P = P 0 . without assuming finite variance, Tanaka [START_REF] Tanaka | Time reversal of random walks in one-dimension[END_REF] obtained a solution of (33) defined by ( 34)

H(x) := E x σ-1 k=0 1 (0,x] (S k ) , x > 0.
By the duality lemma, it also equals the renewal function of the weakly descending ladder heights S * n = S τn , n 1, of the given walk (up to a reflection), viz.

H(x) = n 0 P(S * n > -x) = n 0 P(τ * (-x) > n) = Eτ * (-x)
for x > 0, where τ * (a) := inf{n 0 :

S * n a}. Now, if E|S * 1 | < ∞, a sufficient condition being ES 2
1 < ∞, then Wald's identity further ensures

H(x) = ES * τ * (-x) ES * 1 , x < 0,
and by finally observing S * τ * (-x) = S τ (-x) , we arrive at

(35) H(x) = ES τ (-x) ES * 1 = E x S τ -x ES * 1 .
In other words, if 0 < ES 2 1 < ∞, then H(x) and H(x) := x -E x S τ differ only by a multiplicative positive constant.

An interesting aspect of this last observation is that, unlike H, the function H is very easily shown to be harmonic. Namely, as P(τ (-x) 1) = 1 for x > 0 and ES 1 = 0, we infer by a standard renewal argument

H(x) = -ES τ (-x) = R> -ES τ (-y) P x (S 1 ∈ dy) = E x H(S 1 )
for all x > 0 as required.

A well-known result from renewal theory asserts that

E|S * τ * (-y) + y| y y→∞ ---→ 0 if ES * 1 < ∞,
G(x) = κ(x)H(x) for all x ∈ R.
For centered random walks on the integer lattice Z, where (33) must only hold for x ∈ Z, it was already shown by Spitzer [18, Thm. E3, p. 332] that there is only one positive solution to (33) up to positive multiples (even without additional moment assumptions). More recent work by Doney [10, Thm. 1] also considers the case when the Z-valued random walk has nonzero drift.

Before proving our result, we provide some useful estimates and begin with an extension of the harmonic property of G at random times.

G(x) = E x G(S σ(y) )1 {σ(y)<τ }
holds for all for all 0 < x < y.

Proof. By (33), (G(S τ ∧n ) n 0 is a martingale. Hence, the optional sampling theorem implies

G(x) = E x G(S σ(y)∧τ ∧n ) = E x G(S σ(y) 1 {σ(y)<τ ∧n} + E x G(S n )1 {n<σ(y)∧τ }
for all 0 < x < y and n ∈ N. As n → ∞, we have

E x G(S σ(y) 1 {σ(y)<τ ∧n} → E x G(S σ(y) 1 {σ(y)<τ }
by the monotone convergence theorem, and

E x G(S n )1 {n<σ(y)∧τ } C(y + 1)P x (n < σ(y) ∧ τ ) → 0.
This completes the proof.

Next are some asymptotic estimates involving the level a overshoot R a = S σ(a) -a of the random walk killed upon entering the positive halfline. As a by-product, another formula for H is obtained. where

U a (dx) = n 0 P(S n ∈ dx, 0 < S k a for k = 0, . . . , n) = n 0 P(S n ∈ dx, 0 < S n -S n-k a for k = 0, . . . , n) = n 0 k 0 P σ k = n, S σ k ∈ dx, S σ k a + min 0 j σ k S j = k 0 P S σ k ∈ dx, S σ k a + min 0 j σ k S j k 0 P (S σ k ∈ dx ∩ (0, a]) . Since ES 2 1 < ∞ ensures ES σ 1 < ∞, we infer that U a ([0, a]) k P(S σ k a) Ca
Ψ(x) E x H(S σ(a) ) H(x) 1 {σ(a)<τ <∞} = P ↑ x (σ(a) < ∞) = 1,
where P ↑ x denotes the harmonic transform with respect to H. Using this, we further obtain

E x H(S σ(a/3) )Ψ(S σ(a/3) )1 {σ(a/3)<τ <∞} E x H(S σ(a/3) )1 {S σ(a/3) >2a/3} + E x H(S σ(a/3) )1 {σ(a/3)<τ <∞, S σ(a/3) 2a/3} sup a/3 y 2a/3 Ψ(y). (41)
The first of the two terms on the right-hand side of this inequality converges to 0 as a → ∞ by Step 1. As for the second one, we use that H is harmonic and of linear growth together with Lemma 4.2 (which also holds for H in the place of G) to bound it by

E x H(S σ(a/3) )1 {σ(a/3)<τ <∞} sup a/3 y 2a/3 Ψ(y) = H(x) sup a/3 y 2a/3 Ψ(y).
Furthermore, sup a/3 y 2a/3

Ψ(y) H(2a) H(a/3) sup a/3 y 2a/3 P y (σ(a) < τ < ∞, b < R a a) H(2a) H(a/3) sup 0 y a P(R a-y > b) = (6 + o(1)) sup y 0 P(R y > b) as a → ∞.
Consequently, recalling that ES 2 1 < ∞ implies the tightness of the overshoots R a for a 0, the second term on the right-hand side of (41) converges to 0 as well when first letting a and then b tend to infinity.

Step 3. In order to finally prove the last assertion of the lemma, we first note that, by another appeal to (39), it suffices to show lim a→∞ E x R a 1 {σ(a)<τ <∞, Ra a} = 0 for all x > 0. Fix an arbitrary ε > 0. By Step 2 and (36), we can pick b > 0 so large that lim sup a→∞ E x H(S σ(a) )1 {σ(a)<τ <∞, b<Ra a} < ε 2 and thus also a 0 > 0 such that

E x H(S σ(a) )1 {σ(a)<τ <∞, Ra>b} < ε
for all a a 0 . Consequently, as a → ∞,

E x R a 1 {σ(a)<τ <∞, Ra a} E x H(R a )1 {σ(a)<τ <∞, Ra a} b P x (σ(a) < τ < ∞) + E x H(S σ(a) )1 {σ(a)<τ <∞, Ra>b} o(1) + ε which completes the proof.
This result particularly implies the following identity for H that will be useful below in the proof of Proposition 4.1.

Corollary 4.4. For all x > 0, we have

H(x) = lim y→∞ y P x (σ(y) < τ ).
Proof. By Lemma 4.2, for all y > x > 0, we have

H(x) = E x H(S σ(y) )1 {σ(y) τ } .
Using (36), for all ε > 0 and all y large enough, we deduce

(1 -ε) y P x (σ(y) < τ ) + E x R y 1 {σ(y)<τ } H(x) y P x (σ(y) < τ ) + E x R y 1 {σ(y)<τ } .
Now use Lemma 4.3 upon letting y → ∞ and then ε → 0 to arrive at the assertion.

We are now ready to give the proof of the main result of this section.

Proof of Proposition 4.1. Our proof follows along the same lines as the original one by Choquet and Deny [START_REF] Choquet | Sur l'équation de convolution µ = µ * σ[END_REF]. Note first that, for all A > 0, the function G + AH satisfies the same assumptions as G and is nonnegative on [1, ∞) for large enough A. Therefore, we may assume without loss of generality that G is bounded from below.

We consider the following regularization of the function G. For δ > 0 and x ∈ R, put

G δ (x) := 1 δ x+δ x G(z)dz.
The function G δ is differentiable, and by assumption its derivative satisfies

|(G δ ) (x)| = |G(x + δ) -G(x)| 2C(1 + x + + δ).
for some C > 0. As a consequence, x → G δ (x)/(1 + x + ) is uniformly continuous and bounded. Hence, by the Arzela-Ascoli theorem, there exist 0 < y n ↑ ∞ such that x → G δ (x + y n )/(1 + (x + y n ) + ) converges, uniformly on compact sets, to a bounded and continuous limit denoted as κ δ . The y n may further be chosen from dN if the random walk is d-arithmetic. The next argument shows this function to be harmonic for the random walk (without killing).

Indeed, as G(x) = 0 for x 0, we infer from (33) that

G(x) = EG(x + S 1 )1 {x+S 1 >0} = EG(x + S 1 )
and thereupon, by Fubini's theorem,

G δ (x) = EG δ (x + S 1 ) for all x > 0. ( 42
)
As a consequence,

κ δ (x) = lim n→∞ G δ (x + y n ) 1 + (x + y n ) + = lim n→∞ G δ (x + y n ) y n (43) = lim n→∞ EG δ (x + y n + S 1 ) y n = E lim n→∞ G δ (x + y n + S 1 ) y n = Eκ δ (x + S 1 ),
for all x ∈ R, having used (42), then the domination assumption on G, and finally the dominated convergence theorem. This proves that κ δ is indeed harmonic for the random walk (S n ) n 0 and thus, by Lemma 3.3, either a d-periodic continuous function or a constant.

As the next step, we show that

(44) G δ (x) = κ δ (x)H δ (x) + E x G δ (S τ ).
for all x > 0. First, writing (42) as G δ (x) = E x G δ (x + S 1∧τ ) for all x > 0, it follows that (G δ (x + S n∧τ )) n 0 forms a martingale and then as in the proof of Lemma 4.2 that

G δ (x) = E x G δ (S σ(y)∧τ ) = E x G δ (S σ(y) )1 {σ(y)<τ } + E x G δ (S τ )1 {τ <σ(y)} for all 0 < x < y. Observe that E x G δ (S τ )1 {τ <σ(y)} = E x G δ (S τ ) as y → ∞.
Compactly uniform convergence of G δ (x+y n )/y n to κ δ will now be utilized to compute lim n→∞ E x G δ (S σ(yn) )1 {σ(yn)<τ } by bounding it from above and from below separately. Let ε, K > 0 and choose n large enough such that (45) sup

x∈[0,K] |G δ (x + y n )/y n -κ δ (x)| ε.
Then

E x G δ (S σ(yn) )1 {σ(yn)<τ } E x G δ (S σ(yn) )1 {σ(yn)<τ, Ry n K} (κ δ (x) -ε)y n P x σ(y n ) < τ, R yn K ,
using that κ δ (S σ(yn) -y n ) = κ δ (x) P x -a.s. by the periodicity or constancy of κ δ (recall here that the y n are all chosen from dN if the random walk has lattice-span d > 0). By letting n → ∞ and use of Corollary 4.4, this yields

lim inf n→∞ E x G δ (S σ(yn) )1 {σ(yn)<τ } (κ δ (x) -ε) H(x) -lim sup a→∞ a P x (σ(a) < τ, R a > K) ,
and thereupon, with the help of (37),

lim inf n→∞ E x G δ (S σ(yn) )1 {σ(yn)<τ } H(x)κ(x).
when letting K → ∞ and then ε → 0.

For the upper bound, we obtain by proceeding similarly upon letting n → ∞, then K → ∞ and finally ε → 0. This completes the proof of (44). Finally, we observe that the right continuity of G implies G δ (x) → G(x) as δ → 0 and in combination with G δ (z) = 0 for z < -δ also

E x G δ (S σ(yn) )1 {σ(yn)<τ } (κ δ (x) + ε) (y n + K) P x (σ(y n ) < τ, R yn K) + 2C E x S σ(
|E x G δ (S τ )| sup z∈[0,δ] |G(z)| → 0 as δ → 0.
Consequently, by letting δ → 0 in (44), we conclude that κ δ converges as well. Its limit κ is also d-periodic or constant, right-continuous and satisfies κ(x) = G(x)/H(x) for all x > 0. This finishes the proof.

5. The boundary case: proof of Theorem 1.5. In essence, the same techniques as those used in Section 3 can be used to prove Theorem 1.5. However, additional complications arise because, as predicted by the theorem, -log M (t) = h(t)t α Z, is no longer integrable. As a consequence, it is impossible to directly give an analog of the function F here. Instead, we will have to work with a truncated version of the BRW that only includes individuals in the tree that never went "too high".

Again, let f ∈ S(M) be an arbitrary solution to Eq. ( 1) and a > 0. For n 0, define

(46) M (a) n (t) := |v|=n tL * (v)<a f (tL(v)),
where L * (v) := max k |v| L(v(k)). By another appeal to the branching property of the BRW, it follows immediately that (M (a) n (t)) n 0 constitutes a bounded submartingale and therefore converges a.s. to a limit that we denote by M (a) (t).

Recall that assumption [START_REF] Lyons | A simple path to Biggins' martingale convergence for branching ranwalk, Classical and modern branching processes[END_REF] ensures lim n→∞ sup |v|=n L(v) = 0 a.s. and thus sup v∈V L(v) < ∞. As a consequence, M (a) (t) = M (t) a.s. for all 0 t < a/ sup v∈V L(v).

In particular, M (a) (t) is positive with positive probability for a large enough.

For t 0, a > 1 and n ∈ N 0 , we now define

Z (a) n (t) := |v|=n (tL(v)) α H(-log(tL(v)/a)) 1 {tL * (v)<a}
where H(x) = -ES τ (-x) = x -E x S τ for x > 0 is the essentially unique right-continuous harmonic solution to (33). The last property entails that (Z

n (t)) n 0 constitutes a nonnegative martingale, which is sometimes called the trimmed martingale for obvious reasons. It was introduced in [START_REF] Biggins | Measure change in multitype branching[END_REF] as a positive martingale with an asymptotic behavior that can be linked to the derivative martingale. In particular, it converges a.s. and in L 1 to a limit Z (a) (t) under the assumptions of Theorem 1.5 (see [START_REF] Aïdékon | Convergence in law of the minimum of a branching random walk[END_REF]Proposition A.3]). By similar arguments as the ones above for the martingale M (a) (t) in combination with H(x) = 0 for x 0 and H(x) x as x → ∞, we see that, if t 0 and a > t sup v∈V L(v), then almost surely

Z (a) (t) = lim n→∞ |v|=n (tL(v)) α H(-log(tL(v)/a)) = lim n→∞ |v|=n (tL(v)) α (-log(tL(v)/a)) = lim n→∞ |v|=n (tL(v)) α (-log L(v)) + t α log(a/t) |v|=n L(v) α = t α Z,
where we have also used that the additive martingale |v|=n L(v) α , n 0, converges to 0 a.s. as n → ∞ (see [START_REF] Lyons | A simple path to Biggins' martingale convergence for branching ranwalk, Classical and modern branching processes[END_REF]).

Using these observations, we now prove the following tameness result and counterpart of Lemma 3.1 in the boundary case.

1 log f (t) t α log t C.
Proof. Proceeding in a similar manner as in the proof of Lemma 3.1, we prove that, given any f ∈ S(M), failure of (47), that is

(48) lim sup t→0 log f (t) t α log t = ∞, entails M (t) 1 {Z=0} a.
s. for all t, a > 0 and thus f (0+) < 1 which is impossible. We confine ourselves to the main steps of the proof as technical details are very similar to those in the proof of Lemma 3.1.

Given (48), we can find two decreasing null sequences (ϑ n ) n 1 and (ρ n ) n 1 such that, for all n ∈ N and x ∈ [ρ n ϑ n , ϑ n ],

-log f (x) nx α (-log x).
We then bound the conditional expectation of M (a) (t) given G ϑn/t . Namely, by the branching property of the BRW,

M (a) (t) = lim n→∞ v∈Υ ϑn/t tL * (v)<a f (tL(v)) = exp -lim n→∞ v∈Υ ϑn/t tL * (v)<a -log f (tL(v)) . Bounding -log f (x) by nx α (-log x) if x ∈ [ρ n ϑ n , ϑ n ],
and by 0 otherwise, we then obtain

M (a) (t) exp -lim sup n→∞ n v∈Υ ϑn/t tL(v) ρnϑn, tL * (v)<a (tL(v)) α (-log tL(v)) . (49)
On the other hand, as n 1 G ϑn/t = F ∞ , we infer

Z (a) (t) = lim n→∞ E Z (a) (t)|G ϑn/t = lim n→∞ v∈Υ ϑn/t tL * (v)<a (tL(v)) α H -log(tL(v)/a) .
Therefore, by another use of lim n→∞ max |v|=n L(v) = 0 and H(x)

x as x → ∞, we obtain for all t 0 lim n→∞ v∈Υ ϑn/t tL * (v)<a

(tL(v)) α (-log(tL(v))) = lim n→∞   v∈Υ ϑn/t (tL(v)) α H(-log(tL(v)/a)) + log a v∈Υ ϑn/t L(v) α   = Z (a) (t) a.s.
Next, the many-to-one lemma provides us with (recall

P t = P(•|S 0 = -log t)) E v∈Υ ϑn/t tL(v) ρnϑn, tL * (v)<a (tL(v)) α (-log tL(v)) = t α E(S σ(log(t/ϑn)) -log t)1 {R log(t/ϑn) -log ρn, σ(log(t/ϑn)) τ (log(t/a))} = t α E t S σ(log(1/ϑn)) 1 {R log(1/ϑn) -log ρn, σ(log(1/ϑn)) τ (log(1/a))} ,
which by Lemma 4.3 converges to 0 as n → ∞.

By combining the previous facts, we obtain lim

n→∞ v∈Υ ϑn/t tL(v) ρnϑn, tL * (v)<a (tL(v)) α (-log tL(v)) = Z (a) (t) a.s.
and therefore with the help of (49) that M (a) (t) 1 {Z (a) (t)=0} for all a, t > 0. But the latter entails M (t) 1 {Z=0} upon letting a → ∞ which is impossible because it would imply f (t) = P(Z = 0) < 1 for all t > 0, a contradiction to f (0+) = 1.

Using the tameness assumption for fixed points of the smoothing transform, we now can identify the function defined by ( 50)

F (a) (t) = E -log M (a) (t) .
We prove this function to be harmonic for the random walk (S n ) n 0 killed when hitting (-∞, 0] and therefore to be a multiple of H.

Lemma 5.2. Let r 1 be the span of T . Assuming [START_REF] Lyons | A simple path to Biggins' martingale convergence for branching ranwalk, Classical and modern branching processes[END_REF], for any function f ∈ S(M) with disintegration M (t) and all a > 0, there exists a function h (a) , multiplicatively r-periodic if r > 1 and constant otherwise, such that

F (a) (t) = t α H(-log(t/a)) h (a) (t)
for all t 0.

Proof. The proof follows similar lines as the one of Lemma 3.4. We prove that the function F (a) defined in (50) is related to a harmonic function for the random walk conditioned to stay positive which in turn allows us to characterize it up to multiplication by a multiplicatively r-periodic or constant function.

Recalling that

-log M (a) (t) = lim n→∞ |v|=n -log f (tL(v))1 {tL * (v)<a} a.s.
for all a 1 and t > 0, Lemma 5.1 implies

0 -log M (a) (t) CZ (a) (t) a.s. (51)
Consequently, as (Z for all t a.

By conditioning with respect to F 1 and use of the many-to-one lemma, it follows that for all x > 0, and it is right-continuous because f is left-continuous, by dominated convergence. Furthermore, (51) implies that g (a) (x)

Ca -α e αx EZ (a) (ae -x ) CH(x), and thus the required boundedness of (1 + x) -1 g (a) (x). Invoking Proposition 4.1, we conclude that g (a) equals κ (a) H for some κ (a) which is log rperiodic if T has span r = 1, and is constant otherwise. The proof is completed by rewriting this result in terms of F (a) (t) and putting h (a) (t) := κ (a) (-log(t/a)).

With the help of the last lemma, we are now able to given an explicit expression for M (a) (t) and thereby to find the value of M (t) upon letting a → ∞. for all n ∈ N. Letting n → ∞, this yields M (a) (t) = e -h (a) (t)Z (a) (t) a.s.

Therefore, for all a large enough and all t ∈ [0, a/ sup v∈V L(v)], M (t) = M (a) (t) = e -h (a) (t)t α Z a.s

In particular, as h (a) is multiplicatively r-periodic or constant, we infer that h (a) = h does not depend on a for a large enough. Since Ψ(t) = E (M (t)) = E e -h(t)t α Z , the proof is complete when finally noting that h ∈ H r follows from the fact that Ψ(t) is nonincreasing.

6. Fixed points of the smoothing transform and fractal measures on the boundary of the BRW. The purpose of this supplementary section is to show that any fixed point of the smoothing transform (6) can be thought of as the total mass of a random fractal measure on the boundary of the associated BRW. More precisely, this connection is established by a one-to-one map between these fixed points and random measures ν on the boundary ∂V of the tree (see below for details) such that, for all u ∈ V,

ν ({v ∈ ∂V : v(|u|) = u}) L(u)
is independent of F |u| and has the same law as ν(V). Any random measure ν of this kind is called fractal.

Let X be a random variable with Laplace transform f ∈ S(L), its law thus a fixed point of the smoothing transform. Then there exists a family (X(v)) v∈V of copies of X, defined on the same probability space as the multiplicative BRW L = (L(v)) v∈V (possibly enlarged) such that (52)

X(v) = j 1 T v j X(vj) = j 1 L(vj) L(v) X(vj)
for all v ∈ V. Namely, let {X (n) (v) : |v| = n} for any n ∈ N denote a family of independent copies of X which are also independent of {L(v) : |v| = n}.

For v ∈ V with |v| < n, we then define recursively

X (n) (v) = j 1 L(vj) L(v) X (n) (vj).
As X satisfies [START_REF] Biggins | Measure change in multitype branching[END_REF] and by the branching property of the BRW, we see that each X (n) (v) is a copy of X and depends only on the variables defined on the subtree rooted at vertex v. The existence of (X(v)) v∈V with the claimed properties is now ensured by Kolmogorov's consistency theorem because the laws of {(X (n) (v), L(v)) : |v| n}, n ∈ N constitute a projective familiy.

Recall that ∂V = N N denotes the boundary of the tree V and becomes a complete metric space when endowed with the ultrametric distance d(u, v) = exp(-min{k 1 : 14) and ( 16)) where the former definition would only give the null measure. Indeed, with µ α thus defined and Campbell's formula, we obtain that Ee -tν(B(v)) = E exp(-t α h(t)µ α (B(v))) = f (t), for all v ∈ V as expected.

u k = v k }).

  β ∈ [0, 1]. This was shown by Liu [15, Thm. 1.1] using a truncation argument.

Proposition 4 . 1 .

 41 Given a nontrivial, centered random walk with latticespan d 0 and ES 2 1 < ∞, let G : R → R be a right-continuous function satisfying (33) and sup x 0 |G(x)/(1+|x|)| < ∞. Then there exists a function κ, d-periodic if d > 0 and constant if d = 0, such that

Lemma 4 . 2 .

 42 Under the assumptions of Proposition 4.1,

Lemma 4 . 3 .

 43 Let (S n ) n 0 be a centered random walk with 0 < ES 2 1 < ∞. Then for all x > 0, we have lim b→∞ lim sup a→∞ E x S σ(a) 1 {σ(a)<τ,Ra>b} = 0 (37) and lim a→∞ E x R a 1 {σ(a)<τ } = 0. (38) Proof. Step 1 We first show that (39) lim a→∞ E x H(S σ(a) )1 {σ(a)<τ <∞, S σ(a) >(1+ε)a} = 0 for all ε > 0 and x 0. As H grows like the identity, we may replace H(S σ(a) ) with S σ(a) . It is further no loss of generality to choose x = 0. We then have ES σ(a) 1 {σ(a)<τ, S σ(a) >(1+ε)a} = ∞ (1+ε)a P(σ(a) < τ, S σ(a) > y) dy = ∞ (1+ε)a a 0 P(S 1 > y -x) U a (dx) dy ∞ (1+ε)a P(S 1 > y -a) U a ([0, a]) dy (40)

for some C > 0 and all a 1 .

 1 Returning to (40), we now obtain ES σ(a) 1 {σ(a)<τ, S σ(a) >(1+ε)a} Ca ∞ (1+ε)a P(S 1 > y -a) dy C ε ∞ εa y P(S 1 > y) dy and the last expression goes to 0 as a → ∞ under the proviso ES 2 1 < ∞. Step 2. Next, we show that lim b→∞ lim sup a→∞ E x H(S σ(a) )1 {σ(a)<τ <∞, Ra>b} = 0 for all x 0, thus proving (37). Using the strong Markov property at time σ(a/3), we have E x H(S σ(a) )1 {σ(a)<τ <∞, Ra>b} = E x H(S σ(a/3) )Ψ(S σ(a/3) )1 {σ(a/3)<τ <∞} , where Ψ(x) := E x H(S σ(a) ) H(x) 1 {σ(a)<τ <∞, b<Ra a} for x > 0. Observe that

  yn) 1 {σ(yn)<τ,Ry n >K} , for sufficiently large n, where G δ (y) 2Cy for sufficiently large y has been utilized. Now, by another use of Corollary 4.4, (37) and also lim n→∞ K P x (σ(y n ) < τ, R yn K) = 0, we find lim sup n→∞ E x G δ (S σ(yn) )1 {σ(yn)<τ } H(x)κ δ (x)

Lemma 5 . 1 .

 51 Under the assumptions of Theorem 1.5, for any function f ∈ S(M) there exists 0 < C < ∞ such that (47) sup

  0<t

n

  (t)) n 0 is uniformly integrable, we infer that

F

  (a) (t) = E -log M (a) (t) ∈ [0, Ct α H(-log(t/a))].

FF

  (a) (tL(u))1 {tL(u)<a}   = E F (a) (te -S 1 )e αS 1 1 {S 1 -log t>-log a} for all t a. Hence, the function g (a) (x) := a -α e αx F (a) (ae -x ) satisfies g (a) (x) = Eg (a) (x + S 1 )1 {x+S 1 >0}

Proof of Theorem 1 . 5 .

 15 By the branching property of the BRW, we have almost surelyE -log M (a) (t) F n = |v|=n F (a) (tL(v)) 1 {tL * (v)<a} = h (a) (t) |v|=n (tL(v)) α H(-log(tL(v)/a)) 1 {tL * (v)<a} = h (a) (t)Z (a)n (t)

PuttingB

  (u) := {v ∈ ∂V : v(|u|) = u} in the boundary case (assuming (

  see e.g.[START_REF] Gut | Stopped Random Walks[END_REF] Thm. 3.10.2], giving Moreover, we point out that, by definition, H is right-continuous with left limits at each point.Our main result of this section is the following Choquet-Deny-type lemma. It states that any right-continuous function of at most linear growth and satisfying (33) equals H up to multiplication by a constant, or d-periodic function if the walk is d-arithmetic.

	(36)	x	H(x)	x(1 + o(1)) as x → ∞.

Acknowledgments. Most of this work was done during a visit of the second author in March 2019 at the University of Münster. Financial support and kind hospitality are gratefully acknowledged.

Data availability statement. This manuscript was produced with no additional data.

* Funded by the Deutsche Forschungsgemeinschaft (DFG) under Germany's Excellence Strategy EXC 2044-390685587, Mathematics Münster: Dynamics-Geometry-Structure. 8. Partially funded by the ANR project 16-CE93-0003 (ANR MALIN).

MSC 2010

for u ∈ V, the family (B(u)) u∈V forms a basis of the topology on ∂V and its Borel σ-field.

With the help of the familiy (X(v)) v∈V introduced above, a one-to-one map between the fixed points of the smoothing transform and the random fractal measures on ∂V can now be constructed as follows. Observe that, for any such ν, the total mass ν(∂V) is a fixed point of the smoothing transform associated with L. This follows because, by σ-additivity of ν,

and the fractal property of ν.

Conversely, the above construction allows us to define a fractal measure ν for each fixed point of the smoothing transform such that the law of ν(∂V) equals this fixed point. Namely, with (X(v)) v∈V as defined above, we put

for any v ∈ V. By (52), this provides a well-defined consistent σ-additive measure on N k for each k ∈ N. Thus, by another use of Kolmogorov's consistency theorem, we can extend ν to a random measure on ∂V, and it has the fractal property by definition as X(v) is independent of F |v| for any v.

Under the assumptions of Theorem 1.2 or 1.5, the fractal measure ν can be even explicitly defined as a marked Poisson point process, namely

where (ξ j , v j ) are the atoms of a bivariate Poisson point process on R > × ∂V with intensity π(dx)µ α (dv). Here π equals the Lévy jump measure of a Lévy process with characteristic exponent h(t)t α , h the function associated with f by the respective theorem. Moreover, µ α denotes the random measure on ∂V defined by


Umberto Grandi
email: umberto.grandi@irit.fr

Interaction and Expressivity in Collective Decision-Making

Collective decisions among human and artificial agents can be enhanced by allowing for more interaction among decision-makers and by letting them express more information about their preferences. In this paper I present ongoing research on two settings: iterative voting, which repeatedly applies a voting rule until decision-makers converge to an outcome, and delegative voting on multiple issues.

Introduction

There are many ways in which AI techniques and technologies can contribute to the improvement of collective decision-making processes among human or artificial agents. Many such research directions require that the classical social choice setting (independent voters expressing preferences over typically few independent alternatives) are generalised to more complex settings. In previous research I focused extensively on how to introduce a social network in the modelling of a collective decision problem (see [START_REF] Grandi | Umberto Grandi. Social choice and social networks[END_REF] for an overview, but many other papers appeared since then). In this paper I focus on two further improvements. First, study interactive mechanisms in which voters participate to an iterated election, each time receiving information about the current winner or the other voters' ballots. This setting is known as iterative voting (for a survey of initial work in this area see Meir [2017]). Second, give voters more expressivity by considering collective decisions on multiple issues, most notably in the setting of delegative voting. Both research directions aim at paving the way for some sort of agent-mediated social choice, an idea which I presented in a recent position paper [Grandi, 2019]. 1 Context. Current research in computational social choice 2 moved towards the design and the analysis of algorithms for digital democracy. Research directions have been outlined in a number of recent position papers [START_REF] Brill | Interactive democracy[END_REF]Shapiro, 2018;[START_REF] Brill | From computational social choice to digital democracy[END_REF][START_REF] Talmon | Foundations for grassroots democratic metaverse[END_REF][START_REF] Grossi | Social choice around the block: On the computational social choice of blockchain[END_REF].

1 A similar program was put forward by César Hidalgo in a 2018 TED talk (see www.peopledemocracy.com).

2 For an overview of this research field see [START_REF] Brandt | [END_REF].

Social Influence and Iterative Voting

Consider a simple collective decision in which a set of voters have preferences over a set of candidates or alternatives, and express it in the form of a plurality vote, thus submitting the name of their preferred candidate. Assume now that some of this information is shared among the voters. For instance, an agent can discover for whom other agents close to them have voted for, or get information about the score of each candidate from a publicly accessible poll. There are two ways in which a voter can react to such information: either be influenced, or respond strategically.

The combination of voting and social influence is a wellstudied topic. For instance, settings where a group of voters is steered towards the majority vote [START_REF] Hassanzadeh | [END_REF] or when an external player aims at controlling an election on a social network [START_REF] Faliszewski | [END_REF][START_REF] Wilder | [END_REF][START_REF] Castiglioni | [END_REF]. In past work I designed and analysed social influence models that are adapted to voting situations such as preferences over alternatives or multi-issue voting [START_REF] Grandi | [END_REF][START_REF] Brill | [END_REF][START_REF] Botan | [END_REF] and strategic models of social influence [START_REF] Grandi | [END_REF].

When agents are instead assumed to respond to the information received dynamically from the other voters by changing their reported vote or their reported preference, we enter in the realm of iterative voting. This setting was first proposed as an equilibrium selection mechanism for voting games [Meir et al., 2010;[START_REF] Procaccia | [END_REF], initiating a productive line of research. However, the repeated execution of a simple voting rule such as plurality can also be viewed as a novel voting procedure per se. This approach might solve a tension in the design of collective decisions, that are required to be easy to explain to voters while at the same time satisfy a number of good properties.

In previous work we assessed the quality of the result of a repeated election by measuring social welfare as the average position of the winner in the individual preferences as well as the frequency of election of Condorcet winners, showing the beneficial effects of iterative voting. We used both multiagent simulations in a standard voting-for-candidates situation [START_REF] Grandi | [END_REF] and a behavioural experiment in the lab for multi-issue voting [START_REF] Grandi | [END_REF]. 3 We also designed and implemented a platform for organising iterated plurality elections online called Itero, 4 with the aim to promote iterative voting in outreach events and test it in realistic situations [START_REF] Boudou | [END_REF].

Iterative voting can be seen as a lightweight form of deliberation. Thus, this latter line of research supports the thesis that deliberation among voters can improve the quality of a collective decision and somehow escape the classical impossibilities in social choice (see, e.g., the work of Dryzek and List [2003], the analysis of [START_REF] List | [END_REF] on the data of deliberative polls, or the findings of Rad and Roy [2021]).

Delegations and Multi-issue Voting

A number of social choice problems can be modelled using multiple (binary) issues with the additional use of constraints. Elicitation of preferences, aggregation of partial ballots, and logical dependencies between issues are all problems that have been studied extensively (see, e.g., [START_REF] Lang | [END_REF] and Endriss [2016] for overviews).

In recent work we focused on the setting of delegative voting and more particularly on a mechanism known as liquid democracy, in which voters have the possibility to express their opinion directly or to delegate their vote (and the delegations they received) to another voter. We first focused on the problem of solving delegation cycles, proposing a general language for agents to express ranked multi-agent delegations on multiple issues and proposing algorithms for their unravelling [START_REF] Colley | [END_REF]Colley et al., 2022]. We then moved to study delegations in presence of constraints relating the multiple issues at stake. Generalising initial work by [START_REF] Brill | Pairwise liquid democracy[END_REF] on pairwise preference delegations, and by [START_REF] Jain | [END_REF] on knapsack voting, we proposed polynomial algorithms for delegations under constraints that make use of a priority ordering over the issues that is elicited from the voters [START_REF] Colley | [END_REF].

Conclusions and Perspectives

In this paper I presented recent and ongoing research on enhancing collective decision-making with more interaction and more expressivity. Both topics are concerned with the design of algorithms and their analysis and are guided by philosophical considerations (deliberation can improve collective decisions) or practical applications (the rise of technologies supporting liquid democracy and electronic institutions). One step further is to assess the proposed mechanisms when used by artificial agents acting as proxies for human decisionmakers. Initial work has been done, e.g., on assessing how simple reinforcement learning agents can perform in an iterated voting election [Airiau et al., 2017].

Research on algorithms for digital democracy is experiencing a momentum, and the need for new applications in this domain is real. The rise of an interdisciplinary community around these subjects has the potential of unveiling new fascinating problems and research directions for the AI community studying collective decision-making. To give an example, in a recent experiment that we conducted online during the French presidential elections5 we asked users to approve or disapprove more than one hundred political proposals, and to rank the approved ones, with the aim to construct a collective political program. The design of the platform showed us the need for novel social choice methods that are able to deal with large numbers of alternatives and heavily incomplete preference data, suggesting us a number of research directions for future work.

A similar experiment did not find any statistically significant Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence Early Career Track

improvement in the social welfare of iterated elections[START_REF][END_REF]. The set of voting situations they analyse was however less prone to improvements than the ones considered in our experiment.4 https://itero.irit.fr/

https://monprogramme2022.org/en/about/ Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence Early Career Track

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence Early Career Track

Acknowledgments

I acknowledge the support of the ANR JCJC project SCONE (ANR 18-CE23-0009-01). I am indebted to all my collaborators and co-authors without whom most of the work reported here would not have seen the light.