Y Boubacar Mainassara

C Francq

Estimating structural VARMA models with uncorrelated but non-independent error terms

Keywords: Echelon form, Lagrange Multiplier test, Likelihood Ratio test, Nonlinear processes, QMLE, Structural representation, VARMA models, Wald test

The asymptotic properties of the quasi-maximum likelihood estimator (QMLE) of vector autoregressive moving-average (VARMA) models are derived under the assumption that the errors are uncorrelated but not necessarily independent. Relaxing the independence assumption considerably extends the range of application of the VARMA models, and allows to cover linear representations of general nonlinear processes. Conditions are given for the consistency and asymptotic normality of the QMLE. A particular attention is given to the estimation of the asymptotic variance matrix, which may be very different from that obtained in the standard framework. Modified versions of the Wald, Lagrange Multiplier and Likelihood Ratio tests are proposed for testing linear restrictions on the parameters.

Introduction

This paper is devoted to the problem of estimating VARMA representations of multivariate (nonlinear) processes.

In order to give a precise definition of a linear model and of a nonlinear process, first recall that by the Wold decomposition (see e.g. [START_REF] Brockwell | Time series: theory and methods[END_REF], for the univariate case, and [START_REF] Reinsel | Elements of multivariate time series Analysis[END_REF], in the multivariate framework) any zero-mean purely non deterministic d-dimensional stationary process (X t ) can be written in the form

X t = ∞ ℓ=0 Ψ ℓ ǫ t-ℓ , (ǫ t ) ∼ WN(0, Σ) (1)
where ℓ Ψ ℓ 2 < ∞. The process (ǫ t ) is called the linear innovation process of the process X = (X t ), and the notation (ǫ t ) ∼ WN(0, Σ) signifies that (ǫ t ) is a weak white noise. A weak white noise is a stationary sequence of centered and uncorrelated random variables with common variance matrix Σ. By contrast, a strong white noise, denoted by IID(0, Σ), is an independent and identically distributed (iid) sequence of random variables with mean 0 and variance Σ. A strong white noise is obviously a weak white noise, because independence entails uncorrelatedness, but the reverse is not true. Between weak and strong white noises, one can define a semi-strong white noise as a stationary martingale difference. An example of semi-strong white noise is the generalized autoregressive conditional heteroscedastic (GARCH) model. In the present paper, a process X is said to be linear when (ǫ t ) ∼ IID(0, Σ) in [START_REF] Andrews | Heteroskedasticity and autocorrelation consistent covariance matrix estimation[END_REF], and is said to be nonlinear in the opposite case. With this definition, GARCH-type processes are considered as nonlinear. Leading examples of linear processes are the VARMA and the sub-class of the vector autoregressive (VAR) models with iid noise. Nonlinear models are becoming more and more employed because numerous real time series exhibit nonlinear dynamics, for instance conditional heteroscedasticity, which can not be generated by autoregressive moving-average (ARMA) models with iid noises. 1 The main issue with nonlinear models is that they are generally hard to identify and implement. This is why it is interesting to consider weak (V)ARMA models, that is ARMA models with weak white noises, such linear representations being universal approximations of the Wold decomposition [START_REF] Andrews | Heteroskedasticity and autocorrelation consistent covariance matrix estimation[END_REF]. Linear and nonlinear processes also have exact weak ARMA representations because a same process may satisfy several models, and many important classes of nonlinear processes admit weak ARMA representations (see Francq, Roy and Zakoïan, 2005, and the references therein).

