Bernard Lapeyre
email: bernard.lapeyre@enpc.fr.

Jérôme Lelong
email: jerome.lelong@imag.fr

A framework for adaptive Monte-Carlo procedures

. We establish the convergence and asymptotic normality of the adaptive Monte Carlo estimator under local assumptions which are easily verifiable in practice. We present one way of approximating the optimal importance sampling parameter using a randomly truncated stochastic algorithm. Finally, we apply this technique to some examples of valuation of financial derivatives.

Introduction

Monte-Carlo methods aim at computing the expectation E(Z) of a real-valued random variable Z using samples along the law of Z. In this work, we focus on cases where there exists a parametric representation of the expectation

E(Z) = E (H(θ, X)) for all θ ∈ R d , ( 1
)
where X is a random vector with values in R m and H : R d × R m -→ R is a measurable function satisfying E|H(θ, X)| < ∞ for all θ ∈ R d . We also impose that

θ -→ v(θ) = Var(H(θ, X)) is finite for all θ ∈ R d , (2)
We want to make the most of this free parameter θ to settle an automatic variance reduction method, see [START_REF] Jourdain | Advanced Financial Modelling, chapter Adaptive variance reduction techniques in finance[END_REF] for a recent survey on adaptive variance reduction. It consists in first finding a minimiser θ ⋆ of the variance v and then in plugging it into a Monte Carlo method with a narrower confidence interval. This technique heavily relies on the ability to find a parametric representation and to effectively minimise the function v. Many papers have been written on how to construct parametric representations H(θ, X) for several kinds of random variables Z. We mainly have in mind examples based on control variates (see [START_REF] Glasserman | Monte Carlo methods in financial engineering[END_REF][START_REF] Kim | Adaptive control variates for finite-horizon simulation[END_REF][START_REF] Kim | Adaptive control variates[END_REF]) or importance sampling (see [START_REF] Vázquez-Abad | Accelerated simulation for pricing asian options[END_REF][START_REF] Su | Optimal importance sampling in securities pricing[END_REF][START_REF] Arouna | Adaptative Monte Carlo method, a variance reduction technique[END_REF][START_REF] Arouna | Robbins-Monro algorithms and variance reduction in finance[END_REF]). We refer the reader to section 4 for a presentation of a few examples.

Assume we have a parametric representation of the form H(θ, X) satisfying Equations [START_REF] Arouna | Adaptative Monte Carlo method, a variance reduction technique[END_REF] and [START_REF] Arouna | Robbins-Monro algorithms and variance reduction in finance[END_REF]. Let (X n ) n be an independent and identically distributed sequence of random vectors following the law of X. Assume we know how to use the sequence (X n ) n to build an estimator θ n of θ ⋆ adapted to the filtration F n = σ(X 1 , . . . , X n ). Once such an approximation is available, there are at least two ways of using it to devise a variance reduction method.

The non-adaptive algorithm Algorithm 1.1 (Non adaptive importance sampling (NADIS)). Let n be the number of samples used for the Monte Carlo computation. Draw a second set of n samples (X ′ 1 , . . . , X ′ n ) independent of (X 1 , . . . , X n ) and compute

ξn = 1 n n i=1 H(θ n , X ′ i ).
Since the sequence (θ n ) n converges to θ * , the convergence of ( ξn ) n to E(Z) ensues from the strong law of large numbers and the sequence ( ξn ) n satisfies a central limit theorem

√ n( ξn -E(Z)) law ---→ n→∞ N (0, v(θ ⋆ )) .
This algorithm has been studied in [START_REF] Su | Optimal importance sampling in securities pricing[END_REF][START_REF] Arouna | Robbins-Monro algorithms and variance reduction in finance[END_REF] and required 2n samples. It may use less than 2n samples if the estimation of θ ⋆ is performed on a smaller number of samples but then it raises the question of how many samples to use.

The adaptive algorithm

The adaptive approach is to use the same samples (X 1 , . . . , X n ) to compute θ n and the Monte Carlo estimator. Compared to the sequential algorithm, the adaptive one uses half of the samples.

Algorithm 1.2 (Adaptive Importance Sampling (ADIS)). Let n be the number of samples used for the Monte Carlo computation. For θ 0 fixed in R d , compute

ξ n = 1 n n i=1 H(θ i-1 , X i ). (3)
Note that the sequence (ξ i ) i can be written in a recursive manner so that it can be updated online each time a new iterate θ i is drawn

ξ i+1 = i i + 1 ξ i + 1 i + 1
H(θ i , X i+1 ), with ξ 0 = 0.

Being able to update the sequence (ξ i ) i online has the advantage that there is no need to store the whole sequence (X 1 , . . . , X n ) for computing ξ n . This adaptive algorithm was first studied in [START_REF] Arouna | Adaptative Monte Carlo method, a variance reduction technique[END_REF] in which the author studied the convergence of the sequence (ξ n ) n under assumptions to be verified along the path (θ n ) n which makes them hard to check in practise. In this article, we prove a new convergence result under local integrability conditions on the function H, namely we impose that for any compact subset

K of R n , sup θ∈K E(|H(θ, X)| 2 ) < ∞.
We refer the reader to section 2.1 for a precise statement and proof of these results. We want to emphasize that such assumptions only involving properties of the function H and not of the sequence (θ n ) n are far easier to check in practice. Sofar, we have assumed that we knew how to devise a convergent estimator of θ ⋆ , but this may not be so simple as when no closed form expression is available for E (H(θ, X)), there is hardly no chance that the function v can be computed explicitly. Henceforth, it is needed to approximate θ ⋆ without being able to compute the variance itself. In this work, we recall the methodology based on stochastic approximation developed in [START_REF] Su | Optimal importance sampling in securities pricing[END_REF][START_REF] Vázquez-Abad | Accelerated simulation for pricing asian options[END_REF][START_REF] Arouna | Robbins-Monro algorithms and variance reduction in finance[END_REF] to estimate θ ⋆ using some stochastic gradient style algorithms. We aim at applying this methodology to the evaluation of financial derivatives and the main difficulty in approximating θ ⋆ comes from the non-boundedness of the payoff functions usually considered and consequently the non-boundedness of the H functions. To encompass this problem, several authors as in [START_REF] Vázquez-Abad | Accelerated simulation for pricing asian options[END_REF][START_REF] Su | Optimal importance sampling in securities pricing[END_REF] restrict the parameter θ to lie in a compact set, which is obviously unknown in practice; therefore, this compact set will have to be quite large. Although, it permits to prove the theoretical convergence of the Robbins-Monro algorithm it does not help to build a numerically convergent estimator of θ ⋆ . We all know that the true convergence of stochastic algorithms highly relies on the fine tuning of the gain sequence which reveals to be very difficult when dealing with an artificially bounded parameter set.

In this work following [START_REF] Arouna | Robbins-Monro algorithms and variance reduction in finance[END_REF], we would rather use a randomly truncated algorithm which is known to converge for a much wider class of functions. We give a unified framework with easily verifiable assumptions under which Algorithm 1.2 converges and satisfies a central limit theorem. Then, we combine this convergence result with the new results on randomly truncated stochastic algorithm from [START_REF] Lelong | Almost sure convergence of randomly truncated stochastic algorithms under verifiable conditions[END_REF] to revisit the adaptive algorithm in the Gaussian framework studied in [START_REF] Arouna | Adaptative Monte Carlo method, a variance reduction technique[END_REF].

The paper is organised as follows. In Section 2, we focus on the mathematical foundation of the method and give both a strong law of large numbers and a central limit theorem for the adaptive estimator under weak assumptions. In Section 3, we present one way of constructing a convergent estimator of θ ⋆ and recall some recent results on stochastic approximation. Then, we give in Section 4 some examples of how to construct a parametric estimator using importance sampling or other more elaborate transformations. Finally, we illustrate the convergence results obtained in Section 2 on numerical examples coming from financial problems.

Mathematical foundations of the method

Notations:

• We encode any elements of R m as column vectors.

• If x ∈ R m , x * is a row vector. We use the " * " notation to denote the transpose operator for vectors and matrices.

• If x, y ∈ R m , x • y denotes the Euclidean scalar product of x and y and the associated norm is denoted by | • |.

In this section, (X n ) n≥1 is an i.i.d. sequence following the law of X and we introduce the σ-algebra F n it generates F n = σ(X 1 , . . . , X n ). For technical reasons, we assume that the variance v does not vanish, i.e. inf θ∈R n v(θ) > 0. If such is not the case, it means that we are actually in a better situation as far as variance reduction is concerned but it does not fit in our framework.

