Allan Gut

Josef Steinebach

Asymptotics for increments of stopped renewal processes

Keywords: AMS 2000 subject classifications. Primary 60F05, 60F15, 60G50, 60K05; Secondary 62G10, 62G20 Renewal theory, first passage time, increments, counting process, stopping time, law of large numbers, uniform integrability, moment convergence, strong approximation, Wiener process

Motivated by our earlier work on change-point analysis we prove a number of limit theorems for increments of renewal counting processes, or the corresponding first passage times. The starting point of the increments are deterministic as well as random, the typical example being the first stopping time to detect a change-point of some (continuously) observed process.

U (t)

Introduction

The motivation for this paper comes from our work on the change-point analysis for renewal counting processes {N (t), t ≥ 0}; cf. [START_REF] Gut | Truncated sequential change-point detection based on renewal counting processes[END_REF][START_REF] Gut | A two-step sequential procedure for detecting an epidemic change[END_REF][START_REF] Gut | Stopped Random Walks[END_REF]. In [START_REF] Gut | A two-step sequential procedure for detecting an epidemic change[END_REF], for example, the sequential monitoring for detecting an "epidemic change" was designed such that first a stopping time τ 1 (say) was introduced to detect a possible outbreak of the epidemic and then, based on the increments N (τ 1 + t) -N (t) of the observed renewal process, a second stopping time τ 2 was introduced to find out whether or not the process has returned to its "normal behaviour". Or, as in Gut andSteinebach (2002, 2009), it may be necessary that, after the monitoring has stopped and a "change" has been signalled, some (unknown) parameters have to be estimated for further statistical inference (cf., e.g., Section 7 in [START_REF] Gut | Truncated sequential change-point detection based on renewal counting processes II[END_REF]), again based on the increments N (τ 1 + t) -N (t) of the stopped renewal process. Now, it is well-known that the limiting behaviour of the increments of a stopped process may be different from the limiting behaviour of the original process. [START_REF] Hanson | On the law of large numbers[END_REF], 1983a[START_REF] Hanson | Some more results on the increments of the Wiener process[END_REF], for example, derived a number of powerful strong laws for the increments of a Wiener process with applications to partial sums of i.i.d. random variables. In [START_REF] Steinebach | Limit theorems for lag processes[END_REF] the latter results have been extended to general "lag processes" by making use of a strong invariance principle for the corresponding process.

The aim of this note is to discuss some further asymptotics for the increments of stopped renewal processes {N (t), t ≥ 0} or, equivalently, for their corresponding first passage times {ν(t), t ≥ 0}.

Blackwell's renewal theorem, which we present and extend in the following section, can also be considered as a result for the increments of renewal (counting) processes, or first passage time processes, respectively. Departing from this view point we provide additional results, such as weak laws, strong laws and uniform integrability for such quantities at fixed as well as at random times for such increments.

Blackwell's Theorem

Let X, X 1 , X 2 , . . . be i.i.d. non-negative random variables with finite mean µ, set S n = n k=1 X k , n ≥ 1, and let Allan Gut and Josef Steinebach denote the renewal function. Blackwell's theorem [START_REF] Blackwell | A renewal theorem[END_REF] (see also [START_REF] Gut | Stopped Random Walks[END_REF], Theorem 2.4.2) states that

U (t + h) -U (t) h → 1 µ as t → ∞
for non-arithmetic renewal processes. For the extension to random walks, see [START_REF] Spitzer | A Tauberian theorem and its probability interpretation[END_REF] (also [START_REF] Gut | Stopped Random Walks[END_REF], Theorem 3.6.3), where the renewal function is replaced by

V (t) = ∞ n=0 P ( max 1≤k≤n S k ≤ t), t ≥ 0.
Introducing the counting process

N (t) = max{n : S n ≤ t}, t ≥ 0,
Blackwell's result is equivalent to the statement

E N (t + h) -N (t) h → 1 µ as t → ∞, in view of the fact that {N (t) > n} = {S n ≤ t}.
Letting ν(t) = min{n : S n > t}, t ≥ 0, denote the first passage times of the summation process, Spitzer's result (cf. also [START_REF] Blackwell | Extension of a renewal theorem[END_REF]) is, in the same vein, equivalent to the statement

E ν(t + h) -ν(t) h → 1 µ as t → ∞,
in view of the fact that {ν(t) > n} = { max 1≤k≤n S k ≤ t}.

As indicated at the end of the introduction, Blackwell's theorem (and its extension to random walks) thus provides information about the asymptotic expected size of the increments of renewal counting)processes, or first passage time processes, respectively.

A Weak Law and a Central Limit Theorem

In this section we discuss some weak laws for the increments of a renewal counting process-more precisely for the increments of the first passage times, namely, a weak law of large numbers under the assumption that the mean µ exists and is positive, and a central limit theorem (CLT), if, in addition, the variance σ 2 is finite and positive. In both cases the increment may depart from a fixed as well as a random time, more precisely from a stopping time with respect to the family of first passage times.

Technically, this means that these stopping times are measurable with respect to the (canonical) filtration G = {G t , t ≥ 0}, where G t = σ{ν(s), s ≤ t}.

However, before we turn to our results we need the following piece of notation.

Definition 3.1 Let {X(t), t ≥ 0} be a stochastic process and {y(t), t ≥ 0} a sequence of positive reals.

(a) We say that

X(t) = O p (y(t)) as t → ∞,
if, for every ε > 0, there exist c > 0 and t 0 > 0, such that

P (|X(t)| > cy(t)) ≤ ε for all t > t 0 . (b) We say that X(t) = o p (y(t)) as t → ∞, if X(t) y(t) p → 0 as t → ∞. 2 Theorem 3.1 Let X, X 1 , X 2 , . . . be i.i.d. random variables, such that 0 < µ = EX < ∞. Fur- ther, set S n = n k=1 X k , n ≥ 1, and let ν(t) = min{n : S n > t}, t ≥ 0,
denote the first passage times of the summation process.

(i) Then, ν(t + h(t)) -ν(t) h(t) p → 1 µ as t → ∞,
for any family {h(t), t ≥ 0} of positive reals such that h(t) → ∞ as t → ∞.

(ii) Suppose, in addition, that {τ (t), t ≥ 0} is a family of G-measurable, positive, integer-valued stopping times, such that

τ (t) p → ∞, but τ (t) = O p (t) as t → ∞. Then, ν(τ (t) + h(t)) -ν(τ (t)) h(t) p → 1 µ as t → ∞. Proof. (i) For the increments ν(t + h) -ν(t) (t, h > 0) we have, with R t = X ν(t) -t, ν(t + h) -ν(t) = min{k ≥ 1 : R t + X ν(t)+1 + • • • + X ν(t)+k > h}, if R t ≤ h ; 0, if R t > h .
Since 0 ≤ R t ≤ X ν(t) for the residual life-time R t , we immediately obtain the upper estimate

ν(t + h) -ν(t) ≤ ν 1,t (h) d = ν(h), where ν 1,t (h) = min{k ≥ 1 : X ν(t)+1 + • • • + X ν(t)+k > h}. (3.1)
So, from the law of large numbers for {ν(t), t ≥ 0}, we obviously have, for any ε > 0,

P ν(t + h) -ν(t) > h 1 µ + ε ≤ P ν(h) > h 1 µ + ε → 0 if h = h(t) → ∞. (3.2)
It therefore remains to show that, for 0 < ε < 1/µ, also

P ν(t + h) -ν(t) < h 1 µ -ε → 0 if h = h(t) → ∞. (3.3)
Observe that, on the set {R t ≤ r} with 0 < r < h, we have by a similar estimation as above,

ν(t + h) -ν(t) ≥ ν 1,t (h -r) d = ν(h -r),
with ν 1,t as in (3.1). Hence

P ν(t + h) -ν(t) < h 1 µ -ε ≤ P ν(t + h) -ν(t) < h 1 µ -ε , R t ≤ r + P R t > r ≤ P ν(h -r) < h 1 µ -ε + P R t > r . (3.4)
Next, we choose a family {r(t), t ≥ 0} of positive reals such that r(t) → ∞, but r(t)/h(t) → 0, as t → ∞, e.g., r(t) = h(t).