The estimation of autoregressive moving-average (ARMA) models is however 1 To cite few examples of nonlinear processes, let us mention the self-exciting threshold autoregressive (SETAR), the smooth transition autoregressive (STAR), the exponential autoregressive (EXPAR), the bilinear, the random coefficient autoregressive (RCA), the functional autoregressive (FAR) (see [START_REF] Tong | Non-linear time series: A Dynamical System Approach[END_REF][START_REF] Fan | Nonlinear time series: Nonparametric and parametric methods[END_REF][START_REF] Fan | Nonlinear time series: Nonparametric and parametric methods[END_REF], for references on these nonlinear time series models). All these nonlinear models have been initially proposed for univariate time series, but have multivariate extensions. much more difficult in the multivariate than in univariate case. A first difficulty is that non trivial constraints on the parameters must be imposed for identifiability of the parameters (see [START_REF] Reinsel | Elements of multivariate time series Analysis[END_REF][START_REF] Lütkepohl | New introduction to multiple time series analysis[END_REF]. Secondly, the implementation of standard estimation methods (for instance the Gaussian quasi-maximum likelihood estimation) is not obvious because this requires a constrained high-dimensional optimization (see [START_REF] Lütkepohl | New introduction to multiple time series analysis[END_REF], for a general reference and [START_REF] Kascha | A Comparison of Estimation Methods for Vector Autoregressive Moving-Average Models[END_REF], for a numerical comparison of alternative estimation methods of VARMA models). These technical difficulties certainly explain why VAR models are much more used than VARMA in applied works. This is also the reason why the asymptotic theory of weak ARMA model estimation is mainly limited to the univariate framework (see Francq and Zakoïan, 2005, for a review on weak ARMA models). Notable exceptions are [START_REF] Dufour | Practical methods for modelling weak VARMA processes: identification, estimation and specification with a macroeconomic application[END_REF] who study the asymptotic properties of a generalization of the regression-based estimation method proposed by [START_REF] Hannan | Recursive estimation of mixed of Autoregressive Moving Average order[END_REF] under weak assumptions on the innovation process, and [START_REF] Francq | Multivariate Portmanteau Test for Autoregressive Models with Uncorrelated but Nonindependent Errors[END_REF] who study portmanteau tests for weak VAR models.

For the estimation of ARMA and VARMA models, the commonly used estimation method is the QMLE, which can also be viewed as a nonlinear least squares estimation (LSE). The asymptotic properties of the QMLE of VARMA models are well-known under the restrictive assumption that the errors ǫ t are independent (see [START_REF] Lütkepohl | New introduction to multiple time series analysis[END_REF]. The asymptotic behavior of the QMLE has been studied in a much wider context by [START_REF] Dunsmuir | Vector linear time series models[END_REF] and [START_REF] Hannan | The Statistical Theory of Linear Systems[END_REF] who proved consistency, under weak assumptions on the noise process and based on a spectral analysis. These authors also obtained asymptotic normality under a conditionally homoscedastic martingale difference assumption on the linear innovations. However, this assumption precludes most of the nonlinear models. Little is thus known when the martingale difference assumption is relaxed. Our aim in this paper is to consider a flexible VARMA specification covering the structural forms encountered in econometrics, and to relax the independence assumption, and even the martingale difference assumption, in order to be able to cover weak VARMA representations of general nonlinear models.

The paper is organized as follows. Section 2 presents the structural weak VARMA models that we consider here. Structural forms are employed in econometrics in order to introduce instantaneous relationships between economic variables. The identifiability issues are discussed. It is shown in Section 3 that the QMLE is strongly consistent when the weak white noise (ǫ t ) is ergodic, and that the QMLE is asymptotically normally distributed when (ǫ t ) satisfies mild mixing assumptions. The asymptotic variance of the QMLE may be very different in the weak and strong cases. Section 4 is devoted to the estimation of this covariance matrix. In Section 5 it is shown how the standard Wald, LM (Lagrange multiplier) and LR (likelihood ratio) tests must be adapted in the weak VARMA case in order to test for general linearity constraints. This section is also of interest in the univariate framework because, to our knowledge, these tests have not been studied for weak ARMA models. Numerical experiments are presented in Section 6. The proofs of the main results are collected in the appendix.

Model and assumptions

Consider a d-dimensional stationary process (X t ) satisfying a structural VARMA(p, q) representation of the form

A 00 X t - p i=1 A 0i X t-i = B 00 ǫ t - q i=1 B 0i ǫ t-i , (ǫ t ) ∼ WN(0, Σ 0 ), (2)
where Σ 0 is non singular and t ∈ Z = {0, ±1, . . . }. The standard VARMA(p, q) form, which is sometimes called the reduced form, is obtained for A 00 = B 00 = I d . The structural forms are mainly used in econometrics to identify structural economic shocks and to allow instantaneous relationships between economic variables. Of course, constraints are necessary for the identifiability of the (p + q + 3)d 2 elements of the matrices involved in the VARMA equation [START_REF] Berk | Consistent Autoregressive Spectral Estimates[END_REF].

We thus assume that these matrices are parameterized by a vector ϑ 0 of lower dimension. We then write A 0i = A i (ϑ 0 ) and B 0j = B j (ϑ 0 ) for i = 0, . . . , p and j = 0, . . . , q, and Σ 0 = Σ(ϑ 0 ), where ϑ 0 belongs to the parameter space Θ ⊂ R k 0 , and k 0 is the number of unknown parameters, which is typically much smaller that (p + q + 3)d 2 . The parametrization is often linear (see Example 1 below), and thus satisfies the following smoothness conditions.

A1:

The applications ϑ → A i (ϑ) i = 0, . . . , p, ϑ → B j (ϑ) j = 0, . . . , q and ϑ → Σ(ϑ) admit continuous third order derivatives for all ϑ ∈ Θ.

For simplicity we now write A i , B j and Σ instead of A i (ϑ), B j (ϑ) and Σ(ϑ).

Let A ϑ (z) = A 0 -p i=1 A i z i and B ϑ (z) = B 0 -q i=1 B i z i .
We assume that Θ corresponds to stable and invertible representations, namely

A2:

for all ϑ ∈ Θ, we have det A ϑ (z) det B ϑ (z) = 0 for all |z| ≤ 1.

To show the strong consistency of the QMLE, we will use the following assumptions.

A3:

We have ϑ 0 ∈ Θ, where Θ is compact.

A4:

The process (ǫ t ) is stationary and ergodic.

A5:

For all ϑ ∈ Θ such that ϑ = ϑ 0 , either the transfer functions

A -1 0 B 0 B -1 ϑ (z)A ϑ (z) = A -1 00 B 00 B -1 ϑ 0 (z)A ϑ 0 (z)
for some z ∈ C, or

A -1 0 B 0 ΣB ′ 0 A -1 ′ 0 = A -1 00 B 00 Σ 0 B ′ 00 A -1 ′ 00 .
Remark 1 The previous identifiability assumption is satisfied when the parameter space Θ is sufficiently constrained. Note that the last condition in A5 can be dropped for the standard reduced forms in which A 0 = B 0 = I d , but may be important for structural VARMA forms (see Example 1 below). The identifiability of VARMA processes has been studied in particular by [START_REF] Hannan | The identification and parametrization of ARMAX and state space forms[END_REF] who gave several procedures ensuring identifiability. In particular A5 is satisfied when we impose

A 0 = B 0 = I d , A2,
   1 0 -α 03 1    X t =    α 01 α 02 α 04 α 05    X t-1 + ǫ t .
We also assume that the two components of ǫ t correspond to uncorrelated structural economic shocks, with respective variances σ 2 01 and σ 2 02 . We thus have ϑ ′ 0 = (α 01 , α 02 , α 03 , α 04 , α 05 , σ 2 01 , σ 2 02 ). Note that the identifiability condition A5 is satisfied because for all ϑ = (α 1 , α 2 , α 3 , α 4 , α 5 , σ 2 1 , σ 2 2 ) ′ = ϑ 0 we have

I 2 -    α 1 α 2 α 1 α 3 + α 4 α 2 α 3 + α 5    z = I 2 -    α 01 α 02 α 01 α 03 + α 04 α 02 α 03 + α 05    z for some z ∈ C, or    σ 2 1 σ 2 1 α 3 σ 2 1 α 3 σ 2 1 α 2 3 + σ 2 2    =    σ 2 01 σ 2 01 α 03 σ 2 01 α 03 σ 2 01 α 2 03 + σ 2 02    .
3 Quasi-maximum likelihood estimation Let X 1 , . . . , X n be observations of a process satisfying the VARMA representation [START_REF] Berk | Consistent Autoregressive Spectral Estimates[END_REF]. Note that from A2 the matrices A 00 and B 00 are invertible.

Introducing the innovation process e t = A -1 00 B 00 ǫ t , the structural representation A ϑ 0 (L)X t = B ϑ 0 (L)ǫ t can be rewritten as the reduced VARMA representation

X t - p i=1 A -1 00 A 0i X t-i = e t - q i=1 A -1 00 B 0i B -1 00 A 00 e t-i . (3)
For all ϑ ∈ Θ, we recursively define ẽt (ϑ) for t = 1, . . . , n by

ẽt (ϑ) = X t - p i=1 A -1 0 A i X t-i + q i=1 A -1 0 B i B -1 0 A 0 ẽt-i (ϑ), with initial values ẽ0 (ϑ) = • • • = ẽ1-q (ϑ) = X 0 = • • • = X 1-p = 0.
It will be shown that these initial values are asymptotically negligible and, in particular, that ẽt (ϑ 0 )e t → 0 almost surely as t → ∞. The Gaussian quasi-likelihood is given by

Ln (ϑ) = n t=1 1 (2π) d/2 √ det Σ e exp - 1 2 ẽ′ t (ϑ)Σ -1 e ẽt (ϑ) ,
where

Σ e = Σ e (ϑ) = A -1 0 B 0 ΣB ′ 0 A -1 ′ 0 .
Note that the variance of e t is Σ e0 = Σ e (ϑ 0 ) = A -1 00 B 00 Σ 0 B ′ 00 A -1 ′ 00 . A quasimaximum likelihood estimator (QMLE) is a measurable solution θn of θn = arg max ϑ∈Θ Ln (ϑ) = arg min ϑ∈Θ ln (ϑ), ln (ϑ) = -2 n log Ln (ϑ).

The following theorem shows that, for the consistency of the QMLE, the conventional assumption that the noise (ǫ t ) is an iid sequence can be replaced by the less restrictive ergodicity assumption A4. [START_REF] Dunsmuir | Vector linear time series models[END_REF] for VARMA in reduced form, and [START_REF] Hannan | The Statistical Theory of Linear Systems[END_REF] for VARMAX models, obtained an equivalent result, using spectral analysis. For the proof, we do not use the spectral analysis techniques employed by the above-mentioned authors, but we follow the classical technique of [START_REF] Wald | Note on the consistency of the maximum likelihood estimate[END_REF], as was done by [START_REF] Rissanen | The strong consistency of maximum likelihood estimators for ARMA processes[END_REF] to show the strong consistency of the Gaussian maximum likelihood estimator of VARMA models.

Theorem 1 Let (X t ) be the causal solution of the VARMA equation ( 2) satisfying A1-A5 and let θn be a QMLE. Then θn → ϑ 0 a.s. as n → ∞.

For the asymptotic normality of the QMLE, it is necessary to assume that ϑ 0 is not on the boundary of the parameter space Θ.

A6:

We have ϑ 0 ∈

• Θ , where

• Θ denotes the interior of Θ.

We now introduce mixing assumptions similar to those made by Francq and Zakoïan (1998), hereafter FZ. We denote by α ǫ (k), k = 0, 1, . . . , the strong mixing coefficients of the process (ǫ t ).

A7:

We have

E ǫ t 4+2ν < ∞ and ∞ k=0 {α ǫ (k)} ν 2+ν < ∞ for some ν > 0.
We define the matrix of the coefficients of the reduced form (3) by

M ϑ 0 = [A -1 00 A 01 : • • • : A -1 00 A 0p : A -1 00 B 01 B -1 00 A 00 : • • • : A -1 00 B 0q B -1 00 A 00 : Σ e0 ].
Now we need an assumption which specifies how this matrix depends on the parameter ϑ 0 . Let M ϑ 0 be the matrix ∂vec(M ϑ )/∂ϑ ′ evaluated at ϑ 0 .

A8:

The matrix M ϑ 0 is of full rank k 0 .

One can easily verify that A8 is satisfied in Example 1.

Theorem 2 Under the assumptions of Theorem 1, and A6-A8, we have

√ n θn -ϑ 0 L → N (0, Ω := J -1 IJ -1 ),
where J = J(ϑ 0 ) and I = I(ϑ 0 ), with

J(ϑ) = lim n→∞ ∂ 2 ∂ϑ∂ϑ ′ ln (ϑ) a.s., I(ϑ) = lim n→∞ Var ∂ ∂ϑ ln (ϑ).
For VARMA models in reduced form, it is not very restrictive to assume that the coefficients A 0 , . . . , A p , B 0 , . . . , B q are functionally independent of the coefficient Σ e . Thus we can write ϑ = (ϑ (1) ′ , ϑ (2) ′ ) ′ , where ϑ (1) ∈ R k 1 depends on A 0 , . . . , A p and B 0 , . . . , B q , and where

ϑ (2) ∈ R k 2 depends on Σ e , with k 1 + k 2 = k 0 .
With some abuse of notation, we will then write e t (ϑ) = e t (ϑ (1) ).

A9:

With the previous notation ϑ = (ϑ

(1) ′ , ϑ (2) ′ ) ′ , where ϑ (2) = D vec Σ e for some matrix D of size k 2 × d 2 .
The following theorem shows that for VARMA in reduced form, the QMLE and LSE coincide. We denote by A ⊗ B the Kronecker product of two matrices A and B.

Theorem 3 Under the assumptions of Theorem 2 and A9 the QMLE θn =

( θ(1) ′ n , θ(2) ′ n ) ′ can be obtained from θ(2) n = D vec Σe , Σe = 1 n n t=1 ẽt ( θ(1) n )ẽ ′ t ( θ(1) n ),
and θ(1) n = arg min ϑ (1) det n t=1 ẽt (ϑ (1) )ẽ ′ t (ϑ (1) ).

Moreover J =    J 11 0 0 J 22    , with J 11 = 2E ∂ ∂ϑ (1) e ′ t (ϑ (1) 0 ) Σ -1 e0 ∂ ∂ϑ (1) ′ e t (ϑ (1) 0 ) and J 22 = D(Σ -1 e0 ⊗ Σ -1 e0 )D ′ .
Remark 2 One can see that J has the same expression in the strong and weak ARMA cases (see [START_REF] Lütkepohl | New introduction to multiple time series analysis[END_REF] page 480). On the contrary, the matrix I is in general much more complicated in the weak case than in the strong case.

Remark 3 In the standard strong VARMA case, i.e. when A4 is replaced by the assumption that (ǫ t ) is iid, we have I = 2J, so that Ω = 2J -1 . In the general case we have I = 2J. As a consequence the ready-made software used to fit VARMA do not provide a correct estimation of Ω for weak VARMA processes. The problem also holds in the univariate case (see Francq and Zakoïan, 2007, and the references therein).

Estimating the asymptotic variance matrix

Theorem 2 can be used to obtain confidence intervals and significance tests for the parameters. The asymptotic variance Ω must however be estimated. The matrix J can easily be estimated by its empirical counterpart. For instance, under A9, one can take

Ĵ =    Ĵ11 0 0 Ĵ22    , Ĵ11 = 2 n n t=1 ∂ ∂ϑ (1) ẽ′ t ( θ(1) n ) Σ-1 e ∂ ∂ϑ (1) ′ ẽt ( θ(1) n ) ,
and Ĵ22 = D( Σ-1 e ⊗ Σ-1 e )D ′ . In the standard strong VARMA case Ω = 2 Ĵ-1 is a strongly consistent estimator of Ω. In the general weak VARMA case this estimator is not consistent when I = 2J (see Remark 3). So we need a consistent estimator of I. Note that

I = Var as 1 √ n n t=1 Υ t = +∞ h=-∞ Cov(Υ t , Υ t-h ), (4)
where

Υ t = ∂ ∂ϑ log det Σ e + e ′ t (ϑ (1) )Σ -1 e e t (ϑ (1) ) ϑ=ϑ 0 . (5)
In the econometric literature the nonparametric kernel estimator, also called heteroscedastic autocorrelation consistent (HAC) estimator (see [START_REF] Newey | A simple, positive semi-definite, heteroskedasticity and autocorrelation consistent covariance matrix[END_REF]West, 1987, or Andrews, 1991), is widely used to estimate covariance matrices of the form I. Let Υt be the vector obtained by replacing ϑ 0 by θn in Υ t . The matrix Ω is then estimated by a "sandwich" estimator of the form

ΩHAC = Ĵ-1 ÎHAC Ĵ-1 , ÎHAC = 1 n n t,s=1 ω |t-s| Υt Υs ,
where ω 0 , . . . , ω n-1 is a sequence of weights (see [START_REF] Andrews | Heteroskedasticity and autocorrelation consistent covariance matrix estimation[END_REF], and Newey and West, 1987, for the problem of the choice of weights).

Interpreting (2π) -1 I as the spectral density of the stationary process (Υ t ) evaluated at frequency 0 (see Brockwell and Davis, 1991, p. 459), an alternative method consists in using a parametric AR estimate of the spectral density of (Υ t ). This approach, which has been studied by [START_REF] Berk | Consistent Autoregressive Spectral Estimates[END_REF] (see also den Haan and Levin, 1997), rests on the expression

I = Φ -1 (1)Σ u Φ -1 (1)
when (Υ t ) satisfies an AR(∞) representation of the form

Φ(L)Υ t := Υ t + ∞ i=1 Φ i Υ t-i = u t , (6)
where u t is a weak white noise with variance matrix Σ u . Let Φr (z) = I k 0 + r i=1 Φr,i z i , where Φr,1 , • • • , Φr,r denote the coefficients of the LS regression of Υt on Υt-1 , • • • , Υt-r . Let ûr,t be the residuals of this regression, and let Σûr be the empirical variance of ûr,1 , . . . , ûr,n .

We are now able to state the following theorem, which is an extension of a result given in Francq, Roy and Zakoïan (2005).

Theorem 4 In addition to the assumptions of Theorem 2, assume that the process (Υ t ) defined in (5) admits an AR(∞) representation [START_REF] Dufour | Practical methods for modelling weak VARMA processes: identification, estimation and specification with a macroeconomic application[END_REF] in which the roots of det Φ(z) = 0 are outside the unit disk, Φ i = o(i -2 ), and Σ u = Var(u t ) is non-singular. Moreover we assume that ǫ t 8+4ν < ∞ and ∞ k=0 {α X,ǫ (k)} ν/(2+ν) < ∞ for some ν > 0, where {α X,ǫ (k)} k≥0 denotes the sequence of the strong mixing coefficients of the process (X ′ t , ǫ ′ t ) ′ . Then the spectral estimator of I

ÎSP := Φ-1 r (1) Σûr Φ′-1 r (1) → I
in probability when r = r(n) → ∞ and r 3 /n → 0 as n → ∞.

Testing linear restrictions on the parameter

It may be of interest to test s 0 linear constraints on the elements of ϑ 0 (in particular A 0p = 0 or B 0q = 0). We thus consider a null hypothesis of the form

H 0 : R 0 ϑ 0 = r 0
where R 0 is a known s 0 ×k 0 matrix of rank s 0 and r 0 is a known s 0 -dimensional vector. The Wald, LM and LR principles are employed frequently for testing H 0 . The LM test is also called the score or Rao-score test. We now examine if these principles remain valid in the non standard framework of weak VARMA models.

Let Ω = Ĵ-1 Î Ĵ-1 , where Ĵ and Î are consistent estimator of J and I, as defined in Section 4. Under the assumptions of Theorems 2 and 4, and the assumption that I is invertible, the Wald statistic

W n = n(R 0 θn -r 0 ) ′ (R 0 ΩR ′ 0 ) -1 (R 0 θn -r 0 )
asymptotically follows a χ 2 s 0 distribution under H 0 . Therefore, the standard formulation of the Wald test remains valid. More precisely, at the asymptotic level α, the Wald test consists in rejecting H 0 when W n > χ 2 s 0 (1α). It is however important to note that a consistent estimator of the form Ω = Ĵ-1 Î Ĵ-1 is required. The estimator Ω = 2 Ĵ-1 , which is routinely used in the time series softwares, is only valid in the strong VARMA case.

We now turn to the LM test. Let θc n be the restricted QMLE of the parameter under H 0 . Define the Lagrangean

L(ϑ, λ) = ln (ϑ) -λ ′ (R 0 ϑ -r 0 ),
where λ denotes a s 0 -dimensional vector of Lagrange multipliers. The firstorder conditions yield

∂ ln ∂ϑ ( θc n ) = R ′ 0 λ, R 0 θc n = r 0 .
It will be convenient to write a

= √ n ∂ ln ( θc n ) ∂ϑ -J √ n θn -θc n .
We deduce that

√ n(R 0 θn -r 0 ) = R 0 √ n( θn -θc n ) o P (1) = R 0 J -1 √ n ∂ ln ( θc n ) ∂ϑ = R 0 J -1 R ′ 0 √ n λ.
Thus under H 0 and the previous assumptions,

√ n λ L → N 0, (R 0 J -1 R ′ 0 ) -1 R 0 ΩR ′ 0 (R 0 J -1 R ′ 0 ) -1 , (7)
so that the LM statistic is defined by

LM n = n λ′ (R 0 Ĵ-1 R ′ 0 ) -1 R 0 ΩR ′ 0 (R 0 Ĵ-1 R ′ 0 ) -1 -1 λ = n ∂ ln ∂ϑ ′ ( θc n ) Ĵ-1 R ′ 0 R 0 ΩR ′ 0 -1 R 0 Ĵ-1 ∂ ln ∂ϑ ( θc n ).
Note that in the strong VARMA case, Ω = 2 Ĵ-1 and the LM statistic takes the more conventional form

LM * n = (n/2) λ′ R 0 Ĵ-1 R ′ 0 λ.
In the general case, strong and weak as well, the convergence [START_REF] Dunsmuir | Vector linear time series models[END_REF] implies that the asymptotic distribution of the LM n statistic is χ 2 s 0 under H 0 . The null is therefore rejected when LM n > χ 2 s 0 (1α). Of course the conventional LM test with rejection region LM * n > χ 2 s 0 (1-α) is not asymptotically valid for general weak VARMA models.

Standard Taylor expansions show that

√ n( θn -θc n ) o P (1) = - √ nJ -1 R ′ 0 λ,
and that the LR statistic satisfies

LR n := 2 log Ln ( θn ) -log Ln ( θc n ) o P (1) = n 2 ( θn -θc n ) ′ J( θn -θc n ) o P (1) = LM * n .
Using the previous computations and standard results on quadratic forms of normal vectors (see e.g. Lemma 17.1 in van der Vaart, 1998), we find that the LR n statistic is asymptotically distributed as s 0 i=1 λ i Z 2 i where the Z i 's are iid N (0, 1) and λ 1 , . . . , λ s 0 are the eigenvalues of

Σ LR = J -1/2 S LR J -1/2 , S LR = 1 2 R ′ 0 (R 0 J -1 R ′ 0 ) -1 R 0 ΩR ′ 0 (R 0 J -1 R ′ 0 ) -1 R 0 .
Note that when Ω = 2J -1 , the matrix

Σ LR = J -1/2 R ′ 0 (R 0 J -1 R ′ 0 ) -1 R 0 J -1/
2 is a projection matrix. Its eigenvalues are therefore equal to 0 and 1, and the number of eigenvalues equal to 1 is Tr J

-1/2 R ′ 0 (R 0 J -1 R ′ 0 ) -1 R 0 J -1/2 = Tr I s 0 =
s 0 . Therefore we retrieve the well-known result that LR n ∼ χ 2 s 0 under H 0 in the strong VARMA case. In the weak VARMA case, the asymptotic null distribution of LR n is complicated. It is possible to evaluate the distribution of a quadratic form of a Gaussian vector by means of the Imhof algorithm [START_REF] Imhof | Computing the distribution of quadratic forms in normal variables[END_REF]), but the algorithm is time consuming. An alternative is to use the transformed statistic

n 2 ( θn -θc n ) ′ Ĵ Ŝ- LR Ĵ ( θn -θc n ) (8)
which follows a χ 2 s 0 under H 0 , when Ĵ and Ŝ-LR are weakly consistent estimators of J and of a generalized inverse of S LR . The estimator Ŝ-LR can be obtained from the singular value decomposition of any weakly consistent estimator ŜLR of S LR . More precisely, defining the diagonal matrix Λ = diag( λ1 , . . . , λk 0 ) where λ1 ≥ λ2 ≥ • • • ≥ λk 0 denote the eigenvalues of the symmetric matrix ŜLR , and denoting by P an orthonormal matrix such that ŜLR = P Λ P ′ , one can set Ŝ-LR = P Λ-P ′ , Λ-= diag λ-1 1 , . . . , λ-1 s 0 , 0, . . . , 0 . The matrix Ŝ-LR then converges weakly to a matrix S - LR satisfying S LR S - LR S LR = S LR , because S LR has full rank s 0 .

Numerical illustrations

We first study numerically the behaviour of the QMLE for strong and weak VARMA models of the form

   X 1t X 2t    =    0 0 0 a 1 (2, 2)       X 1,t-1 X 2,t-1    +    ǫ 1,t ǫ 2,t    -    0 0 b 1 (2, 1) b 1 (2, 2)       ǫ 1,t-1 ǫ 2,t-1    , (9) where 
  ǫ 1,t ǫ 2,t    ∼ IID N (0, I 2 ), (10)
in the strong case, and

   ǫ 1,t ǫ 2,t    =    η 1,t (|η 1,t-1 | + 1) -1 η 2,t (|η 2,t-1 | + 1) -1    , with    η 1,t η 2,t    ∼ IID N (0, I 2 ), (11)
in the weak case. Model ( 9) is a VARMA(1,1) model in echelon form. The noise defined by ( 11) is a direct extension of a weak noise defined by Romano and Thombs (1996) in the univariate case. The numerical illustrations of this section are made with the free statistical software R (see http://cran.rproject.org/). We simulated N = 1, 000 independent trajectories of size n = 2, 000 of Model ( 9), first with the strong Gaussian noise [START_REF] Francq | Diagnostic checking in ARMA Models with Uncorrelated Errors[END_REF], second with the weak noise [START_REF] Francq | Estimating linear representations of nonlinear processes[END_REF]. Figure 1 compares the distribution of the QMLE in the strong and weak noise cases. The distributions of â1 (2, 2) and b1 (2, 1) are similar in the two cases, whereas the QMLE of b1 (2, 2) is more accurate in the weak case than in the strong one. Similar simulation experiments, not reported here, reveal that the situation is opposite, that is the QMLE is more accurate in the strong case than in the weak case, when the weak noise is defined by ǫ i,t = η i,t η i,t-1 for i = 1, 2. This is in accordance with the results of [START_REF] Romano | Inference for autocorrelations under weak assumptions[END_REF] who showed that, with similar noises, the asymptotic variance of the sample autocorrelations can be greater or less than 1 as well (1 is the asymptotic variance for strong white noises).

Figure 2 compares the standard estimator Ω = 2 Ĵ-1 and the sandwich estimator Ω = Ĵ-1 Î Ĵ-1 of the QMLE asymptotic variance Ω. We used the spectral estimator Î = ÎSP defined in Theorem 4, and the AR order r is automatically selected by AIC, using the function VARselect() of the vars R package. In the strong VARMA case we know that the two estimators are consistent. In view of the two top panels of Figure 2, it seems that the sandwich estimator is less accurate in the strong case. This is not surprising because the sandwich estimator is more robust, in the sense that this estimator continues to be consistent in the weak VARMA case, contrary to the standard estimator.

It is clear that in the weak case nVar b1 (2, 2)b 1 (2, 2) Table 1 displays the empirical sizes of the standard Wald, LM and LR tests, and that of the modified versions proposed in Section 5. For the nominal level α = 5%, the empirical size over the N = 1, 000 independent replications should vary between the significant limits 3.6% and 6.4% with probability 95%. For the nominal level α = 1%, the significant limits are 0.3% and 1.7%, and for the nominal level α = 10%, they are 8.1% and 11.9%. When the relative rejection frequencies are outside the significant limits, they are displayed in bold type in Table 1. For the strong VARMA model I, all the relative rejection frequencies are inside the significant limits. For the weak VARMA model II, the relative rejection frequencies of the standard tests are definitely outside the significant limits. Thus the error of first kind is well controlled by all the tests in the strong case, but only by modified versions of the tests in the weak case. Table 2 shows that the powers of all the tests are very similar in the Model III case. The same is also true for the two modified tests in the Model IV case. The empirical powers of the standard tests are hardly interpretable for Model IV, because we have already seen in Table 1 that the standard versions of the tests do not well control the error of first kind in the weak VARMA framework.

From these simulation experiments and from the asymptotic theory, we draw the conclusion that the standard methodology, based on the QMLE, allows to fit VARMA representations of a wide class of nonlinear multivariate time series. This standard methodology, including in particular the significance tests on the parameters, needs however to be adapted to take into account the possible lack of independence of the errors terms. In future works, we intent to study how the existing identification (see e.g. [START_REF] Nsiri | Identification of refined ARMA echelon form models for multivariate time series[END_REF] and diagnostic checking (see e.g. [START_REF] Duchesne | On consistent testing for serial correlation of unknown form in vector time series models[END_REF] procedures should be adapted in the weak VARMA framework considered in the present paper. 9)-( 10) with ϑ 0 = (0.95, 2, 0) II: Weak VARMA(1,1) model ( 9)-( 11) with ϑ 0 = (0.95, 2, 0)

A Technical proofs

We begin with a lemma useful to show the identifiability of ϑ 0 . 9) with size n = 2, 000 and unknown parameter ϑ 0 = ((a 1 (2, 2), b 1 (2, 1), b 1 (2, 2)) = (0.95, 2, 0), when the noise is strong (left panels) and when the noise is the weak noise (11) (right panels). Points (a)-(c), in the box-plots of the top panels, display the distribution of the estimation errors θ(i)ϑ 0 (i) for i = 1, 2, 3. The panels of the middle present the Q-Q plot of the estimates θ(3) = b1 (2, 2) of the last parameter. The bottom panels display the distribution of the same estimates. The kernel density estimate is displayed in full line, and the centered Gaussian density with the same variance is plotted in dotted line.

Lemma 1 Assume that Σ 0 is non singular and that A5 holds true. If

A -1 0 B 0 B -1 ϑ (L)A ϑ (L)X t = A -1 00 B 00 ǫ t with probability one and A -1 0 B 0 ΣB ′ 0 A -1 ′ 0 = A -1 00 B 00 Σ 0 B ′ 00 A -1 ′ 00 , then ϑ = ϑ 0 . Proof: Let ϑ = ϑ 0 . Assumption A5 implies that either A -1 0 B 0 ΣB ′ 0 A -1 ′ 0 = A -1 00 B 00 Σ 0 B ′ 00 A -1 ′
00 or there exist matrices C i such that C i 0 = 0 for some i 0 > 0 and

A -1 0 B 0 B -1 ϑ (z)A ϑ (z) -A -1 00 B 00 B -1 ϑ 0 (z)A ϑ 0 (z) = ∞ i=i 0 C i z i .

By contradiction, assume that

A -1 0 B 0 B -1 ϑ (L)A ϑ (L)X t = A -1 00 B 00 ǫ t = A -1
00 B 00 B -1 ϑ 0 (L)A ϑ 0 (L)X t with probability one. This implies that there exists λ = 0 such that λ ′ X t-i 0 is almost surely a linear combination of the components of X t-i , i > i 0 . By stationarity, it follows that λ ′ X t is almost surely a linear combination of the components of X t-i , i > 0. Thus λ ′ ǫ t = 0 almost 9)-( 10) with ϑ 0 = (0.95, 2, 0.05)

IV: Weak VARMA(1,1) model ( 9)-( 11) with ϑ 0 = (0.95, 2, 0.05) surely, which is impossible when the variance Σ 0 of ǫ t is positive definite. 2

Proof of Theorem 1: Note that, due to the initial conditions, {ẽ t (ϑ)} is not stationary, but can be approximated by the stationary ergodic process

e t (ϑ) = A -1 0 B 0 B -1 ϑ (L)A ϑ (L)X t . (A.1)
From an extension of Lemma 1 in FZ, it is easy to show that sup ϑ∈Θ ẽt (ϑ)e t (ϑ) → 0 almost surely at an exponential rate, as t → ∞.

We thus have ln (ϑ)

o P (1) = ℓ n (ϑ) := 1 n n t=1 l t (ϑ) as n → ∞,
where l t (ϑ) = d log(2π) + log det Σ e + e ′ t (ϑ)Σ -1 e e t (ϑ). Now the ergodic theorem shows that almost surely

ℓ n (ϑ) → d log(2π) + Q(ϑ), where Q(ϑ) = log det Σ e + Ee ′ 1 (ϑ)Σ -1
e e 1 (ϑ). We have

Q(ϑ) = E {e 1 (ϑ 0 )} ′ Σ -1 e {e 1 (ϑ 0 )} + log det Σ e +E {e 1 (ϑ) -e 1 (ϑ 0 )} ′ Σ -1 e {e 1 (ϑ) -e 1 (ϑ 0 )} +2E {e 1 (ϑ) -e 1 (ϑ 0 )} ′ Σ -1
e e 1 (ϑ 0 ).

The last expectation is null because the linear innovation e t = e t (ϑ 0 ) is orthogonal to the linear past (i.e. to the Hilbert space H t-1 generated by linear combinations of the X u for u < t), and because {e t (ϑ)e t (ϑ 0 )} belongs to this linear past H t-1 . Moreover

Q(ϑ 0 ) = log det Σ e0 + Ee ′ 1 (ϑ 0 )Σ -1 e0 e 1 (ϑ 0 ) = log det Σ e0 + Tr Σ -1 e0 Ee 1 (ϑ 0 )e ′ 1 (ϑ 0 ) = log det Σ e0 + d.
Thus

Q(ϑ) -Q(ϑ 0 ) ≥ Tr Σ -1 e Σ e0 -log det Σ -1 e Σ e0 -d ≥ 0 (A.2)
using the elementary inequality

Tr(A -1 B) -log det(A -1 B) ≥ Tr(A -1 A) -log det(A -1 A) = d
for all symmetric positive semi-definite matrices of order d × d. At least one of the two inequalities in (A.2) is strict, unless if e 1 (ϑ) = e 1 (ϑ 0 ) with probability 1 and Σ e = Σ e0 , which is equivalent to ϑ = ϑ 0 by Lemma 1. The rest of the proof relies on standard compactness arguments, and is a direct extension of Theorem 1 in FZ.

2

Proof of Theorem 2: In view of Theorem 1 and A6, we have almost surely θn → ϑ 0 ∈

• Θ . Thus ∂ ln ( θn )/∂ϑ = 0 for sufficiently large n, and a Taylor expansion gives

0 o P (1) = √ n ∂ℓ n (ϑ 0 ) ∂ϑ + ∂ 2 ℓ n (ϑ 0 ) ∂ϑ∂ϑ ′ √ n θn -ϑ 0 , (A.3)
using arguments given in FZ (proof of Theorem 2). The proof then directly follows from Lemma 3 and Lemma 5 below. 2

We first state elementary derivative rules, which can be found in Appendix A. 13 of Lütkepohl (1993).

Lemma 2 If f (A) is a scalar function of a matrix A whose elements a ij are function of a variable x, then ∂f (A) ∂x = i,j ∂f (A) ∂a ij ∂a ij ∂x = Tr ∂f (A) ∂A ′ ∂A ∂x . (A.4)
When A is invertible, we also have

∂ log |det(A)| ∂A ′ = A -1 (A.5) ∂Tr(CA -1 B) ∂A ′ = -A -1 BCA -1 (A.6) ∂Tr(CAB) ∂A ′ = BC (A.7)
Lemma 3 Under the assumptions of Theorem 2, almost surely

∂ 2 ℓ n (ϑ 0 ) ∂ϑ∂ϑ ′ → J,
where J is invertible.

Proof of Lemma 3: Let ϑ = (ϑ 1 , . . . , ϑ k 0 ) ′ . In view of (A.4), (A. Using Ee t e ′ t = Σ e , Ee t = 0, the uncorrelatedness between e t and the linear past H t-1 , ∂e t (ϑ 0 )/∂ϑ i ∈ H t-1 , and ∂ 2 e t (ϑ 0 )/∂ϑ i ∂ϑ j ∈ H t-1 , we have

E ∂ 2 l t (ϑ 0 ) ∂ϑ i ∂ϑ j = Tr Σ -1 e0 ∂Σ e (ϑ 0 ) ∂ϑ i Σ -1 e0 ∂Σ e (ϑ 0 ) ∂ϑ j + 2E ∂e ′ t (ϑ 0 ) ∂ϑ i Σ -1 e0 ∂e t (ϑ 0 ) ∂ϑ j = J(i, j).
(A.9)

The ergodic theorem and the next lemma conclude. 2

Lemma 4 Under the assumptions of Theorem 2, the matrix

J = E ∂ 2 l t (ϑ 0 ) ∂ϑ∂ϑ ′ is invertible.
Proof of Lemma 4: In view of (A.9), we have J = J 1 + J 2 , where

J 2 = 2E ∂e ′ t (ϑ 0 ) ∂ϑ Σ -1 e0 ∂e t (ϑ 0 ) ∂ϑ ′ and J 1 (i, j) = Tr Σ -1/2 e0 ∂Σ e (ϑ 0 ) ∂ϑ i Σ -1/2 e0 Σ -1/2 e0 ∂Σ e (ϑ 0 ) ∂ϑ j Σ -1/2 e0 = h ′ i h j ,
with

h i = (Σ -1/2 e0 ⊗ Σ -1/2 e0 )d i , d i = vec ∂Σ e (ϑ 0 ) ∂ϑ i .
In the previous derivations, we used the well-known relations Tr(A ′ B) = (vecA) ′ vecB and vec(ABC) = (C ′ ⊗ A)vecB. Note that the matrices J, J 1 and J 2 are semi-definite positive. If J is singular, then there exists a vector c = (c 1 , . . . , c k 0

) ′ = 0 such that c ′ J 1 c = c ′ J 2 c = 0. Since Σ -1/2 e0 ⊗ Σ -1/2 e0
and Σ -1 e0 are definite positive, we have c ′ J 1 c = 0 if and only if

k 0 k=1 c k d k = k 0 k=1 c k vec ∂Σ e (ϑ 0 ) ∂ϑ k = 0 (A.10) and c ′ J 2 c = 0 if and only if k 0 k=1 c k ∂et(ϑ 0 ) ∂ϑ k = 0 a.s.
Differentiating the two sides of the reduced form representation (3), the latter equation yields the VARMA(p -1, q -1) equation p i=1 A * i X t-i = p j=1 B * j e t-j . The identifiability assumption A5 excludes the existence of such a representation. Thus

A * i = k 0 k=1 c k ∂A -1 0 A i ∂ϑ k (ϑ 0 ) = 0, B * j = k 0 k=1 c k ∂A -1 0 B j B -1 0 A 0 ∂ϑ k (ϑ 0 ) = 0. (A.11)
It can be seen that (A.10) and (A.11), for i = 1, . . . , p and j = 1, . . . , q, are equivalent to M ϑ 0 c = 0. We conclude from A8. 2

Lemma 5 Under the assumptions of Theorem 2,

√ n ∂ℓ n (ϑ 0 ) ∂ϑ L → N (0, I).
Proof of Lemma 5: In view of (A.1), we have [START_REF] Herrndorf | A Functional Central Limit Theorem for Weakly Dependent Sequences of Random Variables[END_REF] we directly obtain

∂e t (ϑ 0 ) ∂ϑ i = ∞ ℓ=1 d ′ ℓ e t-
1 √ n n t=1 Y t,m L → N (0, I m ), I m = ∞ h=-∞ Cov (Y t,m , Y t-h,m ) .
As in FZ Lemma 3, one can show that I = lim m→∞ I m exists. Since Z t,m 2 → 0 at an exponential rate when m → ∞, using the arguments given in FZ Lemma 4, one can show that

lim m→∞ lim sup n→∞ P n -1/2 n t=1 Z t,m > ε = 0
for every ε > 0. From a standard result (see e.g. Brockwell and Davis, 1991, Proposition 6.3.9), we deduce that

1 √ n n t=1 ∂l t (ϑ 0 ) ∂ϑ = 1 √ n n t=1 Y t,m + 1 √ n n t=1 Z t,m L → N (0, I),
which completes the proof. 2

Proof of Theorem 3: Note that

ln (ϑ) = 1 n n t=1 lt (ϑ), lt (ϑ) = d log(2π) + log det Σ e + ẽ′ t (ϑ)Σ -1 e ẽt (ϑ).
Under the assumption of the theorem, ∂ẽ ′ t (ϑ)/∂ϑ (2) = 0, and (A.8) yields

∂ lt ( θn ) ∂ϑ i = Tr Σ-1 e I d -ẽt ( θ(1) n )ẽ ′ t ( θ(1) n ) Σ-1
e ∂Σ e ( θn ) ∂ϑ i for i = k 1 +1, . . . k 0 , with Σe such that θ(2) n = D vec Σe . Assumption A6 entails that the first order condition ∂ ln ( θn )/∂ϑ (2) = 0 is satisfied for n large enough. We then have Σe

= n -1 n t=1 ẽt ( θ(1) n )ẽ ′ t ( θ(1) n ) and ln ( θn ) = d log(2π) + log det Σe + d, because 1 n n t=1 ẽ′ t ( θ(1) n ) Σ-1 e ẽt ( θ(1) n ) = Tr 1 n n t=1 ẽt ( θ(1) n )ẽ ′ t ( θ(1) n ) Σ-1 e = d.

The conclusion follows. 2

Estimating structural VARMA models with uncorrelated but non-independent error terms: Complementary results that are not submitted for publication

sup ϑ∈Θ ẽt (ϑ) -e t (ϑ) ≤ Kρ t ,
where ρ is a constant belonging to [0, 1), and K > 0 is measurable with respect to the σ-field generated by {X u , u ≤ 0}.

Proof of Lemma 4:

We have

e t (ϑ) = X t - p i=1 A -1 0 A i X t-i + q i=1 A -1 0 B i B -1 0 A 0 e t-i (ϑ) ∀t ∈ Z, (C.1) and ẽt (ϑ) = X t - p i=1 A -1 0 A i X t-i + q i=1 A -1 0 B i B -1 0 A 0 ẽt-i (ϑ) t = 1, . . . , n (C.2) with the initial values ẽ0 (ϑ) = • • • = ẽ1-q (ϑ) = X 0 = • • • = X 1-p = 0. Let e t (ϑ) =           e t (ϑ) e t-1 (ϑ) . . . e t-q+1 (ϑ)           , ẽt (ϑ) =           ẽt (ϑ) ẽt-1 (ϑ) . . . ẽt-q+1 (ϑ)          
.

From (C.1) and (C.2), we have

e t (ϑ) = b t + Ce t-1 (ϑ) ∀t ∈ Z, and
ẽt (ϑ) = bt + C ẽt-1 (ϑ) t = 1, . . . , n, where C =    A -1 0 B 1 B -1 0 A 0 • • • A -1 0 B q B -1 0 A 0 I (q-1)d 0 (q-1)d    , b t =           X t -p i=1 A -1 0 A i X t-i 0 d . . . 0 d          
, bt = b t for t > p, bt = 0 qd for t ≤ 0, and

bt =           X t -t-1 i=1 A -1 0 A i X t-i 0 d . . . 0 d          
for t = 1, . . . , p.

Writing d t (ϑ) = e t (ϑ)ẽt (ϑ), we obtain for t > p,

d t (ϑ) = Cd t-1 (ϑ) = C t-p d p (ϑ) = C t-p b p -bp + C b p-1 -bp-1 + • • • + C p-1 b 1 -b1 + C p b 0 .
Note that C is the companion matrix of the polynomial

P(z) = I d - q i=1 A -1 0 B i B -1 0 A 0 z i = A -1 0 B ϑ (z)B -1 0 A 0 .
By A2, the zeroes of P(z) are of modulus strictly greater than one: {ẽ t (ϑ)e t (ϑ)} ′ Σ -1 e ẽt (ϑ) + e ′ t (ϑ)Σ -1 e {ẽ t (ϑ)e t (ϑ)} .

P(z) = 0 ⇒ |z| > 1 (C.
In the proof of this lemma and in the rest on the paper, the letters K and ρ denote generic constants, whose values can be modified along the text, such that K > 0 and 0 < ρ < 1. By Lemma 4,

2

The proof of Theorem 1 is completed by the arguments of [START_REF] Wald | Note on the consistency of the maximum likelihood estimate[END_REF]. More precisely, the compact set Θ is covered by a neighborhood V (ϑ 0 ) of ϑ 0 and a finite number of neighborhoods V (ϑ 1 ), . . . , V (ϑ k ) satisfying (C.6) with ϑ replaced by ϑ i , i = 1, . . . , k. In view of (C.6) and (C. for n large enough. Since the neighborhood V (ϑ 0 ) can be chosen arbitrarily small, the conclusion follows.

c=

  b to signify a = b + c. A Taylor expansion gives under H 0

2 is better estimated by ΩSP ( 3 , 3 )

 33 Figure2compares the standard estimator Ω = 2 Ĵ-1 and the sandwich estimator Ω = Ĵ-1 Î Ĵ-1 of the QMLE asymptotic variance Ω. We used the spectral estimator Î = ÎSP defined in Theorem 4, and the AR order r is automatically selected by AIC, using the function VARselect() of the vars R package. In the strong VARMA case we know that the two estimators are consistent. In view of the two top panels of Figure2, it seems that the sandwich estimator is less accurate in the strong case. This is not surprising because the sandwich estimator is more robust, in the sense that this estimator continues to be consistent in the weak VARMA case, contrary to the standard estimator. It is clear that in the weak case nVar b1 (2, 2)b 1 (2, 2) 2 is better estimated by ΩSP (3, 3) (see the box-plot (c) of the right-bottom panel of Figure 2) than by 2 Ĵ-1 (3, 3) (box-plot (c) of the left-bottom panel). The failure of the standard estimator of Ω in the weak VARMA framework may have important consequences in terms of identification or hypothesis testing.

Figure 1 .

 1 Figure 1. QMLE of N = 1, 000 independent simulations of the VARMA(1,1) model (9) with size n = 2, 000 and unknown parameter ϑ 0 = ((a 1 (2, 2), b 1 (2, 1), b 1 (2, 2)) = (0.95, 2, 0), when the noise is strong (left panels) and when the noise is the weak noise (11) (right panels). Points (a)-(c), in the box-plots of the top panels, display the distribution of the estimation errors θ(i)ϑ 0 (i) for i = 1, 2, 3. The panels of the middle present the Q-Q plot of the

Figure 2 . 2 2

 22 Figure 2. Comparison of standard and modified estimates of the asymptotic variance Ω of the QMLE, on the simulated models presented in Figure 1. The diamond symbols represent the mean, over the N = 1, 000 replications, of the standardized squared errors n {â 1 (2, 2) -0.95} 2 for (a) (0.02 in the strong and weak cases), n b1 (2, 1) -2 2 for (b) (1.02 in the strong case and 1.01 in the strong case) and

A Additional example Example 2 is of full rank k 0 = 7 .C Details on the proof of Theorem 1 Lemma 4

 2714 Denoting by a 0i (k, ℓ) and b 0i (k, ℓ) the generic elements of the matrices A 0i and B 0i , the Kronecker indices are defined by p k = max{i : a 0i (k, ℓ) = 0 or b 0i (k, ℓ) = 0 for some ℓ = 1, . . . , d}. To ensure relatively parsimonious parameterizations, one can specify an echelon form depending on the Kronecker indices (p 1 , . . . , p d ). The reader is refereed to[START_REF] Lütkepohl | Introduction to multiple time series analysis[END_REF] for details about the echelon form. For instance, a 3-variate ARMA process with Kronecker indices (1, 2, 0) admits the echelon form Under the assumptions of Theorem 1, we have

3 ) 1 . 2 3 5

 3125 By a well-known result on companion matrices, (C.3) is equivalent to ρ(C) < 1, where ρ(C) denote the spectral radius of C. By the compactness of Θ, we thus have sup ϑ∈Θ ρ(C) < We thus have sup ϑ∈Θ d t (ϑ) ≤ Kρ t , where K and ρ are as in the statement of the lemma. The conclusion follows. Lemma Under the assumptions of Theorem 1, we have sup ϑ∈Θ ln (ϑ)ℓ n (ϑ) = o(1) almost surely. Proof of Lemma 5: We have ln (ϑ)ℓ n (ϑ) = 1 n n t=1

4 ) 2 Lemma 6 . 6 ). 7 )=

 42667 In view of (C.1), and using A1 and the compactness of Θ, we havee t (ϑ) = X t + ∞ i=1 C i (ϑ)X t-i , sup ϑ∈Θ C i (ϑ) ≤ Kρ i . (C.5)We thus have E sup ϑ∈Θ e t (ϑ) < ∞, and the Markov inequality entails∞ t=1 P ρ t sup ϑ∈Θ e t (ϑ) > ε ≤ E sup ϑ∈Θ e t (ϑ)By the Borel-Cantelli theorem, ρ t sup ϑ∈Θ e t (ϑ) → 0 almost surely as t → ∞.The Cesàro theorem implies that the right-hand side of (C.4) converges to zero almost surely. Under the assumptions of Theorem 1, any ϑ = ϑ 0 has a neighborhood V (ϑ) such thatlim inf n→∞ inf ϑ * ∈V (ϑ) ln (ϑ * ) > El 1 (ϑ 0 ), a.s. (CMoreover for any neighborhood V (ϑ 0 ) of ϑ 0 we havelim sup n→∞ inf ϑ * ∈V (ϑ 0 ) ln (ϑ * ) ≤ El 1 (ϑ 0 ), a.s. (CProof of Lemma 6: For any ϑ ∈ Θ and any positive integer k, let V k (ϑ) be the open ball with center ϑ and radius 1/k. Using Lemma 5, we havelim inf n→∞ inf ϑ * ∈V k (ϑ)∩Θ ln (ϑ * ) ≥ lim inf n→∞ inf ϑ * ∈V k (ϑ)∩Θ ℓ n (ϑ * )lim sup n→∞ sup ϑ∈Θ |ℓ n (ϑ) -ln (ϑ)| ∈V k (ϑ)∩Θ l t (ϑ * ) = E inf ϑ * ∈V k (ϑ)∩Θ l 1 (ϑ * )For the last equality we applied the ergodic theorem to the ergodic stationary processinf ϑ * ∈V k (ϑ)∩Θ ℓ t (ϑ * ) t . By the Beppo-Levi theorem, when k increases to ∞, E inf ϑ * ∈V k (ϑ)∩Θ l 1 (ϑ * ) increases to El 1 (ϑ). Because El 1 (ϑ) = d log(2π) + Q(ϑ),the discussion which follows (A.2) entails El 1 (ϑ) > El 1 (ϑ 0 ), and (C.6) follows. To show (C.7), it suffices to remark that Lemma 5 and the ergodic theorem entail lim sup n→∞ inf ϑ * ∈V (ϑ)∩Θ ln (ϑ * ) ≤ lim sup n→∞ inf ϑ * ∈V (ϑ)∩Θ ℓ n (ϑ * ) + lim sup n→∞ sup ϑ∈Θ |ℓ n (ϑ) -ln (ϑ)| El 1 (ϑ 0 ).

  [START_REF] Dunsmuir | Vector linear time series models[END_REF], we have almost surelyinf ϑ∈Θ ln (ϑ) = min i=0,1,...,k inf ϑ∈V (ϑ i )∩Θ ln (ϑ) = inf ϑ∈V (ϑ 0 )∩Θ ln (ϑ)

  the common left divisors of A ϑ (L) and B ϑ (L) are unimodular (i.e. with nonzero constant determinant), and the matrix [A p : B q ] is of full rank.Inc t = c 1 + α 01 Inc t-1 + α 02 Cons t-1 + ǫ 1t and Cons t = c 2 + α 03 Inc t + α 04 Inc t-1 + α 05 Cons t-1 + ǫ 2t .In the stationary case the process X t = {Inc t -E(Inc t ), Cons t -E(Cons t )} ′ satisfies a structural VAR(1) equation

	The structural form (2) allows to handle seasonal models, instantaneous eco-
	nomic relationships, VARMA in the so-called echelon form representation, and
	many other constrained VARMA representations.
	Example 1 Assume that income (Inc) and consumption (Cons) variables are
	related by the equations

Table 1

 1 Empirical size of standard and modified tests: relative frequencies (in %) of rejection of H 0 : b 1 (2, 2) = 0. The number of replications is N = 1000.

	Model Length n Level	Standard Test	Modified Test
				Wald LM LR	Wald LM	LR
			α = 1%	1.1 0.7 0.8	1.7	0.7	1.7
	I	n = 500	α = 5%	5.0 4.5 5.1	6.0	5.2	6.0
			α = 10%	8.9 9.3 9.4	11.0	9.9 10.9
			α = 1%	0.7 0.8 0.7	1.0	0.6	1.0
	I	n = 2, 000 α = 5%	5.0 4.3 4.6	5.5	5.1	5.5
			α = 10%	9.2 8.6 8.8	10.0	9.0 10.2
			α = 1%	0.0 0.0 0.0	1.4	1.4	1.3
	II	n = 500	α = 5%	0.6 0.5 0.6	6.2 6.5	6.1
			α = 10%	2.3 2.2 2.2	12.0 11.2 12.0
			α = 1%	0.0 0.0 0.0	0.9	0.7	0.9
	II	n = 2, 000 α = 5%	0.4 0.3 0.3	4.6	4.3	4.6
			α = 10%	1.3 1.3 1.3	9.2	9.8	9.2
	I: Strong VARMA(1,1) model (

Table 2

 2 Empirical power of standard and modified tests: relative frequencies (in %) of rejection of H 0 : b 1 (2, 2) = 0. The number of replications is N = 1000.

	Model Length n Level	Standard Test	Modified Test
				Wald LM	LR	Wald LM	LR
			α = 1%	6.8	5.9	6.6	8.0	6.5	7.9
	III	n = 500	α = 5%	20.5 19.4 20.4	21.6 20.1 21.7
			α = 10%	29.5 29.0 29.4	30.6 29.5 30.6
			α = 1%	1.7	1.8	1.7	15.5 14.3 15.6
	IV	n = 500	α = 5%	11.4	9.4 10.1	35.1 34.0 35.0
			α = 10%	21.1 20.2 20.6	47.1 44.9 46.8
	III: Strong VARMA(1,1) model (

  ℓ , (A.[START_REF] Francq | Recent results for linear time series models with non independent innovations[END_REF] where the sequence of matrices d ℓ = d ℓ (i) is such that d ℓ → 0 at a geometric rate as ℓ → ∞. By (A.8), we have for all mLet Y t,m = (Y t,m,1 , . . . , Y t,m,k 0 ) ′ and Z t,m = (Z t,m,1 , . . . , Y t,m,k 0 ) ′ .The processes (Y t,m ) t and (Z t,m ) t are stationary and centered. Moreover, under Assumption A7 and m fixed, the process Y = (Y t,m ) t is strongly mixing, with mixing coefficients α Y (h) ≤ α ǫ (max{0, h -m}). Applying the central limit theorem (CLT) for mixing processes (see

	∂l t (ϑ 0 ) ∂ϑ i	= Tr Σ -1 e0 I d -e t e ′ t Σ -1 e0	∂Σ e (ϑ 0 ) ∂ϑ i	+ 2	∂e ′ t (ϑ 0 ) ∂ϑ i	Σ -1 e0 e t
		= Y t,m,i + Z t,m,i
	where
	Y t,m,i = Tr Σ -1 e0 I d -e t e ′ t Σ -1 e0	∂Σ e (ϑ 0 ) ∂ϑ i	+ 2	ℓ=1 m	e ′ t-ℓ d ′ ℓ Σ -1 e0 e t
		∞
	Z t,m,i = 2	e ′ t-ℓ d ′ ℓ Σ -1 e0 e t .
		ℓ=m+1

  D Details on the proof of Theorem 2 Lemma 7 Under the assumptions of Theorem 2, we have Proof of Lemma 7: Similar to (C.5), Assumption A1 entails that, for k = 1, . . . , k 0 ,

						√	n	∂ ln (ϑ 0 ) ∂ϑ	-	∂ℓ n (ϑ 0 ) ∂ϑ	= o(1)	a.s.
	∂e t (ϑ 0 ) ∂ϑ k	=	∞ i=1	C	(k) i X t-i ,			∂ẽ t (ϑ 0 ) ∂ϑ k	=	t-1 i=1	C	(k) i X t-i ,	C	(k) i	≤ Kρ i .
	It follows that
	Using (A.8), we have
								√	n	∂ℓ n (ϑ 0 ) ∂ϑ k	-	∂ ln (ϑ 0 ) ∂ϑ k	= a 1 + a 2 ,
	with
	a 1 =	2 √ n	n t=1		∂e ′ t (ϑ 0 ) ∂ϑ k	-	∂ẽ ′ t (ϑ 0 ) ∂ϑ k	Σ -1 e e t (ϑ 0 ) +	∂ẽ ′ t (ϑ 0 ) ∂ϑ k	Σ -1
														∂Σ e
														e	∂ϑ k
	2

e (e t (ϑ 0 )ẽt (ϑ 0 ))

a 2 = Tr Σ -1 e {ẽ t (ϑ 0 )e t (ϑ 0 )} ẽ′ t (ϑ 0 ) + e t (ϑ 0 ) {ẽ t (ϑ 0 )e t (ϑ 0 )} ′ Σ -1


Lukasz Je
email: lje@cs.uni.wroc.pl

A 4 3 -COMPETITIVE RANDOMIZED ALGORITHM FOR ONLINE SCHEDULING OF PACKETS WITH AGREEABLE DEADLINES

Keywords: 1998 ACM Subject Classification: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems online algorithms, scheduling, buffer management

 for randomized algorithms against oblivious adversary.

Introduction

We consider the problem of buffer management with bounded delay (aka packet scheduling), introduced by Kesselman et al. [START_REF] Kesselman | Buffer overflow management in QoS switches[END_REF]. It models the behaviour of a single network switch. We assume that time is slotted and divided into steps. At the beginning of a time step, any number of packets may arrive at a switch and are stored in its buffer. A packet has a positive weight and a deadline, which is the number of step right before which the packet expires: unless it has already been transmitted, it is removed from the buffer at the very beginning of that step and thus can no longer be transmitted. Only one packet can be transmitted in a single step. The goal is to maximize the weighted throughput, i.e., the total weight of transmitted packets.

As the process of managing packet queue is inherently a real-time task, we investigate the online variant of the problem. This means that the algorithm has to base its decision of which packet to transmit solely on the packets which have already arrived at a switch, without the knowledge of the future.

Competitive Analysis.

To measure the performance of an online algorithm, we use a standard notion of competitive analysis [START_REF] Borodin | Online Computation and Competitive Analysis[END_REF], which compares the gain of the algorithm to the gain of the optimal solution on the same input sequence. For any algorithm Alg, we denote its gain on the input sequence I by G ALG (I); we denote the optimal offline algorithm by Opt. We say that a deterministic algorithm Alg is R-competitive if on any input sequence I, it holds that G ALG (I) ≥ 1 R • G OPT (I). When analysing the performance of an online algorithm Alg, we view the process as a game between Alg and an adversary. The adversary controls the packets' injection into the buffer and chooses which of them to send. The goal is then to show that the adversary's gain is at most R times Alg's gain.

If the algorithm is randomized, we consider its expected gain, E[G ALG (I)], where the expectation is taken over all possible random choices made by Alg. However, in the randomized case, the power of the adversary has to be further specified. Following Ben-David et al. [START_REF] Ben-David | On the power of randomization in on-line algorithms[END_REF], we distinguish between an oblivious and adaptive-online adversary (called adaptive for short). An oblivious adversary has to construct the whole input sequence in advance, not knowing the random bits used by an algorithm. The expected gain of Alg is compared to the gain of the optimal offline solution on I. An adaptive adversary decides packet injections upon seeing which packets are transmitted by the algorithm. However, it has to provide an answering entity Adv, which creates a solution on-line (in parallel to Alg) and cannot change it afterwards. We say that Alg is R-competitive against an adaptive adversary if for any input sequence I created adaptively and any answering algorithm Adv,

it holds that E[G ALG (I)] ≥ 1 R • E[G ADV (I)].
We note that Adv is (wlog) deterministic, but as Alg is randomized, so is the input sequence I.

In the literature on online algorithms (see e.g. [START_REF] Borodin | Online Computation and Competitive Analysis[END_REF]), the definition of the competitive ratio sometimes allows an additive constant, i.e., a deterministic algorithm is R-competitive if there exists a constant α ≥ 0 such that G ALG (I) ≥ 1 R • G OPT (I)α holds for evry input sequence I. An analogous definition applies to randomized case. Our upper bounds hold for α = 0.

Previous work

The best known deterministic and randomized algorithms for general instances have competitive ratios at most 2 √ 2 -1 ≈ 1.828 [START_REF] Englert | Considering suppressed packets improves buffer management in QoS switches[END_REF] and e/(e -1) ≈ 1.582 [START_REF] Chin | Online competitive algorithms for maximizing weighted throughput of unit jobs[END_REF], respectively. A recent analysis of the latter algorithm shows that it retains its competitive ratio even against adaptive-online adversary [START_REF] Jeż | Randomised buffer management with bounded delay against adaptive adversary[END_REF].

The best known lower bounds on competitive ratio against either adversary type use rather restricted 2-bounded sequences in which every packet has lifespan (deadlinerelease time) either 1 or 2. The lower bounds in question are φ ≈ 1.618 for deterministic algorithms [START_REF] Hajek | On the competitiveness of online scheduling of unit-length packets with hard deadlines in slotted time[END_REF], 4 3 for randomized algorithms against adaptive adversary [START_REF] Bieńkowski | Randomized algorithms for Buffer Management with 2-Bounded Delay[END_REF], and 5 4 for randomized algorithms against oblivious adversary [START_REF] Chin | Online scheduling with partial job values: Does timesharing or randomization help?[END_REF]. All these bounds are tight for 2-bounded sequences [START_REF] Kesselman | Buffer overflow management in QoS switches[END_REF][START_REF] Bieńkowski | Randomized algorithms for Buffer Management with 2-Bounded Delay[END_REF][START_REF] Chin | Online competitive algorithms for maximizing weighted throughput of unit jobs[END_REF].

We restrict ourselves to sequences with agreeable deadlines, in which packets released later have deadlines at least as large as those released before (r i < r j implies d i ≤ d j ). These strictly generalize the 2-bounded sequences. Sequences with agreeable deadlines also properly contain s-uniform sequences for all s, i.e., sequences in which every packet has lifespan exactly s. An optimal φ-competitive deterministic algorithm for sequences with agreeable deadlines is known [START_REF] Li | An optimal online algorithm for packet scheduling with agreeable deadlines[END_REF].

Jeżabek studied the impact of resource augmentation on the deterministic competitive ratio [START_REF] Jeżabek | Increasing machine speed in on-line scheduling of weighted unit-length jobs in slotted time[END_REF][START_REF] Jeżabek | Resource augmentation for QoS Buffer Management with Agreeable Deadlines[END_REF]. It turns out that while allowing the deterministic algorithm to transmit k packets in a single step for any constant k cannot make it 1-competitive (compared to the single-speed offline optimum) on unrestricted sequences [START_REF] Jeżabek | Increasing machine speed in on-line scheduling of weighted unit-length jobs in slotted time[END_REF], k = 2 is sufficient for sequences with agreeable deadlines [START_REF] Jeżabek | Resource augmentation for QoS Buffer Management with Agreeable Deadlines[END_REF].

Our contribution

Motivated by aforementioned results for sequences with agreeable deadlines, we investigate randomized algorithms for such instances. We devise a 4 3 -competitive randomized algorithm against oblivious adversary. The algorithm and its analysis are inspired by those by Li et al. [START_REF] Li | An optimal online algorithm for packet scheduling with agreeable deadlines[END_REF] for deterministic case. The key insight is as follows. The algorithm MG by Li et al. [START_REF] Li | An optimal online algorithm for packet scheduling with agreeable deadlines[END_REF] can be simplified by making it always send either e, the heaviest among the earliest non-dominated packets, or h, the earliest among the heaviest non-dominated packets. We call this algorithm MG ′ , and prove that it remains φ-competitive. Then we turn it into a randomized algorithm RG, simply by making it always transmit e with probability we w h and h with the remaining probability. The proof of RG's 4 3 -competitiveness against oblivious adversary follows by similar analysis.

Preliminaries

We denote the release time, weight, and deadline of a packet j by r j , w j , and d j , respectively. A packet j is pending at step t if r j ≤ t, it has not yet been transmitted, and d j > t. We introduce a linear order ¢ on the packets as follows: i ¢ j if either d i < d j , or d i = d j and w i > w j , or d i = d j and w i = w j and r i ≤ r j .

To make ¢ truly linear we assume that in every single step the packets are released one after another rather then all at once, e.g. that they have unique fractional release times.

A schedule is a mapping from time steps to packets to be transmitted in those time steps. A schedule is feasible if it is injective and for every time step t the packet that t maps to is pending at t. It is convenient to view a feasible schedule S differently, for example as the set {S(t) : t > 0}, the sequence S(1), S(2), . . ., or a matching in the schedulability graph. The schedulability graph is a bipartite graph, one of whose partition classes is the set of packets and the other is the set of time steps. Each packet j is connected precisely to each of the time steps t such that r j ≤ t < d j by an edge of weight w j ; an example is given in Figure 1. Observe that optimal offline schedules correspond to maximum weight matchings in the schedulability graph. Thus an optimal offline schedule can be found in polynomial time using the classic "Hungarian algorithm", see for example [START_REF] Schrijver | Combinatorial Optimization[END_REF]. One may have to remove appropriately chosen time step vertices first, so that the remaining ones match the number of packet vertices, though.

Given any linear order on packets and a (feasible) schedule S, we say that S is consistent with , or that S is a -schedule, if for every t the packet S(t) is the minimum pending packet with respect to . It is fairly easy to observe that if is any earliest deadline first, with ties broken in an arbitrary way, then any feasible schedule can be turned to a unique -schedule by reordering its packets; in particular this applies to ¢.

Recall that the oblivious adversary prepares the whole input sequence in advance and cannot alter it later on. Thus its solution is simply the offline optimal schedule for the complete sequence. Nevertheless, we still refer to the answering entity Adv rather than Opt in our analysis, as it involves altering the set of packets pending for the adversary, which may well be viewed as altering the input sequence. Now we introduce two schedules that are crucial for our algorithms and our analyzes.

Definition 2.1. The oblivious schedule at time step t, denoted O t , is any fixed optimal feasible ¢-schedule over all the packets pending at step t. For fixed O t , a packet j pending at t is called dominated if j / ∈ O t , and non-dominated otherwise. For fixed O t let e denote O t (t), the ¢-minimal of all non-dominated packets, and h denote the ¢-minimal of all non-dominated maximum-weight packets.

Note that both the adversary and the algorithm can calculate their oblivious schedules at any step, and that these will coincide if their buffers are the same. Definition 2.2. For a fixed input sequence, the clairvoyant schedule at time step t, denoted C t , is any fixed optimal feasible schedule over all the packets pending at step t and all the packets that will arrive in the future.

Naturally, the adversary can calculate the clairvoyant schedule, as it knows the fixed input sequence, while the algorithm cannot, since it only knows the part of input revealed so far. However, the oblivious schedule gives some partial information about the clairvoyant schedule: intuitively, if p is dominated at t, it makes no sense to transmit it at t. Formally, (wlog) dominated packets are not included in the clairvoyant schedule, as stated in the following.

Fact 2.3. For any fixed input sequence, time step t, and oblivious schedule O t , there is a clairvoyant schedule C * t such that C * t ∩ {j : r j ≤ t} ⊆ O t . Proof. This is a standard alternating path argument about matchings. If you are unfamiliar with these concepts, refer to a book by A. Schrijver [START_REF] Schrijver | Combinatorial Optimization[END_REF] for example.

Let O t be the oblivious schedule and C t be any clairvoyant schedule. Treat both as matchings in the schedulability graph and consider their symmetric difference C t ⊕ O t .

Consider any job j ∈ C t \ O t such that r j ≤ t. It is an endpoint of an alternating path P in C t ⊕ O t . Note that all the jobs on P are already pending at time t: this is certainly true about j, and all the successive jobs belong to O t , so they are pending as well.

First we prove that P has even length, i.e., it ends in a node corresponding to a job. Assume for contradiction that P 's length is odd, and that P ends in a node corresponding to a timestep t ′ . Note that no job is assigned to t ′ in O t . Then O t ⊕ P is a feasible schedule that, treated as a set, satisfies O t ⊆ O t ⊕ P and j ∈ O t ⊕ P . This contradicts optimality of O t . See Figure 2a for illustration.

Thus P has even length and ends with a job j ′ ∈ O t \ C t . By optimality of both O t and C t , w j = w j ′ holds. Thus C t ⊕ P is an optimal feasible schedule: in terms of sets the only difference between C t and C t ⊕ P is that j has been replaced by j ′ , a job of the same weight. See Figure 2b for illustration. j t ′ (a) P cannot have odd length: in such case the assignment of jobs on P in Ot could be changed to match the strictly better assignment of Ct. Applying such changes iteratively transforms C t to a clairvoyant schedule C * t as announced. To observe that a finite number of iterations suffices, define ∆(S) := |S ∩ {j : r j ≤ t} \ O t | for any schedule S. It follows that ∆(C t ⊕ P ) = ∆(C t ) -1. Since ∆ is non-negative and its value drops by one with each iteration, C * t is obtained in a finite number of steps. Definition 2.4. We say that a clairvoyant schedule C t conforms with an oblivious schedule If j ′ = j, then C * t = C ′ t , and thus it is a clairvoyant ¢-schedule. Assume j ′ = j, i.e., j ′ ¡ j. Then j ′ / ∈ C ′ t , since C ′ t is a ¢-schedule. Thus C * t is feasible as we replace C ′ t 's very first packet by another pending packet which was not included in C t . Observe that C * t is indeed a clairvoyant ¢-schedule: optimality follows from w j ′ = w j , while consistency with ¢ follows from j ′ ¡ j.

O t if C t is a ¢-schedule, C t ∩ {j : r j ≤ t} ⊆ O t ,
It remains to prove that for every i ∈ O t such that i ¡ j ′ , w i < w j ′ = w j holds. Note that i / ∈ C * t as C * t is a ¢-schedule, and that w i = w j ′ = w j holds by the choice of j ′ . Assume for contradiction that w i > w j . Then C * t with j replaced by i is a feasible schedule contradicting optimality of C * t . Now we inspect some properties of conforming schedules. Fact 2.6. Let C t be a clairvoyant schedule conforming with an oblivious schedule O t . If i, j ∈ O t , w i < w j and d i < d j (or, equivalently w i < w j and i ¡ j), and i ∈ C t , then also j ∈ C t .

Proof Recall that p k , p l ∈ C t and that there can be some further packets p ∈ C t such that p k ¡ p ¡ p l ; some of these packets may be not pending yet. We construct a schedule C ′ t by reordering C t . Precisely, we put all the packets from C t that are not yet pending at t after all the packets from C t that are already pending, keeping the order between the pending packets and between those not yet pending. By the agreeable deadlines property, this is an earliest deadline first order, so C ′ t is a clairvoyant schedule. As e = p 1 / ∈ C ′ t and d i ≥ t + i for i = 1, . . . , s, all the packets x ∈ C ′ t preceding h in C ′ t (i.e., x ∈ C ′ t such that r x ≤ t and x ¡ p l = h) have slack in C ′ t , i.e., each of them could also be scheduled one step later. Hence h = p l can be moved to the very front of C ′ t while keeping its feasibility, i.e., C ′ t = p k , p k ′ , . . . , p l ′ , p l can be transformed to a clairvoyant schedule C * t = p l , p k , p k ′ , . . . , p l ′ . The reordering is illustrated in Figure 3.

Algorithms and their analyzes

The Algorithms

The algorithm MG [START_REF] Li | An optimal online algorithm for packet scheduling with agreeable deadlines[END_REF] works as follows: at the beginning of each step t it considers the packets in the buffer and the newly arrived packets, and calculates O t . Then MG identifies the packets e and h. If φw e ≥ w h , MG sends e. Otherwise, it sends the ¢-minimal packet f such that w f ≥ φw e and φw f ≥ w h ; the latter exists as h itself is a valid candidate. Our deterministic algorithm MG ′ does exactly the same with one exception: if φw e < w h , it sends h rather than f . Our randomized algorithm RG also works in a similar fashion: it transmits e with probability we w h and h with the remaining probability. For completeness, we provide pseudo-codes of all three algorithms in Figure 4.

MG (step t) O t ←

Analysis Idea

The analysis of Li et al. [START_REF] Li | An optimal online algorithm for packet scheduling with agreeable deadlines[END_REF] uses the following idea: in each step, after both MG and Adv transmitted their packets, modify Adv's buffer in such a way that it remains the same as MG's and that this change can only improve Adv's gain, both in this step and in the future. Sometimes Adv's schedule is also modified to achieve this goal, specifically, the packets in it may be reordered, and Adv may sometimes be allowed to transmit two packets in a single step. It is proved that in each such step the ratio of Adv's to MG's gain is at most φ. As was already noticed by Li et al. [START_REF] Li | An optimal online algorithm for packet scheduling with agreeable deadlines[END_REF], this is essentially a potential function argument. To simplify the analysis, it is assumed (wlog) that Adv transmits its packets in the ¢ order.

Our analysis follows the outline of the one by Li et al., but we make it more formal. Observe that there may be multiple clairvoyant schedules, and that Adv can transmit C t (t) at every step t, where C t is a clairvoyant schedule chosen arbitrarily in step t. As our algorithms MG ′ and RG determine the oblivious schedule O t at each step, we assume that every C t is a clairvoyant schedule conforming with O t .

There is one exception though. Sometimes, when a reordering in C t does not hinder Adv's performance (taking future arrivals into account), we "force" Adv to follow the reordered schedule. This is the situation described in Lemma 2.7: when e / ∈ C t , there is a clairvoyant schedule C * t such that h = C * t (t). In such case we may assume that Adv follows C * t rather than C t , i.e., that it transmits h at t. Indeed, we make that assumption whenever our algorithm (either MG ′ or RG) transmits h at such step: then Adv and MG ′ (RG) transmit the same packet, which greatly simplifies the analysis.

Our analysis of MG ′ is essentially the same as the original analysis of MG by Li et al. [START_REF] Li | An optimal online algorithm for packet scheduling with agreeable deadlines[END_REF], but lacks one case which is superfluous due to our modification. As our algorithm MG ′ always transmits either e or h, and the packet j that Adv transmits always satisfies j ¢ h by definition of the clairvoyant schedule conforming with O t , the case which MG transmits f such that e ¡ f ¡ j does not occur to MG ′ . The same observation applies to RG, whose analysis also follows the ideas of Li et al.

Analysis of the Deterministic Algorithm

We analyze this algorithm as mentioned before, i.e., assuming (wlog) that at every step t Adv transmits C t (t), where C t is a clairvoyant schedule conforming with O t . Theorem 3.1. MG ′ is φ-competitive on sequences with agreeable deadlines.

Proof. Note that whenever M G ′ and Adv transmit the same packet, clearly their gains are the same, as are their buffers right after such step. In particular this happens when e = h as then MG ′ transmits e = h and Adv does the same: in such case h is both the heaviest packet and the ¢-minimal non-dominated packet, so h = C t (t) by definition of the clairvoyant schedule conforming with O t .

In what follows we inspect the three remaining cases.

φw e ≥ w h : MG ′ transmits e. Adv transmits j = e.. To make the buffers of MG ′ and Adv identical right after this step, we replace e in Adv's buffer by j. This is advantageous for Adv as d j ≥ d e and w j ≥ w e follows from e ¢ j and the definition of a clairvoyant schedule conforming with O t . As φw e ≥ w h , the ratio of gains is

w j w e ≤ w h w e ≤ φ .
φw e < w h : MG ′ transmits h. Adv transmits e.. Note that Adv's clairvoyant schedule from this step contains h by Fact 2.6. We let Adv transmit both e and h in this step and keep e in its buffer, making it identical to the buffer of MG ′ . Keeping e, as well as transmitting two packets at a time is clearly advantageous for Adv. As φw e < w h , the ratio of gains is

w e + w h w h ≤ 1 φ + 1 = φ .
φw e < w h : MG ′ transmits h. Adv transmits j = e.. Note that j ¢ h: by definition of the clairvoyant schedule conforming with O t , for every i ∈ O t such that i ¡ j, w i < w j holds.

There are two cases: either j = h, or w j < w h and d j < d h . In the former one both players do the same and end up with identical buffers. Thus we focus on the latter case. Fact 2.6 implies that h ∈ C t . By Lemma 2.7, C t remains feasible when h is moved to its very beginning. Hence we assume that Adv transmits h in the current step. As this is the packet that MG ′ sends, the gains of Adv and MG ′ are the same and no changes need be made to Adv's buffer.

Analysis of the Randomized Algorithm

We analyze this algorithm as mentioned before, i.e., assuming (wlog) that at every step t Adv transmits C t (t), where C t is a clairvoyant schedule conforming with O t . Theorem 3.2. RG is 4 3 -competitive against oblivious adversary on sequences with agreeable deadlines.

Proof. Observe that if e = h, then RG transmits e = h and Adv does the same: as in such case h is both the heaviest packet and the ¢-minimal non-dominated packet, h = C t (t) by definition of the clairvoyant schedule conforming with O t . In such case the gains of RG and Adv are clearly the same, as are their buffers right after step t. Thus we assume e = h from now on.

Let us first bound the algorithm's expected gain in one step. It equals

G RG = w e w h • w e + 1 - w e w h • w h = 1 w h w 2 e -w e w h + w 2 h = 1 w h w e - w h 2 2 + 3 4 w 2 h ≥ 3 4 w h . (3.1)
Now we describe the changes to Adv's scheduling policy and buffer in the given step. These make Adv's RG's buffers identical, and, furthermore, make the expected gain of the adversary equal exactly w h . This, together with (3.1) yields the desired bound. To this end we consider cases depending on Adv's choice.

(1) Adv transmits e. Note that Adv's clairvoyant schedule from this step contains h by Fact 2.6. If RG transmits e, which it does with probability we w h , both players gain w e and no changes are required.

Otherwise RG transmits h, and we let Adv transmit both e and h in this step and keep e in its buffer, making it identical to RG's buffer. Keeping e, as well as transmitting two packets at a time is clearly advantageous for Adv.

Thus in this case the adversary's expected gain is

G ADV = w e w h
• w e + 1 -w e w h (w e + w h ) = w e + (w hw e ) = w h .

(2) Adv transmits j = e. Note that j ¢ h: by definition of the clairvoyant schedule conforming with O t , for every i ∈ O t such that i ¡ j, w i < w j holds. If RG sends e, which it does with probability we w h , we simply replace e in Adv's buffer by j. This is advantageous for Adv as w j > w e and d j > d e follow from e ¡ j and the definition of the clairvoyant schedule conforming with O t .

Otherwise RG sends h, and we claim that (wlog) Adv does the same. Suppose that j = h, which implies that w j < w h and d j < d h . Then h ∈ C t , by Fact 2.6. Thus, by Lemma 2.7, C t remains feasible when h is moved to its very beginning. Hence we assume that Adv transmits h in the current step. No further changes need be made to Adv's buffer as RG also sends h.

Thus in this case the adversary's expected gain is w h .

Conclusion and Open Problems

We have shown that, as long as the adversary is oblivious, the ideas of Li et al. [START_REF] Li | An optimal online algorithm for packet scheduling with agreeable deadlines[END_REF] can be applied to randomized algorithms, and devised a 4 3 -competitive algorithm this way. However, the gap between the 5 4 lower bound and our 4 3 upper bound remains. Some parts of our analysis hold even in the adaptive adversary model [START_REF] Jeż | Randomised buffer management with bounded delay against adaptive adversary[END_REF]. On the other hand, other parts do not extend to adaptive adversary model, since in general such adversary's schedule is a random variable depending on the algorithm's random choices. Therefore it is not possible to assume that this "schedule" is ordered by deadlines, let alone perform reordering like the one in proof of Lemma 2.7.

This makes bridging either the 5 4 , 4 3 gap in the oblivious adversary model, or the

Figure 1 :

 1 Figure 1: Schedulability graph for packets j 1 , j 2 , . . . , j 5 , whose release times and deadlines are (2,3), (2,4), (3,7), (4,7), (6,7) respectively; we ignore packet weights in the figure. Packets are represented by discs, time steps by squares.

  P has even length: now the assignment of jobs on P in Ct can be changed to match the assignment of Ot so that the value of ∆ drops.

Figure 2 :

 2 Figure 2: The alternating path P . Packets are represented by discs, time steps by squares. Dashed lines represent C t , solid lines represent O t .

1 == h p 2 p 3 p 4 p 6 p l- 1 Figure 3 :

 113 Figure 3: Construction of the schedule C * t . Packets are represented by circles: the ones included in C t (C * t ) are filled, the remaining ones are hollow.

Figure 4 :

 4 Figure 4: The three algorithms

4 3 , e e- 1

 31 gap in the adaptive adversary model all the more interesting.

  and for all i ∈ O t such that i ¡ j = C t (t), w i < w j holds. Fact 2.5. For every oblivious schedule O t there is a conforming clairvoyant schedule C * t . Proof. Let C t be a clairvoyant schedule such that C t ∩ {j : r j ≤ t} ⊆ O t ; Fact 2.3 guarantees its existence. Let C * t be the schedule obtained from C t by first turning it into a ¢-schedule C ′ t and then replacing j = C ′ t (t) with a ¢-minimal non-dominated packet j ′ of the same weight.

  . Assume for contradiction that j / ∈ C t . Then C t with i replaced by j is a feasible schedule contradicting optimality of C t . Lemma 2.7. Let C t be a clairvoyant schedule conforming with an oblivious schedule O t . Suppose that e = O t (t) / ∈ C t . Then there is a clairvoyant schedule C * t obtained from C t by reordering of packets such that C * t (t) = h. Proof. Let j = C t (t) = h and let O t = p 1 , p 2 , . . . , p s . Observe that h ∈ C t by Fact 2.6. So in particular e = p 1 , j = p k , and h = p l for some 1 < k < l ≤ s. Let d i denote the deadline of p i for 1 ≤ i ≤ s. Since O t is feasible in the absence of future arrivals, d i ≥ t + i for i = 1, . . . , s.

This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/3.0/.

Acknowledgements

I would like to thank my brother, Artur Jeż, for numerous comments on the draft of this paper.

This work has been supported by MNiSW grants no. N N206 1723 33, 2007-2010 and N N206 490638, 2010-2011.