Dias Abstract: We consider a random covering determined by a random variableX of the spaceD={0,1}N

Nova S´erie

HOW MANY INTERVALS COVER A POINT IN RANDOM DYADIC COVERING?

A.H. Fan and J.P. Kahane Presented by J.P. Dias

Abstract: We consider a random covering determined by a random variableX of the spaceD⁼{0,1}^N. We are interested in the covering numberNn(t) of a pointt∈D by cylinders of lengths≥2⁻ⁿ. It is proved that points in D are differently covered in the sense that the random sets{t∈D^{: Nn(t)}−b n ∼ c n^α}are non-empty for a certain range ofb, any real numbercand any 1/2< α <1. Actually, the Hausdorff dimensions of these sets are calculated. The method may be applied to the first percolation on an infinite and locally finite tree.

1 – Introduction

We consider the sequence space D={0,1}^N and a probability distribution represented by a random variableXwhich takes values in the set of non-negative integers (our methods also apply to the case of an infinite and locally finite tree and a real-valued variable). For any finite sequence (²₁, ..., ²_n) of 0 and 1, we de- note byI(²₁, ..., ²_n) then-cylinder inD(also called interval of length 2⁻ⁿ) which is defined in the usual way and byX_²1,...,²n a random variable which has the same distribution as X. We consider X_²1,...,²n as the covering number of the cylin- derI(²₁, ..., ²_n), that is to say, the cylinder I(²₁, ..., ²_n) is cut off with probability p₀=P(X= 0) and is covered m times with probability p_m =P(X=m), m= 1,2, .... In the sequel, we assume that all variablesX²1,...,²n are independent and they are defined on a probability space (Ω,A, P).

Received: July 3, 2000.

AMS Subject Classification: 52A22, 52A45, 60D05.

