Kenneth S Alexander

Quentin Berger
email: quentin.berger@upmc.fr

Local asymptotics for the first intersection of two independent renewals

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

1.1. Setting of the paper. We assume that there exist α, α 0 and slowly varying functions ϕ, ϕ such that (1.1)

P(τ 1 = n) = ϕ(n) n -(1+α) , P(σ 1 = n) = ϕ(n) n -(1+ α) .
(As mentioned above, τ and σ are non-delayed, if not specified otherwise.) With no loss of generality, we assume that α α. We define µ n := E[τ 1 ∧ n] and µ n := E[σ 1 ∧ n] the truncated means, and also E[τ 1 ] = µ = lim n→∞ µ n ∞, and similarly µ = lim n→∞ µ n .

The assumption (1.1) is very natural, and is widely used in the literature (for example, once again in pinning models). It covers in particular the case of the return times τ = {n , S 2n = 0}, where (S n ) n 0 is the simple symmetric nearestneighbor random walk on Z d (see e.g. [8, Ch. III] for d = 1, [START_REF] Jain | The range of random walk[END_REF]Thm. 4] for d = 2 and [6, Thm. 4] for d = 3), or the case τ = {n , S n = 0} where (S n ) n 0 an aperiodic random walk in the domain of attraction of a symmetric stable law, see [START_REF] Kesten | Ratio Theorems for Random Walks II[END_REF]Thm. 8].

In Section 2, we recall the strong renewal theorems for τ and σ under assumption (1.1) (from [START_REF] Alexander | Renewal theory with index 0[END_REF][START_REF] Doney | One-sided local large deviation and renewal theorems in the case of an infinite mean[END_REF][START_REF] Erickson | Strong renewal theorems with infinite mean[END_REF] in the recurrent case, [START_REF] Giacomin | Random polymer models[END_REF]App. A.5] in the transient case), as well as newer reverse renewal theorems (from [START_REF] Alexander | Renewal theory with index 0[END_REF]). We collect the results when τ is recurrent in the following table, denoting r n := P(τ 1 > n), and we refer to (2.1) for the transient case.

α 1 α ∈ (0, 1) α = 0

P(n ∈ τ ) n→∞ ∼ µ n -1 α sin(πα) π n -(1-α) ϕ(n) -1 ϕ(n) n r 2 n
Table 1. Asymptotics of the renewal mass function if τ is recurrent, and has inter-arrival distribution P(τ 1 = n) = ϕ(n)n -(1+α) with α 0.

From Table 1 and (2.1), the renewal mass function of ρ satisfies (1.2)

P(n ∈ ρ) = P(n ∈ τ )P(n ∈ σ) = ψ * (n) n -θ *
for some θ * 0 and slowly varying function ψ * (n). For example, if both τ and σ are recurrent we have

(1.3) θ * = 2 -α ∧ 1 -α ∧ 1;
if also α, α ∈ (0, 1), then ψ * is a constant multiple of 1/ϕ ϕ. If instead both τ and σ are transient then θ * = 2 + α + α. Note that ρ is transient for θ * > 1 and recurrent for θ * < 1. Recalling that α α, if we define (1.4)

α * =      α if ρ is recurrent and α 1, 1 -θ * if ρ is recurrent and α < 1, θ * -1 if ρ is transient,
then, based on Theorem 2.1 in the transient case and Table 1 in the recurrent case, we expect P(ρ 1 = n) to be expressed as n -(1+α * ) multiplied by a slowly varying function.

Observe that the renewal function of ρ, defined as

U * n := n k=0 P(n ∈ ρ),
is always regularly varying, with exponent α * = 1 -θ * in the recurrent case and 0 in the transient case.

Our goal is to derive from (1.1) the local asymptotics of the inter-arrival distribution, that is, the asymptotics of P(ρ 1 = n). For general renewal processes ρ these asymptotics should not be uniquely determined by the asymptotic behavior of the renewal mass function (1.2) (which is known is our case), but the extra structure given by ρ = τ ∩ σ under (1.1) makes such determination possible.

Remark 1.1. For ρ to be recurrent, it is necessary that both τ and σ are recurrent, so (1.3) holds. It follows from Table 1 that ρ is recurrent if and only if one of the following also holds:

(i) α + α > 1, (ii) α, α ∈ (0, 1), α + α = 1 and n 1 1 nϕ(n) ϕ(n) = +∞, (iii) α = 0, α = 1 and n 1 ϕ(n) n r 2 n µn = +∞. 1.2. Main results.
Case of transient ρ. Since P(n ∈ ρ) is summable (with sum E(|ρ|)), we must have θ *

1. Here the following is immediate from ([2], Theorem 1.4), given below as Theorem 2.1.

Theorem 1.2. Assume (1.1), and suppose that ρ is transient. Then

P(ρ 1 = n) n→∞ ∼ 1 E(|ρ|) 2 P(n ∈ τ )P(n ∈ σ) .
Case of recurrent ρ. Here τ and σ must be recurrent, so (1.3) holds with θ * ∈ [0, 1], and

α * = 1 -θ * if α 1, α * = α if α 1.
Theorem 1.3. Assume (1.1), and suppose that ρ is recurrent. Then for α * from (1.4) (with θ * defined as in (1.3)), the following hold.

(i) If α * ∈ (0, 1) then

(1.5) P(ρ 1 > n) n→∞ ∼ sin(πα * ) π ψ * (n) -1 n -α * . (ii) If α * = 0 then (1.6) P(ρ 1 > n) n→∞ ∼ n j=1 ψ * (j) j -1 , which is slowly varying. (iii) If α * 1 then (1.7) P(ρ 1 > n) n→∞ ∼ µ n P(τ 1 > n) + µ n P(σ 1 > n).
In Theorem 1.3(iii), µ n , µ n are slowly varying since α α 1 (recall (1.4)), and they may be replaced by µ or µ if that mean is finite.

We will prove Theorem 1.3 in Sections 3-4. The cases (i) and (ii) are essentially immediate from known relations of form P(ρ 1 > n) ∼ c/U * n and are given in Section 3. Item (iii) seems to be a new result, and is treated in Section 4 via a probabilistic method. Note that in all cases, P(ρ 1 > n) is regularly varying with exponent -α * .

To obtain the asymptotics of P(ρ 1 = n) from Theorem 1.3 (in the case α * > 0), or using the weak reverse renewal Theorem 2.2 (in the case α * = 0), we only need to show that P(ρ 1 = k) is approximately constant on an interval [(1 -ε)n, n] with ε small. To that end we have the following lemma, which we will prove in Section 5.

Lemma 1.4. Assume (1.1), and suppose that ρ is recurrent. Let v n := P(ρ 1 > n) 2 P(n ∈ ρ). Then for every δ > 0, there exists some ε > 0 such that, if n is large enough we have for all k ∈ (0, εn)

(1.8) (1 -δ)P(ρ 1 = n -k) -δv n P(ρ 1 = n) (1 + δ)P(ρ 1 = n + k) + δv n .
We will see later that v n = O(P(ρ 1 = n)), so Lemma 1.4 is actually true without the δv n terms, but we will not need this improved result.

We can now state our main theorem, which we will prove in Section 6.

Theorem 1.5. Assume (1.1) with α α, and suppose that ρ is recurrent. Let α * be as in (1.4).

(i) If α * ∈ (0, 1) then

P(ρ 1 = n) n→∞ ∼ α * sin(πα * ) π ψ * (n) -1 n -(1+α * ) .
(ii) If α * = 0 then

P(ρ 1 = n) n→∞ ∼ n k=1 ψ * (k) k -2 ψ * (n) n .
(iii) If α * 1 then

P(ρ 1 = n) n→∞ ∼ µ n P(τ 1 = n) + µ n P(σ 1 = n) n→∞ ∼ µ n ϕ(n) + µ n ϕ(n)n α-α n 1+α * .
As in Theorem 1.3, in (iii), µ n , µ n may be replaced by µ or µ if that mean is finite. We now illustrate this theorem with some subcases, using Table 1.

1. If τ, σ are recurrent with α, α ∈ (0, 1) and α + α > 1, then ρ is recurrent with α * = α + α -1 ∈ (0, 1) and (1.9) P(ρ

1 = n) n→∞ ∼ c α, α ϕ(n) ϕ(n) n -(α+ α)
with c α, α = πα * sin(πα * ) α α sin(πα) sin(π α) .

2. If τ, σ are recurrent with α, α ∈ (0, 1),

α + α = 1 and ∞ n=1 1/nϕ(n) ϕ(n) = ∞, then ρ is recurrent, α * = 0, ψ * (n) ∼ c α, α ϕ(n) -1 ϕ(n) -1 with c α, α = α α sin(πα) sin(π α) π 2 . Therefore, (1.10) P(ρ 1 = n) n→∞ ∼ 1 c α, α n k=1 1 kϕ(k) ϕ(k) -2 1 nϕ(n) ϕ(n) .
As a special case, suppose τ = {n, S 2n = 0}, σ = {n, S 2n = 0} are the return times of independent symmetric simple random walks (SSRW) on Z.

Then α = α = 1/2 and ϕ(n) = ϕ(n) → 1 2 √ π so (1.11) P(ρ 1 = n) n→∞ ∼ π n(log n) 2 .
Rotating the lattice by π/4 shows that this is the same as the return time distribution for (S n ) n 0 the SSRW on Z 2 (the even return times: ρ = {n, S 2n = 0}). Hence (1.11) is a classical result of Jain and Pruitt [START_REF] Jain | The range of random walk[END_REF].

3. If τ is recurrent with α ∈ (0, 1), and α 1 (so µ n is slowly varying; this includes the case when µ < +∞), then α * = α and (1.12)

P(ρ 1 = n) n→∞ ∼ µ n ϕ(n)n -(1+α) n→∞ ∼ µ n P(τ 1 = n) .
1.3. Application to a coupling-related quantity. We now provide an application of Theorem 1.3.

Theorem 1.6. Let τ be a recurrent renewal process satisfying (1.1), and let u n := P(n ∈ τ ) be its renewal mass function. There exist constants c i > 0 such that (1.13)

|u n -u n-1 | c 1 u n P(ρ 1 > n)    c 2 n -1/2 ϕ(n) -1 n j=1 1 jϕ(j) 2 -1 if α = 1/2 c 2 n -α ϕ(n) -1 if α > 1/2.
Note that the right side of (1.13) is of order P(τ 1 > n) when α > 1/2. It is summable precisely when µ = E[τ 1 ] < +∞, and then, by Theorem 1.3(iii), (1.13) says |u n -u n-1 | c 3 P(τ 1 > n). This gives additional information compared to the known asymptotics