An adaptive strong law of large numbers

Theorem 2.1 (Adaptive strong law of large numbers). Assume Equation (1) and (2) hold. Let (θ n ) n≥0 be a (F n )-adapted sequence with values in R d such that for all n ≥ 0, θ n < ∞ a.s and for any compact subset

K ⊂ R d , sup θ∈K E(|H(θ, X)| 2 ) < ∞. If inf θ∈R d v(θ) > 0 and 1 n n k=0 v(θ k ) < ∞ a.s., ( 4
)
then ξ n converges a.s. to E(Z).

Proof. For any p ≥ 0, we define τ p = inf{k ≥ 0; |θ k | ≥ p}. The sequence (τ p ) p is an increasing sequence of (F n )-stopping times such that lim p→∞ τ p ↑ ∞ a.s.. Let

M n = n-1 i=0 H(θ i , X i+1 ) -E(Z). We introduce M τp n = M τp∧n defined by M τp n = n-1∧τp i=0 H(θ i , X i+1 ) -E(Z) = n-1 i=0 (H(θ i , X i+1 ) -E(Z))1 {i≤τp} . E(|H(θ i , X i+1 ) -E(Z)| 2 1 {i≤τp} ) ≤ E(1 {i≤τp} E(|H(θ, X) -E(Z)| 2 ) θ=θ i ).
On the set {i ≤ τ p }, the conditional expectation is bounded from above by sup |θ|≤p v(θ). Hence, the sequence (M τp n ) n is square integrable and it is obvious that (M τp n ) n is a martingale, which means that the sequence (M n ) n is a locally square integrable martingale (i.e. a local martingale which is locally square integrable).

M n = n-1 i=0 E((H(θ i , X i+1 ) -E(Z)) 2 |F i ) = n-1 i=0 v(θ i ).
By Condition (4), we have a.s. lim sup n 1 n M n < ∞ and lim inf n 1 n M n > 0. Applying the strong law of large numbers for locally L 2 martingales (see [START_REF] Lépingle | Sur le comportement asymptotique des martingales locales[END_REF]) yields the result.

The sequence (θ n ) n can be any sequence adapted to (X n ) n≥1 convergent or not. For instance, (θ n ) n can be an ergodic Markov chain distributed around the minimizer θ ⋆ such as Monte Carlo Markov Chain algorithms.

Remark 2.2. When the sequence (θ n ) n≥0 converges a.s. to a deterministic constant θ ∞ , it is sufficient to assume that v is continuous at θ ∞ and v(θ ∞ ) > 0 to ensure that Condition (4) is satisfied. Note that there is no need to impose that θ ∞ = θ ⋆ although it is undoubtedly wished in practice. For instance, θ ∞ can be an approximation of θ ⋆ obtained either by heuristic arguments such as large deviations.

A Central limit theorem for the adaptive strong law of large numbers

To derive a central limit theorem for the adaptive estimator ξ n , we need a central limit theorem for locally square integrable martingales, whose convergence rate has been extensively studied. We refer to the works of Rebolledo [START_REF] Rebolledo | Central limit theorems for local martingales[END_REF], Jacod and Shiryaev [START_REF] Jacod | Limit Theorems for Stochastic Processes[END_REF], Hall and Heyde [START_REF] Hall | Martingale limit theory and its application[END_REF] and Whitt [START_REF] Whitt | Proofs of the martingale FCLT[END_REF] to find different statements of central limit theorems for locally square integrable càdlàg martingales in continuous time, from which theorems can easily be deduced for discrete time locally square integrable martingales.

Theorem 2.3. Assume Equation (1) and (2) hold. Let (θ n ) n≥0 be a F n -adapted sequence with values in R d such that for all n ≥ 0, θ n < ∞ a.s and converging to some deterministic value θ ∞ . Assume there exists η > 0 such that the function

s 2+η : θ ∈ R d -→ E |H(θ, X)| 2+η is finite for all θ ∈ R d and continuous at θ ∞ . Moreover, if v is continuous at θ ∞ and v(θ ∞ ) > 0, then, √ n(ξ n -E(Z)) law --→ N (0, v(θ ∞ )).
Proof. We know from the proof of Theorem 2.1 that

M n = n-1 i=0 H(θ i , X i+1 ) -E(Z) is a locally square integrable martingale and that 1 n M n converges a.s. to v(θ ∞ ). 1 n n-1 i=0 E(|H(θ i , X i+1 ) -E(Z)| 2+η |F i ) ≤ c 1 n n-1 i=0 s 2+η (θ i ) + E(Z) 2+η .
The term on the r.h.s is bounded thanks to the continuity of s 2+η at θ ∞ . Hence, the local martingale (M n ) n satisfies Lindeberg's condition. The result ensues from the central limit theorem for locally L 2 martingales.

Corollary 2.4 (Effective central limit theorem with confidence interval). Assume Equation (1) and (2) hold. Let (θ n ) n≥0 be a F n -adapted sequence with values in R d such that for all n ≥ 0, θ n < ∞ a.s and converging to some deterministic value θ ∞ . Assume there exists η > 0 such that the function

s 4+η : θ ∈ R d -→ E |H(θ, X)| 4+η is finite for all θ ∈ R d and continuous at θ ∞ . Then, σ 2 n = 1 n n-1 i=0 H(θ i , X i+1 ) 2 -ξ 2 n a.s. --→ v(θ ∞ ). If moreover v(θ ∞ ) > 0, then √ n σn (ξ n -E(Z)) law -----→ n→+∞ N (0, 1).
Remark 2.5. Even if v(θ ∞ ) > 0, σ n may take negative values for n small. This corollary is really essential from a practical point of view because it proves that confidence intervals can be built as in the case of a crude Monte Carlo procedure. The only difference lies in the way of approximating the asymptotic variance.

The assumptions of Theorem 2.3 are fairly easy to check in practice since they are formulated independently of the sequence (θ n ) n . When θ ∞ = θ ⋆ , which is nonetheless not required, the limiting variance is optimal in the sense that a crude Monte Carlo computation with the optimal parameter θ ⋆ would have lead to the same limiting variance. These assumptions are satisfied in the frameworks introduced in Section 4.

Estimation of the optimal variance parameter

From Theorem 2.1 and Theorem 2.3, we know that if we can construct a convergent estimator (θ n ) n of θ ⋆ , the adaptive estimator ξ n is a convergent and asymptotically normal estimator of the expectation E(Z). The challenging issue is now to propose an automatic way of approximating the minimiser

θ ⋆ of v(θ) = E(H(θ, X) 2 ) -E(Z) 2 .
In the following, we will assume that v is strictly convex, goes to infinity at infinity and is continuously differentiable. Moreover, we assume that ∇v admits a representation as an expectation

∇v(θ) = E(U (θ, X)),
where U : R d × R m -→ R d is a measurable and integrable function. We could see in the examples developed in Section 4 that these conditions are very easily satisfied. Stochastic algorithms such as the Robbins Monro algorithm (see [START_REF] Robbins | A stochastic approximation method[END_REF]) are perfectly well suited to estimate quantities defined as the root of an expectation. Because for the applications we are targeting we cannot impose that E(|U (θ, X)| 2 ) < c(1 + |θ| 2 ), the Robbins-Monro algorithm will fail to converge and we need a more robust algorithm. This will naturally lead us to consider randomly truncated stochastic algorithms as introduced by Chen et al. [START_REF] Chen | Stochastic Approximation Procedure with randomly varying truncations[END_REF]. When dealing with stochastic approximations, the idea of averaging the iterates comes out quite naturally to smooth the trajectories, see Section 3.2.

Randomly truncated stochastic algorithms

Let (X n ) n≥1 be an i.i.d sequence of random variables following the law of X and (γ n ) n≥1 be a decreasing sequence of a positive real numbers satisfying

n γ n = ∞ and n γ 2 n < ∞. (5)
The sequence (γ n ) n is often called the gain sequence or the step sequence. We define the σ-field