Since h(t)r(t) ∼ h(t) as t → ∞, it follows, once again from the law of large numbers for {ν(t), t ≥ 0}, that

P ν(h(t) -r(t)) < h(t) 1 µ -ε → 0 as t → ∞.

Allan Gut and Josef Steinebach

Finally, since R t = O p (1) as t → ∞ (cf. [START_REF] Gut | Stopped Random Walks[END_REF], Theorem 3.10.3),

P R t > r(t) → 0 as t → ∞. (3.5)
A combination of (3.4) and (3.5) completes the proof of (3.3), and this, together with (3.2), proves part (i).

(ii) By the same estimation as in (3.2) we have

P ν(τ (t) + h) -ν(τ (t)) > h 1 µ + ε ≤ P ν 1,τ (t) (h) > h 1 µ + ε → 0 if h = h(t) → ∞.
(3.6) Note that, since τ (t) is a G-measurable, positive, integer-valued stopping time, one can easily check that the sets of random variables X 1 , . . . , X ν(τ (t)) and X ν(τ (t))+1 , X ν(τ (t))+2 , . . . are independent for any fixed t > 0, which, in turn, implies that ν 1,τ (t) (h) d = ν(h). So, by decomposing as in (3.4), we obtain

P ν(τ (t) + h) -ν(τ (t)) < h 1 µ -ε ≤ P ν(τ (t) + h) -ν(τ (t)) < h 1 µ -ε , R τ (t) ≤ r + P R τ (t) > r ≤ P ν(h -r) < h 1 µ -ε + P R τ (t) > r . (3.7)
By choosing r(t) as in the first part of the proof we have