u n - 1 µ ∼ 1 µ 2 k>n P(τ 1 > k)
from [START_REF] Rogozin | An estimate of the remainder term in limit theorems of renewal theory[END_REF]. We can sum (1.13) to obtain |u n -1/µ| c 3 k>n P(τ 1 > k), which is of the right order, but we cannot obtain the proper constant 1/µ 2 . We also mention the works of Topchii [START_REF] Topchii | Derivative of renewal density with infinite moment with α ∈ (0, 1/2[END_REF][START_REF] Topchii | The asymptotic behaviour of derivatives of the renewal function for distributions with infinite first moment and regularly varying tails of index β ∈ (1/2, 1][END_REF], treating the case when τ 1 is a continuous random variable with

E[τ 1 ] = ∞ and density f (t) t→∞ ∼ ϕ(t)t -(1+α) , studying the density u(t) = ∞ k=0 f * k (t) u(t)
of the renewal function, and also u (t). Under some additional regularity conditions on f (t), letting m(t)

:= E[τ 1 ∧ t], it is proven that u (t) t→∞ ∼ α(α-1) sin(πα) π ϕ(t) -1 t -(2-α) if 0 < α < 1, 1 m(t) 2 ϕ(t) t -1 if α = 1 and E[τ 1 ] = ∞.
This is a better estimate than its analog in the infinite-mean case in Theorem 1.6, but the techniques of [START_REF] Topchii | Derivative of renewal density with infinite moment with α ∈ (0, 1/2[END_REF][START_REF] Topchii | The asymptotic behaviour of derivatives of the renewal function for distributions with infinite first moment and regularly varying tails of index β ∈ (1/2, 1][END_REF] do not appear adaptable to the discrete setting.

Proof of Theorem 1.6. The second inequality in (1.13) is a direct consequence of Theorem 1.3(iii) and Table 1, so we prove the first one. Take σ a renewal process independent from τ , with the same inter-arrival distribution, but starting from σ 0 = 1. We can couple τ and σ so that τ = σ on [ρ 1 , ∞). Then denoting the corresponding joint distribution by P 0,1 we have

|u n -u n-1 | = E 0,1 [1 {n∈τ } -1 {n∈σ} ] P 0,1 (n ∈ τ, ρ 1 > n) + P 0,1 (n ∈ σ, ρ 1 > n).
By Lemma A.1 there is a constant C 0 such that

P 0,1 (n ∈ τ, ρ 1 > n) P 0,1 (n ∈ τ )P 0,1 (ρ 1 > n/4 | n ∈ τ ) C 0 u n P 0,1 (ρ 1 > n/4),
and similarly for P 0,1

(n ∈ σ, ρ 1 > n), since u n-1 ∼ u n . Now, fix k 0 such that P(τ 1 = k 0 + 1)P(τ 1 = k 0 ) > 0,
and observe that for any x > 0

P(ρ 1 > x + k 0 ) P(σ 1 = k 0 + 1)P(τ 1 = k 0 )P 0,1 (ρ 1 > x). Since P(ρ 1 > n) is regularly varying (cf. Theorem 1.
3), it follows that there is a constant c 4 > 0 such that P 0,1 (ρ 1 > n/4) c 4 P(ρ 1 > n), and hence Theorem 1.6 follows.

1.4. Organization of the rest of the paper and idea of the proof. First of all, we recall renewal and reverse renewal theorems in Section 2, which are used throughout the paper. Sections 3-4 are devoted to the proof of Theorem 1.3. Items (i)-(ii) are dealt with using Theorem 8.7.3 in [START_REF] Bingham | Regular variations[END_REF], and our main contribution is the proof of item (iii). The underlying idea is that, in order to have {ρ 1 > n} either one of τ or σ typically makes a jump of order at least n. We decompose P(ρ 1 > n) according to the number k of steps before τ (resp. σ) escapes beyond n by a jump larger than (1 -ε)n: we find that the expected number of steps is approximately µ n (resp. µ n ), giving Theorem 1.3(iii).

Sections 5-6 contain the proof of Theorem 1.5. In Section 5, we prove Lemma 1.4 in two steps. First, we show that when ρ 1 = n, having only gaps of length δn is very unlikely ; then, given that there is, say in τ , a gap larger than δn, we can stretch it (together with associated σ intervals) by k δn at little cost: this proves that P(ρ 1 = n) ≈ P(ρ 1 = n + k). In Section 6, we conclude the proof of Theorem 1.5 by combining Lemma 1.4 with Theorem 1.3.

Background on renewal and reverse renewal theorems

We consider a renewal τ = {τ 0 , τ 1 , . . . }, with τ 0 = 0. The corresponding renewal mass function is P(n ∈ τ ), n 0.

On renewal theorems.

In what follows we assume that the inter-arrival distribution of τ satisfies (1.1).

Transient case. If τ is transient, then (see [11, App. A.5]) (2.1) P(n ∈ τ ) n→∞ ∼ 1 (p τ ∞ ) 2 P(τ 1 = n) , where p τ ∞ := P(τ 1 = +∞) ∈ (0, 1).

Recurrent case.

Here there are multiple subcases, as follows.

• If E[τ 1 ] < +∞, then the classical Renewal Theorem says (2.2)

lim n→∞ P(n ∈ τ ) = 1 E[τ 1 ]
.

• If α = 1, E[τ 1 ] = +∞, then from [7, eq. (2.4)],
(2.3)

P(n ∈ τ ) n→∞ ∼ (µ n ) -1 ,
where

µ n := E(τ 1 ∧ n) is slowly varying. • If α ∈ (0, 1) then by [5, Thm. B],
(2.4)

P(n ∈ τ ) n→∞ ∼ α sin(πα) π n -(1-α) ϕ(n) -1 .
(Note that there is a typo in [5, Eq. (1.8)].)

• If α = 0, then from [2, Thm. 1.2], (2.5)
P(n ∈ τ ) n→∞ ∼ P(τ 1 = n) P(τ 1 > n) 2 .
We recall that the results in the case of a recurrent τ are collected in Table 1.

2.2. On reverse renewal theorems. In the opposite direction, if in place of (1.1), one assumes that P(n ∈ τ ) is regularly varying with exponent 1 -α, then for 0 α < 1 the asymptotics of P(τ 1 > n) follow from [4, Thm. 8.7.3]. It is not possible in general to deduce the asymptotics of P(τ 1 = n), which need not even be regularly varying. However, in certain cases, one can recover at least some behavior of P(τ 1 = n) from that of P(n ∈ τ ) when the latter is regularly varying; we call such a result a reverse renewal theorem. Specifically, if the renewal function

U n := n k=0 P(k ∈ τ ), n ∞,
is slowly varying (as happens in the case of transient τ or α = 0), the following theorems apply.

Transient case. We write |τ | for |{τ 0 , τ 1 , . . . }|, which is geometrically distributed in the transient case, with E(|τ |) = 1/p τ ∞ . Theorem 2.1 (Theorem 1.4 in [START_REF] Alexander | Renewal theory with index 0[END_REF]). If P(n ∈ τ ) is regularly varying and τ is transient, then

P(τ 1 = n) n→∞ ∼ 1 E(|τ |) 2 P(n ∈ τ ) .
Recurrent case. If U n is growing to infinity as a slowly varying function, then we have only a weaker reverse renewal theorem corresponding to (2.5).

Theorem 2.2 (Theorem 1.3 in [START_REF] Alexander | Renewal theory with index 0[END_REF]). If P(n ∈ τ ) is regularly varying, and if U n is slowly varying, then there exists some ε n n→∞ → 0 such that

1 ε n n n k=(1-εn)n P(τ 1 = k) n→∞ ∼ (U n ) -2 P(n ∈ τ ) .
One can therefore obtain the local asymptotics of P(τ 1 = n) from this last theorem when one can show P(τ 1 = n) is approximately constant over an interval of length o(n), as done in Lemma 1.4.

Proof of Theorem 1.3(i), (ii)

In case (i) we have

U * n ∼ 1 α * ψ * (n)n α * , and in case (ii) U * n = n j=1 ψ * (j) j
which is slowly varying. Hence by [START_REF] Bingham | Regular variations[END_REF]Thm. 8.7.3], in case (i),

P(ρ 1 > n) n→∞ ∼ 1 Γ(1 -α * )Γ(1 + α * ) 1 U * n n→∞ ∼ sin(πα * ) π ψ * (n) -1 n -α * ,
and in case (ii), (3.1)

P(ρ 1 > n) n→∞ ∼ 1 U * n = n j=1 ψ * (j) j -1
.

Proof of Theorem 1.3(iii)

For α * 1 (i.e. α 1), we cannot extract the behavior of P(ρ 1 > n) directly from that of U * n as in Section 3, and we need a preliminary result: we prove that P(ρ 1 > n) is regularly varying and hence for any ε > 0 we have (4.1)

P(ρ 1 > εn) = O(P(ρ 1 > n)) as n → ∞.
In Section 4.1, we prove (4.1), with the help of [START_REF] Frenk | The behavior of the renewal sequence in case the tail of the waiting-time distribution is regularly varying with index -1[END_REF]. In Section 4.3, we prove an upper bound for P(ρ 1 > n). Finally, in Section 4.4, we prove the corresponding lower bound. 4.1. Proof of (4.1). A sequence {u n } is said to be in the de Haan class Π if there exists a slowly varying sequence n such that for all λ > 0,

u λn -u n n → log λ as n → ∞.
We write RVS -α for the set of regularly varying sequences of index -α. We can state the results of Frenk [START_REF] Frenk | The behavior of the renewal sequence in case the tail of the waiting-time distribution is regularly varying with index -1[END_REF] as follows.

Proposition 4.1 ([10], main theorem and Lemma 4). Let ν be a renewal process, and denote u n = P(n ∈ ν). Then, we have

(4.2) P(ν 1 > n) ∈ RVS -1 ⇔ u n ∈ Π .
Moreover, for any α > 1, denoting m = E[ν 1 ] < +∞, we have

(4.3) P(ν 1 > n) ∈ RVS -α ⇔ u n - 1 m ∈ RVS 1-α ,
and each implies that

(4.4) u n - 1 m n→∞ ∼ 1 m 2 (α -1) nP(ν 1 > n) .
Using Proposition 4.1, we prove that P(ρ 1 > n) is regularly varying with exponent -α, as follows, yielding (4.1).

If α = α = 1, then Proposition 4.1 tells that the slowly varying sequences u n = P(n ∈ τ ), u n = P(n ∈ σ) are both in Π, with some corresponding slowly varying sequences n , n . (One expects n ∼ ϕ(n) but we do not have or need proof of this.) Therefore, letting L n := n u n + n u n , the product sequence P(n ∈ ρ) = u n u n satisfies

u λn u λn -u n u n L n = u λn u n u λn -u n n n u n L n + u λn -u n n n u n L n n→∞ → log λ (4.5)
for all λ > 0, so the product sequence is in Π. Applying Proposition 4.1 again, we see that P(ρ 1 > n) is regularly varying with index -1.

If α = 1, α > 1, then {u n } is in Π (with some corresponding slowly varying sequence n ), and u n -1 µ is regularly varying with index 1 -α. Hence,

u λn u λn -u n u n µ -1 n = u λn µ -1 u λn -u n n + u n u λn -u n µ -1 n n→∞ → log λ,
where we used that u λn -u n is in RVS 1-α so that the second term in the sum goes to 0 (since u n / n is regularly varying with index 0). Hence P(n ∈ ρ) = u n u n is in Π, and applying Proposition 4.1, we get that P(ρ 1 > n) is regularly varying with index -1.

If 1 < α α, then using Proposition 4.1, we get that

u n u n - 1 µ µ = 1 µ + 1 + o(1) µ 2 (α -1) nP(τ 1 > n) 1 µ + 1 + o(1) µ 2 (α -1) nP(σ 1 > n) - 1 µ µ = 1 + o(1) µµ 2 ( α -1) nP(τ 1 > n) + 1 + o(1) µ µ 2 ( α -1) nP(σ 1 > n), (4.6)
and therefore u n u n -1 µ µ ∈ RVS 1-α . Applying Proposition 4.1 again, we get that P(ρ 1 > n) is regularly varying with index -α , and so (4.1) is proven. Proposition 4.1 and (4.6) further give that

P(ρ 1 > n) = (1 + o(1)) 1 n (µ µ) 2 (α -1) u n u n - 1 µ µ = (1 + o(1)) µP(τ 1 > n) + (1 + o(1))µ α -1 α -1 P(σ 1 > n) (4.7)
The second term is negligible compared to the first if α > α > 1, so this proves Theorem 1.3(iii) when 1 < α α.

We will present the rest of our proof of Theorem 1.3 in the whole range 1 α α even though it is now needed only for α = 1; this adds no complexity. The advantage is that it is a more probabilistic approach, in that we use Proposition 4.1 only to get the regular variation of P(ρ 1 > n), and avoid using the un-probabilistic (4.4) (with ν = ρ) to estimate P(ρ 1 > n) as in (4.7). The method also provides an interpretation of the terms µ n , µ n appearing in Theorem 1.3(iii). 4.2. Some useful preliminary lemmas. Before we prove Theorem 1.3(iii), we need two technical lemmas. Lemma 4.2. Let τ, σ be independent renewal processes, suppose ρ = τ ∩ σ is recurrent with E(σ 1 ) < ∞, and let K := min{k 1 : τ k ∈ σ}. Then E(K) = E(σ 1 ).

Proof Since P(n ∈ ρ) = P(n ∈ τ )P(n ∈ σ), the renewal theorem gives (4.8) E(ρ 1 ) = E(σ 1 )E(τ 1 ).

Let K 1 , K 2 , . . . be i.i.d. copies of K and let

S m := K 1 + • • • + K m .
Then τ Sm has the distribution of ρ m , so using (4.8),

τ Sm m → E[ρ 1 ] = E[τ 1 ]E[σ 1 ] a.s., and
τ Sm m = τ Sm S m S m m → E[τ 1 ]E[K] a.s.,
and the lemma follows. Write P x,y (•) for P(• | τ 0 = x, σ 0 = y), and write E x,y the corresponding expectation.

Lemma 4.3. Assume (1.1), and suppose ρ is recurrent and α * > 0 (equivalently, α + α > 1.) Given η > 0, provided δ is sufficiently small we have for large n and all 0 x δn:

(4.9) P -x,0 (ρ ∩ [0, n] = ∅) < η .
If also α 1, then the same is true with δ > 0 arbitrary. The analogous results with τ, σ interchanged hold as well.

Proof Fix x δn and let

N := |ρ ∩ [0, n]|. Then P -x,0 (ρ ∩ [0, n] = ∅) = P -x,0 (N = 0) and E -x,0 (N | N 1) U * n , so (4.10) P -x,0 (N = 0) = E -x,0 (N | N 1) -E -x,0 (N ) E -x,0 (N | N 1) U * n -E -x,0 (N ) U * n while U * n -E -x,0 (N ) = n j=0 P(j ∈ σ) P(j ∈ τ ) -P(j + x ∈ τ ) . (4.11)
Since P(j ∈ τ ) is regularly varying, given η > 0, there exists A (large) such that for δ > 0, for n large we have for all x δn and Aδn j n that (4.12) P(j ∈ τ ) -P(j

+ x ∈ τ ) η 2 P(j ∈ τ ) .
Since U * k is regularly varying, with positive index since α * > 0, if δ, and therefore Aδ, is sufficiently small then for large n we have U * Aδn η 2 U * n . With (4.11) this gives that for large n,

(4.13) U * n -E -x,0 (N ) U * Aδn + η 2 U * n ηU * n .
With (4.10), this proves (4.9) for large n.

Now consider α 1, meaning P(k ∈ τ ) is slowly varying. Given η > 0, for any δ > 0 we can choose A (small this time) so that U * Aδn η 2 U * n for large n. Inequality (4.12) holds for all j Aδn and x δn, for n large, so (4.13) is valid and (4.9) follows.

Upper bound for

P(ρ 1 > n). Let us fix ε > 0. Let us call a gap τ k -τ k-1 or σ k -σ k-1 long if it exceeds (1 -2ε
)n; the starting and ending points of such a gap are τ k-1 , τ k or σ k-1 , σ k . Let S be the first starting point of a long gap in τ or σ, and let T be the ending point of the gap that starts at S. (To make things well-defined, if both τ and σ have long gaps starting at S, then we take T to be the first endpoint among these two gaps.) Then

P(ρ 1 > n) P(ρ 1 > n, σ ∩ [εn, (1 -ε)n] = ∅, τ ∩ [εn, (1 -ε)n] = ∅) + P(ρ 1 T ). (4.14)
For fixed n, we let τ1 have the distribution of τ 1 given τ 1

(1 -2ε)n, and similarly for σ1 . Let τ and σ be renewal processes with gaps distributed as τ1 and σ1 , respectively, and let K := min{k 1 : τ k ∈ σ} and K := min{k 1 : τk ∈ σ}. Then, we have

P(ρ 1 T, S ∈ τ ) = k 0 P K > k, τ i -τ i-1 (1 -2ε)n for all i k, τ k+1 -τ k > (1 -2ε)n, σ i -σ i-1 (1 -2ε)n for all i with σ i-1 τ k k 0 P( K > k)P(τ 1 > (1 -2ε)n) = E[ K]P(τ 1 > (1 -2ε)n). (4.15) From Lemma 4.2 we have E[ K] = E(σ 1 | σ 1 (1 -2ε)n) µ n .
Thus for large n we have

P(ρ 1 T, S ∈ τ ) (1 -3ε) -α µ n P(τ 1 > n).
A similar computation holds for P(ρ 1 T, S ∈ σ) so we have for large n:

(4.16) P(ρ 1 T ) (1 -3ε) -α { µ n P(τ 1 > n) + µ n P(σ 1 > n)} .
We now need a much smaller bound for the first term on the right side of (4.14). Define U := min τ ∩ (εn, ∞) and V := min σ ∩ (εn, ∞). Then

P ρ 1 > n, σ ∩ (εn, (1 -ε)n) = ∅, τ ∩ (εn, (1 -ε)n) = ∅, U < V u<v,u,v∈(εn,(1-ε)n) P(ρ 1 > εn, U = u, V = v)P u-v,0 (ρ 1 > εn). (4.17)
We may now apply Lemma 4.3 for the last probability. Fix η > 0. Then, since α α 1 for n large enough, P -x,0 (ρ 1 > εn) < η for all 0 x n. (4.18) Therefore, summing over u, v, the right side of (4.17) is bounded by ηP(ρ 1 > εn, U < V ), and a similar bound holds when U > V . Hence, combining this with with (4.14) and (4.16), we get that

(4.19) P(ρ 1 > n) (1 -3ε) -α { µ n P(τ 1 > n) + µ n P(σ 1 > n)} + ηP(ρ 1 > εn) .
Now we may use (4.1) to control the last term: we finally get that, provided η is small enough, for large n, (4.20)

P(ρ 1 > n) (1 + 4 αε) { µ n P(τ 1 > n) + µ n P(σ 1 > n)} .

4.4.

Lower bound for P(ρ 1 > n). We use a modification of our earlier truncation.

Fix n and, analogously to τ , σ, let τ and σ be renewal processes with gaps τ i -τ i-1 = (τ i -τ i-1 )∧(n+1) and σ i -σ i-1 = (σ i -σ i-1 )∧(n+1), respectively, and let ρ = τ ∩ σ and K := min{k 1 : τ k ∈ σ}. We call a gap in τ or σ large if its length is n + 1.

Let [S τ , T τ ] and [S σ , T σ ] be the first large gaps in τ and σ respectively, and let J τ and J σ be the number of large gaps in τ and σ respectively before time ρ

(n)

1 . Observe that (4.21) P(ρ 1 > n) = P( ρ 1 > n) P(J τ 1) + P(J σ 1) -P(J τ 1, J σ 1).

We claim that (4.22)

P(J τ 1) (1 -o(1))E[J τ ] as n → ∞ and (4.23) P(J τ 1, J σ 1) = o (P(J τ 1) + P(J σ 1)) as n → ∞.
Assuming (4.22) and (4.23), we have (4.24)

P(ρ 1 > n) (1 -o(1)) E[J τ ] + E[J σ ] .
Then using Lemma 4.2 to get

E[ K] = E[ σ 1 ] = µ n+1 we obtain E[J τ ] k 0 P τ k+1 -τ k > n, K > k = E[ K]P(τ 1 > n) = µ n+1 P(τ 1 > n), (4.25)
and similarly for E[J σ ]. With (4.24) this shows that (4.26)

P(ρ 1 > n) (1 -o(1)) { µ n P(τ 1 > n) + µ n P(σ 1 > n)} .
This and (4.20) prove Theorem 1.3(iii).

It remains to prove (4.22) and (4.23). We begin with (4.23). We write

P(J τ 1, J σ 1) = P(J τ 1, J σ 1, S τ < S σ ) + P(J τ 1, J σ 1, S τ > S σ ), (4.27)
and we control both terms separately. On the event {S τ < S σ }, we decompose over the first σ renewal in the interval (S τ , T τ ), to obtain that (4.28) P(J τ 1, J σ 1, S τ < S σ ) P(J τ 1) × sup x∈(0,n] P x,0 (J σ 1) .

From Lemma 4.3 we have that for any η > 0, for n large enough, for all 1 x n/2, (4.29) P x,0 (J σ 1) P x,0 (ρ 1 n/2) η .

If x ∈ (n/2, n], then we decompose over the first σ renewal in the interval [x/2, x) if it exists, to get (4.30) P x,0 (J σ 1)

P(σ ∩ [x/2, x) = ∅) + sup y∈[1,x/2]
P y,0 (J σ 1) .

The last sup in bounded as in (4.29). For the first probability on the right, using the renewal theorem when α > 1 and [START_REF] Erickson | Strong renewal theorems with infinite mean[END_REF] when α = 1, we get that there is a constant c 5 such that

P(σ ∩ [x/2, x) = ∅) x/2 k=1 P(k ∈ σ)P(σ 1 > x/2) c 5 x µ x ϕ(x)x -α → 0 as x → ∞.
The convergence to 0 is straightforward when α > 1, and uses that ϕ(x)/µ x → 0 as x → ∞ when α = 1 (see for example Theorem 1 in [9, Ch. VIII, Sec. 9]). It follows that the sup in (4.28) approaches 0 as n → ∞. The second probability on the right side of (4.27) is handled similarly, and this proves (4.23).

We now turn to (4.22). We show that for any η > 0, we can take n large enough so that for any j 1, (4.31) P(J τ j + 1) ηP (J τ j) .

This easily gives that E [J τ ] = j 1 P(J τ j)

1 1-η P(J τ 1), which is (4.22).

To prove (4.31), we denote T τ ), we get, similarly to (4.28) P(J τ j + 1) P (J τ j) × sup x∈(0,n] P 0,-x (J τ 1)