F n = σ(X k , k ≤ n). We introduce an increasing sequence of compact sets (K j ) j of R d ∞ n=0 K n = R d and K n Kn+1 (6)
Now, we can present the randomly truncated stochastic algorithm introduced in [START_REF] Chen | Stochastic Approximation Procedure with randomly varying truncations[END_REF], which essentially consists in a truncation of the Robbins Monro algorithm on an increasing sequence of compact sets. For θ 0 ∈ K 0 and α 0 = 0, we define the sequences of random variables (θ n ) n and (α n

) n by        θ n+ 1 2 = θ n -γ n+1 U (θ n , X n+1 ), if θ n+ 1 2 ∈ K αn θ n+1 = θ n+ 1 2 and α n+1 = α n , if θ n+ 1 2 / ∈ K αn θ n+1 = θ 0 and α n+1 = α n + 1. ( 7
)
θ n+ 1 2
is the new sample we draw, either we accept it and set θ n+1 = θ n+ 1 2 or we reject it and reset the algorithm to θ 0 when it tries to jump too far ahead in a single step. Note that θ n+ 1 2 is actually drawn along the dynamics of the Robbins Monro algorithm and either we accept it as the new iterate or we reject it when the algorithm tries to jump to far ahead and in this case we reset the new iterate to θ 0 . In the following, we write Equation ( 7) in a more condensed form

θ n+1 = T Kα n (θ n -γ n+1 U (θ n , X n+1 )) , (8)
where T Kα n denotes the truncation on the compact sets K αn . The use of truncations enables to relax the hypotheses required to ensure the convergence. From the recent results of [START_REF] Lelong | Almost sure convergence of randomly truncated stochastic algorithms under verifiable conditions[END_REF], we can state the following convergence result Theorem 3.1. Assume that (A1) ∇v is continuous and there exists a unique θ ⋆ s.t. ∇v(θ ⋆ ) = 0 and

∀ θ = θ ⋆ , (∇v(θ) | θ -θ ⋆ ) > 0. (A2) ∀q > 0, sup |θ|≤q E(|U (θ, Z)| 2 ) < ∞.
Then, the sequence (θ n ) n defined by ( 7) converges a.s. to θ ⋆ for any sequence of compact sets satisfying [START_REF] Hall | Martingale limit theory and its application[END_REF] and moreover the sequence (α n ) n is a.s. finite.

Note that the assumptions required to ensure the convergence are very weak and are formulated independently of the algorithm trajectories, which makes them easy to check. Since the variance reduction technique we settle here aims at being automatic in the sense that it does not require any fiddling with the gain sequence depending on the function U , it is quite natural to average the procedure defined by Equation (7).

Averaging a stochastic algorithm

This section is based on the remark that Cesaro type averages tend to smooth the behaviour of convergent estimators at least from a theoretical point of view. Such averaging techniques have already been studied and proved to provide asymptotically efficient estimators (see for instance [START_REF] Polyak | Acceleration of stochastic approximation by averaging[END_REF], [START_REF] Kushner | Stochastic approximation with averaging of the iterates: Optimal asymptotic rate of convergence for general processes[END_REF] or [START_REF] Pelletier | Asymptotic almost sure efficiency of averaged stochastic algorithms[END_REF]).

At the same time, it is well known that true Cesaro averages are not so efficient from a practical point of view because the rate at which the impact of the first iterates vanishes in the average is too slow and it induces some kind of a numerical bias which in turn dramatically slows down the convergence. Combining these two facts has led us to consider a moving window average of Algorithm [START_REF] Jacod | Limit Theorems for Stochastic Processes[END_REF]. In this section, we restrict to gain sequences of the form γ n = γ (n+1) a with 1 2 < a < 1. Let τ > 0 be the length of the window used for averaging. For n ≥ 1, we introduce

θn (τ ) = γ p τ p+⌊τ /γp⌋ i=p θ i with p = sup{k ≥ 1 : k + τ /γ k ≤ n} ∧ n. (9)
We use the convention sup ∅ = +∞. The almost sure convergence of ( θn (τ )) n can easily be deduced from Theorem 3.1. The asymptotic normality of the sequence ( θn (τ )) n has been studied in [START_REF] Lelong | Etude asymptotique des algorithmes stochastiques et calcul du prix des options Parisiennes[END_REF]. The definition of θn is a little different from the one used in [START_REF] Lelong | Etude asymptotique des algorithmes stochastiques et calcul du prix des options Parisiennes[END_REF] because we want to ensure that the sequence ( θn ) n is adapted to the filtration F n in view of the use of θn as an estimator of θ ⋆ in Algorithm 1.2.

Examples of parametric Monte-Carlo settings

In this section, we give various examples of cases in which a parametric representation of the expectation of interest is available

E(Z) = E(H(θ, X)).
In each example, we highlight the strong convexity and the regularity of the function θ -→ E(H 2 (θ, X)) such that the minimiser θ ⋆ is uniquely defined as the one root of θ -→ ∇ θ E(H 2 (θ, X)).

Importance sampling for normal random variables

Let G = (G 1 , . . . , G d ) be a d-dimensional standard normal random vector. For any measurable function h :

R d -→ R such that E(|h(G)|) < ∞, one has for all θ ∈ R d E (h(G)) = E e -θ•G-|θ| 2 2 h(G + θ) . (10)
Assume we want to compute E(f (G)) for a measurable function f : R d -→ R such that f (G) is integrable. By applying equality [START_REF] Kawai | Adaptive monte carlo variance reducion for Lévy processes with twotime-scale stochastic approximation[END_REF]

to h = f and h(x) = f 2 (x) e -θ•x+ |θ| 2 2
, one obtains that the expectation and the variance of the random variable

f (G + θ) e -θ•G -|θ| 2 2 are respectively equal to E(f (G)) and v(θ) -E 2 (f (G)) where v(θ) = E f 2 (G) e -θ•G+ |θ| 2 2 .
The strict convexity of the function v is already known from [START_REF] Su | Optimal importance sampling in securities pricing[END_REF] for instance. For the sake of completeness, we prove here a slightly improved version of this result.

P(f (G) = 0) > 0, ( 11
)
∃ε > 0, E(|f (G)| 2+ε ) < ∞ (12)
Then, v is infinitely continuously differentiable and strongly convex.

Proof. The function θ → f 2 (G)e -θ•G+ |θ| 2 2
is infinitely continuously differentiable. Since,

sup |θ|≤M |∂ θ j f 2 (G)e -θ•G+ |θ| 2 2 | ≤ e M 2 2 f 2 (G) M + (e G j + e -G j ) d k=1 (e M G k + e -M G k )
where the right hand side is integrable because by Hölder's inequality and Equation ( 12), we have

∀θ ∈ R d , E f 2 (G) e -θ•G < ∞. Lebesgue's theorem ensures that v is continuously differentiable with ∂ ∂ θ j v(θ) = E f 2 (G)(θ j -G j )e -θ•G+ |θ| 2 2
. Higher order differentiability properties are obtained by similar arguments and in particular the Hessian matrix writes

∇ 2 v(θ) = E f 2 (G)e -θ•G+ |θ| 2 2 ) I + E (θ -G)(θ -G) * f 2 (G)e -θ•G+ |θ| 2 2
The second term in the above equation is a positive semi-definite matrix, hence

∇ 2 v(θ) ≥ E(f 2 (G)e -θ•G+ |θ| 2 2 ) = E(f 2 (G)e -θ•G )E(e θ•G ) ≥ E(|f (G)|) 2 .
Assumption [START_REF] Kawai | Optimal importance sampling parameter search for Lévy processes via stochastic approximation[END_REF] ensures that E(|f (G)|) > 0. Then, the Hessian matrix is uniformly bounded from below by the positive definite matrix E(|f (G)|) 2 I. This yields the strong convexity of the function v.

Proposition 4.1 implies that v has a unique minimiser θ ⋆ characterised by ∇v(θ

⋆ ) = 0, i.e. E (θ ⋆ -G)e -θ ⋆ •G+ |θ ⋆ | 2 2 f 2 (G) = 0.

Importance sampling for processes

Equality [START_REF] Kawai | Adaptive monte carlo variance reducion for Lévy processes with twotime-scale stochastic approximation[END_REF] can actually be extended to the Brownian motion framework using Girsanov's theorem. Let (W t , 0 ≤ t ≤ T ) be a d-dimensional Brownian motion and F its natural filtration. For any measurable and F-predictable process (θ t , 0 ≤ t ≤ T ) such that E e