Keywords: Random covering; Hausdorff dimension; Indexed martingale; Peyri`ere measure.

For t= (t_n)_n≥1 ∈D, let

N_n(t) = Xn k=1

X_t1,...,tk .

The quantityN_n(t) is called the covering number (or more precisely then-cover- ing number) of the point t by cylinders of lengths 2^−k (k= 1,2, ..., n). As a consequence of the law of large numbers and Fubini’s theorem, we have

n→∞lim Nn(t)

n = EX

almost surely (a.s.) for almost every point t (with respect to Lebesgue mea- sure on D). It is also well known in the theory of birth processes that a.s.

lim_n→∞N_n(t) =∞ forevery t∈D if and only if p₀ = P(X= 0) < 1 2 .

That is to say, a.s. every point is infinitely covered when the above condition is satisfied.

Our aim in this paper is to study the behavior of Nn(t) by considering the random sets

E_b =

½

t∈D: lim

n→∞

N_n(t)

n = b

¾

for different b∈ R. If t ∈ E_b, we may say that the point t is covered by about b n cylinders of lengths≥2⁻ⁿ(with the convention that the cylinderI(²₁, ..., ²_n) is coveredmtimes when X²1,...,²n=m). Actually our method allows us to study the subsets ofE_b defined by

E_b,s = ⁿt∈D: N_n(t)−b n ∼ s_n, as n→ ∞^o wheres={s_n}is a sequence of real numbers such that s_n=o(n).

We make the hypothesis that X is not constant andEe^tX<∞ for all t∈R (similar results hold whenEe^tX<∞ for some interval oft). Let

ϕ(u) =Ee^uX, c(u) = logϕ(u) .

The function c(u) is called the free energy of X. Notice that c(u) is strictly increasing and strictly convex. Its Legendre–Fenchel transform is defined by

c^∗(s) = sup

u∈R

³s u−c(u)^´ .

Notice also that c^∗ is a well defined continuous convex function in the interval [c⁰(−∞), c⁰(+∞)] which is contained in [0,+∞], and that it attains its minimal value 0 atu=EX.

In the following theorems, dim means the Hausdorff dimension as well as the packing dimension. See [M2] for the definitions of these two notions of dimension.

We recall the metric of D, which is defined as d(t, s) = 2⁻ⁿ for t, s ∈ D with n= sup{m: t_j =s_j, ∀1≤j≤m}. We denote

J =ⁿb∈[c⁰(−∞), c⁰(+∞)] : c^∗(b)≤log 2^o .

Theorem 1. Suppose X is a non-constant random variable taking values in the set of non negative integers such that Ee^tX < ∞ (∀t ∈ R). Then for any number b ∈J and any sequence of positive numbers s = (s_n) such that s_n−s_n−1 =o(1) and √

nlog logn=o(s_n), we have a.s.

dimE_b,s = dimE_b = 1−c^∗(b) log 2 .

The proof of Theorem 1 will show that the dimension of the set of pointstsuch that lim infn⁻¹Nn(t) ≥ b is equal to dimE_b when b > EX and the dimension of the set of points t such that lim supn⁻¹N_n(t) ≤ b is equal to dimE_b when b <EX.

What happens forE_b whenb6∈J? This question is answered by the following theorem.

Theorem 2. Suppose X satisfies the same condition as in Theorem 1. Let A= infJ and B = supJ. Then we have a.s.

A ≤ lim inf

n→∞

Nn(t)

n ≤ lim sup

n→∞

Nn(t)

n ≤ B (∀t∈D) .

If lim^Nn_n^(t) doesn’t exist, we may say that t is irregularly covered. The fol- lowing theorem shows that many points are irregularly covered.

Theorem 3. SupposeX satisfies the same condition as in Theorem 1. Then the set of irregularly covered points is a.s. of Hausdorff dimension1.

The present study was partially motivated by Dvoretzky random covering problem on the unit circle [D] (see [S, K2, FK, K5, K6] for the developments of

the subject). Recent work on the circle related to ours may be found in [F3], the results are less complete than those for the sequence spaceD studied here.

The restriction onDand the positivity assumption ofX are not essential: the above results can be generalized to tree-indexed walks. See [B, L, LP, BP, PP]

for related works on tree-indexed walks.

Using results on percolation in [L], Lyons and Pemantle [LP] have obtained the dimension formula for dimE_b, but their method does not give results on dimE_b,s.

2 – Preliminaries

Our main tool is multiplicative chaos (for a lower estimate for the dimension).

As usual, large deviation is used to get an upper estimate of dimension.

First of all, we recall the notion of the dimension of a measure [F2]. The lower dimension of a measureµ, denoted by dim_∗µ, is the supremum of β’s such that µ(E) = 0 for any E with dimE < β. The upper dimension of a measure µ, denoted by dim^∗µ, is the infimum of dimF forF’s such that µ(F^c) = 0. It is clear that for a given Borel setA, we have

dimA ≥ dim_∗µ if µ(A)>0 . When dim_∗µ= dim^∗µ=α, we write dimµ=α.

The general theory of multiplicative chaos was developed by the second author in [K3]. We recall it here briefly. The key part for us is the Peyri`ere probability measure. Let (P_n) be a sequence of non-negative independent random functions defined onDsuch thatEP_n(t) = 1 (∀t∈D). Consider the finite products

Q_n(t) = Yn k=1

P_n(t).

We call Q_n(t) an indexed martingale because it is a martingale for each t ∈ D. It was proved in [K3] that for any Borel probability measure µ on D, a.s. the random measures Q_n(t)dµ(t) converge weakly to a (random) measure that we denote byQµ. The operatorQis called a multiplicative chaos. If the total mass martingale

Y_n = Z

DQ_n(t)dµ(t)

converges in L¹, the measure Qµ does not vanish and a probability measure