P (J τ j) sup x∈(0,n] P 0,-x (ρ 1 n + 1) η P (J τ j) ,
where the last inequality is valid provided that n is large enough, thanks to Lemma 4.3. This completes the proof of (4.22), and thus also of Theorem 1.7(iii).

Proof of Lemma 1.4: Stretching of gaps

By assumption ρ is recurrent, and we need to show that when n is large P(ρ 1 = n) ≈ P(ρ 1 = n + k) for all k ∈ (0, εn), with ε 1. The idea is to take the set of trajectories of τ and σ such that ρ 1 = n, and to stretch them slightly so that ρ 1 = n + k, see Figure 1. In Section 5.1, we prove that for some δ > 0, conditioned on ρ 1 = n, the largest gap of τ and σ in [0, n] is larger than δn with high probability; see Lemma 5.1. Assume that it is a τ -gap, and that it has length m. Then, in Section 5.2, we show that for ε δ we can stretch this τ -gap by k εn m, and stretch σ inside this τ -gap by the same k, without altering the probability significantly.

σ τ 0 ρ 1 = n τ i -τ i-1 = m δn p t 1 t 2 t 3 j Figure 1.
How to "stretch" trajectories, to go from ρ 1 = n to ρ 1 = n + k : we identify the largest gap in τ (which is larger than δn with great probability, see Lemma 5.1) and we stretch it by k, while at the same time stretching one of the three associated σ-intervals (the largest of t 1 , t 2 , t 3 ). See the proof of Lemma 5.2 for more detailed explanations.