1 2 T 0 |θt| 2 dt < ∞, one has E (f (W t , 0 ≤ t ≤ T )) = E e -T 0 θt•dWt-1 2 T 0 |θt| 2 dt f W t + t 0 θ s ds, 0 ≤ t ≤ T . Assume θ t = θ ∈ R d , for all t ∈ [0, T ]. The variance of e -θ•W T -θ 2 T 2 f (W t , 0 ≤ t ≤ T ) writes down v(θ) -E f 2 (W t , 0 ≤ t ≤ T ) with v(θ) = E e -θ•W T + |θ| 2 2 T f 2 (W t + θt, 0 ≤ t ≤ T ) .
A similar result to Proposition 4.1 holds; in particular v is infinitely continuously differentiable, strictly convex and goes to infinity at infinity. For more general processes (θ t , 0 ≤ t ≤ T ), we refer the reader to [START_REF] Lemaire | Unconstrained recursive importance sampling[END_REF].

The exponential change of measure

The idea of tilting some probability measure to find the ones that minimises the variance is a very common idea which can be also be applied to a wide range of distribution, see for instance the recent results of Kawai [START_REF] Kawai | Optimal importance sampling parameter search for Lévy processes via stochastic approximation[END_REF][START_REF] Kawai | Adaptive monte carlo variance reducion for Lévy processes with twotime-scale stochastic approximation[END_REF] in which he applied an exponential change of measure to Lévy processes, also known as the Esscher transform. Consider a random variable X with values in R d and cumulative generating function ψ(θ) = log E e θ•X . We assume that ψ(θ) < ∞ for all θ ∈ R d . Let p denote the density of X. We define the density p θ by

p θ (x) = p(x) e θ•x-ψ(θ) , x ∈ R d .
Let X (θ) have p θ as a density, then

E(f (X)) = E f (X (θ) ) p(X (θ) ) p θ (X (θ) ) . The variance of f (X (θ) ) p(X (θ) ) p θ (X (θ) ) writes v(θ) -E f (X (θ) ) 2 p(X (θ) ) 2 p θ (X (θ) ) 2 with v(θ) = E   f (X (θ) ) p(X (θ) ) p θ (X (θ) ) 2   = E f (X) 2 e -θ•X+ψ(θ) .
Obviously, this change of measure is only valuable as a variance reduction technique if X (θ) can be simulated at approximately the same cost as X.

Proposition 4.2. Assume that

∃ε > 0, E(|f (G)| 2+ε ) < ∞ (13) lim |θ|-→∞ p θ (x) = 0 for all x in R d (14)
Then, v is infinitely continuously differentiable, convex and lim |θ|-→∞ v(θ) = ∞.

Proof. To prove the differentiability of v, it suffices to reproduce the first part of the proof of Proposition 4.1. The convexity of v comes from the log-convexity of ψ. Moreover,

v(θ) = E f (X) 2 e -θ•X+ψ(θ) = E f (X) 2 p(X) p θ (X)
Combining Equation ( 14) with Fatou's Lemma yields that lim |θ|-→∞ v(θ) = ∞.

Remark 4.3. If X is a random standard normal vector, p θ (x) = p(xθ) and X (θ) is a random normal vector with mean θ and identity covariance matrix. Hence, we recover Equality [START_REF] Kawai | Adaptive monte carlo variance reducion for Lévy processes with twotime-scale stochastic approximation[END_REF].

5 Application to the Gaussian random vector framework

Presentation of the problem

We consider a D-multidimensional local volatility model in which each asset is supposed to be driven by the following dynamics under the risk neutral measure.

dS i t = S i t (rdt + σ(t, S i t ) • dW i t ), S i 0 = s i . W = (W 1 , . . . , W D ) * is
a vector of correlated standard Brownian motions. The covariance structure of the Brownian motions is given by W, W t = Γt where Γ is a definite positive matrix with a diagonal filled with ones. In our numerical examples, we take Γ ij = 1 {i=j} + ρ1 {i =j} with ρ ∈ ( -1 D-1 , 1) to ensure that the matrix Γ is positive definite. The function σ is the local volatility function, r is the instantaneous interest rate and the vector (s 1 , . . . , s D ) is the vector of the spot values. In this model, we want to price path-dependent options whose payoffs can be written as a function of (S t , t ≤ T ). Hence, the price is given by the discounted expectation e -rT E(ψ(S t , t ≤ T )). Most of the time, this expectation must be computed by Monte Carlo methods and one has to consider an approximation of ψ(S t , t ≤ T ) on a time grid 0 = t 0 < t 1 < • • • < t N = T . Then, the quantity of interest becomes e -rT E( ψ(S t 0 , S t 1 , . . . , S t N )).

The discretisation of the asset S can for instance be obtained using an Euler scheme, which means that the function ψ can be expressed in terms of the Brownian increments or equivalently using a random normal vector. These remarks finally turn the original pricing problem into the computation of an expectation of the form E(φ(G)) where G is a standard normal random vector in R N D and φ : R N ×D -→ R is a measurable and integrable function. Using Equation ( 10), we have for all θ ∈ R d ,

E(φ(G)) = E φ(G + Aθ)e -Aθ•G-|Aθ| 2 2 , ( 15
)
where A is d × N D matrix. The particular choice d = N D and A = I d corresponds to Equation [START_REF] Kawai | Adaptive monte carlo variance reducion for Lévy processes with twotime-scale stochastic approximation[END_REF]. When D = 1, the choice d = 1 and A = (

√ t 1 , √ t 2 -t 1 , . . . , √ t N -t N -1 ) *
corresponds to adding a linear drift to the one dimensional standard Brownian motion W and we recover the Cameron-Martin formula. Transformation [START_REF] Lelong | Etude asymptotique des algorithmes stochastiques et calcul du prix des options Parisiennes[END_REF] actually relies on an importance sampling change of measure. Other strategies may be applicable such as stratification for instance as it is explained by Glasserman et al. in [START_REF] Glasserman | Asymptotically optimal importance sampling and stratification for pricing path-dependent options[END_REF].

Proof. We only do the proof for (θ 1 n ) n and ( θ 1 n ) n as the same ideas can be applied to (θ 2 n ) n and ( θ 2 n ) n . We know from Proposition 4.1, that the function v defined by Equation ( 16) is strongly convex and infinitely differentiable, hence ∇v satisfies Assumption (A1). Let q > 0. For any θ satisfying |θ| ≤ q, we have

E U 1 (θ, G) 2 ≤ E ( A ( A q + |G|) 2 φ(G) 4 e -2Aθ•G e A 2 q 2 .
Using Hölder's inequality, it can easily be proved that the expectation on the right hand side is uniformly bounded for |θ| ≤ q. Hence Assumption (A2) is satisfied. Therefore, θ 1 n and θ1 n both converge to θ ⋆ . Let η > 0,

E |H(θ, G)| 2+η = E |φ(G)| 2+η e -(1+η)Aθ•G e |Aθ| 2 (1+η) 2
.

Using the integrability of φ(G) and Hölder's inequality, one can prove that the expectation on the .r.h.s is bounded for θ in a ball. Moreover, combining this with Lebesgue's theorem, we obtain that the functions θ -→ E|H(θ, G)| 2 and θ -→ E|H(θ, G)| 2+η are continuous. Therefore, the convergence and asymptotic normality of ξ n issues from Theorems (2.1) and (2.3).

Remark 5.2. Theorem 5.1 extends the result of [START_REF] Arouna | Robbins-Monro algorithms and variance reduction in finance[END_REF]Theorem 4]. Our result is valid for any increasing sequences of compact sets (K j ) j satisfying ( 6) whereas Arouna needed a condition on the compact sets to ensure the convergence of the (θ n ) n estimators. The only condition required is some integrability on the payoff function and nothing has to be checked along the algorithm paths, which is a great improvement from a practical point of view.

For the vast majority of payoff functions commonly used, the assumptions of Theorem 5.1 are always satisfied.

Numerical results

Complexity of the different approximations

In the introduction, we have presented two different strategies for implementing a variance reduction method based on the approximation of the optimal variance parameter. We know from Theorem 5.1, that the adaptive and non-adaptive algorithms both converges at the same rate and the same limiting variance. Therefore, to decide which one is the better, we have to compare their computational costs. In this section, we assume that the computational cost of the different algorithms is determined by the number of evaluations of the function φ. We will see in the examples later that this assumption is realistic and therefore it becomes obvious that the averaging and non-averaging estimators of θ ⋆ all have the same computational costs when implemented with expertise.