Q=Qµ on Ω×D, called Peyri`ere measure, may be defined by the relation Z

Ω×Dϕ(ω, t)dQµ(ω, t) = E^Z

Dϕ(ω, t)dQµ(t)

(for all bounded measurable functions ϕ). A very useful fact is that if the dis- tribution of the variable P_n(t) is independent of t∈D, then P_n(t, ω) (n≥1) considered as random variables on Ω×D are Q-independent. Furthermore, we have the formula

E^Qh(Pn) = Eh(Pn)Pn

(for any Borel functionh).

We shall use a particular class of multiplicative chaos. This corresponds to P_n(t) = W_t1,...,tn

where all the random variables {Wt1,...,tn} are independent, non-negative and normalized (i.e. EW_t1,...,tn = 1), and for any n ≥ 1, the subfamily of variables {W_t1,...,tn}are identically distributed with common law represented by a variable Wf_n. The corresponding chaos is called (generalized) random cascades determined by W^f_n. When W^f_n are identically distributed, we recover the classical random cascades, well studied in [KP, M1]. The following lemmas study the random measure Qλ determined by a sequence {W^f_n} and the Lebesgue measure λ=dt onD. Recall that Y_n denotes the total mass martingale ^R_DQ_n(t)dt.

Lemma 1. Suppose that for some 0< h <1 we have lim inf

n→∞

Elog₂W^f_n^h h−1 > 1.

Then the martingaleYn converges a.s. to zero. ConsequentlyQλ= 0 a.s..

Proof: The condition implies that EW^f_j < 2^h−1 for large j. Let B be an arbitrary ball of radius 2⁻ⁿ. We have

E sup

t∈B

Q_n(t)^h = Yn j=1

EW^f_j^h ≤ C2^−n(1−h)

where C is a constant independent of the ball B. We conclude by applying theorem 3 from [K3].

Lemma 2. Suppose that for some h >1 we have lim sup

n→∞

Elog₂W^f_n^h h−1 < 1 .

Then the martingale Y_n converges in L^h. Consequently the Peyri`ere measure Q=Qλ exists.

Proof: The condition implies that there exists² >0 such that 2^1−hEW^f_j ≤ e^²(1−h) for largej. By the same calculation as in [K1] (p. 622), we have

EY_n−1^h ≤ EY_n^h ≤ EY_n−1^h EW^f_n^h 2^1−h µ

1 +E²Y_n−1^h/2 EY_n−1^h

¶h−1

.

It follows that for largen, we haveEY_n−1^h ≤1/². Thus the total mass martingale is bounded inL^h.

Lemma 3. Let 0< h⁰ <1< h⁰⁰. Denote D₋ = 1−lim inf

n→∞

Elog₂W^f_n^h0

h⁰−1 , D₊ = 1−lim sup

n→∞

E log₂W^f_n^h00 h⁰⁰−1 . Then D₊≤dim_∗Qλ≤dim^∗Qλ≤D₋ a.s..

Proof: We follow [K4] using a result from [F1]. For β > 0, let W_β be the variable such that P(W_β = 2^β) = 2^−β = 1−P(W_β = 0). The random cascades determined byW_β (called β-model) gives rise to a multiplicative chaos Q_β. We construct Q_β independent ofQ. The product Q_βQ is the chaos defined by{W_βW^fn}. A simple calculation gives

log₂(W^f_nW_β)^h

h−1 = log₂W^f_n^h

h−1 + β (∀h6= 1) .

Take 0< β < D₊ (there is nothing to do ifD₊ is negative). We have lim sup

n→∞

log₂(W^fnWβ)^h00

h⁰⁰−1 = 1−D++β < 1 . By Lemma 2 and the main result of [F1], we get dim_∗Qλ≥β a.s..

Take β > D₋. We have lim inf

n→∞

log₂(W^f_nW_β)^h00

h⁰⁰−1 = 1−D₋+β > 1 . By Lemma 1 and the result of [F1], we get dim∗Qλ≤β a.s..

Suppose c⁰(λ_b) =b. Takeξ_n=λ_b+η_n withη_n→0 as n→ ∞. Consider Wfn = e^ξnX

ϕ(ξ_n)

whereX is the variable determining our covering. For different choices{η_n}, the corresponding random measure Qλ may be singular each other, but they have the same dimension.

Lemma 4. Let Qλ be the random measure defined by the above sequence {W^f_n}. Then

dimQλ = 1−c^∗(b)

log 2 a.s..

Proof: Since ξ_n→λ_b and logEW^f_n^h

h−1 = c(ξ_nh)−c(ξ_n)

h−1 −c(ξn) , we have