5.1. Probability of having a large gap. Denote by A δ the event that there is a gap (either in σ or τ ) longer than δn:

(5.1)

A δ := ∃ i : τ i -τ i-1 > δn , τ i n or σ i -σ i-1 > δn , σ i n .
We will show that A c δ contributes only a small part of {ρ 1 = n}. Recall that v n = P(ρ 1 > n) 2 P(n ∈ ρ) .

Lemma 5.1. Assume (1.1). There exist c 6 > 0 and δ 0 such that if δ ∈ (0, δ 0 ), then for n sufficiently large,

P ρ 1 = n ; A c δ e -c 6 /δ v n .
Proof On the event {ρ 1 = n} ∩ A c δ , all τ and σ gaps are smaller than δn, and therefore all blocks of length at least δn are visited by both τ and σ. We control probabilities in each third of [0, n] separately. To that end, define τ = max τ ∩ (0, n/3), σ = max σ ∩ (0, n/3), and define events (5.2)

G 1 : τ ∩ σ ∩ (0, n/8) = ∅, G 2 : τ ∩ σ ∩ [n/3, 2n/3] = ∅, G 3 : τ ∩ σ ∩ (7n/8, n) = ∅, D δτ : τ i -τ i-1 δn for all i with [τ i-1 , τ i ] ∩ [n/3, 2n/3] = ∅, D δσ : σ i -σ i-1 δn for all i with [σ i-1 , σ i ] ∩ [n/3, 2n/3] = ∅, L 1 : τ , σ ∈ (n/4, n/3). Assuming δ < 1/12, we have A c δ ⊆ D δτ ∩ D δσ ⊆ L 1 . End thirds. By Lemma A.1, there exists C 0 such that max i,j∈(n/4,n/3) P G 1 | τ = i, σ = j) = max i,j∈(n/4,n/3) P G 1 | i ∈ τ, j ∈ σ) C 0 P(G 1 ). (5.3) It follows that P(ρ 1 =n, A c δ | n ∈ ρ) P G 1 ∩ G 2 ∩ G 3 ∩ D δτ ∩ D δσ n ∈ ρ = P (G 1 | G 2 ∩ G 3 ∩ D δτ ∩ D δσ ∩ {n ∈ ρ}) P (G 2 ∩ G 3 ∩ D δτ ∩ D δσ | n ∈ ρ) = E P(G 1 | τ , σ ) G 2 ∩ G 3 ∩ D δτ ∩ D δσ ∩ {n ∈ ρ} × P (G 2 ∩ G 3 ∩ D δτ ∩ D δσ | n ∈ ρ) C 0 P(G 1 )P (G 2 ∩ G 3 ∩ D δτ ∩ D δσ | n ∈ ρ) . (5.4)
Symmetrically we obtain

P G 2 ∩ G 3 ∩ D δτ ∩ D δσ n ∈ ρ C 0 P(G 3 )P G 2 ∩ D δτ ∩ D δσ n ∈ ρ (5.5) so, using Theorem 1.3, P(ρ 1 = n, A c δ | n ∈ ρ) C 2 0 P(ρ 1 n/8) 2 P G 2 ∩ D δτ ∩ D δσ n ∈ ρ c 7 P(ρ 1 > n) 2 P G 2 ∩ D δτ ∩ D δσ n ∈ ρ . (5.6)
Middle third. We need to bound the last probability in (5.6). We divide the interval [n/3, 2n/3] into blocks B i = [a i-1 , a i ] of length Aδn where A is a (large) constant to be specified. We denote by d δτ : τ j -τ j-1 δn for all j with τ j-1 ∈ B

i , D (i) δσ : σ j -σ j-1 δn for all j with σ j-1 ∈ B where for last inequality we used that ϕ(n) n α-1 µn → 0 as n → ∞ (since ϕ(n)/µ n → 0 when α = 1), and similarly ϕ(n) n α-1 µn → 0. The claim (6.1) is now proved. For δ sufficiently small, applying Lemma 1.4 and (6.1) we get that for n large and c 13 = c 10 + 1, P(ρ 1 = n) (1 -c 13 δ)A - n (δ 3 ) . (6.4) Similarly, we get (6.5) P(ρ 1 = n) (1 + c 13 δ)A + n (δ 3 ) . If α * = 0, as with (6.2) it follows easily from Theorem 2.2 that for large n we have A - n (δ 3 ) (1 -δ)(U * n ) -2 P(n ∈ ρ) and A + n (δ 3 ) (1 + δ)(U * n ) -2 P(n ∈ ρ), and then part (ii) of the theorem follows from (6.4) and (6.5).

If α * ∈ (0, 1), then by Theorem 1.3(i), when δ is small we have for large n