The non-adaptive algorithm We know from [START_REF] Arouna | Robbins-Monro algorithms and variance reduction in finance[END_REF][START_REF] Su | Optimal importance sampling in securities pricing[END_REF] that the sequential algorithm converges with a rate of v(θ ⋆ )/n if we have 2n samples at hand and want to implement the sequential algorithm by using the first n samples for approximating θ ⋆ and the last n samples for actually computing the Monte Carlo estimator with the previously computed approximation of θ ⋆ . Whatever approximation of θ ⋆ is used, be it (θ

1 n ) n , (θ 2 n ) n , ( θ 1 n ) n or ( θ 2 n
) n , this algorithm requires 2n evaluations of the function φ whereas a crude Monte Carlo method only evaluates the function φ n times and achieves a convergence rate of v(0)/n, hence this method only becomes efficient when v(θ ⋆ ) ≤ v(0)/2.

The adaptive algorithm From Theorem 5.1, we know that the adaptive estimators

(ξ 1 n ) n , (ξ 2 n ) n , ( ξ1 n ) n , ( ξ2
n ) n all converge with the same rate v(θ ⋆ )/n but as we will see it they do not have the same computational cost. First, let us concentrate on (ξ 1 n ) n and ( ξ1 n ) n , at each iteration i, the function φ has to be computed twice : once at the point

G i+1 + θ 1 i (or G i+1 + θ1 i )
to update the Monte Carlo estimator and once at the point G i+1 to update θ 1 i+1 or θ1 i+1 . Hence, the computation of ξ 1 n or ξ1 n requires 2n evaluations of the function φ. Similarly, the computation of ξ2 n requires at each step 2 evaluations of the function φ : one at the point G i+1 + θ2

i to update the Monte Carlo estimator and one at the point G i+1 + θ 2 i to update the stochastic algorithm. So the overall cost is still 2n evaluations of the function φ. But looking closely at the computation of (ξ 2 n ) n immediately highlights the benefit of having put the parameter θ back into the function φ in the expression of ∇v : the updates of ξ 2 i+1 and θ 2 i+1 both use the evaluation of the function φ at the same point G i+1 + θ 2 i . Hence, the computation of ξ 2 n only needs n evaluations of the function φ instead of 2n for all the others algorithms. Obviously, the computational costs of the different estimators cannot really be reduced to the number of times the function φ is evaluated so one should not expect that computing ξ 2 n is twice less costly than the other estimators but we will see in the examples below that the estimator ξ 2 n is indeed faster than the others.

To shortly conclude on the complexity of the different algorithms, be they sequential or adaptive, one should bear in mind that all the estimators except (ξ 2 n ) n roughly require twice the computational time of the crude Monte-Carlo method.

Practical implementation

The choice of using Equations [START_REF] Jacod | Limit Theorems for Stochastic Processes[END_REF] or [START_REF] Jourdain | Robust adaptive importance sampling for normal random vectors[END_REF] to build an estimator of θ ⋆ becomes really important when one has to implement the variance reduction procedure either by using Algorithms (1.1) or (1.2). Both the averaging and non-averaging strategies have pros and cons. The averaging algorithm theoretically converges a little slower but has a much smoother behaviour with respect to the proper adjustment of the gain sequence (γ n ) n . Then, to have a robust estimator -in the sense that the numerical convergence of the estimator does not depend too much on the choice of of the gain sequence -the averaging procedure proves to be better in practice. The non averaging algorithm should converge a little faster even though we do not notice it in practise as the convergence oscillates too much and is far more sensitive to the proper choice of the sequence (γ n ) n . Eventually, both algorithms produce very similar results regarding variance reduction; the averaging one is easier to tune but requires more computational time.

In the numerical experiments of this section, we compare the different algorithms on multi-asset options. The quantity "Var MC" denotes the variance of the crude Monte Carlo estimator computed on-line on a single run of the algorithm. The variance denoted "Var ξ 2 " (resp. "Var ξ2 ") is the variance of the ADIS algorithm (see Algorithm 1.2) which uses (θ 2 n ) n (resp. ( θ2 n ) n ) to estimate θ ⋆ . These variances are computed using the on-line estimator given by Corollary 2.4. These adaptive algorithms are also compared to the sequential strategy described by Algorithm 1.1 denoted by "θ 2 +MC" or " θ2 +MC" depending on how θ ⋆ is approximated. In all these algorithms, the matrix A introduced in Equation ( 15) is chosen as the identity matrix. When A is not the identity matrix, its purpose is to reduce the dimension of the space in which the optimal θ ⋆ is searched and in such cases the algorithms will be call "reduced". Note that for the comparison to be fair between the different strategies, we have used n samples for the adaptive algorithms but 2n for the sequential algorithms so that they all satisfy a central limit theorem with the rate √ n. 1.

Basket options

The results of Table 1 indicate that the adaptive algorithm using an averaging stochastic approximation outperforms not only the crude Monte Carlo approach but also the adapted algorithms using non-averaging stochastic approximation. The better performance of the algorithms using averaging estimators of θ ⋆ comes from the better smoothness of the averaging algorithm (see Equation ( 9)). Nonetheless, these good results in terms of variance reduction must be considered together with their computation costs reported in Table 2. As explained in Section 5.3.1, we notice that the computational cost of the estimator ξ 2 is very close to the one of the crude Monte Carlo estimator because the implementation made the most of the fact that the updates of ξ 2 i+1 and θ 2 i+1 both need to evaluate the function φ at the same point. Note that, because this implementation trick cannot be applied to ξ2 , the adaptive algorithm using an averaging stochastic approximation is twice slower. For a given precision, the adaptive algorithm is between 5 and 10 times faster.

Barrier Basket Options We consider basket options in dimension D with a discrete barrier on each asset. For instance, if we consider a Down and Out Call option, the payoff writes down ( D i=1 ω i S i T -K) + 1 {∀i≤D, ∀j≤N, S i t j

≥L i } where ω = (ω 1 , . . . , ω D ) is a vector of positive weights, L = (L 1 , . . . , L D ) is the vector of barriers, K > 0 the strike value and t N = T . We consider one time step per month, which means that for an option with maturity time T = 2, the number of time steps is N = 24. From now on, we fix D = 5. Hence if we use the identity matrix A, the parameter θ is of size N × D = 120. Here, we propose to reduce the dimension of θ and we will in Table 3 that it achieves almost the same variance reduction. Of course the matrix A cannot be chosen independently of the structure of the problem. Remember that the vector G actually corresponds to the increments of the Brownian motion B with values in R d on the grid (t k = kT /N, k = 0, . . . , N ). We recall that we can simulate the Brownian motion B on the time grid (t k ) k by using the following equality in law

       B t 1 B t 2 . . . B t N-1 B t N        =         √ t 1 I D 0 0 . . . 0 √ t 1 I D √ t 2 -t 1 I D 0 . . . 0 . . . . . . . . . . . . . . . . . . . . . . . . √ t N -1 -t N -2 I D 0 √ t 1 √ t 2 -t 1 I D . . . √ t N -1 -t N -2 I D √ t N -t N -1 I D         G where I D is the identity matrix in dimension D. If we choose A =         √ t 1 I D √ t 2 -t 1 I D . . . . . . √ t N -t N -1 I D        
then the transformation G + Aθ corresponds to the transformation (B t 1 + θt 1 , B t 2 + θt 2 , . . . , B t N + θt N ) * and it reduces the effective dimension of the importance sampling parameter to D = 5 rather than DN = 120. 3.

K γ

the importance sampling parameter to reduce the noise in the stochastic approximation and therefore in the adaptive Monte Carlo estimator. Comparing the columns "Var MC", "Var ξ 2 " and "Var ξ2 " points out that when the convergence of the estimator of θ ⋆ is too slow the first iterates of the adaptive Monte Carlo estimators use wrong values of θ and therefore cannot reach v(θ ⋆ ) whereas if a sequential algorithm is used all the iterates of the Monte Carlo estimator use the same and better approximation of θ. We can see in Table 3 that the variance of " ξ2 +MC" is half the one of ξ 2 or ξ2 but its CPU time is twice the one of ξ 2 as noted in Table 4.

The reduced algorithms are a little faster than the non-reduced ones but their real advantage is to converge much more stably and to achieve the same variance as " ξ2 +MC" but in far less computational time. As in the previous examples, we still observe that the estimator "ξ 2 reduced" is faster than the others and has a variance very close to the best method which is " θ2 +MC".

Conclusion