R τ (t) = o p (r(τ (t)) = o p (r(t)) as t → ∞, (3.8)
since

τ (t) p → ∞, but τ (t) = O p (t)
, so that a combination of (3.7) and (3.8) proves that

P ν(τ (t) + h) -ν(τ (t)) < h 1 µ -ε → 0 if h = h(t) → ∞, (3.9)
which, together with (3.6) completes the proof of part (ii). 2 A particular case is obtained by the choice h(t) = t 1/r , r > 0, which yields the following weak Chow type law (cf. [START_REF] Chow | Delayed sums and Borel summability of independent, identically distributed random variables[END_REF]). For an almost sure version we refer to Remark 4.3 ahead. Corollary 3.1 Let r > 0, and suppose that the appropriate conditions of Theorem 3.1 are satisfied. Then, for λ > 0,

ν(t + λt 1/r ) -ν(t) λt 1/r p → 1 µ as t → ∞, and ν(τ (t) + λt 1/r ) -ν(τ (t)) λt 1/r p → 1 µ as t → ∞.
The following central limit theorem for the increments can be obtained by similar arguments as follows.

Theorem 3.2 Let {ν(t), t ≥ 0} be as in Theorem 3.1, suppose, in addition, that 0 < σ 2 = Var X < ∞, and let {h(t), t ≥ 0} be a family of positive reals such that h

(t) → ∞ as t → ∞. (i) Then ν(t + h(t)) -ν(t) -h(t)/µ h(t) σ 2 µ -3 d → N (0, 1) as t → ∞,
where N (0, 1) denotes a standard normal random variable.

(ii) Suppose, in addition, that {τ (t), t ≥ 0} is a family of G-measurable, positive, integer-valued stopping times, such that

τ (t) p → ∞, but τ (t) = O p (t) as t → ∞.
Then also ν(τ

(t) + h(t)) -ν(τ (t)) -h(t)/µ h(t) σ 2 µ -3 d → N (0, 1) as t → ∞,
with N (0, 1) as above.

A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT

Asymptotics for Increments of Stopped Renewal Processes 5

Proof. (i) We wish to show that, for any x ∈ R,

P ν(t + h(t)) -ν(t) -h(t)/µ h(t) σ 2 µ -3 ≤ x → Φ(x) as t → ∞,
where Φ denotes the standard normal distribution function.

Set

h 1 = h 1 (x) = h/µ + x h σ 2 /µ 3 .
Then, by the same estimates as in part (i) of the proof of Theorem 3.1,

P ν(t + h(t)) -ν(t) ≤ h 1 ≥ P ν(h) ≤ h 1 → Φ(x) as t → ∞,
in view of the central limit theorem for {ν(t), t ≥ 0}.

Moreover, for 0 < r < h,

P ν(t + h) -ν(t) ≤ h 1 ≤ P ν(t + h) -ν(t) ≤ h 1 , R t ≤ r + P R t > r ≤ P ν(h -r) ≤ h 1 + P R t > r . Now, if r = r(t) → ∞, but r = o( √ h), with h = h(t), then h 1 = (h -r)/µ + x (h -r) σ 2 /µ 3 + r/µ + O r/ √ h , = (h -r)/µ + x (h -r) σ 2 /µ 3 + o √ h -r ,
so that an application of the CLT for {ν(t), t ≥ 0} also yields

P ν(h -r) ≤ h 1 → Φ(x) as t → ∞.
This, in combination with P (R t > r(t)) → 0 as t → ∞, completes the proof of part (i).

(ii) The second part is proved by analogous arguments as in the proof of (ii) of Theorem 3.1. 2

Strong Laws

The first subsection provides a Kolmogorov type strong law analog of the results of the previous section. In the second subsection we prove a Marcinkiewicz-Zygmund type law.

The proofs in the first subsection are based on strong approximation, which necessitates moment assumptions of some order strictly greater than two. The remaining results do not exploit this method which implies that the results are stronger in the sense that optimal moment conditions are assumed. The price we pay is that less general functions h are considered.

A Kolmogorov strong law

Theorem 4.1 Let X, X 1 , X 2 , . . . be i.i.d. random variables, such that E|X| r < ∞ for some r > 2, and let µ > 0 and σ 2 denote mean and variance, respectively, of the summands. Further, set S n = n k=1 X k , n ≥ 1, and let ν(t) = min{n : S n > t}, t ≥ 0, denote the first passage times of the summation process. → 0 as t → ∞.

(i)
For h(t) = λt, with λ > 0, this implies that = O(t) as t → ∞, it follows as above, with λ > 0, that ν(τ (t) + λt)ν(τ (t))λt/µ t 1/r a.s.

ν(t + λt) -(t + λt)/µ t 1/r = ν(t + λt) -(t + λt)/µ (t + λt) 1/r • (t + λt)
→ 0 as t → ∞.

We summarize the results of this subsection as follows:

Theorem 4.2 Let X, X 1 , X 2 , . . . be i.i.d. random variables, such that E|X| r < ∞ for some 1 ≤ r < 2, and suppose that E X = µ > 0. Further, set S n = n k=1 X k , n ≥ 1, and let ν(t) = min{n : S n > t}, t ≥ 0, denote the first passage times of the summation process.

(i) Then, for λ > 0, ν(t + λt)ν(t)λt/µ t 1/r a.s.

→ 0 as t → ∞.

(ii) Suppose, in addition, that {τ (t), t ≥ 0} is a family of non-negative random variables such that τ (t) a.s.

→ ∞, but τ (t) a.s.

= O(t) as t → ∞.

Then, for λ > 0, ν(τ (t) + λt)ν(τ (t))λt/µ t 1/r a.s.

→ 0 as t → ∞.

Remark 4.1 Recall that for the case r = 1 we rediscover Theorem 4.1 under a weaker moment assumption, but for a more restricted class of functions h.

  Allan Gut and Josef Steinebach Proof. Set η = σµ -3/2 . Via the strong approximation of {ν(t), t ≥ 0} by a Wiener process (cf., e.g.[START_REF] Csörgő | Invariance principles for renewal processes[END_REF]), and since t + h(t) ∼ t as t → ∞, we have

	ν(t + h(t)) -ν(t) -h(t)/µ	a.s. = η{W (t + h(t)) -W (t)} + o(t 1/r ) as t → ∞.
	Now, according to Csörgő and Révész (1981), Theorem 1.2.1,
		W (t + h(t)) -W (t)	a.s. = O h(t){log(t/h(t)) + log log t}	as t → ∞,
	so that (i) is immediate from a combination of the latter assertions and our assumptions on the family {h(t), t ≥ 0}. Note that, in view of our conditions, {log(t/h(t)) + log log t}/h(t) → 0 as t → ∞. Assertion (ii) follows by a corresponding argument. 2
	4.2 A Marcinkiewicz-Zygmund strong law
	The Marcinkiewicz-Zygmund strong law for first passage times (Gut (1974), Theorem 2.8.a, Gut (2009), Theorem 3.4.4) tells us that if E|X| r < ∞, 1 ≤ r < 2, then
			t 1/r ν(t) -t/µ	a.s.
	Then,	ν(t + h(t)) -ν(t) h(t)	a.s. →	1 µ	as t → ∞,
	for any family {h(t), t ≥ 0} of positive reals such that h(t) ↑ ∞, h(t)/t ↓ 0, and t 1/r = O(h(t)) as t → ∞. (ii) Suppose, in addition, that {τ (t), t ≥ 0} is a family of non-negative random variables, such that τ (t) a.s. but τ (t) a.s. → ∞, Then, ν(τ (t) + h(t)) -ν(τ (t)) h(t) a.s. → 1 µ as t → ∞.

= O(t) as t → ∞.

Acknowledgement

Thanks to a referee for some useful remarks which helped to clarify our setup.

ACCEPTED MANUSCRIPT

Asymptotics for Increments of Stopped Renewal Processes 7

Remark 4. [START_REF] Blackwell | Extension of a renewal theorem[END_REF] The "obvious" case in (ii) is, of course, τ (t)/t a.s.

→ θ as t → ∞ for some θ ∈ (0, ∞).

Remark 4.3 By the same arguments as above it can easily be checked that, if E|X| r < ∞ for some 1 ≤ r < 2 and EX = µ > 0, then also

for any λ > 0, and, moreover, that

if, in addition, {τ (t), t ≥ 0} is a family of non-negative random variables such that, for some

→ θ as t → ∞. The conclusions of the latter assertions may be interpreted as first passage time analogs of Chow's strong law [START_REF] Chow | Delayed sums and Borel summability of independent, identically distributed random variables[END_REF])for delayed sums with fixed and random times, respectively. The same remark also applies to Theorem 4.1, where (as remarked earlier in the paper) the windows are more general, the price of which is paid by the stronger moment assumption, which is necessary in order for the strong invariance principle to apply). 2

Uniform Integrability, Convergence of Moments

In this section we turn our attention to uniform integrability and moment convergence. We begin by quoting Gut (2009), Theorem 3.3.1, according to which, if 0 < µ = EX < ∞, then for all t ≥ 0 and p ≥ 1,

Next we observe that, by monotonicity and subadditivity (cf. [START_REF] Gut | Stopped Random Walks[END_REF], p. 58),

where {ν k (1), k ≥ 1} are i.i.d. random variables distributed as ν(1), so that, for h(t) ≥ 1,

which, in turn, shows that, for some t 0 > 0, the sequence

is dominated by the uniformly integrable sequence

and, hence, is uniformly integrable.

Moreover, in view of Theorem 3.1, we have

ACCEPTED MANUSCRIPT 8 Allan Gut and Josef Steinebach

A similar argument holds with t being replaced by a G-measurable stopping time τ (t), since the sets of random variables X 1 , . . . , X ν(τ (t)) and X ν(τ (t))+1 , X ν(τ (t))+2 , . . . are independent for any fixed t > 0 (cf. the proof of Theorem 3.1(ii)), so that

A combination of the latter assertions results in the estimates

which, once again, is finite iff E(X -) p < ∞, and since

p , t ≥ t 0 , the desired uniform integrability follows. Invoking Theorem 3.1 again, finally, tells us that

The following result emerges.

Theorem 5.1 (i) Let {h(t), t ≥ 0} be a family of positive reals such that h(t) → ∞ as t → ∞. If E(X -) p < ∞ for some p ≥ 1 and 0 < µ = EX < ∞, then, for some t 0 > 0,

For p = 1 we obtain the following extension of the Blackwell-Spitzer result.

Corollary 5.1 Under the conditions of Theorems 3.1 and 5.1,

Note that no assumption concerning the random walk being arithmetic or non-arithmetic is made.


E Gonc ¸alves

N Mendes-Lopes

E Gonçalves

On the structure of generalized threshold arch processes

Keywords: 2000 Mathematics Subject Classification. 62G20, 62M10 GTARCH models, minimal representation, nonlinear time series, stationarity

The aim of this paper is to develop probabilistic studies, useful for applications, namely in what concerns the implementation and validation of subsequent statistical methods. More precisely, we establish new conditions on the stationarity and ergodicity of the GTARCH model and obtain an unique representation of its conditional volatility in terms of present and past observations. A minimal definition of a GTARCH process is then deduced.

Introduction

Let ε = (ε t , t ∈ Z) be a real stochastic process following a generalized threshold auto-regressive conditionally heteroscedastic model with orders p and q, gtarch(p, q), defined by [START_REF] Zakoian | Threshold heteroskedasticity models[END_REF] as

   ε t = σ t Z t σ t = α 0 + q i=1 α i ε + t-i - q i=1 β i ε - t-i + p j=1 γ j σ t-j (1.1)
where α 0 > 0, α i ≥ 0, β i ≥ 0 (i = 1, ..., q) , γ j ≥ 0 (j = 1, ..., p) are real constants, ε + t = ε t I {ε t ≥0} , ε - t = ε t I {ε t <0} and Z = (Z t , t ∈ Z) , called a generating process, is a sequence of independent and identically distributed real random variables, with zero mean and unit variance and such that Z t is independent of ε t-1 for each t ∈ Z, with ε t-1 denoting the σ-field generated by ε t-1 , ε t-2 , ... If γ j = 0, j = 1, ..., p, the gtarch(p, q) model is simply denoted tarch(q).

In this formulation, the conditional standard deviation of the process at time t given ε t-1 is a piecewise linear function of past observations depending, not necessarily symmetrically, on whether they are positive or negative. So, this class of nonlinear stochastic models has the advantage over garch ones [START_REF] Engle | Autoregressive conditional heteroskedasticity with estimates of the variance of the United Kingdom inflation[END_REF][START_REF] Bollerslev | Generalized autoregressive conditional heteroskedasticity[END_REF] of taking account of the asymmetries, so often found in some real series. For instance, recent studies (He and Teräsvirta, ACCEPTED MANUSCRIPT 1999, [START_REF] Gonçalves | A mathematical approach to detect the Taylor property in TARCH processes[END_REF] show that tarch models are better able to capture the presence of Taylor's property (whose presence in many financial time series has been emphasized since [START_REF] Taylor | Modelling Financial Time Series[END_REF]) than arch ones. Some probabilistic results have been established for these models, in particular necessary and sufficient conditions of stationarity and ergodicity (Gonçalves andMendes-Lopes, 1994, 1996). More precisely, the strict stationarity and ergodicity of the general model (1.1) is expressed by a condition on the following sequence of random square matrices, (A t , t ∈ Z) , of p + 2q -2 order, written in block form:

A t =           α 1 Z + t -β 1 Z - t + γ 1 γ 2,p-1 γ p α 2,q-1 α q β 2,q-1 β q 1 0 0 0 0 0 0 0 I p-2 0 0 0 0 0 Z + t 0 0 0 0 0 0 0 0 0 I q-2 0 0 0 -Z - t 0 0 0 0 0 0 0 0 0 0 0 I q-2 0           where α 2,q-1 = (α 2 , ..., α q-1 ) if q ≥ 3, β 2,q-1 = β 2 , ..., β q-1 if q ≥ 3, γ 2,p-1 = γ 2 , ..., γ p-1 if p ≥ 3
, and I k is the identity matrix of order k (k ≥ 1). Moreover, the column beginning γ p (resp. α q and β q ) is only defined for p ≥ 2 (resp. q ≥ 2) as well as the row beginning by 1 (resp. Z + t and -Z - t ). As we assume that (Z t , t ∈ Z) are independent and identically distributed random variables, the random matrices (A t , t ∈ Z) are also independent and identically distributed.

Considering any norm on the set M p+2q-2 of the square matrices of order p + 2q -2, [START_REF] Gonçalves | Stationarity of GTARCH processes[END_REF] proved that there is an unique strictly stationary and ergodic solution of the gtarch model given in (1.1) if and only if the sequence 1 n log A 0 ...A -n n∈N converges almost surely (a.s.) to a strictly negative constant γ L . This limit is the non random Lyapounov exponent associated with the sequence of matrices (A t , t ∈ Z) , defined as

γ L = inf 1≤n<+∞ 1 n E (log A 0 ...A -n ) .
The condition E log + A 0 < +∞ and the subadditive ergodic Theorem [START_REF] Kingman | Subadditive processes[END_REF] (a.s.) . We note that this condition is independent of the chosen norm since M p+2q-2 is a finite dimensional space.

imply lim n 1 n log A 0 ...A -n = γ L ,
We point out that the proof of this necessary and sufficient condition of strict stationarity of model (1.1), as well as its ergodicity, uses the vectorial stochastic process of R p+2q-2 , X = (X t , t ∈ Z), defined by

X t = σ t , σ t-1 , ..., σ t-p+1 , ε + t-1 , ..., ε + t-q+1 , -ε - t-1 , ..., -ε - t-q+1 T
where T denotes the transpose. This process verifies the following auto-regressive equation X t+1 = A t X t + B, with B = (α 0 , 0, ..., 0) T ∈ R p+2q-2 , and the unique strictly stationary and ergodic solution of model (1.1) is the first component of the random vector that is solution of that equation, namely,

X t = B + lim k-→+∞ (a.s.) k i=1 A t-1 ...A t-i B, t ∈ Z.
(1.2)

ACCEPTED MANUSCRIPT

When we intend to obtain the stationary region of the model using the previous necessary and sufficient condition we are confronted with an analysis of great complexity, even for small values of p or q. This justifies the interest of checking alternative stationary conditions. In Section 2, we state conditions ensuring the existence of the strictly stationary and ergodic solution, directly expressed on the coefficients of the gtarch model defined in (1.1).

In Section 3 we establish an unique representation of the conditional standard deviation of a gtarch process as an infinite sum of functions of present and past observations. A minimal definition of these models is obtained as a consequence.

Whenever necessary we consider on the set M p+2q-2 the norm induced by the Euclidean norm, . 2 , on R p+2q-2 ,

∀M ∈ M p+2q-2 , M = sup Mx 2 x 2 , x ∈ R p+2q-2 , x = 0 .

GTARCH processes: strict stationarity and conditions on the coefficients

The following result establishes sufficient conditions for the existence of the strictly stationary and ergodic solution of model (1.1) previously mentioned. We denote the marginal probability law of the generating process Z = (Z t , t ∈ Z) by λ.

Theorem 2.1. Let ν = E Z + t .
1. The unique strictly stationary and ergodic solution of model (1.1) exists if

p j=1 γ j + ν q i=1 (α i + β i ) < 1.
2. We suppose that the support of λ is not bounded, with λ ({0}) = 0, and that all the coefficients α 0 , α i , β i (i = 1, ..., q) , γ j (j = 1, ..., p) are positive. The unique strictly stationary and ergodic solution of model (1.1) exists if

p j=1 γ j + ν q i=1 (α i + β i ) = 1.
Proof. Following the idea presented in [START_REF] Bougerol | Stationarity of GARCH processes and of some nonnegative time series[END_REF], let us consider the matrix

E (A 1 ). As E (Z t ) = 0 then -E Z - t = ν and we have now the identity det (zI -E (A 1 )) = z p+2q-2 1 - p j=1 γ j z -j -ν q i=1 (α i + β i ) z -i . Then, it follows from the inequality |a -b| ≥ ||a| -|b|| that if |z| > 1 |det (zI -E (A 1 ))| > 1 - p j=1 γ j z -j + ν q i=1 (α i + β i ) z -i . ACCEPTED MANUSCRIPT So, |det (zI -E (A 1 ))| > 1 - p j=1 γ j -ν q i=1 (α i + β i ) .
(2.1)

If p j=1 γ j + ν q i=1
(α i + β i ) < 1 we conclude, from this inequality and from the previous equality written for |z| = 1, that the spectral radius ρ of the matrix E (A 1 ) satisfies ρ < 1. But, as Kesten and Spitzer (1984, (1.4)) pointed out, it is always true that γ L ≤ log ρ. So, γ L < 0 and, by [START_REF] Gonçalves | Stationarity of GTARCH processes[END_REF], the gtarch model presented in (1.1) has a unique strictly stationary and ergodic solution.

If

p j=1 γ j + ν q i=1 (α i + β i ) = 1
, the right-hand side of (2.1) is zero and, as

det (I -E (A 1 )) = 1 - p j=1 γ j -ν q i=1
(α i + β i ) = 0, we conclude that the spectral radius ρ of the matrix E (A 1 ) is 1. On the other hand, almost surely, all the coefficients of the matrix A 2 A 1 are positive and A 1 has no zero column nor zero row. Under these conditions and taking into account that A 1 is not a.s. bounded, we deduce from Kesten and Spitzer (1984, Theorem 2) that the equality γ L ≤ log ρ doesn't hold. So, the top Lyapunov exponent γ L satisfies γ L < log ρ and the result follows.

We point out that the condition

p j=1 γ j + ν q i=1 (α i + β i ) < 1 is not a necessary
one for the existence of the strictly stationary solution of model (1.1). In fact, let us consider the gtarch(1, 1) model

ε t = σ t Z t σ t = α 0 + αε + t-1 -βε - t-1 + γσ t-1 .
We know that there is a strictly stationary solution for this model if and only if E (log A t ) < 0, where A t = αZ + t -βZ - t + γ. Moreover, using the inequality of Jensen, we have

E (log A t ) ≤ log γ + log α+β γ E Z + t + 1 . Let us consider α = β = γ = 0.
5 and suppose that the generator process, Z, has a Gaussian distribution. As

E Z + t = √ 2π
2π , from the last inequality we get E (log A t ) < 0 and, in consequence, the solution is strictly stationary and ergodic. Nevertheless, γ

+ E Z + t (α + β) ≃ 1.39 > 1.
A necessary condition for the existence of a strictly stationary solution of model (1.1) is now stated. As any weakly stationary gtarch model is also strictly stationary [START_REF] Gonçalves | The generalized threshold ARCH model: wide sense stationarity and asymptotic normality of the temporal aggregate[END_REF], we point out that this condition is also a necessary one for the existence of the widely stationary solution.

Theorem 2.2. If the gtarch model presented in (1.1) has a strictly stationary solution then p j=1 γ j < 1.

ACCEPTED MANUSCRIPT

Proof. Let A be the matrix which is obtained replacing Z + t and Z - t by 0 in the matrices A t . Since, for each k ∈ Z, A k ≥ A, we have A 0 ...A -n ≥ A n+1 . So, the top Lyapunov exponent associated with the sequence of matrices (A t , t ∈ Z) satisfies γ L ≥ log A . As A ≥ ρ (A) , where ρ (A) is the spectral radius of matrix A, and, by [START_REF] Gonçalves | Stationarity of GTARCH processes[END_REF], γ L < 0, we deduce that ρ (A) < 1. Moreover, we have det (zI

-A) = z p+2q-2 1 - p j=1 γ j z -j . We conclude that the continuous function f (x) = 1 - p j=1 γ j x j has no zeros when 0 ≤ x ≤ 1. Since f (0) = 1, this implies that f (1) = 1 - p j=1
γ j > 0, as required.

Structure of GTARCH processes

In this section we obtain a representation unique for the process ε = (ε t , t ∈ Z) defined in (1.1), in terms of its past, described by ε + t-i and ε - t-i , i ≥ 1, and the generator process Z. We also state a necessary and sufficient condition for the existence of a minimal representation of ε t . We begin by establishing a representation for σ k in terms of past values ε + k-i and ε - k-i , i ≥ 1. Let us define the following polynomials, whose coefficients are those present in the conditional standard deviation of the gtarch process ε:

A 1 (x) = α 1 x+...+α q x q , A 2 (x) = β 1 x+...+β q x q , B (x) = 1-γ 1 x-...-γ p x p .
To ensure that the model orders are in fact p and q, we suppose γ p = 0 and α q or β q non zero. We assume the strict stationarity of the gtarch process ε = (ε t , t ∈ Z) defined in (1.1) and that the matrices A t , t ∈ Z, satisfy the condition E log + A 0 < +∞. From Theorem 2.2 we have γ 1 + ... + γ p < 1 and so all the roots of B (x) = 0 are outside the unit circle, which implies 1

B (x) = +∞ j=0 d j x j , |x| ≤ 1,
where the coefficients d j decrease exponentially as j -→ +∞. Obviously,

A 1 (x) B(x) = +∞ j=1 c j x j , A 2 (x) B(x) = +∞ j=1 c j x j , |x| ≤ 1, with c 0 = α0 B(1) = α 0 +∞ j=0 d j , c j = α 1 d j-1 +...+α q d j-q , c j = β 1 d j-1 +...+β q d j-q ,
j ≥ 1, and c j and c j decreasing exponentially as j -→ +∞.

Theorem 3.1.

If E |log σ 0 | < +∞ then σ k = c 0 + +∞ i=1 c i ε + k-i - +∞ i=1 c i ε - k-i , for every k, (3.1)
with probability 1. If, in addition, Z + 0 and Z - 0 are non-degenerated random variables, the given representation is unique.

A C C E P T E D M A N U S C R I P T

ACCEPTED MANUSCRIPT

Proof. As E log + A 0 < +∞ and A 0 ≥ 1 we deduce that E log + Z + 0 and E log + Z - 0 are finite. Consequently, the same occurs to E log + ε + 0 and to E log + ε - 0 . Moreover, ε + t , 0 ≤ t < +∞ is a sequence of real random variables, identically distributed, as well as ε - t , 0 ≤ t < +∞ , since (ε t , 0 ≤ t < +∞) is strictly stationary. In consequence ( 1 ), the series

+∞ i=1 c i ε + t-i and +∞ i=1 c i ε - t-i are absolutely convergent with probability 1.
Considering the strictly stationary process ξ = (ξ k , k ∈ Z) such that

ξ k = α 0 + q i=1 α i ε + k-i - q i=1 β i ε - k-i let us show that σ k = +∞ m=0 d m ξ k-m . (3.2)
As E log + |ξ 0 | < +∞, this series is absolutely convergent with probability 1, taking into account the exponential decrease of d m , m ∈ N. On the other hand, from 1

B (x) = +∞ j=0 d j x j ⇐⇒ 1 = 1 -γ 1 x -... -γ p x p +∞ j=0 d j x j we deduce                1 = d 0 d 1 = γ 1 d 2 = d 1 γ 1 + γ 2 ... d p = d p-1 γ 1 + ... + d 1 γ p-1 + γ p d i = d i-1 γ 1 + ... + d i-p γ p , for i > p.
For j ≥ p, the following relation, proved in Appendix A, holds

ξ k + d 1 ξ k-1 + ... + d j ξ k-j = σ k - p i=1 d i+j-p γ p + ... + d j γ i σ k-i-j .
The left-hand side of this equality converges a.s., when j -→ +∞, to the right-hand side of (3.2). Moreover, using the exponential decrease of d j and the fact that E |log σ 0 | < +∞ we prove, in Appendix B, that

+∞ j=1 P p i=1 d i+j-p γ p + ... + d j γ i σ k-i-j > δ < +∞, ∀δ > 0.
From Borel-Cantelli Lemma, we obtain

σ k = c 0 + +∞ i=1 c i ε + k-i - +∞ i=1 c i ε - k-i , with probability 1. 1 If (ξ k , 0 ≤ k < +∞
) is a sequence of real random variables identically distributed such that E log + |ξ 0 | < +∞, then the series +∞ P k=0 ξ k z k converges, with probability 1, for any z in the region |z| < 1 (Lemma 2.2 of [START_REF] Berkes | GARCH processes: structure and estimation[END_REF].

ACCEPTED MANUSCRIPT

Now, let Z + 0 and Z - 0 be non degenerated variables. To establish the unicity of the representation obtained for σ k , let us consider, for some k,

σ k = c 0 + +∞ i=1 c i ε + k-i - +∞ i=1 c i ε - k-i (a.s.) and σ k = f 0 + +∞ i=1 f i ε + k-i - +∞ i=1 f i ε - k-i (a.s.) .
By contradiction, let m 1 > 0 and m 2 > 0 be the smallest integers such that c m1 = f m1 and c m2 = f m2 (we note that if c i = f i and c i = f i , ∀i > 0 then c 0 = f 0 ). By the definition of m 1 and m 2 , and taking into account that

ε k = σ k Z k , we obtain (f m1 -c m1 ) σ k-m1 Z + k-m1 + f m2 -c m2 ε - k-m2 = c 0 -f 0 + + +∞ i=m1+1 (c i -f i ) ε + k-i - +∞ i=m2+1 c i -f i ε - k-i . If m 1 ≤ m 2 (the conclusion is analogous if m 1 > m 2 ), we get Z + k-m1 = 1 (fm 1 -cm 1 )σk-m 1 c m2 -f m2 ε - k-m2 + (c 0 -f 0 ) + + 1 (fm 1 -cm 1 )σk-m 1 +∞ i=m1+1 (c i -f i ) ε + k-i - +∞ i=m2+1 c i -f i ε - k-i .
As σ k-m1 ≥ α 0 > 0, Z + k-m1 is well defined. As ε + j is Z j -measurable, as well as ε - j (Z j is the σ-field generated by Z j , Z j-1 , ...), the right-hand side of the last relation (and, consequently, Z + k-m1 ) is a real random variable measurable with respect to Z k-m1-1 . Taking into account that Z k , k ∈ Z, are independent, we conclude that Z + k-m1 is constant (a.s.).

Using the backward shift operator L, the representation (3.1) may be written as:

σ k = 1 B(L) α 0 + A 1 (L) ε + k -A 2 (L) ε - k = α0 B(1) + A1(L) B(L) ε + k -A2(L) B(L) ε - k . (3.3)
From this representation we deduce an unique representation of ε k in terms of its past, for each arbitrarily fixed generator process Z.

Let us now study the minimality of the definition (1.1) of the gtarch process, in the sense that there is no pair (p * , q * ) , such that p * < p or q * < q and

σ k = α * 0 + q * i=1 α * i ε + k-i - q * i=1 β * i ε - k-i + p * j=1 γ * j σ k-j (3.4) for some (not necessarily non negatives) α * 0 , α * i , β * i (i = 1, ..., q * ) , γ * j (j = 1, ..., p * ) .
Theorem 3.2. We suppose that E |log σ 0 | < +∞ and that the random variables Z + 0 and Z - 0 are non degenerated. The definition (1.1) is minimal if and only if the polynomials A 1 (x) and B(x) are coprimes or the polynomials A 2 (x) and B(x) are coprimes, (3.5) in the set of the polynomials with real coefficients.

Proof. We suppose that A 1 (x) and B(x) are coprimes or A 2 (x) and B(x) are coprimes and that there are (p * , q * ) , p * < p or q * < q, and α *

0 , α * i , β * i A C C E P T E D M A N U S C R I P T

ACCEPTED MANUSCRIPT

(i = 1, ..., q * ) , γ * j (j = 1, ..., p * ) such that (3.4) holds. From the strict stationarity we necessarily have

p * j=1 γ * j < 1. We define A * 1 (x) = α * 1 x + ... + α * q * x q * , A * 2 (x) = β * 1 x + ... + β * q * x q * and B * (x) = 1 -γ * 1 x -... -γ * p * x p * . This gives A * 1 (x) B * (x) = +∞ j=1 c j x j , A * 2 (x) B * (x) = +∞ j=1 c j x j
and so, from the unicity of the representation,

A 1 (x) B (x) = A * 1 (x) B * (x) , A 2 (x) B (x) = A * 2 (x) B * (x)
.

If A 1 (x) and B (x) are coprimes, we conclude that there is a polynomial P (x) such that A * 1 (x) = A 1 (x) P (x), B * (x) = B (x) P (x), with a similar conclusion if A 2 and B are coprimes. Then p * ≥ p, q * ≥ q, which is a contradiction.

Conversely, let us now suppose that the definition (1.1) is minimal but the condition (3.5) fails, that is, neither A 1 and B nor A 2 and B are coprimes. Introducing F A1 (x) = gcd (B (x) , A 1 (x)) and F A2 (x) = gcd (B (x) , A 2 (x)) it is always possible to write

B(x) = F A1 (x) F A2 (x) B 1 (x)
where B 1 (x) is a polynomial with a degree less than or equal to p -2. Similarly, we have

A 1 (x) = F A1 (x) A • 1 (x) , A 2 (x) = F A2 (x) A • 2 (x)
, where degree(A • i (x)) < q, i = 1, 2. If we introduce F (x) = lcm (F A1 (x) , F A2 (x)) , we have, from (3.3), with α 0 = α 0 F (1) B 1 (1) B (1) ,

σ k = 1 B (L) α 0 + A 1 (L) ε + k -A 2 (L) ε - k = α 0 F (1) B 1 (1) + A • 1 (L) F A2 (L) B 1 (L) ε + k - A • 2 (L) F A1 (L) B 1 (L) ε - k = α 0 F (1) B 1 (1) + A • 1 (L) F (L) FA 2 (L) F (L) B 1 (L) ε + k - A • 2 (L) F (L) FA 1 (L) F (L) B 1 (L) ε - k .
So, we have L) are polynomials whose degrees are less than those of B, A 1 and A 2 , respectively. This fact contradicts the hypothesis of minimal definition.

σ k = 1 F (L) B 1 (L) α 0 + A 1 (L) ε + k -A 2 (L) ε - k where F (L) B 1 (L) , A 1 (L) = A • 1 (L) F (L) FA 2 (L) and A 2 (L) = A • 2 (L) F (L) FA 1 (
Finally, under the hypotheses of the Theorem 3.2 and supposing that the polynomials A 1 (x) and B(x) are coprimes or the polynomials A 2 (x) and B(x)

A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT

are coprimes, the unicity of the minimal definition of the conditional standard deviation of the process is assured because there is no α * 0 , α * i , β * i (i = 1, ..., q) , γ * j (j = 1, ..., p) = α 0 , α i , β i (i = 1, ..., q) , γ j (j = 1, ..., p)

such that σ k = α * 0 + q i=1 α * i ε + k-i - q i=1 β * i ε - k-i + p j=1 γ * j σ k-j .

Conclusions

The explicit finding of the regions of stationarity for the generalized threshold ARCH model by means of the necessary and sufficient condition referred in the Introduction is quite difficult, involving complex numerical studies even for small values of the orders p and q.

On the contrary, the conditions stated on Section 2 ensuring the existence of the strictly stationary and ergodic solution have a great simplicity, as they are directly expressed on the coefficients of the model. This is a really positive contribution in what concerns the practical applications of these models, particularly in statistical approaches.

Moreover, the results stated on Section 3 reinforce this contribution as we obtain an unique representation for the volatility, σ t , as a function of the present and past process values. Given the conditionally heteroscedastic nature of these models, this may have a great relevance in the forecasting phase. Finally, we point out that from this representation of the volatility process we deduce, in particular, a minimal representation for the process ε itself.

A. Appendix A Denoting a 1 (L) = j i=0 d i L i and a 2 (L) = +∞ i=j+1 d i L i , with j ≥ p, we have 1 B(L) ξ k = a 1 (L) ξ k + a 2 (L) ξ k ⇔ σ k = j i=0 d i ξ k-i + a 2 (L) B (L) σ k . Now,

d

  let us study the series a 2 (L)B (L) = +∞ i=j+1 d i L i 1γ 1 L -...γ p L p = +∞ m=j+1 c m L m . We deduce that                    c j+1 = d j+1 c j+2 = d j+2d j+1 γ 1 c j+3 = d j+3d j+2 γ 1d j+1 γ 2 ... c j+p-1 = d j+p-1d j+p-2 γ 1d j+p-2 γ 2 -...d j+1 γ p-2 c j+p = d j+pd j+p-1 γ 1d j+p-2 γ 2 -...d j+1 γ p-1 c j+l = d j+ld j+l-1 γ 1d j+l-2 γ 2 -...d j+l-p γ p ,for l > p.ACCEPTED MANUSCRIPTTaking now into account that, for j > p,d j = d j-1 γ 1 + d j-2 γ 2 + ... + d j-p γ p , we obtain                    c j+1 = d j γ 1 + d j-1 γ 2 + ... + d j+1-p γ p c j+2 = d j γ 2 + ... + d j+2-p γ p c j+3 = d j γ 3 + ... + d j+3-p γ p ... c j+p-1 = d j γ p-1 + d j-1 γ p c j+p = d j γ p c j+l = 0, for l > p. So, c j+i = d j γ i + d j-1 γ i+1 + ... + d j+i-p γ p , i = 1, ..., p 0, i ≥ p + 1, and, in consequence, a 2 (L) B (L) σ k = +∞ m=j+1 c m L m σ k = j+p m=j+1 c m L m σ k = p i=1 c j+i σ k-j-i .Then, for j ≥ p,σ k = j i=0 d i ξ k-i + a 2 (L) B (L) σ k ⇔ ξ k + d 1 ξ k-1 + ... + d j ξ k-j = σ k -p i=1 d i+j-p γ p + ... + d j γ i σ k-i-j . i+j-p γ p + ... + d j γ i σ k-i-j > δ < +∞, ∀δ > 0.As d j ≥ 0, γ i ≥ 0 and σ k-i-j ≥ 0, we have, with c = γ p + ...+ γ 1 , p i=1 d i+j-p γ p + ... + d j γ i σ k-i-j ≤ c max(d 1+j-p , ..., d j ) p γ p + ... + d j γ i σ k-i-j > δ d1+j-p,...,dj) .Considering d j = O 1 α j , α > 1, and using the strict stationarity of σ k we obtain p i=1 P σ k-i-j > δ pc max(d1+j-p,...,dj)

Acknowledgment

The authors are grateful to the referees for their constructive comments and suggestions.

A C C E P T E D M A N U S C R I P T

ACCEPTED MANUSCRIPT

So, as we assume


Andreas Maurer

Dominated concentration

Keywords:

The concentration properties of one random variable may be governed by the values of another random variable which is concentrated and more easily analyzed. We present a general concentration inequality to handle such cases and apply it to the eigenvalues of the Gram matrix for a sample of independent vectors distributed in the unit ball of a Hilbert space. For large samples the deviation of the eigenvalues from their mean is shown to scale with the largest eigenvalue.

Introduction

For all of the following we assume that Ω = n 1 Ω i is some product space with product probability µ = ⊗ n 1 µ k and that F : Ω → R is some bounded measurable function. We write EF = F dµ. If x ∈ Ω, k ∈ {1, ..., n} and y ∈ Ω k we use x y,k to denote the vector obtained from x by replacing the k-th component with y, and we define a function DF : Ω → R by

DF (x) = k F (x) -inf y∈Ω k F (x y,k ) 2 .
The function DF is a local measure of the sensitivity of F to modifications of its individual arguments. It is shown in [START_REF] Maurer | Concentration inequalities for functions of independent variables[END_REF] that uniform bounds on DF lead to exponential tail inequalities for F , and that the upwards deviation bounds so obtained improve over the results obtained from Talagrand's convex distance inequality in many cases. If the function DF is bounded by a constant multiple of F itself other concentration properties can be deduced, as in the following result taken from [START_REF] Maurer | Concentration inequalities for functions of independent variables[END_REF].

Theorem 1. Suppose that a > 0 and that DF ≤ aF.

(1)

ACCEPTED MANUSCRIPT

Then for t > 0

Pr {F -E [F ] ≥ t} ≤ exp -t 2 2aE [F ] + at , and, if a ≥ 1 and F -inf k F ≤ 1 ∀k, then Pr {E [F ] -F ≥ t} ≤ exp -t 2 2aE [F ]
.

These results were derived from the entropy method, a technique which has been developed and refined by Ledoux, Bobkov, Massart, Boucheron, Lugosi, Rio, Bousquet and others ( see Ledoux (1996), [START_REF] Massart | Some applications of concentration inequalities to statistics[END_REF], Boucheron et al (2003), etc). The entropy method is rooted in the tensorization property of the entropy and seems to be evolving into a general toolbox to derive concentration inequalities. Recently [START_REF] Boucheron | On concentration of self-bounding functions[END_REF] demonstrated that Theorem 1 above can be used to derive a version of Talagrand's convex distance inequality. The authors also weakened the condition a ≥ 1 to a ≥ 1/3 in the lower tail bound above. Following them we will call a function F weakly self-bounded, if it satisfies condition (1) above.

In some situations it is not possible to prove weak self-boundedness of F , but there is another function G which is weakly-self bounded, and DF is bounded by a constant multiple of G. In this situation one may use the following result, which is the principal contribution of this paper.

Theorem 2. Suppose that F, G : Ω → R and a ≥ 1 such that (i)

0 ≤ F ≤ G (ii) DF ≤ aG (iii) DG ≤ aG Then, for t > 0, Pr {F -EF > t} ≤ exp -t 2 4aEG + 3at/2 .
and, if in addition F (x) -F (x y,k ) ≤ 1, for all k,and for all y ∈ Ω k , then

Pr {EF -F > t} ≤ exp -t 2 4aEG + at .
The proof of Theorem 2 also uses the entropy method and the tools developed by [START_REF] Boucheron | Concentration Inequalities using the entropy method[END_REF] and [START_REF] Maurer | Concentration inequalities for functions of independent variables[END_REF].

In many applications in learning theory concentration inequalities are used to estimate the expectation of a random variable from the observation of a single sample vector, when the underlying distribution is unknown. In such cases one might use the following corollary, which results from combining Theorem 1 with Theorem 2.

ACCEPTED MANUSCRIPT

Corollary 3. Under the conditions of Theorem 2, if G (x) -G (x y,k ) ≤ 1 for all k, y ∈ Ω k , we have for δ ∈ (0, 1): Pr F -EF ≤ 4aG ln 2/δ + 3a ln 2/δ ≥ 1 -δ,
and, if in addition F (x) -F (x y,k ) ≤ 1 for all k, and for all y ∈ Ω k , then

Pr EF -F ≤ 4aG ln 2/δ + 5 2 a ln 2/δ ≥ 1 -δ.
To exemplify the utility of these results, let X = (X 1 , ..., X n ) be a vector of independent random variables with values in the unit ball B of some Hilbert space H, let A (X) be the Gramian A (X) ij = X i , X j and λ d = λ d (X) the d-th eigenvalue of A (X) in descending order, counting eigenvalues according to their multiplicity. We will prove the following concentration property of the random variable λ d .

Theorem 4. For t > 0 Pr {λ d -Eλ d > t} ≤ exp -t 2 16Eλ max + 6t and Pr {Eλ d -λ d > t} ≤ exp -t 2 16Eλ max + 4t
Since X is distributed in the unit ball, the trace of A (X) can be at most n, but λ max can be much smaller, so the above bound can be considerably better than what we get if the bounded difference inequality [START_REF] Mcdiarmid | Concentration, in Probabilistic Methods of Algorithmic Discrete Mathematics[END_REF] is applied to the eigenvalues of the Gramian, as done by Shawe-Taylor et al (2005).

Let Ĉ (X) be the random operator on H defined by

Ĉ (X) y, z = 1 n n i=1 y, X i X i , z for y, z ∈ H.
Ĉ is sometimes called the (non-centered) empirical covariance operator. It describes the inertial moments of the empirical distribution (1/n) n i=1 δ Xi about the origin. The nonzero eigenvalues µ d of Ĉ satisfy µ d = λ d /n, as will be shown in Lemma 10 below. As with the more general Theorem 2, we obtain the following, purely empirical bound:

Corollary 5. Let δ ∈ (0, 1). Then Pr Eµ d ≥ µ d - 16µ max ln 2/δ n - 12 ln 2/δ n ≥ 1 -δ ACCEPTED MANUSCRIPT and Pr Eµ d ≤ µ d + 16µ max ln 2/δ n + 10 ln 2/δ n ≥ 1 -δ.
For large n the size of the confidence interval for our estimation of Eµ d by µ d scales with the observed value of √ µ max , or, equivalently, with the largest singular value of the data-matrix X.

Proofs

We first introduce some additional notation and state some useful auxiliary results. Then we prove Theorem 2 and Corollary 3, and finally we apply these results to the concentration of eigenvalues. Questions of measurability will be ignored throughout.

Let F be a bounded random variable, β ∈ R\ {0}. The Helmholtz energy is the real number

H F (β) = 1 β ln Ee βF .
By l'Hospital's rule the function H F is continuously extended to R by defining H F (0) = EF . The thermal expectation at inverse temperature β is defined by

E βF f = Ef e βF Ee βF for f : Ω → R.
To lighten notation we will not explicitely denote the dependence of H F and E βF on the underlying measure µ. We will also make repeated use of the real function g defined by g (t) = (e -t + t -1) /t 2 for t = 0 1/2 for t = 0 .

(2)

The function g is positive, nonincreasing, and for t ≤ 0 and a > 0 we have

ag (t) 1 -atg (t) ≤ max {1, a} 2 . ( 3
)
The following lemma is proved in (Maurer, 2006, Lemma 11).

Lemma 6. For β > 0 and any

F : Ω → R (i) ln E e β(F -E[F ]) ≤ β 2 β 0 E γF [DF ] dγ. ( 4
) (ii) If F -inf k F ≤ 1 for all k, then ln E e β(EF -F ) ≤ βg (-β) β 0 E -γF [DF ] dγ. (5)

ACCEPTED MANUSCRIPT

Our proofs rely on the following decoupling technique: If µ and ν are two probability measures and ν is absolutely continuous w.r.t. µ then it is easy to show that

E ν f ≤ KL (dν, dµ) + ln E µ e f ,
where KL (., .) is the Kullback-Leibler divergence or relative entropy KL (dν, dµ) = E ν ln (dν/dµ). A straightforward computation gives

KL e βF dµ E µ e βF , dµ = βE βF F -ln Ee βF = β 2 H ′ F (β) ,
so we obtain the following Lemma 7. We have for any

f : Ω → R E βF [f ] ≤ β 2 H ′ F (β) + ln E e f . (6)
We also need two technical optimization inequalities.

Lemma 8. For t ≥ 0 we have

inf β∈[0,1) -βt + β 2 (2 -β) (1 -β) 2 ≤ -t 2 8 + 3t
Proof. Consider the polynomial p (s) = 3s 2 -3ss 3 + 1.

Then p (1) = 0, p ′ (1) = 0 and p ′′ (s) ≤ 0 for all s ≥ 1. It follows that p (s) ≤ 0 for all s ≥ 1. Now define

h (β, t) = β 2 (2 -β) (1 -β) 2 -βt + t 2 8 + 3t
.

It suffices to show that inf β∈[0,1) h (β, t) ≤ 0 for all t ≥ 0. Write s = 1 + t/2, so that s ≥ 1. Then

inf β∈[0,1) h (β, t) = inf β∈[0,1) h β, 2 s 2 -1 ≤ h 1 - 1 s , 2 s 2 -1 = s 2 -1 s (1 + 3s 2 ) p (s) ≤ 0.
Lemma 9. Let C and b denote two positive real numbers, t > 0. Then

inf β∈[0,1/b) -βt + Cβ 2 1 -bβ ≤ -t 2 2 (2C + bt) . ( 7
)

ACCEPTED MANUSCRIPT

The proof of this lemma can be found in (Maurer, 2006, Lemma 12).

Proof of Theorem 2. We first claim that for β ∈ (0, 2/a)

ln

E e βG ≤ βEG 1 -aβ/2 , (8)
a fact which we will need for both tailbounds. Using Lemma 6 (i) and the weak self-boundedness assumption (iii) we have for β > 0 that

ln E e β(G-E[G]) ≤ aβ 2 β 0 E γG [G] dγ = aβ 2 ln Ee βG ,
where the last identity follows from the fact that E γG [G] = (d/dγ) ln Ee γG . Thus ln E e βG ≤ aβ 2 ln Ee βG + βEG, and rearranging this inequality for β ∈ (0, 2/a) establishes the claim. Now we prove the upwards deviation bound. For β ∈ (0, 2/a) by Lemma 7 for any function f : Ω → R,

β 0 E γF [f ] dγ ≤ β 0 γ 2 H ′ F (γ) dγ + β ln E e f = β ln E e βF -2 β 0 ln E e γF dγ + β ln E e f ≤ β ln E e βF + β ln E e f = β ln E e β(F -E[F ]) + β 2 E [F ] + β ln E e f .
In the second line we used integration by parts and in the third line the fact that ln E e γF ≥ 0 if γ ≥ 0, since F ≥ 0. So, replacing f by βG we get by Lemma 6 (i) and DF ≤ aG

ln E e β(F -E[F ]) ≤ a 2 β 0 E γF [βG] dγ ≤ aβ 2 ln E e β(F -E[F ]) + aβ 2 2 E [F ] + aβ 2 ln E e βG .
Substitution of (8) and subtracting (aβ/2) ln

E e β(F -E[F ]) gives 1 - aβ 2 ln E e β(F -E[F ]) ≤ aβ 2 2 E [F ] + a 2 β 2 E [G] 1 -aβ/2 ≤ β 2 a 2 E [G] 1 + 1 1 -aβ/2 ,

ACCEPTED MANUSCRIPT

where we used EF ≤ EG for the second inequality. Dividing by 1aβ/2 we obtain

ln E e β(F -E[F ]) ≤ a 2 E [G] β 2 (2 -aβ/2) (1 -aβ/2) 2 .
Now we make use of Lemma 8 for t > 0 inf

β∈[0,2/a) a 2 E [G] β 2 (2 -aβ/2) (1 -aβ/2) 2 -βt = 2 a E [G] inf β∈[0,1) β 2 (2 -β) (1 -β) 2 -β t E [G] ≤ -t 2 4aE [G] + 3at/2 .
From Markov's inequality we now conclude that for t > 0

Pr {F -EF > t} ≤ inf β∈(0,2/a) Ee β(F -EF )-βt ≤ exp -t 2 4aE [G] + 3at/2 .
To prove the lower tailbound let again β ∈ (0, 2/a). Using Lemma 6 (ii) and DF ≤ aG we get ln Ee β(EF -F ) ≤ βg (-β)

β 0 E -γF [DF ] dγ ≤ ag (-β) β 0 E -γF [βG] dγ. (9)
Since F is nonnegative, ln Ee -γF is nonincreasing and

β(EF -F ) ≤ ag (-β) 1 + aβg (-β) β 2 EF + β ln Ee βG ≤ a 2 β 2 EF + β ln Ee βG , A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT
where we used (3). But for β ∈ (0, 2/a) we can substitute inequality (8) and use assumption (i) to get

ln Ee β(EF -F ) ≤ a 2 β 2 EF + β 2 E [G] 1 -aβ/2 ≤ aE [G] 2 2β 2 -aβ 3 /2 1 -aβ/2 ≤ aE [G] β 2 1 -aβ/2 . Now Lemma 9 gives us inf β∈(0,2/a) -βt + aE [G] β 2 1 -aβ/2 ≤ -t 2 4aE [G] + at .
Conclude with Markov's inequality as before

Proof of Corollary 3. Equating the two deviation probabilities in Theorem 2 to δ/2 gives Pr If we use a union bound to substitute this inequality in ( 10) and ( 11) and observe that √ 2 < 3/2, we obtain the conclusions To apply our result to the eigenvalues of Gramian matrices and the related inertial operators we first further clarify the relationship between these objects. Suppose that x = (x 1 , ..., x n ) ∈ H n is some configuration of vectors. The Gramian matrix A (x) and the inertial operator Ĉ (x) have already been introduced. We define an operator T (x) ∈ L (H) by the formula

F -EF > 2 √ EG a ln 2/δ + 3a ln 2/δ 2 < δ/2, (10) and
T (x) v = n i=1
v, x i x i for v ∈ H, so that Ĉ (x) = (1/n) T (x). Notice that T (x) has rank at most n. If S is a finite-rank operator (or matrix) acting on a Hilbert space we use σ (S) to denote the set of eigenvalues of S.

β 0 ln 0 ln 0 E

 000 Ee -γF dγ ≥ β ln Ee -βF . From integration by parts (usingH ′ F (-γ) = -(d/dγ) H F (-γ)) we therefore find that β 0 γ 2 H ′ F (-γ) dγ = β ln Ee -βF -2 β Ee -γF dγ ≤ -β ln Ee -βF ,By the decoupling lemma 7 it follows thatβ -γF [βG] dγ ≤ β 0 γ 2 H ′ F (-γ) + ln Ee βG dγ ≤ -β ln Ee -βF + β ln Ee βG .Resubstitution of this result in (9) givesln Ee β(EF -F ) ≤ ag (-β) -β ln Ee -βF + β ln Ee βG = -aβg (-β) ln Ee β(EF -F ) + ag (-β) β 2 EF + β ln Ee βG .Now add aβg (-β) ln Ee β(EF -F ) to both sides, factor out ln Ee β(EF -F ) and rearrange to get ln Ee

  , if F (x) -F (x y,k ) for all k, y ∈ Ω k , then Pr EF -F > 2 √ EG a ln 2/δ + a ln 2/δ < δ/2. (11)It follows from Theorem 1 that under the conditions of the corollary also Pr EG -G > 2aEG ln 2/δ < δ/2, from which we derive Pr √ EG > √ G + 2a ln 2/δ < δ/2.

Preprint submitted to ElsevierDecember 26, 2009

ACCEPTED MANUSCRIPT

Lemma 10. σ (A (x)) ⊆ σ (T (x)) and σ (T (x)) \ {0} ⊆ σ (A (x)).

Proof. If λ is any eigenvalue of A (x) let γ ∈ R n be a corresponding eigenvector and set e = γ i x i to obtain

Observe, that we also showed that if γ ∈ ker (A (x)), then γ i x i ∈ ker (T (x)). Now if λ is a nonzero eigenvalue of T (x) let e be a corresponding eigenvector. Since λ is nonzero we must have e ∈ [x], so e = γ i x i , with γ = 0, and, by the above, also γ / ∈ ker (A (x)). We have

so λ is also an eigenvalue of A (x) with nonzero eigenvector A (x) γ

Note that, whenever dim (H) > n and the x i are independent, zero is an eigenvalue of T (x), but not of A (x) so that σ (A (x)) ⊂ σ (T (x)) is a proper inclusion. To prove Theorem 4 and Corollary 5 we will use the following technical result:

Proposition 11. Let B be the unit ball in some separable real Hilbert-space H. For x ∈ B n define λ d (x) to be the d-th eigenvalue (in descending order) of the Gramian A ij (x) = x i , x j . Then ∀x ∈ B n , k ∈ {1, ..., n} we have

Proof. Fix x ∈ B n and some integer k ∈ {1, ..., n}. We first claim that

The l.h.s. is clearly less than or equal the r.h.s. so we just have to show the reverse inequality. By Lemma 10 λ d (x) is also the d-th eigenvalue of T (x). Now let y ∈ B be arbitrary and let Q y be the operator defined by

By Weyls monotonicity theorem (see Horn and Johnson, 1985, Corollary 4.3.3) the d-th eigenvalue of T (x 0,k ) can only increase by adding the positive operator Q y . Since the nonzero eigenvalues of T (x) are the same as those of A (x) we have λ d (x 0,k ) ≤ λ d (x y,k ), which proves the claim. Now let V be the span of the d dominant eigenvectors v 1 , ..., v d of A (x), and let W be the span of the d -1 dominant eigenvectors of A (x 0,k ). Then

and we can choose a unit vector u ∈ W ⊥ ∩ V . We now use the variational characterization of the eigenvalues (Theorem 4.2.11 in [START_REF] Horn | Matrix Analysis[END_REF]): Since u ∈ V we have λ d (x) ≤ A (x) u, u , and since u ∈ W ⊥ we have A (x 0,k ) u, u ≤ λ d (x 0,k ). Thus, using the definition of the Gramian, polarization and Cauchy-Schwarz, The author wishes to thank the anonymous referee for many valuable comments and suggestions.