A - n (δ 3 ) (1 -δ) α * sin(πα * ) π ψ * (n) -1 n -(1+α * ) , A + n (δ 3 ) (1 + δ) α * sin(πα * ) π ψ * (n) -1 n -(1+α * ) ,
and again part (i) of the theorem follows from (6.4) and (6. We split this sum into j n/2 and j > n/2.

For j n/2, we use that P(k ∈ τ ) is regularly varying and n -j n/2, to bound the corresponding part of the sum in (A. Here for α = 0 we used (2.5), and for α > 0 we used the regular variation of P(n ∈ τ ). This completes the proof of (A.1).

  the jth large gap in τ . Then, decomposing over the first σ renewal in the interval [T

  τ the first and last renewals, respectively, of τ in B i , and similarly for d(i) σ , f (i) σ . Let B i, := [a i-1 , a i-1 + δn] and B i,r := [a i -δn, a i ]. On the event D δτ ∩ D δσ , we have d (i) τ , d (i) σ ∈ B i, and f (i) τ , f (i) σ ∈ B i,r . Let B (1) i := [a i-1 , a i-1 + Aδn/3] denote the first third of B i . Define events D (i)

  Using again Lemma A.1, we obtainP G 2 ∩ D δτ ∩ D δσ n ∈ ρ i 1/3Aδ max h,k∈B i, , j,m∈B i,r P τ ∩ σ ∩ B δσ d (i) τ = h, f (i) τ = j, d (i) σ = k, f (i) σ = m i 1/3Aδ max h,k∈B i, C 0 P τ ∩ σ ∩ B (1) i = ∅, D (i) δτ , D (i) δσ d (i) τ = h, d (i) σ = k . (5.7)

  [START_REF] Doney | One-sided local large deviation and renewal theorems in the case of an infinite mean[END_REF]. If α * 1, then by Theorem 1.3(iii), when δ is small we have for large nA - n (δ 3 ) (1 -δ) µ n ϕ(n) n 1+α + µ n ϕ(n) n 1+ α , A + n (δ 3 ) (1 + δ) µ n ϕ(n) n 1+α + µ n ϕ(n) n 1+ α, and part (iii) of the theorem follows once more from (6.4) and (6.5).

  1 = j + n -m|τ 1 n -m) c 15 P(2n ∈ τ ) .For j > n/2, we use that for n j > n/2 and n m 0,P(τ 1 = j + n -m | τ 1 n -m) c 16 P(τ 1 = n | τ 1 n -m) c 16 P(τ 1 = n | τ 1 n)to bound the corresponding part of the sum in (A.2) byc 16 P(τ 1 = n) P(τ 1 n) U n c 17 P(2n ∈ τ ) if α = 0; c 18 n -1 U n c 19 P(2n ∈ τ ) if α > 0.

We claim that for any η > 0, there exists A > 0 such that, for δ small, for n large enough, for all h, k ∈ [0, δn), (5.8) P h,k τ ∩ σ ∩ (0, 1 3 Aδn] = ∅ , D

δτ , D

This bounds all the probabilities on the right side of (5.7) by η, which with (5.6) and (5.7) shows that, provided η is small, 2 (C 0 η) 1/3Aδ e -c 6 /δ P(ρ 1 > n) 2 , which completes the proof of the lemma.

It remains to prove (5.8). In the case of α 1, α 1, we can drop the events D [START_REF] Alexander | Pinning a renewal on a quenched renewal[END_REF] δτ , D

δσ and (5.8) follows from Lemma 4.3. So suppose α < 1; we will show that P 0,0 (D

δτ ) for all h, k ∈ [0, δn) and the last probability is unchanged if we replace δn with 0 and 1 3 A with 1 3 A -1.) We therefore drop the subscript 0, 0 in the notation.

Let J := min{j 1 : τ j -τ j-1 > δn}, let τ1 have the distribution of τ 1 given τ 1 δn, and let τ be a renewal process with gaps distributed as τ1 . We have for k 1:

Aδn + e -kP(τ 1 >δn) . (5.9) Then we use that for any α ∈ [0, 1) there exist some c 8 , c 9 > 0 such that for large n, E[τ 1 ] c 8 ϕ(n)(δn) 1-α , and P(τ 1 > δn) c 9 ϕ(n)(δn) -α (in fact P(τ 1 > δn) ϕ(n) for α = 0.) We obtain that (5.10)

Choosing k = A 1/2 ϕ(n) -1 (δn) α with A large enough, we get that P(D

δτ ) η. This completes the proof of (5.8).

Stretching argument.

We next show that, on the event A δ , we can formalize the stretching previously described, and the cost of the stretching is small. Lemma 5.2. Assume (1.1). Given δ > 0, if n is sufficiently large, then for any k ∈ [0, 2δ 3 n] we have

Proof Fix n and denote

We will show that provided that δ is small enough, for n large enough and k ∈ [0, 2δ 3 n]

(5.11)

. The analogous statement also holds with A σ δ (n) instead of A τ δ (n); combining the two completes the proof.

To prove (5.11), define random indices

We call [τ i 0 -1 , τ i 0 ] the maximal gap, and the three intervals

are called associated σ-intervals. We decompose the probability according to the locations of this gap and the intervals: define the events

This means the maximal gap (in τ ) is from j to j + m, and σ has gaps from p to p + t 1 and from p + t 1 + t 2 to p + t 1 + t 2 + t 3 , each containing an endpoint of the maximal τ gap, see Figure 1. For the event to be nonempty, we must have m δn and

(5.12) 0 p < j < p + t 1 p + t 1 + t 2 < j + m p + t 1 + t 2 + t 3 n.

Given such indices let us define I 3 by t I = max{t 1 , t 2 , t 3 }, with ties broken arbitrarily. Consider now the map Φ k which assigns to each nonempty event A τ δ (n, j, m, p, t 1 , t 2 , t 3 ) the event

Applying Φ k corresponds to stretching the maximal gap and the longest of the associated σ-intervals by the amount k. It is easy to see that for distinct tuples (j, m, p, t 1 , t 2 , t 3 ), the corresponding events Φ k (A τ δ (n, j, m, p, t 1 , t 2 , t 3 )) are disjoint subsets of A τ δ (n + k); this just means that the relevant interval and gap lengths in the original configuration are identifiable from the stretched configuration. We claim that provided δ is small enough, for n large enough and k ∈ [0, 2δ 3 n],

(5.13) P (A τ δ (n, j, m, p, t 1 , t 2 , t 3 )) (1 + δ)P Φ k A τ δ (n, j, m, p, t 1 , t 2 , t 3 ) whenever A τ δ (n, j, m, p, t 1 , t 2 , t 3 ) = ∅. Due to the aforementioned disjointness, summing this over (j, m, p, t 1 , t 2 , t 3 ) immediately yields (5.11). To prove (5.13), note that if I = 1 then t 1 m/3, so k/t 1 6δ 2 , while k/m < 2δ 2 , so provided δ is small,

The same bound holds if I = 3. If I = 2 we have t 2 m/3, so k/t 2 6δ 2 , and provided that δ is small

The claim (5.13), and hence the lemma, now follow. We proceed with the proof of Lemma 1.4. Indeed, the second inequality in (1.8) is immediate from Lemmas 5.1 and 5.2. Also, since v n is regularly varying, Lemma 5.1 gives that for δ small, for any j ∈ (0, δ 3 n],

This and Lemma 5.2 yield that for any k ∈ (0, δ 3 n] ⊆ (0, 2δ 3 (n -k)],

(5.14)

and the first inequality in (1.8) follows.

6. Proof of Theorem 1.5

Let

We claim that, if ρ is recurrent, there is a constant c 10 > 0 such that for sufficiently small ε > 0, when n is large, (6.1) v n c 10 A ± n (ε) . It is sufficient to prove this for A + n (ε), since v n is regularly varying. Consider first α * = 0. It follows readily from (3.1) and Theorem 2.2 that for small ε, when n is large we have (6.2)

Next consider α * ∈ (0, 1). Here α * = 1 -θ * , so by Theorem 1.3, for some c 11 , for small ε we have for large n

1; here 1 α α. Since P(τ 1 = n) and P(σ 1 = n) are regularly varying, it follows from Theorem 1.3 that for ε small and large n,

Appendix A. Extension of Lemma A.2 in [START_REF] Giacomin | Marginal relevance of disorder for pinning models[END_REF] We generalize here Lemma A.2 of [START_REF] Giacomin | Marginal relevance of disorder for pinning models[END_REF], which covers α > 0, to include α = 0. The idea is essentially unchanged, but the computations are different.

Lemma A.1. Assume that P(τ 1 = k) = ϕ(k)k -(1+α) for some α 0 and some slowly varying function ϕ(•). Then, there exists a constant C 0 > 0 such that, for all sufficiently large n, for any non-negative function f n (τ ) depending only on τ ∩ {0, . . . , n}, we have

Proof We define X n to be the last τ -renewal up to n. It is sufficient to show that there exists c 14 > 0 such that for large n, for any 0 m n (A.1) P(2n ∈ τ | X n = m) c 14 P(2n ∈ τ ) .

To prove this, we write


A Lopez Aldaba

D Lopez-Torres

J Ascorbe

S Rota

C Elosua

M Lopez-Amo

F J Arregui

J.-L Auguste

R Jamier

P Roy

SnO2-MOF-Fabry-Pérot humidity optical sensor system based on fast Fourier transform technique

Keywords: Photonic crystal fiber, microstructured optical fiber, fiber sensor, humidity sensing

In this paper, a new sensor system for relative humidity measurements based on a SnO2 sputtering deposition on a microstructure (MOF) low-finesse Fabry-Pérot sensing head is presented and characterized. The interrogation of the sensing head is carried out by monitoring the fast Fourier transform phase variations of the FP interference frequency. This method is independent of the signal amplitude and also avoids the necessity of tracking the wavelength evolution in the spectrum; moreover, it is applicable networks that require narrow band sensors, allowing high multiplexation rates. The sensor is operated within a wide humidity range (20%-90% relative humidity) with a maximum sensitivity achieved of 0.14rad/%. The system uses an optical interrogator as unique active element which presents a cost-effective feature.

INTRODUCTION

Optical fiber based sensors have shown relevant capabilities to measure different parameters such as temperature, curvature, displacement, pressure, refractive index, electric field, relative humidity and gases, among others. Since the first experiments with microstructured optical fibers (MOFs), they have shown improved characteristics over conventional optical fibers and great potential for sensing applications [START_REF] Pinto | Photonic Crystal Fibers for Sensing Applications[END_REF]. Several geometries have been proposed for this kind of fiber. Among them, suspended-core MOFs present relatively large air holes surrounding a small core (typically few m of diameter) that seems to be suspended along the fiber length and maintained by small width silica bridges. Different pure silica suspended-core fibers have been applied for instance in temperature and curvature sensing [START_REF] Frazao | All Fiber Mach-Zehnder Interferometer Based on Suspended Twin-Core Fiber[END_REF] and in gas sensing [START_REF] Webb | Suspended-core holey fiber for evanescent-field sensing[END_REF].

Fiber based optical Fabry-Pérot (FP) interferometers are quite a popular sensor configuration due to their compactness, simple configuration, flexibility in tuning sensitivity and dynamic range. A fiber based FP sensor is most of the times fabricated by splicing a section of waveguide, which acts as the cavity, to a standard optical fiber, providing it with the potential for low insertion-loss and multiplexing capability. The FP cavity output signal presents an interference pattern that is a function of the length and of the refractive index of the cavity, or more precisely, the effective indices of the different modes supported by the fiber sample. FP cavities composed by MOFs are an even more common structure: a hybrid structure that used a MOF as the guiding fiber and cascade it with a hollow-core fiber and a single mode fiber (SMF), for high-temperature sensing, was demonstrated [START_REF] Choi | Miniature fiber-optic high temperature sensor based on a hybrid structured Fabry-Perot interferometer[END_REF]. Other fiber based sensors were accomplished by fusing a small length of PCF to the end of a cleaved SMF for relative humidity ranged 40%-95% RH [START_REF] Mathew | Humidity sensor based on photonic crystal fibre interferometer[END_REF] or by chemical deposition of PSP and PAH [START_REF] Hernaez | Sensitivity Enhancement of a Humidity Sensor Based on poly (sodium phosphate) and poly (allylamine hydrochloride)[END_REF].

Among optical fiber sensors, those based on nanocoatings have recently experienced a remarkable development [START_REF] Arregui | Sensors Based on Nanostructured Materials[END_REF]. Furthermore, new techniques in chemical deposition, such as sputtering [START_REF] Stowell | RFsuperimposed DC and pulsed DC sputtering for deposition of transparent conductive oxides[END_REF], allow the morphology of the deposited coatings to be controlled with high accuracy, and as a consequence, the final features (sensitivity, kinetics) of the sensor.

In this paper, a SnO2-(would it be interesting to explain a little bit here or just at the beginning of the next section how SnO2 coating is performed in order to facilitate the understanding?) hybrid-Fabry-Pérot interferometer based on a novel four-bridge dual highly coupled Y shaped cores microstructured optical fiber is presented and characterized. By monitoring the fast Fourier transform (FFT) phase variations of the PF interference frequency an experimental study of aitor.lopez@unavara.es; phone +34 948 16 9841; fax +34948 16 9720 this cavity's response with relative humidity changes, and optical power fluctuations in time is presented. This measuring method is independent of the signal amplitude and avoids the necessity of tracking the wavelength evolution in the spectrum, which simplifies the measurements.

EXPERIMENTAL SET-UP AND OPERATION PRINCIPLE

The Fabry-Pérot interferometer was fabricated by splicing a single mode fiber to ~1mm of a novel four-bridge MOF, with its end cleaved, as shown in Figure 1 a. (which process for SNO2 coating, where and what are the characteristics of the coating layer?) The fiber is composed by four big air holes divided by four thin silica bridges, approximately 900 nm thick, and presents an elongated core of 3.2µm by 1.07µm, exhibiting a double Y shape. This specific core shape can be seen as two coupled single mode guiding cores [START_REF] Lopez-Aldaba | Experimental and Numerical Characterization of a Hybrid Fabry-Pérot Cavity for Temperature Sensing[END_REF]. This specific shape provides unprecedented possibilities for interferometric sensing. The cross-section of the four-bridge MOF and its core details are presented in Figure 1 b and 1 c, respectively. It should be noticed that this equipment was originally commercialized for FBG sensors´ monitoring and allows sensors to be interrogated in real time (sampling frequency of 1Hz) [START_REF] Leandro | Real-time FFT analysis for interferometric sensors multiplexing[END_REF]. The SM125 is remotely controlled through a MATLAB software that also executes the FFT real time analysis. The sensing head was inserted into a climatic chamber where humidity ranges from 20% to 90% were applied at a constant temperature of 25ºC to evaluate its response to this magnitude.

Due to the use of the FFT phase as the sensing parameter, power constraints are not as limiting as in other techniques, allowing more sensors to be multiplexed. The MOF-FP optical fiber core was used as the substrate in a DC-Sputter deposition process (Pulsed DC Sputtering System, Nadetech Innovations) with a partial pressure of argon of 6.75×10 -2 mbar, intensity of 140 mA and voltage of 190 V. The SnO2 target 99.99% of purity was purchased from ZhongNuo Advanced Material Technology Co.

The device sensing principle consists on the interaction between the evanescent field of the guided light and the SnO2 deposition on the core lateral surfaces and on the reflective interface at the end of the FP cavity.

EXPERIMENTAL RESULTS

The output signal of the Fabry-Pérot interferometer can be seen in Figure 3. It presents an interferometric fringe pattern with a wavelength spacing of 1.6 nm (Figure 3.A). Figure 3 b) shows the FFT of the FP spectra. As a result of the periodicity of the spectra, the FFT presents a narrow set of frequencies that characterize completely the sensing head, with its main component located at 0.8375nm -1 . To measure the changes induced by the humidity changes, the phase variations of this frequency component were studied. This behavior in addition to the FFT analysis allows a number of different sensors to be multiplexed and simultaneously interrogated of just by setting correctly its spatial frequency, which is a result of the wavelength spacing and so of the length of the fiber PCF fused. In order to verify the proper operation of the SnO2-FP sensing head, the humidity-sensing performance of the sensor in the atmosphere of different RHs, with the temperature set at 25ºC, was experimentally carried out. Figure 4 a) illustrates the FP performance without any chemical deposition. It can be seen that there is an unclear tendency to follow the climatic chamber variations in humidity: sensitivity is very low and the signal is too much noisy. Therefore, the interferometer is inoperative with no deposition. The sensor performance after the chemical deposition is shown in Figure 4 b). SnO2 chemical deposition enhances its sensitivity and improves de Signal to Noise rate. Typically, the sensitivity of humidity sensors is different depending on the humidity range [START_REF] Mathew | Humidity sensor based on photonic crystal fibre interferometer[END_REF], but in our case, the sensor response shows a linear behavior in the measured humidity range (20%-90%) with a sensitivity of 0.14π rad/% RH. Two of the main characteristics of this sensing head are its speed reaction to humidity changes and its reversibility, allowing the sensor to work continuously without its replacement after saturation.