In this work, we have explained how one could devise an adaptive variance reduction method for computing an expectation with a free parameter. Different algorithms have been studied both from a theoretical point of view and in practice. Although all the adaptive algorithms satisfy the same central limit theorem, they may behave very differently in practice, in particular adaptive algorithms using a non-averaging stochastic approximation of the optimal variance parameter can be implemented in a clever way which makes them as fast as a crude Monte Carlo approach. Nevertheless, the numerical convergence of these stochastic is very sensitive to the tuning of their gain sequence and one way to smooth this behaviour is to plug an averaging procedure on top of the stochastic approximation but then the computational time significantly increases and yet the dependency with respect to the gain sequence is still a serious drawback. To encounter the fine tuning of the algorithm, Jourdain and Lelong [START_REF] Jourdain | Robust adaptive importance sampling for normal random vectors[END_REF] have recently suggested to use deterministic optimisation techniques coupled with sample approximation, but their technique can not be implemented in an adaptive manner which increases its computational cost.

Proposition 4 . 1 .

 41 Assume that

Table 1 :

 1 We consider options with payoffs of the form ( d i=1 ω i S i T -K) + where (ω 1 , . . . , ω d ) is a vector of algebraic weights (enabling us to consider exchange options). Basket option in dimension d = 40 with r = 0.05, T = 1, S i 0 = 50, σ i = 0.2, ω i = 1 d for all i = 1, . . . , d and n = 100 000.

	ρ K γ Price Var MC Var ξ 2 Var ξ2
	0.1 45 1	7.21	12.24	1.59	1.10
	55 10 0.56	1.83	0.19	0.14
	0.2 50 0.1 3.29	13.53	1.82	1.76
	0.5 45 0.1 7.65	43.25	6.25	4.97
	55 0.1 1.90	14.74	1.91	1.4
	0.9 45 0.1 8.24	69.47	10.20	7.78
	55 0.1 2.82	30.87	2.7	2.6
	Estimators MC ξ 2	ξ2
	CPU time 0.85 0.9 1.64

Table 2 :

 2 CPU times for the option of Table

Table 3 :

 3 Price Var MC Var ξ 2 Var ξ2 Var Var ξ 2 Down and Out Call option in dimension I = 5 with σ = 0.2, S 0 = (50, 40, 60, 30, 20), L = (40, 30, 45, 20, 10), ρ = 0.3, r = 0.05, T = 2, ω = (0.2, 0.2, 0.2, 0.2, 0.2) and n = 100 000.First, we note from Table3that the reduced and non-reduced ADIS algorithm achieve almost the same variance reduction. Actually, it is even advisable to reduce the size of

	Var ξ2	Var
	θ2 +MC	θ2 +MC
	reduced reduced reduced

Table 4 :

 4 CPU times for the option of Table

Bespoke estimators for the optimal variance parameter

It ensues from Proposition 4.1, that the second moment

is strongly convex, infinitely differentiable and

If we apply Equation ( 10) again, we obtain an other expression for

Let us introduce the following two functions

Using either Equation ( 17) or ( 18), we can write ∇v(θ

) and these two functions U 1 and U 2 fit in the framework of Section 3 and enable to construct two estimators of θ ⋆ (θ 1 n ) n and (θ 2 n ) n following Equation ( 7)

where G n is an i.i.d sequence of random variables following the law of G. We also introduce their corresponding averaging versions ( θ 1 n ) n and ( θ 2 n ) n following Equation [START_REF] Jourdain | Robust adaptive importance sampling for normal random vectors[END_REF]. Based on Equation (15), we define

Corresponding to the different estimators of θ ⋆ listed above, we can define as many approximations of E(φ(G)) following Equation ( 3)

where the sequence G i has already been used to build the (θ n ) n estimators. From Proposition 4.1 and Theorems 3.1, 2.1 and 2.3, we can deduce the following result.

Theorem 5.1. If there exists ε > 0 such that E(φ(G) 4+ε ) < ∞ then, the sequences

n ) n defined by Equations [START_REF] Jacod | Limit Theorems for Stochastic Processes[END_REF] or (9) converge a.s. to θ ⋆ for any increasing sequence of compact sets (K j ) j satisfying [START_REF] Hall | Martingale limit theory and its application[END_REF] and the adaptive estimator (ξ 1 n ) n , (ξ 2 n ) n , ( ξ1 n ) n , ( ξ2 n ) n converge to E(φ(G)) and are asymptotically normal with optimal limiting variance v(θ ⋆ ).


Douglas J Leith

David Malone

Field Measurements of 802.11 Collision, Noise and Hidden-Node Loss Rates

In this paper we present the first field measurements taken using a new approach proposed in [1] for measuring link impairments in 802.11 WLANs. This uses a sender-side MAC/PHY cross-layer technique that can be implemented on standard hardware and is able to explicitly classify lost transmission opportunities into noise-related losses, collision induced losses, hidden-node losses and to distinguish among these different types of impairments on a per-link basis. We show that potential benefits arising from the availability of accurate and reliable data are considerable.

I. INTRODUCTION

In 802.11 there are a variety of reasons why a packet can fail to be transmitted successfully including collisions, hidden nodes, weak signal strength, etc. However, feedback to the sender of a frame is limited to the presence or absence of an acknowledgement. This limited feedback makes schemes for understanding the of the 802.11 channel particularly interesting; information on the cause of failed transmission is required to effectively adapt to the environment.

In this paper we present field measurements taken using a new approach proposed in [START_REF] Giustiniano | Measuring transmission opportunities in 802.11 links[END_REF] for measuring link impairments in 802.11 WLANs. This uses a sender-side MAC/PHY crosslayer technique that can be implemented on standard hardware. The scheme is able to classify lost transmission opportunities as noise-related losses, collision induced losses, hidden-node losses and to distinguish among these different types of impairments on a per-link basis. As the technique is based at the sender, where most choices about packet transmission are made, it can be used to adapt parameters such as PHY rate and contention window. We show that potential benefits arising from the availability of accurate and reliable data are considerable.

We note that it is the current lack of such measurements that underlies the poor performance of many approaches currently implemented in commodity hardware. For example, at present rate adaptation is commonly based on the number of transmission retries (e.g. a typical approach might involve lowering the rate after n retries and increasing the rate after m successful transmissions). However, since the number of retries is affected not just by channel noise but is also closely linked to the number of contending stations (with associated collision related losses), this can easily lead to poor performance [START_REF] Ramachandran | Scalability analysis of Rate Adaptation Techniques in Congested IEEE 802.11 Networks: An ORBIT Testbed Comparative Study[END_REF]. Analogous problems occur in the presence of hidden nodes, e.g. see [START_REF] Wong | Robust Rate Adaptation for 802.11 Wireless Networks[END_REF]. The availability of a measure of This material is based upon works supported by the Science Foundation Ireland under Grant Nos. 07/IN.1/I901 and 07/SK/I1216a. the loss rate specifically induced by channel noise would potentially allow much more effective rate adaptation algorithms to be employed. Similarly, channel selection algorithms are fundamentally related to channel impairments and typically depend upon the availability of an appropriate channel quality metric, which can then be optimised by a suitable search over available channels.

The paper is organised as follows. In Section II we introduce aspects of the 802.11 MAC that are important for our measurement technique, and then describe the link impairments that we aim to identify. In Section III we detail our measurement methodology and then in Sections IV-VI we present baseline and field measurements that show how these measurements give insight into the state of an 802.11 channel.

II. LINK IMPAIRMENTS IN 802.11

A. CSMA/CA protocol

In 802.11 WLANs, the basic mechanism controlling medium access is the Distributed Coordination Function (DCF). This is a random access scheme, based on Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). In the DCF Basic Access mode, a station with a new packet to transmit selects a random backoff counter. Time is slotted and if the channel is sensed idle the station first waits for a Distributed Inter-Frame Space (DIFS), then decrements the backoff counter each PHY time slot. If the channel is detected busy, the countdown is halted and only resumed after the channel is detected idle again for a DIFS. Channel idle/busy status is sensed via:

• CCA (Clear Channel Assessment) at the physical level which is based on a carrier sense threshold for energy detection, e.g. -80dBm. CCA is expected to be updated every physical slot time. It aims to detect transmissions within the interference range.