n→∞lim

logEW^f_n^h

h−1 = c(λ_bh)−c(λ_b)

h−1 −c(λ_b) . The functionc(·) being strictly convex, we have

c(λ_bh)−c(λ_b)

h−1 −c(λ_b) > c⁰(λ_b)λ_b−c(λ_b) = c^∗(b) if h >1 ; c(λ_bh)−c(λ_b)

h−1 −c(λ_b) < c⁰(λ_b)λ_b−c(λ_b) = c^∗(b) if h <1 . Now we can apply Lemma 3.

Now let us recall some properties of the free energy function of X and of its Legendre–Fenchel transform. Letxmax (resp.xmin) be the essential upper (resp.

lower) bound of the variableX. Then let

p_min=P(X=x_min), p_max=P(X=x_max) . We first claim that (assuming pmin>0)

c⁰(−∞) =xmin, c^∗(xmin) = log 1 p_min . In fact, since

Ee^tX = p_mine^txmin(1 +O(e^t)) (t→ −∞) , EXe^tX = p_minx_mine^txmin(1 +O(e^t)) (t→ −∞) , we have

c⁰(t) = EXe^tX

Ee^tX = x_min+O(e^t) (t→ −∞) ,

c^∗(c(t)) = t c⁰(t)−c(t) = p_minx_mine^txmin(1 +O(te^t)) (t→ −∞).

We also claim that if x_max<∞

c⁰(+∞) =x_max, c^∗(x_max) = log 1 p_max .

In fact, the proof is the same as above because, assuming p_max>0, Ee^tX = p_maxe^txmax(1 +O(e^−t)) (t→+∞) ,

EXe^tX = p_maxx_maxe^txmax(1 +O(e^−t)) (t→+∞).

Consequently, we have c^∗(x_min) ≤log 2 if and only if p_min ≥ ¹₂. If p_min< ¹₂, there is a point 0< c0<EX such thatc^∗(c0) = log 2. Also ifpmax< ¹₂, there is a pointb₀ >EX such thatc^∗(b₀) = log 2.

3 – Proof of Theorem 1

Let us first prove dim_P E_b≤1−c^∗(b)/log 2 where dim_P denotes the packing dimension. Notice that the interval J contains EX because EX = c⁰(0) and c^∗(c⁰(0)) = 0. Suppose b > EX. (The case b < EX may be similarly treated).

Fix a smallδ >0. Let Cn =

(

I(t₁, ..., t_n) : Xn k=1

X_t1,...,tk >(b−δ)n )

.

LetG_n be the union set of all cylinders inCn. It is clear that Eb ⊂