Finally, in order to probe the stability of the system, the phase variations during 200 minutes for a 40% RH and 25ºC, have been tested showing an instability of around 0.007π rad. These results are shown in Figure 5.

CONCLUSIONS

To summarize, a new sensor system for relative humidity measurements based on its interaction with a SnO2 chemical deposition on a MOF-Fabry-Pérot cavity has been proposed and experimentally demonstrated. The interrogation of the sensing head has been carried out by monitoring the FFT phase variations of one of the FP interference frequency. This method is independent of the signal amplitude and also avoids the necessity of tracking the wavelength evolution of the spectrum, which can be a handicap when noise is present and allows to multiplex several sensors. The sensor has been operated within a wide humidity range (20%-90% RH) with a maximum sensitivity achieved of 0.14rad/% RH and a phase standard deviation of 0.0043π rad. It presents linear and constant response along the entire RH range. The SnO2 MOF-FP sensor presents high-speed response, reversibility, high repeatability rate, robust and compact features, and the FFT-based interrogation technique complements the system with powerful multiplexing capabilities.

Figure 1 .

 1 Figure 1. A) MOF based Fabry-Perot interferometer, (B) the cross-section of the used four-bridge MOF and (C) the four-bridge MOF core detail.

Figure 2

 2 Figure2presents the experimental set-up used to characterize the four-bridge MOF Fabry-Pérot based sensing head and the SnO2-FP final sensor. A commercial interrogating sensor device (Smartec SM125) was used to illuminate the network and also to analyze the spectra of the signal guided through the sensor. It should be noticed that this equipment was originally commercialized for FBG sensors´ monitoring and allows sensors to be interrogated in real time (sampling frequency of 1Hz)[START_REF] Leandro | Real-time FFT analysis for interferometric sensors multiplexing[END_REF]. The SM125 is remotely controlled through a MATLAB software that also executes the FFT real time analysis. The sensing head was inserted into a climatic chamber where humidity ranges from 20% to 90% were applied at a constant temperature of 25ºC to evaluate its response to this magnitude.

Figure 2 .

 2 Figure 2. Experimental setup of the proposed system.

Figure 3 .

 3 Figure 3. (a) Optical spectra of the sensor before deposition at 25ºC and 40% humidity (room conditions) and (b) its fast Fourier transform.

Figure 4 .

 4 Figure 4. Sensor response to humidity: a) before deposition, and b) after SnO2 deposition.

Figure 5 .

 5 Figure 5. Phase fluctuations along 200 minutes for 40% and 25ºC.


Salah Eddine Elayoubi

James Roberts

Performance Evaluation of Video Transcoding and Caching Solutions in Mobile Networks

The rapid growth in demand for video streaming applications is stressing the performance of wireless access networks. To alleviate congestion, vendors currently propose devices to be placed in the operator's network that transcode videos to a lower rate in order to reduce traffic volume in case of congestion. The devices are also able to cache popular videos, both to reduce the burden of transcoding and to alleviate backhaul load. The paper proposes a model of this augmented radio access network enabling an evaluation of the performance benefits for given transcoding and caching capacities. Our results show that a gain in cell capacity of 15% can be realized with moderate transcoding and cache capacities.

I. INTRODUCTION

Video downloads represent a large and increasing proportion of the traffic handled in mobile access networks. Cisco forecasts a 69% annual growth rate for video demand with its share of traffic increasing from 53% in 2013 to more than 70% in 2018 [START_REF]Cisco. Visual networking index: Global mobile data traffic forecast update[END_REF]. This growth is stressing the performance of the wireless segment and, as any user knows, video streaming frequently suffers from stalling events that occur whenever the download rate is persistently less than the intrinsic video rate causing the playout buffer to empty.

If congestion cannot be avoided, network operators may consider it preferable to avoid stalling and other manifestations of demand overload by reducing the quality of downloaded content. Devices to perform "dynamic content optimization" are currently marketed by equipment vendors [START_REF] Nokia | Intelligent base stations[END_REF] [START_REF] Huawei | Cloud-based media storage and processing data center[END_REF]. Moreover, this function is highlighted as a use case to be considered by the recently launched Mobile-edge computing industry initiative [START_REF]Mobile-edge computing[END_REF]. Reducing image quality means reducing the traffic volume, thus alleviating congestion. From another point of view, since traffic is reduced, the required network capacity to meet user quality requirements is smaller leading to lower expenditure. The aim of the present paper is to investigate the tradeoff realized between the cost of the content optimization devices and the resulting savings in network infrastructure.

In view of the high proportion of video traffic, we restrict attention in this paper to an evaluation of the benefits of optimizing just video content. The considered devices reduce the volume of video demand, as necessary, by transcoding downloaded videos to a lower rate. The devices can also cache frequently requested items to limit the transcoding load. We consequently coin the generic name for such a device as, "video transcoder and cache" or VTC. Figure 1 shows the position of the VTC in the mobile access network. It is situated at some convenient point to act on the traffic of a number of base stations. Determining the precise location, implying the degree of traffic concentration and the device workload, is a design issue.

Other questions we address are, what capacity gain is possible through transcoding? and how should the device be dimensioned? i.e., how many videos can be transcoded in parallel and how many videos should the VTC be able to hold in its cache. It is impossible to provide definitive answers to these questions since the relative benefits of alternative solutions depend on many local parameters. Rather, we provide analytical tools to be used to evaluate relevant scenarios. These tools take account of the impact of different radio conditions, the dynamics of flow arrivals of different types, the traffic mix between these types, the distribution of video popularity and its impact on cache performance. We illustrate the use of the tools and how they can guide design and network planning decisions though a number of numerical applications.

Only certain downloads are susceptible to transcoding and the relative proportion of traffic in this category clearly significantly impacts the effectiveness of the VTC device. The current trend is towards greater proportions of content encryption reducing the potential advantage of transcoding and caching since these operations become ineffective. Nevertheless, it remains of interest to evaluate these advantages since, if they are significant, it might in fact modify the observed trends. Moreover, the emergence of so-called informationcentric networks may solve the security and commercial issues that encryption is designed to resolve.

In the next section we more completely describe the consid-ered VTC equipped mobile access network. We then proceed in Section III to build a performance model accounting for the random process of download arrivals and completions and the impact of diverse radio conditions within a cell, under the assumption that the VTC is "perfect" in always being able to supply a transcoded version of a requested video when necessary. In this section, we also propose performance criteria to be used when determining cell traffic capacity. Section IV further develops the performance model to account for limited VTC transcoding and caching capacity. The model is used in Section V to derive some numerical results illustrating possible system parameter choices and their impact on performance and, ultimately, on network traffic capacity.

II. SYSTEM DESCRIPTION

We first broadly characterize downloads into three types depending on their adaptivity. We then describe the considered VTC device before proposing a simple model of the radio link and how its spectrum is shared by concurrent downloads.

A. Traffic types

Cell downlink capacity is shared by flows of three types. Type 1 flows are video downloads that can be identified by the considered VTC device through deep packet inspection. These video downloads are subject to transcoding and are the principal object of this evaluation. The other two types constitute background traffic.

Type 2 flows consist of regular downloads of documents of various kinds like web pages, emails, pictures as well as videos that are not compressible (because they are encrypted, for example). Type 3 flows are adaptive video streaming flows. Their download rate is adjusted by the application to approximately match the currently available bandwidth. This is achieved by the application requesting the video in segments of 2 to 4 seconds, say, where each segment exists in several versions corresponding to different rates. The application selects the segment version corresponding to its evaluation of the current path available bandwidth (see [START_REF] Huang | A buffer-based approach to rate adaptation: Evidence from a large video streaming service[END_REF], for example).

B. Video transcoding and caching

The VTC can transcode and cache type 1 videos. These videos are assumed to be downloaded as fast as possible for subsequent viewing. "As fast as possible" means the download rate is determined as a fair share of cell capacity accounting for the number of competing flows and their particular radio conditions, as discussed in Section II-C below. With respect to transcoding, we envisage online and offline scenarios. In the online scenario, the original version is transcoded on-thefly and a compressed version is sent to the user. The VTC can only perform online transcoding for a limited number of videos in parallel. In the offline scenario, a compressed version is created when absent from the cache, either systematically whenever the video is requested, or just when the video is requested and the user's cell has attained a certain degree of congestion. The user triggering transcoding always receives a copy of the original version.

The VTC can cache a limited number of videos. Several options are possible.

• it caches the version requested by the operator, original or compressed, • it caches both versions systematically when either is requested and the video is not already cached, • it only ever caches the compressed version, always referring to an upstream cache or server for the original version. The adopted caching policy impacts the effectiveness of the VTC in increasing cell capacity.

The network operator determines which version of the video to download based on current cell traffic conditions. In periods of light traffic, or when the radio conditions of a requester are particularly favorable, the operator will forward the user's request for the original version. This might be found in the VTC cache or, if not, in some upstream cache or video server. Otherwise, the operator will seek to download a compressed version obtained from the cache or by online transcoding. The type of coding is determined by the operator at the start of transmission and does not change, even though the cell congestion status might evolve.

C. Download rates