• NAV (Network Allocation Vector) timer at MAC level which is encapsulated in the MAC header of each 802.11 frame and is used to predict the end of a received frame on air. It is naturally updated once per packet and can only gather information from stations within the decoding range. This method is also called virtual carrier sense. The channel is detected as idle if the CCA detects the channel as idle and the NAV is zero. Otherwise, the channel is detected as busy. A station transmits when the backoff counter reaches zero. The 802.11 protocol uses a half-duplex process where an acknowledgement (ACK) is always sent by the receiver upon the successful receipt of a unicast frame. The ACK is sent after a period of time called the Short Inter-Frame Space (SIFS). As the SIFS is shorter than a DIFS, no other station is able to detect the channel idle for a DIFS until the end of the ACK transmission. The DCF allows the fragmentation of packets into smaller units. Each fragment is sent as an ordinary 802.11 frame, which the sender expects to be ACKed. However, the fragments may be sent as a burst. That is, the first fragment contends for medium access as usual. When the first fragment is successfully sent, subsequent fragments are sent after a SIFS, so no collisions are possible. In addition, the medium is reserved using virtual carrier sense for the next fragment both at the sender (by setting the 802.11 NAV field in the fragment) and at the receiver (by updating the NAV in the ACK). Burst transmission is halted after the last fragment has been sent or when loss is detected. A similar bursting technique is used in 802.11e's TXOP feature, though greater flexibility in setting the NAV is permitted.

B. Link impairments

The manner in which link impairments are manifested is closely linked to the interaction between MAC and PHY operation. We distinguish three main types of link impairment when using the 802.11 DCF.

1) Collisions: Collisions are part of the correct operation of CSMA/CA. Collisions occur when two or more stations have simultaneously decremented their backoff counter to 0 and then transmit. Note that collisions can only occur on data packet transmissions. The level of collision induced packet losses is dependent on both load and the number of stations active in the network. For example, 802.11b with four saturated nodes has a collision probability of around 14%, while 20 saturated have a collision probability of around 40% [START_REF] Bianchi | Performance analysis of IEEE 802.11 distributed coordination function[END_REF]. We denote by p c the probability that a transmitted data frame is lost due to a collision.

2) Hidden nodes: Frame corruption due to concurrent transmissions other than collisions are referred to as hidden node interference. We denote by p h,data the probability that a data transmission fails to be received correctly due to hidden node interference. Similarly, we denote by p h,ack the probability that an ACK transmission is lost due to hidden node interference. A lost data packet or a lost ACK both lead to a failed transmission and so we combine data and ACK losses into an overall hidden node error probability p h .

3) Noise errors: Frame corruption due to sources other than transmissions by other 802.11 stations are referred to as noise losses. We denote by p n,data (respectively, p n,ack ) the probability that a data (respectively, ACK) frame is lost due to noise related errors. Since data and ACK losses both lead to a failed transmission we lump these together into a combined noise loss probability p n .

III. MEASUREMENT METHODOLOGY

Similarly to the approach proposed in [START_REF] Giustiniano | Measuring transmission opportunities in 802.11 links[END_REF], we make use of the following properties of the 802.11 MAC:

1) Time is slotted, with well-defined boundaries at which frame transmissions by a station are permitted.

2) The standard data-ACK handshake is affected by all types of link impairment considered and a sender-side analysis can reveal any loss. 3) When fragmentation is enabled, second and subsequent fragment transmissions are protected from collisions and hidden nodes by the NAV values in the fragments and ACKs. We treat hidden nodes that are unable to decode either NAV value as channel noise. We may also use TXOP packet bursting with alternative NAV settings.

A. Estimating Noise Errors

Consider a station sending fragmented packets to a given receiver. Each fragment is immediately acked by the receiver when it arrives, allowing detection of loss. Fragments are sent back to back with a SIFS interval between them. Hence, second and subsequent packets are protected from collisions. Importantly, fragment ACK frames update the NAV and so the fragment-ACK handshake is akin to an RTS-CTS exchange from the point of view of hidden nodes Hence, second and subsequent fragments are also protected from hidden node collisions. That is, while the first fragment will be subject to collisions, noise and hidden node errors, subsequent fragments are only subject to noise errors and we have that

P[fragment 2 success] = A S /T S = (1 -p n ), (1)
where the station transmits T S second and subsequent data frames and of these A S are successful because an ACK is received. We can therefore directly estimate the probability of noise errors p n from the fraction of second and subsequent fragments with no ACK,

p n = 1 -A S /T S (2)
Since the impact of noise losses may depend on the frame length (longer frames typically having higher probability of experiencing bit errors), we equalize the length of the fragments we send and transmit fragments of length equal to the packet size used for regular data transmissions. The frame loss rate estimated from fragment measurements can then be reliably applied to estimate the loss rate for other transmissions.

B. Estimating Hidden Node Interference

We now distinguish frame losses due to hidden node interference. To achieve this we exploit the fact the NAV value in the header of ACK packets echoes the value in the header of the corresponding data packet. Hence, by changing the NAV value in the first fragment packet header we can change the NAV in the ACK so that it covers just the ACK transmission i.e. does not protect the second fragment. Note that this is essentially equivalent to the TXOP functionality in 802.11e. Such second fragments are then subject to noise or hidden node interference, but not to collision losses. That is,

P[TXOP 2 success] = A 1 /T 1 = (1 -p h )(1 -p n ), (3)
where the station transmits T 1 second fragment frames that are not protected by the ACK NAV and of these A 1 are successful 2)), to allow estimation of the probability p h of hidden node losses as:

p h = 1 -(A 1 • T S )/(A S • T 1 ). (4)

C. Estimating Collision Rate

The first packet in a fragment or TXOP burst is subject to collisions, hidden nodes and noise errors. Suppose that over some time period the station contends and transmits such first in a burst data frames T 0 times and of these A 0 are successful because an ACK is received. Assuming that these sources of frame loss are independent, if the station transmits the probability of success over the link is:

P[success] = A 0 /T 0 = (1 -p c )(1 -p h )(1 -p n ). (5)
Finally p c can be estimated from Eq. ( 5) and ( 3):

p c = 1 -(T 1 • A 0 )/(T 0 • A 1 ). (6)

D. Experimental apparatus

We implemented the above link quality measurement methodology via a modified Linux Madwifi driver (based on 10.5.6 HAL, 0.9.4 driver). We performed sender-side measurements using an Asus 700 laptop running Debian Lenny with 2.6.26 Linux kernel. The laptop is equipped with an Atheros 802.11 a/b/g chipset (radio 14.2, MAC 8.0, PHY 10.2). We disabled Atheros's Ambient Noise Immunity feature which has been reported to cause unwanted side effects [START_REF] Tinnirello | On the sideeffects of proprietary solutions for fading and interference mitigation in IEEE 802[END_REF]. Transmission power was fixed and antenna diversity disabled. We took measurements using a number of different APs, see Table I. AP2 operated in 802.11a mode, all other APs in 802.11b/g mode. AP1 and AP4 are located in Hamilton Institute, AP2 in a domestic residence in Dublin, AP3 in the university library at NUI Maynooth. We use multiple AP types, because these are the APs available in the field, but we have also used it to eliminate the possibility that a measurement is due to a peculiarity of a particular AP.

IV. BASELINE MEASUREMENTS

A. OFDM noise floor

We first present measurements with the client laptop on which measurements are being taken located in close proximity to the access point. For AP2 and AP4 the radio environment is clean with, as determined using a spectrum analyser, no other transmitters in the channel. For AP1 and AP3 where measurements are taken in, respectively, an office and a a library environment, other network users are active. Figure 1 plots typical measurements of packet loss rate as the PHY rate/modulation is gradually increased from 1Mbps to 54Mbps. Packet losses are categorised into first packet losses, losses of second fragments in a burst (i.e. with NAV protection) and losses of second packets in a TXOP burst (i.e. without NAV protection). Measurements are shown for four different APs as detailed in Table I. Since the channel is clean for AP2 and AP4 , we expect the loss rates of first and second packets to be similar and indeed this is the case. For AP1 and AP2 the rate of first packet losses is higher than the rate of second packet losses, which is attributed to colliding transmissions from other network users. The rates of the two types of second packet loss are similar, consistent with a low-noise, hidden-node free link.

Since the laptop and AP are co-located, we might expect to see a loss rate for second packets very close to zero for all PHY rates (and similarly low loss rates for first packets, except for AP3 measurements). However, while we measure loss rates close to zero at the 802.11b rates (1, 2, 5.5, 11Mpbs), it can be seen from Figure 1 that there a significant second packet loss rate of 1-5% is consistently observed for the 802.11a/g rates. While the measurements presented in Figure 1 cover a range of different AP hardware and software, the client laptop is common to the measurements and so might be the source of the observed behaviour. However, we have also taken measurements with a number of different client hardware/software configurations and observed a similar lossrate floor and so this seems unlikely. One clue is that we find that this behaviour is only observed with unicast traffic and not broadcast, and so it seems to be associated with lossy reception of MAC ACKs. Recalling that the 802.11a/g rates use OFDM modulation while the 802.11b rates use CCK modulation, with associated differences in transmitter and receiver processing, and we speculate that the observed behaviour may be associated with this difference, e.g. related to calibration of the gain thresholds for triggering decoding that are used in the OFDM but not the CCK receiver.