[∞

`=1

\∞ n=`

Gn .

Then

dim_PE_b ≤ sup

`≥1

dim_P

\∞ n=`

G_n ≤ sup

`≥1

dim_B

\∞ n=`

G_n

where dim_B denotes the upper box dimension. Remark that when n≥`,Cn is a cover of <sup>T∞</sup><sub>n=`</sub>G_n by cylinders of length 2⁻ⁿ. Thus we have

dim_B

\∞ n=`

Gn ≤ lim sup

n→∞

CardCn

log 2ⁿ . Now estimate the random variable CardCn. It is obvious that

ECard Cn = ^X

t1,...tn

P Ã _n

X

k=1

X_t1,...,tk > (b−δ)n

! .

However, by the theorem of large deviation [E] (p. 230), we have P

à _n X

k=1

X_t1,...,tk > (b−δ)n

!

≤ e^{−nc∗(b−δ)} = 2^−nc

∗(b−δ) log 2 .

This, together with the preceding equality, gives us E Card Cn ≤ 2^n(1−c

∗(b−δ) log 2 )

. Then

E X∞ n=1

n⁻²2⁻ⁿ⁽¹⁻

c∗(b−δ) log 2 )

Card Cn < ∞ . It follows that almost surely we have

CardCn = O^³n² 2ⁿ⁽¹⁻

c∗(b−δ) log 2 )´

. Therefore

lim sup

n→∞

Card Cn

log 2ⁿ ≤ 1− c^∗(b−δ) log 2 . Lettingδ→0, we obtain the desired upper bound.

Suppose b is an interior point of J. In order to prove dim_HE_b,s ≥ 1 − c^∗(b)/log 2, we consider the random measure Qλ determined by

Wf_n = e^ξnX ϕ(ξn)

whereξn∈Ris the solution of c⁰(ξn) =b+(sn−sn−1). By Lemma 2, the Peyri`ere measureQ is well defined. We have

E^QXt1,...,tn = EX e^ξnX

ϕ(ξn) = c⁰(ξn) , E^QX_t²_1,...,tn = EX²e^ξnX

ϕ(ξ_n) = ϕ⁰⁰(ξn) ϕ(ξ_n) , Var_QX_t1,...,tn = c⁰⁰(ξ_n) .

Notice that the variablesX_t1,...,tn (n= 1,2, ...) are Q-independent. Then by the law of the iterated logarithm,Q-almost surely

Xn k=1

X_t1,...,tk−bn−s_n = O^³pnlog logn^´.

Since√

nlog logn=o(s_n), Qλ(E_b,s^c ) = 0 a.s.. Then dim_HE_b,s ≥ dim_∗Qλ a.s..

On the other hand, by Lemma 4,

dimQλ = 1−c^∗(b) log 2 a.s..

Thus the formula is proved whenb is in the interior ofJ.

LetAbe the left end point ofJ. Ifc^∗(A) = log 2, the proof of the upper bound shows that dimE_A= 0 then dimE_A,s= 0. Suppose c^∗(A) <log 2. This implies A=x_min=c⁰(−∞)>−∞(see the definition ofJ and the strict convexity ofc^∗).

In order to prove dimEx_min,s = 1−log_{2 p}¹

min, it suffices to consider the random cascade by choosingξ_n tending to−∞ such that c⁰(x_n) =c⁰(−∞) + (s_n−s_n−1) to get the lower bound (the upper bound is proved as above).

LetB <+∞be the right end point ofJ. As for the left end point, if c^∗(B) = log 2, we have dimEB = dimEB,s= 0. Suppose c^∗(B) < log 2. This implies x_max = c⁰(+∞) = B < ∞. In order to prove dimE_xmax,s = 1−log_2p¹

max, it suffices to consider the random cascade by choosingξn tending to +∞ such that c⁰(x_n) =c⁰(+∞) + (s_n−s_n−1) to get the lower bound.

4 – Proof of Theorem 2 Notice that

xmin ≤ Nn(t)

n ≤ xmax .

So, there is nothing to prove for lim sup^Nn_n^(t) ≤supJ when supJ = x_max and nothing to prove for lim inf^Nn_n^(t) ≥infJ when infJ =x_min.

Suppose that supJ < xmax. That implies c^∗(c⁰(∞))> log 2. Denote by [x]

the integral part of a real numberx. Letγ > 0 be a large number. For j ≥4, introduce the following notation

Sj(t) = ^X

[γ(j−1) log(j−1)]≤k<[γjlogj]

Xt1,...,tk

U_j = max

t∈D S_j(t), V_j = min

t∈DS_j(t) .

Suppose U_j =S_j(t₀) for some point t₀. It is clear thatU_j ≤S_j(t) for all t in the [γlogj]-cylinder containing t₀. It follows that for anyλ >0, we have

e^λUj ≤ 2^γlogj Z

De^λSj(t)dt .

Taking expectation gives us

Ee^λUj ≤ 2^γlogj(Ee^λX)^γlogj .

TakeB⁰ > B. Thenc^∗(B⁰)>log 2. By using Chebyshev’s inequality, we get P(U_j ≥B⁰γlogj) ≤ j^{γ{log 2−(B0λ−c(λ))}} .

Take λ > 0 such that c⁰(λ) = B⁰ and B⁰λ−c(λ) = sup_t(B⁰t−c(t)) = c^∗(B⁰).

Such aλ >0 does exist because c^∗(c⁰(∞))>log 2. Then P(U_j ≥B⁰γlogj) = O(j^{γ(log 2−c∗(B0))}).

Since log 2−c^∗(B⁰) is strictly negative, the series ^P_jj^{γ(log 2−c∗(B0))} converges if γ is sufficiently large. According to the Borel–Cantelli lemma, almost surely for largej

Uj ≤ B⁰γ logj . Thus we have

XJ j=1

Uj ≤ B⁰γ XJ j=1

logj + O(1) ≤ B⁰γ J logJ + O(1).

For any n≥1, there is a K such that [γ(K−1) log(K−1)]≤n <[γ K logK].

Then

Xn k=1

X_²1,...,²k ≤ XK j=1

U_j ≤ B⁰γ K logK+O(1) ∼ B⁰n . Thus we have proved

lim sup

n→∞

Nn(t)

n ≤ B⁰ (∀t∈D) .

Since B⁰ is an arbitrary number such that B⁰> B, it follows from the last in- equality that

lim sup

n→∞

N_n(t)

n ≤ B (∀t∈D) .

The proof of the lower estimate is similar. We just point out what should be changed. If Vj = Sj(t0) for some point t0, then Vj ≥ Sj(t) for all t in the [γ logj]-cylinder containing t₀. This allows us to get that for any λ >0,

Ee^−λVj ≤ 2^γlogj(Ee^−λX)^γlogj .

By using Chebyshev’s inequality, forA⁰ < Awe get

P(V_j ≤A⁰γlogj) ≤ jγ{log 2−(−A⁰λ−c(−λ))} .

Takeλ >0 such that A⁰(−λ)−c(−λ) = sup_t(A⁰t−c(t)) =c^∗(A⁰). Then P(V_j ≤A⁰γlogj) ≤ j^{γ(log 2−c∗(A0))} .

5 – Proof of Theorem 3

Let (ξ_n) be a sequence of positive numbers such that 0< a≤ξ_n≤b <∞ which will be determined later. Consider the random measureQλdefined by

Wfn = e^ξnX ϕ(ξ_n) .

By Lemma 2, ifb is small enough, the Peyri`ere measureQ exists. From now on, we assume thatb is small. Since

EQX_²1,...,²k = c⁰(ξ_k), Var_Q(X_²1,...,²k) = c⁰⁰(ξ_k), by the law of the iterated logarithm,Q-almost everywhere

Xn k=1

X²1,...,²k− Xn k=1

c⁰(ξ_k) = O^³qσ_n²log logσ_n^2´ where

σ_n² = Xn k=1

c⁰⁰(ξ_k) ≈ n . Thus a.s.Q-almost everywhere we have the equivalence

N_n(t) ∼ Xn k=1

c⁰(ξ_k) .

Take a rapidly increasing sequence of positive integers (n_k) such that

k→∞lim

n_k n1+...+nk

= 1.

For any two given small numbers 0< a < b, define the sequence (ξj) in the following way

ξ_j = a if n_2k ≤j < n_2k+1 , ξ_j = b if n_2k+1 ≤j < n_2k+2 .

Then we have lim inf

n→∞

1 n

Xn k=1

c⁰(ξ_k) ≤ c⁰(a) < c⁰(b) ≤ lim sup

n→∞

1 n

Xn k=1

c⁰(ξ_k) .

Let E be the set of points t ∈ D such that lim^Nn_n^(t) doesn’t exists. Then almost surely Qλ(E^c) = 0. It follows that almost surely dimE ≥ dimQλ. By Lemma 3, ifb→0 then dimQ→1. We get dimE = 1.

6 – Poisson covering and Bernoulli covering

We look at two examples.

Example 1. Suppose X is a Poisson variable with parameter a >0 (i.e.P(X=k) =e^{−a a}_k!^k). Then

ϕ(t) =e^−a(1−et), c(t) =−a(1−e^t) . Letb=c⁰(t) =a e^t. That meanst= log_a^b. We have

c^∗(b) = t c⁰(t)−c(t) = log b

a·b+ (a−b). Thus we get

Theorem 4. SupposeX is a Poisson variable with parametera >0. Then there is an intervalJa such that forb∈Ja, almost surely

dimE_b = 1− 1 log 2

·

(a−b) +blog b a

¸

;

for b 6∈ J_a, E_b = ∅. The interval J_a consists of b ≥ 0 such that F(b) ≤ log 2 whereF(b) =a−b+blog_a^b.

The intervalJ_amay be calculated explicitly. Notice that x_min = 0,x_max=∞ and

c^∗(0) =a , c^∗(∞) =∞.

LetB > abe the solution of F(B) = log 2. Ifa≤log 2,J_a= [0, B]. Ifa >log 2, J_a= [A, B] where 0< A < a is the other solution ofF(A) = log 2.

Remark that if a≤log 2, the above theorem implies that lim^Nn_n^(t) may be as small as possible. But ifa >log 2, it is uniformly (in t) bounded from below by A >0.

Remark also that the variableXtakes all positive integers as values. A priori, one might assume that lim^Nn_n^(t) may take large values. But by the above theorem, it is uniformly (int) bounded by B.

Example 2. Suppose X is a Bernoulli variable with parameter p >0 (i.e.P(X= 1) =p= 1−P(X= 0)). Then

ϕ(t) = 1−p+p e^t, c(t) = log(1−p+p e^t) . Letb=c⁰(t) = _1−p+pe^pet t. That means t= log^b(1−p)_p(1−b). We have

c^∗(b) = t c⁰(t)−c(t) = blogb

p+ (1−b) log1−b 1−p . Thus we get

Theorem 5. SupposeX is a Bernoulli variable with parameter 0< p <1.

Then there is an intervalI_p such that for b∈I_p, dimE_b = 1− 1

log 2

"

b logb

p + (1−b) log1−b 1−p

#

a.s. ;

for b6∈Ip,E_b =∅. The interval Ip consists of 0≤b≤1 such that F(b)≤log 2 whereF(b) =b log_p^b + (1−b) log_1−p^1−b.

The interval I_p may be calculated as follows. Notice first that x_min = 0, x_max= 1 and

c^∗(0) = log 1

1−p, c^∗(1) = log1 p .

If p = ¹₂, I_p = [0,1]. If p > ¹₂, I_p = [A,1] where 0< A < p is the solution of F(A) = log 2; if p < ¹₂, I_p = [0, B] where p < B <1 is the solution of F(B) = log 2.

Notice that if p < ¹₂, lim sup^Nn_n^(t) ≤ B (∀t ∈ D) for some B < 1; if p > ¹₂, lim inf^Nn_n^(t) ≥A (∀t∈D) for some A >0.

Finally we remark that the condition √

nlog logn = o(s_n) in Theorem 1 is not always necessary. Consider the Bernoulli covering with 0< p <1/2. Let

ξ_n = log µ1−p

p (s_n−s_n−1)

¶ .

Notice thatξ_n→ −∞because ofs_n−s_n−1=o(1). Consider the random measure Qλdefined by

Wfn= e^ξkX ϕ(ξ_k) .

It may be checked that the Peyri`ere measure Q is well defined and dimQλ = 1−log_21−p¹ (by Lemma 2 and Lemma 3). Notice thatX_t1,...,tk= 0 or 1. We have

E^QX_t1,...,tk = E^QX_t²_1,...,tk = EX_t1,...,tkW_t1,...,tk = c⁰(ξ_k) . It follows that the variance

Var_QX_t1,...,tk = c⁰(ξ_k)−c⁰(ξ_k)² . Since

c⁰(t) = pe^t

1−p+p e^t = p

1−pe^t+O(e^2t) (t→ −∞) , we have

EQX_t1,...,tk = Var_QX_t1,...,tk = s_k−s_k−1+O((s_k−s_k−1)²) . Sinces_n−s_n−1=o(1), we have

Xn k=1

(s_k−s_k−1)² = o(s_n) .

By using the law of the iterated logarithm,Q-almost everywhere we have Nn(t) ∼ p

1−p Xn k=1

e^ξk = Xn k=1

(s_k−s_k−1) = sn .

Thus for the Bernoulli covering with 0 < p < 1/2, for any sequence such that sn−sn−1 =o(1) we have a.s.

dimE_0,s = 1−log₂ 1

1−p = 1−c^∗(0) log 2 .

ACKNOWLEDGEMENT – The authors thank Professor A.H. Dooley for his careful reading and linguistic suggestions.

REFERENCES

[B] Biggins, J.D. – Chernoff’s theorem in the branching random walk, J. Appl.

Prob., 14 (1977), 630–636.

[BP] Benjamini, I. and Peres, Y. – Tree-indexed random walks and first passage percolation,Probab. Th. Rel. Fields,98 (1994), 91–112.

[D] Dvoretzky, A. –On covering a circle by randomly placed arcs,Pro. Nat. Acad.

Sci. USA, 42 (1956), 199–203.

[E] Ellis, R.S. – Entropy, Large Deviation and Statistical Mechanics, Springer- Verlag, 1985.

[F1] Fan, A.H. – Sur certains processus de naissance et de mort, C.R. Acad. Sci.

Paris, S´er. I,310 (1990), 441–444.

[F2] Fan, A.H. – Sur les dimensions de mesures,Studia Math., 111 (1994), 1–17.

[F3] Fan, A.H. –How many intervals cover a point in Dvoretzky covering?, submitted to Israel J. Math..

[FK] Fan, A.H. andKahane, J.P. – Raret´e des intervalles recouvrant un point dans un recouvrement al´eatoire, Ann. Inst. Henri Poincar´e, 29(3) (1993), 453–466.

[K1] Kahane, J.P. – Sur le mod`ele de turbulence de Benoˆıt Mandelbrot,C. R. Acad.

Sci. Paris, 278 (1974), 621–623.

[K2] Kahane, J.P. – Some Random Series of Functions, Cambridge University Press, 1985.

[K3] Kahane, J.P. –Positive martingales and random measures,Chinese Ann. Math., 8B1 (1987), 1–12.

[K4] Kahane, J.P. –Multiplications al´eatoires et dimensions de Hausdorff,Ann. Inst.

H. Poincar´e, 23 (1987), 289–296.

[K5] Kahane, J.P. – Produits de poids al´eatoires ind´ependants et applications, in

“Fractal Geometry and Analysis” (J. B´elair and S. Duduc, Eds.), Kluwer Acad.

Publ., 1991, 277–324.

[K6] Kahane, J.P. – Random coverings and multiplicative processes, in “Fractal Ge- ometry and Stochastics II” (Ch. Bandt, S. Graf and M. Z¨ahle, Eds.), Progress in Probability, vol. 46, Birkh¨auser, 2000.

[KP] Kahane, J.P.andPeyri`ere, J. – Sur certaines martingales de Benoˆıt Mandel- brot,Advances in Math., 22 (1976), 131–145.

[L] Lyons, R. – Random walks and percolation on trees, Ann. Probab., 18 (1990), 931–958.

[LP] Lyons, R. and Pemantle, R. – Random walks in a random environment and first passage percolation on trees,Ann. Probab., 20 (1992), 125–136.

[M1] Mandelbrot, B.B. – Multiplications al´eatoires it´er´ees et distributions invari- antes par moyenne pond´er´ee al´eatoire, C. R. Acad. Sci. Paris, S´er. I,278 (1974), 289–292 and 355–358.

[M2] Mattila, P. –Geometry of Sets and Measures in Euclidean Spaces, Fractals and Rectifiability, Cambridge University Press, 1995.

[PP] Pemantle, R. and Peres, Y. – Critical random walk in random environment on trees,Ann. Probab., 23 (1995), 105–140.

[S] Shepp, L. – Covering the circle with random arc, Israel J. Math., 11 (199-72), 163–170.

Ai Hua Fan

D´epartement de Math´ematiques et Informatique, Universit´e de Picardie Jules Verne 33, Rue Saint Leu, 80039 Amiens Cedex 1 – FRANCE

E-mail: [email protected] and

Jean Pierre Kahane

Analyse harmonique, Universit´e de Paris Sud 91405 Orsay Cedex – FRANCE E-mail: [email protected]