We consider an isolated cell where the radio condition of a given user is assumed to remain constant for the duration of a download. Specifically, we assume a discrete set of M radio conditions (determined by the user's position relative to the base station, for instance) characterized by peak rates R i bit/s for i = 1, . . . , M . R i is the rate a mobile terminal with conditions i would get if it were alone in the cell. When the overall number of users in the cell is n, users in radio class i get rate R i /n. This is approximately the rate provided by the MAC layer of 3G and 4G cellular networks where cell capacity is shared by assigning roughly the same rate of equal length time slots to all cell users [START_REF] Bonald | Wireless downlink data channels: User performance and cell dimensioning[END_REF], [START_REF] Rong | Performance evaluation of cellular networks offering tv services[END_REF].

The operator is assumed to determine which version of a downloaded video of type 1 to request from two parameters:

• the radio condition, as determined by the peak rate R i , of the user in question, • the number n of users currently active in the cell of any type. The rate available to a new user is then R i /(n + 1) and the requested coding rate should be chosen in consequence.

Type 2 downloads naturally proceed at the current fair rate for their class, R i /n. The adaptive video streaming applications managing type 3 flows have several versions of each segment available, each corresponding to a different rate. The application in the user terminal chooses the version to request for each segment depending on its current vision of the network congestion state. Available rates vary from application to application and the algorithm used to choose the rate of each segment is typically quite complex (e.g., [START_REF] Huang | A buffer-based approach to rate adaptation: Evidence from a large video streaming service[END_REF]). As our focus is on the performance of the VTC, we adopt a simplified model of type 3 rate adjustments in the following evaluation (see Sec. III-A).

III. CELL PERFORMANCE

We propose a Markov model to characterize the population of simultaneous downloads of all types. The model is first defined here under the simplifying assumption that a compressed coding is always available for download whenever requested. We then discuss performance criteria to be used to determine the maximum per-cell load attainable. We consider the additional impact of limited VTC capacity in Section IV.

A. Markov model

We adopt a simple Markovian traffic model for the sake of tractability. We note, however, that the derived results are typically more generally valid thanks to the insensitivity properties of the underlying processor sharing system [START_REF] Bonald | Wireless downlink data channels: User performance and cell dimensioning[END_REF]. Flows of type j with radio condition i are assumed to arrive as a Poisson process of rate λ ij for i = 1, ..., M and j = 1, 2, 3.

The size of a type 1 flow depends on the video coding rate. We assume the video when played back has an exponentially distributed duration of mean τ 1 seconds and that the original and compressed coding rates are C o and C c bit/s, respectively. The amount of data to download is thus either C o τ 1 or C c τ 1 bits. We consider here that the compressed version is always available, either through online transcoding or thanks to a very large cache yielding negligible miss rates. This enables us to quantify the maximum gain in capacity attainable by the use of the VTC. We assume compressed coding is requested for a new download under condition i whenever the population of users n is greater than

R i /C o .
Each flow of type 2 requires the download of an exponentially distributed volume of mean σ 2 bits and a download with condition i proceeds at rate R i /n. To model type 3 adaptive streaming flows, we suppose their rate is adjusted continuously, exactly like type 2 flows. However, the duration of the flow is now independent of the download rate. We assume the distribution of this duration is exponential of mean τ 3 .

System state is defined by the number of flows in progress of each radio condition and each type, distinguishing the video coding rate of type 1 flows. Let a io and a ic be the number of type 1 flows with radio condition i downloading the original and the compressed version, respectively. Let b i and c i be the number of type 2 and 3 flows with radio condition i, respectively. Finally, denote by n the overall number of flows in progress, n

= M i=1 (a io + a ic + b i + c i ). Vector n = (a 1o , . . . , a M o , a 1c , . . . , a M c , b 1 , . . . , b M , c 1 , . . . , c M )
is a Markov process with the following non-zero transition rates:

• a io increases to a io + 1 at rate λ i2 if Ri n+1 ≥ C o , • a io decreases to a io -1 at rate a io Ri nCoτ1 , • a ic increases to a ic + 1 at rate λ i2 if Ri n+1 < C o , • a ic decreases to a ic -1 at rate a ic Ri nCcτ1 , • b i increases to b i + 1 at rate λ i1 , • b i decreases to b i -1 at rate b i Ri nσ2 , • c i increases to c i + 1 at rate λ i3 , • c i decreases to c i -1 at rate ci nτ3 .
The above transition rates for valid states n define a transition matrix Q and the steady state probabilities π( n) can be obtained by solving πQ = 0. This system can be readily solved numerically as long as the state space is not too large.

B. Performance criteria

We consider the following three performance metrics.

a) Compression probability: This is the probability an arriving type 1 user should be sent the compressed version. It depends on the new user's radio condition and the total number of active users in the cell. The compression probability p i c for a flow starting with radio condition i is thus

p i c = 1 - n∈S i π( n), (1)
where the summation domain n ∈ S i covers states such that

k (a ko + a kc + b k + c k + 1) < Ri
Co . b) Rate deficit probability: A rate deficit occurs if the instantaneous download rate of a type 1 flow is less than the nominal coding rate, C o or C c for original and compressed versions, respectively. It is a measure of video quality in that a flow suffering persistent rate deficit will likely experience playout stalling. This metric is chosen for the sake of tractability since it is hardly possible to compute the stalling probability for this system [START_REF] Xu | Probabilistic analysis of buffer starvation in markovian queues[END_REF].

The rate deficit probability is equal to the probability an ongoing flow shares cell capacity with a number of users greater than the threshold corresponding to its radio condition and coding version. When the system is in state n, there are a ij video users of radio class i downloading version j (original or compressed). These videos suffer rate deficit if the overall number of users n is greater than the ratio

p i d = n ( a io a io + a ic 1 {n> R i Co } + a ic a io + a ic 1 {n> R i Cc } )π( n) (2)
and the overall rate deficit probability is

p d = M i=1 n p i d . (3)
c) Cell utilization: This metric is the proportion of time the cell is actively downloading data. It is equal to 1-π( 0). A classical pragmatic criterion used to dimension cell networks is to maintain utilization below some threshold, 1-π( 0) ≤ .8, say.

IV. IMPACT OF VTC CAPACITY LIMITATIONS

We now consider the end-to-end performance realized by the VTC device accounting for the impact on the model of Section III of its finite transcoding and caching capacities.

A. Cache hit rates

The VTC device is supposed to be situated at a backhaul node as depicted in Figure 1 and processes requests from a relatively large number of cells. The cache hit rate is evaluated under the following assumptions:

• the type 1 catalogue is of size N videos,

• the VTC contains a cache of size N δ bytes and applies the least recently used (LRU) replacement policy, • the average size of a video is σ o bytes in its original coding and σ c bytes in its compressed version (

σ c /σ o = C c /C o ), • we assume N δ
σ o so that we can ignore edge effects and assume the cache is saturated if and only if n o σ o + n c σ c ≥ N δ where n o and n c represent the number of videos stored in the original and compressed versions, respectively.

• we apply the independent reference model (IRM), equivalently assuming requests for both original and compressed versions arrive as a Poisson process (see [START_REF] Fricker | A versatile and accurate approximation for lru. cache performance[END_REF], for example, for a discussion on the validity of this approximate model), • video popularity is assumed to follow a Zipf law of parameter α, i.e., the arrival rate for requests for the r th most popular video is proportional to 1/r α , • the probability p i c a compressed version is requested is given by (1), independently for all videos. To evaluate hit rates we use the Che approximation [START_REF] Che | Hierarchical web caching systems: modeling, design and experimental results[END_REF] and, more explicitly, its Gaussian approximation for Zipf popularities derived by Fricker et al. [START_REF] Fricker | A versatile and accurate approximation for lru. cache performance[END_REF]. We in fact extend the approximation somewhat to account for the different sizes of the original and compressed versions.

Let p o and p c denote the probability original and compressed versions are inserted in the cache on a request for the video (of either type). If only the requested version is cached, p c = i λ i p i c / i λ i and p o = 1 -p c where p i c is given by (1). If both versions are systematically cached,

p o = p c = 1. If only the compressed version is cached, p c = i λ i p i c / i λ i and p o = 0.
By the Che approximation, the hit rate for version j ∈ {o, c} of the r th most popular video is h (r) j = 1 -e -pj t C /r α where t C is the so-called characteristic time for a cache of size C. A straightforward extension of the arguments in [START_REF] Fricker | A versatile and accurate approximation for lru. cache performance[END_REF] shows that t N δ is asymptotically equal to βN α where β is the solution to the equation

δ = σ o 1 0 (1 -e -poβ/x α ) + σ c 1 0
(1 -e -pcβ/x α ).

In the following we need the overall hit rate for just the compressed version (cell performance does not depend on whether the original version comes from the VTC cache or an upstream server). Denoting this hit rate by h c , we have

h c = p c r h (r) c /r α r 1/r α .

B. Impact on cell performance

We now turn to the interaction between caching performance and cell performance, accounting for the fact that a requested compressed coded video is not always available as assumed in Section III. We temporarily ignore the possibility to perform on-the-fly video transcoding.

The transition rates of Section III-A remain the same except for the following:

• a ic increases to a ic + 1 at rate h c λ i2 if R i /(n + 1) < C o , • a io increases to a io +1 at rate (1-h c )λ i2 if R i /(n+1) < C o .
The overall compressed version hit rate h c is independent of the user radio condition i. Its value depends on the assumed caching policy. If both original and compressed versions are cached together, or if only the compressed version is ever cached, the value of h c does not depend on the radio model (that determines the probability the compressed version is requested). This is so because the hit rates, computed as in Sec. IV-A, do not then depend on the values of p o and p c . The hit rate does depend on the radio model when the original and compressed versions are cached independently. For this case, we apply a fixed point approximation, as follows.

We first calculate the probabilities p o and p c for each version using an initial estimate of h c . The hit rate is then calculated using the Che approximation with these relative request rates. The new value of h c is used to refine the estimates of p o and p c , and so on until convergence.

C. Limited transcoding capacity

On-the-fly transcoding improves cell performance by satisfying some requests for the compressed version of videos absent from the VTC cache. Suppose the VTC is equipped to transcode a maximum of T videos in parallel. This capacity is to be shared by a number of cells as depicted in Figure 1. We assume there are K cells and, for the sake of simplicity, that these cells have the same radio and traffic characteristics.

The system operates as follows: on detecting a new type 1 flow, the network operator decides if it should request a compressed version; if so, it checks the VTC cache and downloads the compressed version if present; if not, and if the VTC is currently transcoding less than T videos, the requested video is transcoded on-the-fly; if there is no cached copy and all transcoding capacity is already in use, the cell downloads the original version (leading to rate deficit for some ongoing flows).

Let θ(k) for k ≥ 0 be the distribution of the number of type 1 videos currently being downloaded in the compressed version. This marginal distribution is derived by summing probabilities π( n) over states n such that i a ic = k. Given k compressed version downloads, the probability that l of these are being satisfied by transcoding, for 0 ≤ l ≤ k, can be approximated by the binomial distribution with "success probability" 1 -h c . It is then straightforward to compute the mean m and variance v of the number of videos currently being transcoded. We have,

m = k≥1 k(1 -h c )θ(k), (4) v
= k≥1 k(1 -h c )(k -kh c + h c )θ(k) -m 2 . ( 5
)
We now approximate the aggregate transcoding load from K cells by a Gaussian distribution with mean Km and variance Kv. An estimate of the probability a transcoding request fails, f , is then given by the probability load exceeds capacity,

f = 1 2 erfc( T -Km √ 2Kv ) ( 6
)
where erfc is the standard error function.

Finally, for a given cell, the probability a request for a compressed type 1 video can be satisfied is given by the revised "hit rate",

h c = h c + (1 -h c )(1 -f ).
This probability must be substituted for h c in the transition rates of Sec. IV-B and applied in the fixed point approximation described therein.

V. NUMERICAL RESULTS

We present a selection of numerical results intended to illustrate the tradeoffs realized by the considered VTC device and the possibility to optimize performance by appropriate dimensioning.

A. Radio conditions and traffic data

We consider downloads in a nominal 3G system with just two distinct radio conditions: users at the cell edge have a peak rate of 5 Mbps while users at the center have a peak rate of 15 Mbps. This is clearly a crude approximation that nevertheless allows us to capture the significant impact on performance of heterogeneous radio conditions. Half of downloads are assumed to be to edge users and half to center users for all three types.

We suppose 75% of flows are video downloads of which a variable proportion is of type 1 and can be transcoded. The original rate of type 1 videos is C o = 1 Mb/s and we assume the VTC transcodes this, as necessary, bringing the rate down to C c = 0.25 Mb/s. The mean duration of these videos is τ 1 = 5 minutes. The mean size of a regular document download (type 2 flows) is σ 2 = 10 MB. The mean duration of adaptive streaming videos is τ 2 = 5 minutes. Results are plotted below in terms of the overall flow arrival rate bearing in mind that the cell load is not an independent variable because of the use of transcoding (type 1) and adaptive streaming (type 3).

B. Maximum gains from the VTC

We first assume transcoding is not limited by the capacity of the VTC, and the model presented in Section III applies. This enables an evaluation of the maximum potential capacity gain as a function of the traffic mix. Figures 2, 3 and4 plot the values of the performance criteria, compression probability, rate deficit probability and cell utilization, respectively, under the assumption that 70% of video traffic can be transcoded (i.e., is of type 1).