B. Path attenuation

Figure 2 illustrates the impact of increasing the distance between the client laptop and the AP. It can be seen that the loss rate remains low as the PHY rate is increased until a "cliff" is reached at which point the loss rate rises to a high value. This reflects the quantisation present in the set of PHY rates supported by 802.11g, and the exponential dependence of loss-rate on SNR. Similar behaviour has, of course, been widely observed in other measurement studies and measurements are included here firstly as additional validation of our measurement methodology and secondly to provide a comparison against which to compare the interference-related loss measurements presented in the next section.

C. External interference: microwave oven

Figure 3 illustrates the impact of external (non-802.11) interference generated using a microwave oven. These measurements were taken using AP2 in a clean environment (as confirmed using a spectrum analyser) with the client the loss-rate experienced by first packets is roughly constant with PHY rate, in contrast to the situation with path attenuation induced losses.

Although we lack sufficient details of the interference generated by the specific oven used here to obtain a definitive explanation of these features, we note that the microwave oven radio power (i) has an on-off duty cycle and (ii) during an on cycle the power is expected to be sufficient to corrupt packets at all available transmit rates. First packets in a fragment or TXOP burst are transmitted at random times (due to the stochastic nature of CSMA/CA channel access) and so can be expected to randomly sample the on and off interference cycles, yielding a high loss rate for first packets that is insensitive to PHY rate. However, the transmission of second packets is conditioned on the successful transmission of a first packet, and second packets are transmitted back to back (with a SIFS space) to the first packet. The first packet therefore acts as a "probe" packet for second packets. At higher PHY rates, where packet transmission durations are sufficiently short, success of the first packet indicates an interference off cycle and a subsequent second packet may often be transmitted quickly enough to complete before the next on cycle starts, yielding a lower loss rate for second packets than for first packets. At the lower 1 and 2Mbps PHY rates, we infer that packet transmissions take a sufficiently long time that the transmission of two back to back packets takes longer than the length of an off cycle and so the loss rate of second packets is increased above that for first packets.

D. Discussion

In summary, our baseline measurements indicate at least two qualitatively different patterns of loss rate versus PHY rate. Namely, 1) Loss rate is small for low PHY rates, with a "cliff" or sharp increase in loss rate above a threshold PHY rate. This is expected behaviour in conventional channel models such as AWGN channels. 2) Loss rate is insensitive to PHY rate. This appears to be associated with on-off interference/noise where during an on cycle packets are corrupted regardless of the PHY rate used, while during an off cycle packets are transmitted successfully at all PHY rates. In addition, there is observed to be a loss-floor of around 1-2% when OFDM modulation is used. As we will see later, these qualitative patterns can prove helpful in diagnosing sources of packet loss in field measurements where the environment is less well controlled than in these baseline tests.

Fig. 3 .

 3 Fig. 3. Measured loss rates vs PHY rate with client laptop located 1m from AP5. Interference is generated using a microwave oven.

TABLE I ACCESS

 I POINT DETAILS because an ACK is received. We can now use our estimate of p n (based on fragment loss measurements, see equation (

laptop located ≈1m from the AP. The oven is operating for approximately the middle 120 measurement samples for each PHY rate, and not operating for the first and last 20 samples. The latter samples, without interference, provide a baseline against which to compare the impact of the interference. It is interesting to compare the measurements in Figure 3 to those in Figure 2. One immediate observation is that the loss-rate of second packets in Figure 3 is not monotonic in PHY rate, decreasing significantly at rates above 2Mbps. A second is that V. FIELD MEASUREMENTS: NUIM LIBRARY

In this section we present field measurements taken at the National University of Ireland Maynooth library, corresponding to AP3 in Table I. The client laptop is located outside the library building, approximately 30m from the AP, and we note that this is a production network with other active users. Figure 4(a) shows typical measurements of loss rate vs PHY rate. It can be seen that the measured loss rates exhibit quite complex behaviour that appears to consist of a mix of the behaviours observed in our baseline measurements in the previous section. At PHY rates of 36Mbps and above, the loss rate for both first and second packets increases to be close to one (data points for these extremely high loss rates are not shown in Figure 4(a) due to difficulties associating with the AP) -this "cliff" appears to be associated with path attenuation. At PHY rates below 36Mbps, the loss rate for first packets appears insensitive to the PHY rate and is around 20% -this may indicate on-off interference. The loss rate for second packets is similar to that for first packets for PHY rates of 5.5Mbps and above, but significantly different at PHY rates of 1 and 2Mbps. At these lower rates the loss rate for second packets in TXOP bursts is around 60% while that for second fragments in a burst is less than 5%. This difference in loss rates for the different types of second packets indicates the presence of hidden node interference; we are also able to observe beacons from at least one other AP. To our knowledge, this is the first time that measurements of this type have been presented.

In view of the complex nature of the radio environment, we can expect that PHY rate control algorithms will experience difficulties in selecting a good rate at which to operate. Figure 4(b) plots measurements of completion time vs connection size for uploads to the Hamilton Institute web server from the client laptop via the same AP (we expect similar behaviour in the download direction, but can only directly control the PHY rate on the client laptop since we do not have administrative access to the AP). Measurements are shown using (the default in the Madwifi driver) SampleRate algorithm and for fixed PHY rates of 11Mbps and 18Mbps, and include both the measured completion times for individual connections and the mean completion time over multiple runs. It can be seen that by using either the 11Mbps or 18Mbps rates the mean completion times can be reduced by a factor of 2-3 compared to SampleRate. We expect that the performance of the rate control algorithm might be improved by making use of the additional information provided by our link quality measurement methodology, but leave investigation of this as future work.

VI. FIELD MEASUREMENTS: HAMILTON INSTITUTE

We took a second set of field measurements within the Hamilton Institute, corresponding to AP4. These measurements were taken within an office environment. Figure 5 shows typical measurements of loss rate vs PHY rate. Measurements are shown for AP4 operating on channels 1, 6 and 11. It is known that the building security system generates substantial radio interference in channel 11 and this is reflected in the high loss rates experience by both first and second packets at all PHY rates, see Figure 5(a). A wireless testbed operates on channel 1 in an adjacent room and it can be seen from Figure 5(c) that the resulting colliding transmissions lead to an increased loss rate for first packet transmissions, although both types of second packet experience similar loss rates which indicates that there are no significant hidden node effects.

Figure 6 shows the corresponding RSSI measurements. It can be seen that these provide a poor basis for selecting the best channel on which to operate AP4 -channel 11 has the lowest RSSI yet from Figure 5 we know that this channel experiences a far higher loss rate than channel 6. This discrepancy arises because the RSSI measurements are derived from the signal strength of MAC ACKs received by the client laptop and so are conditioned on successful transmission of a data packet while the sender-side measurements in Figure 5 take account of both failed and successful data packet transmissions. To explore this issue further, we took measurements of completion time vs connection size for uploads to the Hamilton Institute web server from the client laptop. These measurements are shown in Figure 7 for channels 1 and 6 from which it can be seen that use of channel 6 yields approximately a factor of 3 reduction in flow completion time compared to channel 1. Measurements are not shown for channel 11 as the high level of packet loss led to TCP timeouts and grossly long completion times. This suggests that the additional information provided by the measurements in Figure 5 might be used to assist in making better channel allocation choices at APs, or AP association choices at client stations. channel 6 @ 54Mbps mean channel 6 @ 54Mbps channel 1 @ 54Mbps mean channel 1 @ 54Mbps channel 6 @ 54Mbps, CWmin=2 mean channel 6 @ 54Mbps, CWmin=2 Fig. 7. Measured completion times vs connection size and choice of channel.

VII. CONCLUSION

In this paper we have presented field measurements of 802.11 collision, noise and hidden-node loss rates. We see that the measurement technique from [START_REF] Giustiniano | Measuring transmission opportunities in 802.11 links[END_REF] is able to offer insight into the causes of lost packets. While we identify collision, noise and hidden-node related losses, we are able to identify effects that seem to be related to OFDM reception and on-off noise. We show that these measurements could be used to drive rate control or channel selection decisions that offer considerable performance benefits.

We would like to use this technique to estimate how common various impairments are in production 802.11 environments. We would also like to implement this measurement technique on a other 802.11 chipsets to determine if issues such as the OFDM loss-floor are chipset specific.