The results of Figure 2 show that transcoding is mainly performed for users with the worst radio conditions at the cell edge. The proportion is significant for moderate load and increases steadily with load. Figure 3 plots the rate deficit with and without transcoding, distinguishing edge and center users. Again, this performance degradation impacts only the cell edge users. For the particular configuration considered, the average rate deficit probability is reduced by half when transcoding is applied. Lastly, Figure 4 shows how cell utilization is reduced by about 15% by the use of transcoding. Note that utilization increases sub-linearly with the flow arrival rate even without transcoding due to the presence of type 3 adaptive streaming flows. The use of transcoding for type 1 accentuates this effect.

C. Cell capacity

The performance improvement brought by the use of transcoding leads to an increase in network capacity. By this we mean the network is dimensioned to meet performance targets that are reached at higher loads when the VTC is used. This implies for a given level of demand (in flows/sec/m 2 ) that the cell density can be so much smaller and the investment in infrastructure so much less. In this subsection we quantify the average gain in the capacity of one cell under the following performance thresholds:

• The proportion of users served with the compressed version should be less than 30%. We choose this value as it is commonly used as the threshold on the proportion of calls served at half-rate in a mobile telephone network. • The probability of rate deficit is limited to a maximum of 10%. This threshold is intended to ensure a sufficiently small probability of stalling in video playouts. • Cell utilization must be less than 80%. This is a threshold typically used to dimension mobile data networks. Table I presents some results illustrating the potential capacity gain for different proportions of the three types of flow. The first column corresponds to the traffic mix used in Figures 2, 3 and4 and is derived by applying the above dimensioning thresholds. It turns out that with this configuration the most severe constraint is the rate deficit probability. This limits cell capacity to 31 flows/s without transcoding, increasing by 16% to 36 flows/s with a perfect VTC. The other two columns show that this gain is naturally less significant as the proportion of type 1 flows in the traffic mix decreases. This capacity gain is to be set against the cost of the VTC. One can naturally test the impact of alternative dimensioning criteria. If the threshold on the rate deficit probability is increased to 20%, the cell capacity increases but the gain brought by transcoding remains approximately the same.

D. Impact of the cache size and the online transcoding capacity

Recall that the results above are derived assuming the compressed version is always available when requested. In this section we relax this assumption and quantify the impact of cache misses on realizable capacity gains. We first discuss h c (δN ) as a function of δ, giving the hit rate of requests for the compressed version for given cache size where the latter is expressed as a fraction of the amount of memory needed to cache the entire catalogue in the original version. We assume a catalogue size of N = 10 4 videos having a Zipf popularity distribution with exponent α = 0.8. Figure 5 plots this function for the three caching options considered in Section II-B: cache the version requested, cache both versions systematically, cache only the compressed version.

To derive the first curve on the left, we assume the probability the compressed version is requested is p c = 0.1 (cf. Fig. 2). Note the unfavorable impact of only caching the requested version. It is more effective for the hit rate of the compressed version to cache it systematically whenever either version is requested. This is because the popularity of the compressed version is otherwise 10 times less than that of the original version (since p c = .1).

More significantly, comparison with the leftmost curve shows that the cache is much more efficiently used (for our objective of alleviating congestion in the radio part) if only the compressed version is ever cached. This curve is, in fact, identical to the second (caching both versions) with the x coordinate divided by five (since

(C o + C c )/C c = 5).
To evaluate the impact of the hit rate on cell capacity, we first integrate the effects of a limited transcoding capacity. We suppose the number of cells K is equal to 100 and use the formulas of Section IV-C to determine the modified hit rate h c with h c evaluated for the option where the VTC only caches the compressed version. Our three performance criteria are then evaluated, as previously indicated.

Figures 6, 7 and 8 plot the compression probability, rate deficit probability and utilization, respectively, as functions of the relative cache size δ. The figures show one curve for each of three chosen values for the VTC transcoding capacity, 0, 10 and 20 videos in parallel.

Obviously, all three performance criteria improve as either the cache capacity or the transcoding capacity increase. More interestingly, the results of the figures suggest the maximum gains discussed in Section V-C can be attained with relatively small VTC capacities. If the transcoding capacity is 10 parallel downloads, a relative cache size of only δ = .025 (i.e., 10% of the entire catalogue in compressed coding) is sufficient. Alternatively, with a coding capacity of 20, it is unnecessary to equip the VTC with a cache (in fact, a transcoding capacity of only slightly more than 10 is sufficient). On-the fly transcoding would only be unnecessary if the cache were sized to contain The above results relate to a VTC concentrating the traffic of 100 base stations. It is interesting to understand how the VTC should be dimensioned to to serve a different number of base stations. According to the IRM model of caching, the cache size required for a given hit rate is independent of the concentration factor. On the other hand, the transcoding load and the resulting probability of failure (6) do depend on how much traffic the VTC receives.

Figure 9 shows the transcoding capacity required to realize maximum network capacity gains as a function of the relative cache size for a VTC concentrating 100 and 1000 base stations. These results reveal a transcoding scale economy in that the capacity for 1000 cells is less than 10 times the capacity required for 100. Scale economies are actually more significant in increasing the concentration factor from 10 to 100, say. Of course, scale economies are greatest for caching since cache size is independent of the traffic volume. On the other hand, larger VTCs placed to concentrate a greater number of cells lead to more traffic to be handled in the wired network between the VTC and the base station. This particular cache-bandwidth tradeoff is significant but out of scope for the present work.

VI. RELATED WORK

We are not aware of other work specifically on evaluating the relationship between transcoding and the performance of the radio access network, even though video transcoding in this context has long been recognized as an interesting possibility (e.g., [START_REF] Warabino | Video transcoding proxy for 3g wireless mobile internet access[END_REF]) and is highly relevant to very recent proposals (e.g., [START_REF]Mobile-edge computing[END_REF]). Transcoding has, of course, already been widely used for voice calls through the use of half-rate coding, although the performance model for this service, as proposed by Ivanovich et al. [START_REF] Ivanovich | Performance between circuit allocation schemes for half-and full-rate connections in gsm[END_REF], for example, cannot be applied to our system. The accepted use of half-rate coding usefully illustrates that a tradeoff of performance criteria, like reduced voice quality for lower call blocking or reduced image quality for less video stalling, is reasonable despite possible concerns over network neutrality issues.

There is currently a large amount of ongoing research into the performance of caching, mainly in the context of information-centric networking. Our simple model of Zipf popularity with the assumed independent reference model is clearly only an approximation. Recent developments, as discussed in the paper by Martina et al. [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF], for instance, account more accurately for phenomena like catalogue and popularity dynamics. However, as results in the cited paper confirm, the IRM model may be considered to remain a reasonable choice for our intended broad discussion of design choices.

While the literature is sparse on the envisaged transcoding and caching solution, there is a growing body of work on the relation between caching and adaptive video coding. For example, the paper by Grandl et al. [START_REF] Grandl | On the interaction of adaptive video streaming with content-centric networking[END_REF] considers how adaptive coding impacts the performance of a proposed informationcentric network solution where variously coded video segments are cached in the access network. Caching is used in this context mainly to reduce traffic in the backhaul, however, and not in the radio link. The paper by Aouine et al. [START_REF] Aouini | Improving caching efficiency and quality of experience with cf-dash[END_REF], on the other hand, is somewhat more relevant in that it envisages a network where the operator intervenes to limit the number of codings available to end users. The objective is to improve the efficiency of caching in reducing backhaul traffic but it is interesting to note that this type of intervention might additionally be made to alleviate radio congestion, like transcoding, by imposing lower rate segments when necessary.

In evaluating the transcoding option, it is important to account appropriately for the performance of the radio link. We have adopted here a relatively simple model linking radio conditions with dynamic, stochastic demand, inspired by the seminal work of Bonald and Proutière [START_REF] Bonald | Wireless downlink data channels: User performance and cell dimensioning[END_REF]. There is clearly scope for refining this model to account more precisely for the physical and link layer mechanisms of real 3G and 4G networks (e.g. [START_REF] Combes | Cross-layer analysis of scheduling gains: Application to lmmse receivers in frequency-selective rayleigh-fading channels[END_REF]). However, for the present purpose of gaining insight and understanding tradeoffs, we believe the simple model is sufficient.

VII. CONCLUSIONS

We have proposed a performance model to evaluate the potential gains brought by proposed video transcoder and cache (VTC) devices to be introduced in the downstream mobile access network. The model accounts for heterogeneous radio conditions, the random process of flow arrivals of three distinct types, and the on-the-fly transcoding and caching capacities of the VTC. This model has been developed to enable an operator to appraise the economic interest of these devices, proposed either as stand-alone appliances or as part of a future software-defined radio access network.

The operator's appraisal must take account of multiple criteria defining the system dimensions and costs whose detailed discussion is beyond the scope of the present paper. We believe, however, that the model itself and the sample of numerical results presented here bring some useful insights into the design options.

The gains in network capacity are at first sight modest (no more than 16% in the considered scenarios) though the high cost of the mobile access network may still outweigh the cost of the devices. The 16% gain was evaluated assuming more than 50% of network flows are susceptible to transcoding to a relatively low compressed rate. Unfortunately, the trend is for this proportion to be diminished due to the increasing use by video content providers of encryption, preventing both transcoding and transparent caching. A new business model to align the interests of operator and content providers is perhaps necessary before the gains of the VTC device can be fully exploited.

The current trend to use adaptive streaming for video applications is also reducing the proportion of video demand that is susceptible to transcoding. On the other hand, adaptive streaming applications may be considered to obviate the need for transcoding since they naturally reduce the flow rate when the network is congested or when radio conditions are poor. A simpler device might be employed by an operator to ensure the rate adaptations requested by applications have the desired impact on cell performance.

Online, on-the-fly transcoding and caching are to some extent interchangeable. If the VTC can transcode offline and cache a large proportion of compressed videos using LRU replacement, on-the fly coding is unnecessary. On the other hand, if the device is capable of transcoding a moderate number of videos in parallel, the VTC can dispense with caching. The optimum mix of cache and transcoding capacity depend on relative costs and can readily be derived from the proposed model.

Fig. 1 .

 1 Fig. 1. The video transcoder and cache (VTC) concentrates the traffic of a number of base stations.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Probability of being served with the compressed version.

Fig. 4 .

 4 Fig. 4. Cell utilization.

Fig. 5 .

 5 Fig. 5. Hit rate of compressed objects as a function of relative cache size δ.

Fig. 6 .Fig. 7 .

 67 Fig. 6. Probability of being served with the compressed codec for different cache sizes and different online transcoding capabilities.

Fig. 8 .Fig. 9 .

 89 Fig. 8. Cell load for different cache sizes and different online transcoding capabilities.

TABLE I CAPACITY

 I GAIN FOR DIFFERENT TRAFFIC MIXES (TYPES 1:2:3).

	Traffic mix (%)	52.5:22.5:25	37.5:37.5:25	22.5:52.5:25
	Original capacity	0.31 flows/s	0.33 flows/s	0.35 flows/s
	Gain with VTC	16%	15%	11%

ACKNOWLEDGMENT

This research work has been partially funded by the Technological Research Institute SystemX, within the project "Network Architectures" hosted at LINCS.