Estelle Delpech

Patrick Saint-Dizier

A Model for Processing Procedural Texts

This paper presents ongoing work dedicated to parsing the textual structure of procedural texts. We propose here a model for the intructional structure and criteria to identify its main components: titles, instructions, warnings and prerequisites. The main aim of this project, besides a contribution to text processing, is to be able to answer procedural questions (How-to? questions), where the answer is a well-formed portion of a text, not a small set of words as for factoid questions.

1.

Introduction

The main goal of this work is to be able to answer procedural questions, which are questions whose induced response is typically a fragment, more or less large, of a procedure, i.e., a set of coherent instructions designed to reach a goal. Recent informal observations from queries to Web search engines tend to show that procedural questions is the second largest set of queries after factoid questions [START_REF] De Rijke | Question Answering: What's Next?[END_REF]. This is confirmed by another detailed study carried out by [START_REF] Yin | Topic Analysis and Answering Procedural Questions[END_REF]. Procedural question-answering systems are of much interest both to the large-public via the Web, and to more technical staff, for example to query large textual databases dedicated to various types of procedures.

Answering procedural questions thus requires to be able to extract not simply a word in a text fragment, as for factoid questions, but a well-formed text structure which may be quite large. Thus, the techniques used for factoid questions do not seem adequate to deal with the problem at hand. It is clear that a different approach should be adopted. We believe that the use of text grammars is a more appropriate and a more precise manner for representing and recognizing procedural knowledge in a text.

Analysing a procedural text requires a dedicated discourse analysis, e.g. by means of a grammar. Such grammars are not very common yet due to the complex intertwinning of lexical, syntactic, semantic and pragmatic factors they require (see e.g. functional discourse grammars and systemic grammars) to get a correct analysis. Discourse grammars have basically a top-down organization, they take discourse acts as their basic units, instead of just words, they account for the structure and for the interactions between these acts and they require a relatively elaborated conceptual representation as output. Such a grammar must capture the discourse cohesion, possibly the communicative intentions, as well as the discourse organization, e.g. in terms of plans.

Procedural texts explain how to execute procedures. In our perspective, procedural texts range from apparently simple cooking recipes to large maintenance manuals (whose paper versions are measured in tons e.g. for aircraft maintenance). They also include documents as diverse as teaching texts, medical notices, social behavior recommendations, directions for use, assembly notices, do-it-yourself notices, itinerary guides, advice texts, savoir-faire guides etc. Even if procedural texts adhere more or less to a number of structural criteria, which may depend on the author's writing abilities and on traditions associated with a given domain, we observed a very large variety of realisations, which makes parsing such texts quite challenging.

Procedural texts explain how to realize a certain goal by means of actions which are at least partially temporally organized. Procedural texts can indeed be a simple, ordered list of instructions to reach a goal, but they can also be less linear, outlining different ways to realize something, with arguments, advices, conditions, hypothesis, preferences. They also often contain a number of recommendations, warnings, and comments of various sorts. The organization of a procedural text is in general made visible by means of linguistic and typographic marks. Another feature is that procedural texts tend to minimize the distance between language and action. Plans to realize a goal are made as immediate and explicit as necessary, the objective being to reduce the inferences that the user will have to make before acting. Texts are thus oriented towards action, they therefore combine instructions with icons, images, graphics, summaries, preventions, advices, etc.

Research on procedural texts was initiated by works in psychology, cognitive ergonomics, and didactics. Several facets, such as temporal and argumentative structures have then been subject to general purpose investigations in linguistics, but they need to be customized to this type of text. There is however very little work done in Computational 1 hal-00502424, version 1 -14 Jul 2010 Author manuscript, published in "Language and technology Conference Poland ( 2007)" Linguistics circles. The present work is based on a preliminary experiment we carried out (Delpech et ali. 07), where a preliminary structure was proposed.

From a methodological point of view, our approach is based on (1) a conceptual and linguistic analysis of the notion of procedure and (2) a mainly manual corpus-based analysis, whose aim is to validate and enrich the former.

The structure of procedural texts

The answer to a procedural question is a well-formed fragment of a text, it includes in general a sequence of instructions linked by various markers (e.g. coordinators, temporal marks) or typographical marks (e.g. comma, dot, newline). In this section we develop an analysis of the segment title-sequence of instructions. This analysis is quite formal, but it is a necessary step before any form of processing.

In our approach, the instructional structure of procedural texts is composed of the following items:

• titles, hierarchically organized, which express a goal to reach, realized by the instructions that follow,

• instructions, associated with titles. However, instructions are not just lists of actions to perform. They often form a complex structure, presented hereafter, where there are main and subordinate instructions, comments, etc. We will therefore be here essentially concerned with an extended view of the structure of instructions, that we call instructional compounds,

• lists of prerequisites and warnings, besides those included into instructional compounds.

Let us essentially, in this contribution, focus on the instructional compound structure, which is, by far, the most complex element. It has a relatively well organized discourse structure, composed of several layers, which are:

• The justification and explanation structure, which has wider scope over the remainder of the compound, indicates motivations for doing actions that follow in the compound (e.g. in your bedroom, you must clean regularly the curtains..., which here motivates actions to undertake).

• The instruction kernel structure, which contains the main instructions. These can be organized temporally or just be sets of actions (as, for example, in social behavior texts, where instructions are rather unordered lists of advices). Actions are identified most frequently via the presence of action verbs (in relation to the domain) in the imperative form, or in the infinitive form introduced by a modal. Instructions may be subject to various conditions, and deontic and illocutionary parameters. We observed also a number of forms of subordinated instructions associated with the main instructions. These are in general organized within the compound by means of rhetorical relations, that we introduce below.

• The deontic and illocutionary force structures: consist of marks that operate over instructions, outling different parameters:

-deontic: obligatory, optional, forbidden or impossible, alternates (or),

-illocutionary and related aspects: stresses on actions: necessary, advised, recommended, to be avoided, etc.

• The conditional structure: introduces conditions over instructions in the compound or even over the whole instructional compound.

• The rhetorical structure whose goal is to enrich the kernel structure by means of a number of subordinated aspects (realized as propositions, possibly instructions) among which, most notably: causality, enablement, motivation, argument for, circumstance, elaboration, instrument, precaution, manner.

The rhetorical structure is in general composed of instructions (satellites) related to the instructions in the kernel.

An instructional compound must contain at least one action verb in the imperative or a modal followed infinitive verb (in French). A few, less frequent forms have also been observed like the use of the impersonal pronoun 'on'. Several such verbs in a given sentence (e.g. coordinated) form a kernel composed of several actions which are closely related. Instructional compounds are separated by means of two main devices:

• punctuation (mainly end of sentence marks) or typodispositional marks (in .html, for example): new paragraphs, different elements in an enumeration. These are the most frequent separators.

• linguistic marks that indicate a strong break. Among these we have temporal marks that introduce a new temporal phase (glosses from French): next, after 2 hours; aspectual verbs: begin by, resume, etc.; fixed forms: this being done, you can now proceed, etc. strong breaks may also be conditional marks.

It is not necessarily easy, on the basis of linguistic marks, to make a distinction between marks that introduce a clear separation between instructional compounds from those which structure internally an instructional compound. These latter marks are weak separators or they convey an idea of continuity between instructions. Weak marks are, for example: then, finally, now, when, etc. Our strategy is to isolate two compounds when the separation mark is sufficiently strong. The general strategy to identify instructional compounds is as follows. Any new paragraph starts an instructional compound if it contains at least one action verb in one of the forms given above (imperative or modal + infinitive). If so, the paragraph is traversed till a relevant punctuation of strong break mark is found. When this is so, the instructional compound ends and a new one is hypothetized. Sentences in a paragraph with no action verb are bound to the previous compound.

Let us now give two illustrative examples (translated from French). Here is a text extracted from the 'Home' domain: In the bedroom, it is necessary to clean curtains.

These are cleaned first with a vacuum-cleaner to remove dust, then, if they are in cotton, they can be washed in the washing machine at 60 degrees; if they are white, it is even recommended to add some bleech so that they look whiter. With some starch, they can be easily ironed.

The sequence: In the bedroom, it is necessary to clean curtains is analyzed as a justification of the actions to undertake. The next portion: These are cleaned first with a vacuum-cleaner to remove dust, then, if they are in cotton, they can be washed in the washing machine at 60 degrees. If they are white, it is even recommended to add some bleech so that they look whiter is the instruction kernel, where the last two instructions are associated with conditions. Finally, With some starch, they can be easily ironed. is an advice.

The second example introduces a subordinate instruction: A window appears to allow you to define the properties of the server, a password is the asked, choose it with at least 6 digits. It is better to define it now since it will be asked to the user. The first proposition describes a circumstance, it is followed by the kernel: a password is asked, note that this is a kind of indirect action (please provide a password), and then followed by a subordinate action of type 'precaution': choose it with at least 6 digits. The text ends by a motivation or justification.

Segmentation of instructions and titles

The segmentor has several goals:

• First, to tag terminal discourse elements: instructions, titles (viewed as the expression of goals), warnings stated outside instructions, prerequisites, and connectors.

• Via the tagging, to allow for the identification in a large text of zones which are more procedural than others (large texts may be verbose and contain non procedural elements such as comments or historical considerations), allowing then to focus the search of responses on a certain text area.

It is clear that the form of the linguistic objects and the criteria required to recognize instructions, compounds and subordinated instructions largely varies over application domains, textual genres and the targeted audiences. Our strategy was to define several sets of criteria, valid for a group of domains that share common discourse forms for describing procedures. Our approach was to proceed by 'domain aggregation'. For example, we first considered samples from coocking recipes texts, and defined the segmentation criteria. Then, we considered other domains which turn out to have a close structure: 'do it yourself' and video game solutions. At a certain stage, we get a stable set of criteria which can be implemented as an automaton. We plan to have in the end a small number of automata, each encoding the discourse structure of a group of domains.

Finally, each type of object we have to segment requires a different approach to segmentation, because the identification criteria are very different. We briefly present them below.

Dealing with Instructions

As far as instructions are concerned, the model is a relatively straightforward finite state automaton based on the recognition of verbs, together with their morphology (basically infinitive + modal or imperative forms are quite frequent incoocking recipes, but inflected tenses are found in other domains), and their semantic class (action verbs and subclasses) since semantic class may be used to identify different types of instructions; deverbals and predicative nouns are also relevant. Various classes of marks may also be of interest, for example to identify modalities, deontic situations or illocutionary force. Most frequent marks are: modal marks ('you must do'), reminders ('do not forget to'), performance marks ('care about doing'), marks describing optionality or advices ('it is preferable to'), injunctive forms, and adverbs of manner.

Recognizing Titles

Recognizing titles is much more challenging. They have in general the form of an instruction (e.g. mounting your computer), but with a different layout. Recognizing titles is crucial for answering questions.

Titles are first identified by the typography: bold font, possibly underlined, or via the use of dedicated html marks (h1, etc.). When this is not possible, elements such as the number of words and the proximity to an instructional zone of a certain density are good heuristics. In general, titles are much shorter than instructions. Finally, we can also rely on the level of generality of the verbs used in titles, which are more generic than those found in instructions (we use the Volem verb base for that purpose). In fact, titles can be viewed as 'super-instructions', this distinction being however highly domain dependent.

Prerequisites as well as warnings may also have titles. However, these two latter objects have a different typology (although they may also contain instructions), which allows us to make the distinction among types of titles, and to isolate those effectively governing instructions, to be interpreted as denoting goals.

A second problem is to identify the hierarchy of titles, which occurs in most texts of a certain length. Identifying such a hierarchy allows us to associate more precisely sequences of instructions to a goal. Since dedicated html tags are not so frequent to discriminate titles, we must rely on other factors, which are very delicate to handle, among which:

• presence of capital letters, or size in number of words (quite frequently 4 to 5 words, with no pronominal references),

• level of the verbs in titles: higher titles contain more generic verbs,

• identification of islands of instructions which share a quite large number of common words (entailing a certain thematic cohesion of instructions below a title, as in Centering Theory).

• identification of summaries or introductions below titles which contain words present in subtitles.

However, these criteria largely vary from one domain and author to another, and results are somewhat inconsistent. So far, we can identify 2 levels, and it may be sufficient to answer procedural questions from texts which are not too large. Gping beyond requires a much deeper analysis, and it is not clear a whether general solution can emerge.

Another kind of difficulty is that titles are often elliptic (e.g. the verb is missing). In some situation they may be just absent, therefore, we may need, to answer questions, to be able to reconstruct these, via some form of inference on the set of instructions it heads.

Dealing with Warnings

Warnings as well as arguments are introduced by a range of specific verbs often in the imperative form or by negative connectors, which is quite easy to identify in French. Warnings can appear at almost any position in the text. Here are a few examples:

• negative connectors: sous peine de, sinon, car sinon, sans quoi, etc. (otherwise, under the risk of),

• risk verbs: risquer, causer, nuire, commettre, etc.

• prevention verbs: éviter, prévenir, etc.

• negative expressions: de facon à ne pas, pour ne pas, pour que ... ne ...pas, etc. (in order not to).

Indentifying Discursive marks

Temporal marks are the most frequent marks, they include: precedence, overlap, inclusion, parallelism, etc. They are mainly realized by means of adverbs, prepositions, conjunctions, aspectual verbs and propositions describing the realization of an event. Marks are annotated by the TreeTagger and typed via a predefined list we have elaborated.

Causal marks are particularly rich and diverse. They are used to relate a goal to a set of instructions, or to specify within an instruction its aim; causal marks are also used to identify objectives, warnings and various forms of preventions, consequences and some forms of conclusions.

Besides these two main classes of marks, we noted a few conditionals and alternative marks. These are often prepositions or semantically closely related to the semantic typology specific of prepositions. To identify and interpret them, we use the PrepNet framework (www.irit.fr/recherches/ILPL/prepnet.html).

Global Architecture

The automaton first recognises instructions, then titles, warnings and prerequisites. Segmentation is confronted to several difficulties, among which:

The result of the segmentor is a representation based on XML tags of the following form (simplified for readability): This representation is still quite simple and straightforward. It needs further elaborations, e.g. to deal with scoping problems which are not fully resolved. We also view this representation as a kind of dependency structure between the different constituents of the text.

At the moment, we are still updating the implementation (carried out in Perl and in Prolog) with the goal of refining the linguistic criteria necessary to accurately recognize instructional compounds, titles, warnings and prerequisites. The results we get are rather good, but they are very difficult to evaluate precisely: readers may indeed differ on their segmentation judgements for instructional compounds. Evaluating the recognition of titles is however much easier.

Perspectives

This short paper relates ongoing work on parsing procedural texts on various domains, with the aim of responding to procedural questions in natural language. The implementation proposed so far are preliminary and allow us to explore the various types of problems one may encounter when dealing with text grammars. The corpus considered is of a rather modest size, but with quite diverse structures. It is a development corpus, allowing us to better analyse the behavior of the different components we have developed. Outputs are checked manually at this stage: this is a quite challenging task, since most texts include more than one hundred tags, and since the boundaries of instructional compounds may be debatable. The investigations on marks is still a largely open problem since some marks may be quite pragmatic.

The global structure of a procedural text (composed of at least a main title, subtitles, prerequisites, warnings, instructional compounds) is represented by means of discourse dependency relations. In (Delpech et ali. 07), we propose a syntactic model based on elements of generative syntax for the structure of procedural texts which is fine but somewhat rigid. An approach based on dependencies, while keeping the same principles and categories allows us to have a more flexible representations, allowing some forms of gaps in the links. Similarly, we need to introduce some forms of underspecifications, in particular in relation with the difficulty of organizing titles and subtitles, in order to allow flexible forms to express scope (e.g. of a title over instructional compounds, of a condition over instructions). By default, warnings and prerequisites have scope over the text that follow them.

We thank the French ANR-RNTL program through the TextCoop project for supporting this research. We are grateful in particular to Claude de Loupy, Francoise Gayral, Thierry Poibeau, Frederik Cailliau and Eli Murguia for their discussions and support.


Jaroslav Krystul
email: krystulj@ewi.utwente.nl

François Le Gland
email: legland@irisa.fr

Pascal Lezaud
email: lezaud@recherche.enac.fr

Keywords: Modèles et méthodes stochastiques rare event simulation, switching diffusion, multilevel splitting, stratification, central limit theorem (CLT) simulation d'évènement rare, diffusion à paramètre markovien, branchement multi-niveaux, stratification, théorème central limite (TCL)

: instead of starting the algorithm with N particles randomly distributed, we draw in each mode j, a fixed number N j of particles and at each resampling step, the same number of particles is sampled for each visited mode. In this paper, we establish a law of large numbers theorem as well as a central limit theorem (CLT) for the estimate of the rare event probability.

Introduction

Rare event simulation requires acceleration techniques to speed up the occurrence of the rare events under consideration, otherwise it may take unacceptably large sample sizes to get enough positive realizations, or even a single one, on average. A well known technique is importance sampling, whose idea is to change the probability laws driving the model in order to make the events of interest more likely, and to correct the bias by multiplying the estimator by the suitable likelihood ratio [START_REF] Pierre | Importance sampling[END_REF]. An alternative technique called multilevel splitting does not need to modify the probability laws that drive the system; this means that the computer program that implements the simulation model can just be a black box [START_REF] Pierre | Splitting techniques[END_REF]. The idea of the splitting is to express the small probability of rare event to be estimated as the product of a certain number of larger probabilities, which can be efficiently estimated by the Monte Carlo methods. This can be achieved by introducing sets of intermediate states that are visited by stochastic process one after the other, in an ordered sequence, before reaching the final set of rare event states. The probability of rare event is then given by the product of the conditional probabilities of reaching a set of intermediate states given that the previous set of intermediate states have been reached. Each conditional probability is estimated by simulating in parallel several copies of the system, i.e. each copy is considered as a particle following the trajectory generated through the system dynamics. Each particle branches (i.e. the trajectory splits into a number of independent subpaths, which subsequently evolve independently of each other) as soon as it enters the intermediate states, which is usually characterized by the crossing of a threshold defined by an importance function. Reaching intermediate states is more likely than reaching the rare event states, and by splitting at each threshold the chances to reach the rare event states are increasing. Several strategies have been designed to determine the importance function, to decide the number of splits at each level, and to handle the trajectories that tend to go in the wrong direction (away from the rare event of interest). The most difficulty is to find an appropriate importance function, a poor choice can easily lead to bad results [START_REF] Marnix | The Splitting Method in Rare Event Simulation[END_REF][START_REF] Glasserman | Multilevel splitting for estimating rare event probabilities[END_REF][START_REF] Lagnoux | Rare event simulation[END_REF]. One of the best-know versions of splitting is the RESTART method [START_REF] Villén | RESTART : A straightforward method for fast simulation of rare events[END_REF][START_REF] Villén | Analysis of RESTART simulation : Theoretical basis and sensitivity study[END_REF][START_REF] Villén | On the efficiency of RESTART for multidimensional state systems[END_REF].

The multilevel splitting technique can also be considered as an interacting particle interpretation (IPS) of the Feynman-Kac models, a general framework presented in [START_REF] Del | Genealogical and Interacting Particle Systems with Applications. Probability and its Applications[END_REF]. This abstract Feynman-Kac formulation gives a powerful tool which in particular allows to establish a Strong law of large numbers and a central limit theorem for the estimate of the rare event probability [START_REF] Del | Genealogical and Interacting Particle Systems with Applications. Probability and its Applications[END_REF][START_REF] Del | Branching and interacting particle interpretation of rare event probabilities[END_REF][START_REF] Cérou | Genetic genealogical models in rare event analysis[END_REF].

Owing to the increasing demands for modelling large-scale and complex systems, switching diffusions (a subclass of hybrid processes) are lately receiving growing attention [START_REF] Blom | Stochastic hybrid processes with hybrid jumps[END_REF][START_REF] Krystul | Modelling of Stochastic Hybrid Systems with Applications to Accident Risk Assessment[END_REF][START_REF] Zhu | Asymptotic properties of hybrid diffusion systems[END_REF][START_REF] Blom | Rare event estimation for a large-scale stochastic hybrid system with air traffic application[END_REF]. A distinctive feature of these systems is the coexistence of continuous dynamics and discrete events; they also satisfy the strong Markov property. While in theory the IPS approach is virtually applicable to any strong Markov process, in practice the straightforward application of this approach to switching diffusions fails to produce reasonable estimates within a reasonable amount of simulation time. The reason is that there may be few if no particles in modes with small probabilities (i.e. "light" modes). This happens because each resampling step tends to sample more "heavy" particles from modes with higher probabilities, thus, "light" particles in the "light" modes tend to be discarded. By increasing the number of particles the IPS estimates should improve but only at the cost of substantially increased simulation time which makes the performance of IPS approach in switching diffusions similar to one of the standard Monte Carlo. To avoid this, a conditional "sampling per mode" algorithm has been proposed in [START_REF] Krystul | Modelling of Stochastic Hybrid Systems with Applications to Accident Risk Assessment[END_REF]; instead of starting the algorithm with N particles randomly distributed, we draw in each mode j, a fixed number N j particles and at each resampling step, the same number of particles is sampled for each visited mode. Using the techniques introduced in [START_REF] Del | Genealogical and Interacting Particle Systems with Applications. Probability and its Applications[END_REF][START_REF] François | A sequential algorithm that keeps the particle system alive[END_REF], we recently established a law of large numbers theorem as well as a central limit theorem for the estimate of the rare event probability as the number of particles increase to infinity.

The rest of the paper is arranged as follows. In Section 2, we introduce the abstract of Feynman-Kac and particle theory in the context of multilevel splitting and we adapt this framework to take into account the discrete modes of the switching diffusion. In particular, we detail the conditional "sampling per mode" algorithm. The Section 3 is devoted to the asymptotic behaviour of algorithm as the number of particles tends to infinity. Using an approach based on a martingale decomposition, as presented in [START_REF] Del | Genealogical and Interacting Particle Systems with Applications. Probability and its Applications[END_REF], we establish a law of large numbers and a central limit theorem for the particle approximation of the rare event probability. Finally, Section 4 summarizes the paper and outlines a number of directions for future research.

Multilevel Feynman-Kac distributions

Formulation

We consider a switching diffusion Z = {(X t , θ t ); t ≥ 0} taking values in R d × M for some d > 0 and M = {1, • • • , M }. More precisely, Z t is a two-component Markov process such that (X t ) is a continuous component taking values in R d and (θ t ) is a jump process taking values in the finite set M; it can be described by

dX t = b (X t , θ t ) dt + σ (X t , θ t ) dB t , and
P (θ t+∆t = j|θ t = i, X t = x) = λ ij (x)∆t + o(∆t), i = j.
where

B t is a d-dimensional standard Brownian motion, b(•, •) : R n × M → R n and σ(•, •) : R n × M → R n×d .
Throughout the paper, we assume that Z is a strong Markov process and we denote by η 0 the law of Z 0 . Let D ⊂ R d be some closed critical region, in which the continuous component of Z could enters but with a very small probability. Let us introduce an embedded sequence of closed regions

[0, ∞) × D = D n ⊂ • • • ⊂ D 1 ⊂ D 0 ⊂ [0, ∞) × R d ,
which are usually defined by

D k = {(t, x) ∈ [0, ∞) × R d : h(t, x) ≤ c k },
where h is some lower semi-continuous function, called the importance function, and the cylinders

B = D × M and A k = D k × M.
Set the corresponding hitting times

T k = inf{t ≥ 0 : (t, Z t ) ∈ A k } = inf{t ≥ 0 : (t, X t ) ∈ D k }, which satisfy 0 = T 0 ≤ T 1 ≤ • • • ≤ T n = T B .
To capture the precise behaviour of the process Z in each region, we consider the random excursions Z k of Z between the successive random times T k-1 and T k . More precisely, we introduce the discrete-time Markov chain Z = {Z k , k = 1, • • • , n} with value in the excursion set E, defined by

Z k = ((t, X t , θ t ), T k-1 ∧ T ≤ t ≤ T k ∧ T ) ,
with t ∧ T = inf{T, t} and T a deterministic or stopping time. We observe that these excursions can be decomposed in a string of diffusions, one by discrete mode; each of them having a random length. The nonhomogeneous Markov kernels M k , which describe the Markovian transitions of the Markov chain Z, are defined for all excursion e and all functions f on E by

M k f (e) = E [f (Z k )|Z k-1 = e] .
To check whether or not a given path e = ((t, Z t ), t 1 ≤ t ≤ t 2 ) , starting at (t 1 , Z t1 ) ∈ A k-1 at time t 1 , has succeeded to reach the level A k at time t 2 , it is convenient to introduce the terminal point π(e) = (t 2 , Z t2 ) of the excursion and the indicator functions g k defined by

g k (e) = 1 {π(e) ∈ A k } ,
and to capture the discrete component, we introduce the potential functions

g j k (e) = 1 {π(e) ∈ D k × {j}} , j ∈ M,
giving the following decomposition g k (e) = j∈M g j k (e).

(2.1)

With these notations, and for each k, we have T k ≤ T if and only if g k (Z k ) = 1, and we have

T k ≤ T with θ T k = j if and only if g j k (Z k ) = 1, hence 1 {T k ≤ T } = g k (Z k ), and 1 {T k ≤ T, θ T k = j} = g j k (Z k ).

RR n°7499

Now define for k = 1, • • • , n the so-called unnormalized Feynman-Kac measures, γ k and γ k on the path space E in such a way that the integral of all bounded measurable functions f relatively to these measures are given by

γ k (f ) = E [f (Z k )g k-1 (Z k-1 )] = E f ((t, X t , θ t ), T k-1 ≤ t ≤ T k ∧ T )1 {T k-1 ≤ T } , γ k (f ) = E [f (Z k )g k (Z k )] = E f ((t, X t , θ t ), T k-1 ≤ t ≤ T k )1 {T k ≤ T } .
In particular, when f is the constant function 1, we obtain

γ k (1) = P[T k-1 ≤ T ] ,
and

γ k (1) = P[T k ≤ T ].
The Feynman-Kac distributions η k and η k are derived by normalizing these measures,

η k (f ) = γ k (f ) γ k (1) = E [f ((t, X t , θ t ), T k-1 ≤ t ≤ T k ∧ T )|T k-1 ≤ T ] , η k (f ) = γ k (f ) γ k (1) = E [f ((t, X t , θ t ), T k-1 ≤ t ≤ T k )|T k ≤ T ] ,
and using the convention T -1 = 0 leads to the observation that γ 0 = η 0 . We observe that

1 {T k ≤ T } = 1 {T k-1 ≤ T, T k ≤ T } , or equivalently g k (Z k ) = g k-1 (Z k-1 )g k (Z k ), hence γ k (f g k ) = γ k (f ) , and η k (f ) = γ k (f g k ) γ k (g k ) = η k (f g k ) η k (g k ) , (2.2)
and more interestingly, how the probabilities of transition from one region to the following are related to the Feynman-Kac distributions,

η k (g k ) = P[T k ≤ T |T k-1 ≤ T ] := P k , η k (g j k ) = P[T k ≤ T, θ T k = j|T k-1 ≤ T ] := P j k .
From now on, we assume that not only P k = 0 for all k, but also that P j k are non zero all modes j ∈ M. Furthermore, the "unnormalized models" (γ k , γ k ) are related to the Feynman-Kac distribution flow (η p ) p≤k , by the following key formula

γ k (f ) = η k (f ) k-1 p=0 η p (g p ) and γ k (f ) = η k (f ) k p=0 η p (g p ).
(2.3)

In order to keep trace of the discrete mode, we construct for any j ∈ M the unnormalized Feynman-Kac measures γ j k and γ j k defined by

γ j k (f ) = E f (Z k )g j k-1 (Z k-1 ) = E f ((t, X t , θ t ), T k-1 ≤ t ≤ T k ∧ T )1 {T k-1 ≤ T, θ T k-1 = j} , γ j k (f ) = E f (Z k )g j k (Z k ) = E f ((t, X t , θ t ), T k-1 ≤ t ≤ T k )1 {T k ≤ T, θ T k = j} .
The Feynman-Kac distributions η j k and η j k are derived by normalizing these measures, respectively

η j k (f ) = γ j k (f ) γ j k (1) = E f ((t, X t , θ t ), T k-1 ≤ t ≤ T k ∧ T )|T k-1 ≤ T, θ T k-1 = j , η j k (f ) = γ j k (f ) γ j k (1) = E [f ((t, X t , θ t ), T k-1 ≤ t ≤ T k )|T k ≤ T, θ T k = j] .
We observe that

1 {T k ≤ T, θ T k = j} = 1 {T k-1 ≤ T, T k ≤ T, θ T k = j} , or equivalently g j k (Z k ) = g k-1 (Z k-1 )g j k (Z k ), hence γ k (f g j k ) = γ j k (f ) , and η j k (f ) = γ k (f g j k ) γ k (g j k ) = η k (f g j k ) η k (g j k )
.

(2.4)

Clearly, we have the decompositions

η k = j∈M ω j k η j k , η k+1 = j∈M ω j k η j k+1 . (2.5)
where

ω j k = η k (g j k ) = η k (g j k ) η k (g k ) = γ j k (1) γ k (1) = P(θ T k = j|T k ≤ T ). (2.6)

Feynman-Kac semigroups

Previously, we have introduced the Feynman-Kac distributions η k . Now, we will investigate the time evolution of the Feynman-Kac flow (η k ; 0 ≤ k ≤ n). In fact, from the Markov property of the process Z, we see that

γ k (f ) = E [g k-1 (Z k-1 )E [f (Z k )|Z k-1 ]] = γ k-1 (g k-1 M k f ) = γ k-1 (M k f ) , (2.7)
and in the context of switching jump diffusions, for any j ∈ M

γ j k (f ) = E g j k-1 (Z k-1 )E [f (Z k )|Z k-1 ] = γ k-1 g j k-1 M k f = γ j k-1 (M k f ) . (2.8)
These formulas suggest the introduction of the linear operators Q k and Q j k defined respectively by

Q k f = g k-1 M k f and Q j k f = g j k-1 M k f. (2.9)
An immediate consequence of (2.7) and (2.8) is that γ k and γ j k satisfy linear equations of the form

γ k = γ k-1 Q k and γ j k = γ k-1 Q j k .
(2.10)

Nevertheless, we seek the evolution of the normalized Feynman-Kac measures η k and η j k , that we suscept to be nonlinear. To establish it, we introduce the mappings Φ k from the set of measures P k (E) = {η : η(g k ) > 0} into the set P(E) of measure on E defined by

Φ k (η)(f ) = Ψ k-1 (η) (M k f ) , with Ψ k (η)(f ) = η(f g k ) η(g k ) .
It can now be easily verified that the Feynman-Kac flow is the solution of a nonlinear measure-valued dynamical system

η k = Φ k (η k-1 ), (2.11)
Since Ψ k (η k ) = η k , we see that the recursion (2.11) involves two separate selection/mutation transitions

η k ∈ P k (E) selection -----→ η k := Ψ k (η k ) ∈ P(E) mutation ------→ η k+1 = η k M k+1 ∈ P(E).
(2.12)

In the specific case of switching jump diffusions, we introduce for any j ∈ M the following transformations

Φ j k (η)(f ) := Ψ j k-1 (η) (M k f ) with Ψ j k (η)(f ) := η g j k f η g j k ,
and from (2.4), we check that

η j k = Ψ j k (η k ), and η j k+1 = Φ j k+1 (η k ) = η j k M k+1 . (2.13)
Furthermore, the operator Φ k can be written as the weighted sum

Φ k (η) = j∈M η(g j k-1 ) η(g k-1 ) Φ j k (η), (2.14)
and from (2.6), we deduce the particular case

Φ k (η k-1 ) = j∈M ω j k-1 Φ j k (η k-1 ).
We have seen how the measure η n is related to the previous measure η n-1 , but we will need to express η n in terms of η p for all 0 ≤ p ≤ n. Nevertheless, the evolution being nonlinear it is easier to start by considering the evolution of γ n and γ j n , since a straightforward iteration of (2.10) leads us to introduce for any j ∈ M, the linear semigroups Q p,n and Q j p,n , defined respectively by

Q p,n = Q p+1 Q p+2 • • • Q n , Q j p,n = Q p+1 Q p+2 • • • Q n-1 Q j n = Q p,n-1 Q j n , (2.15)
with the convention Q n,n = Id. We remark firstly that

Q p,n 1 = Q p,n-1 g n-1 , Q j p,n 1 = Q p,n-1 g j n-1 .
Secondly, we get

η n (f ) = γ p (Q p,n f ) γ p (Q p,n 1) = η p (Q p,n f ) η p (Q p,n 1) , (2.16)
and, for any j ∈ M

γ j n (f ) = γ p Q j p,n f , η j n (f ) = η p Q j p,n f η p Q j p,n 1
.

(2.17)

Note that an immediate consequence of (2.16) and (2.17) is that

η p (Q p,n 1) = γ n (1) γ p (1) = n-1 q=p
η q (g q ), and η p Q j p,n 1 =

γ j n (1) γ p (1) . ( 2

.18)

We obtain also

ω j n-1 = η p Q j p,n 1 η p (Q p,n 1)
.

(2.19)

Interacting particle system approximations

Introduction

From a pure mathematical point of view, particles methods can be interpreted as a kind of stochastic linearization technique for solving nonlinear equations in measure space. The idea is to associate to the nonlinear dynamical structure (2.11) a sequence ξ = (ξ 1 , • • • , ξ N ), of N excursion-valued particles, such that the empirical measure of the configurations converge as N → ∞ to the desired distribution η.

More precisely, at time k, we consider the particles

ξ i k = (t, X i t , θ i t ), ; T i k-1 ≤ t ≤ T i k ∧ T ∈ E ∪ {∆}, ξ i k = (t, X i t , θ i t ), ; T i k-1 ≤ t ≤ T i k ∈ E ∪ {∆},
where ∆ stands for a cemetery point that we introduce here to take into account the possible stopping of the algorithm. The random lengths of the corresponding excursions ξ i k and

ξ i k are T i k ∧ T -T i k-1 and T i k -T i k-1
respectively. The interacting particle system (IPS) approach consists in approximating the two step transitions (2.12) of the system (2.11) by the two step transitions

η N k := 1 N N i=1 δ ξ i k selection -----→ η N k := 1 N N i=1 δ ξ i k mutation ------→ η k+1 = 1 N N i=1 δ ξ i k+1 .
(2.20) So, starting from an approximation η N 0 to η 0 , during the mutation transition ξ k → ξ k+1 , each selected particle ξ κ k evolves randomly according to the Markov transition M k+1 , independently of each other. The selection transition ξ k+1 → ξ k+1 is defined as follows: only some of the particles ξ k+1 have succeeded in reaching the desired set A k+1 ; unless the amount of these is equal to zero (in this case, the algorithm is stopped), we sample, randomly and independently, the N particles ξ k+1 distributed according to the distribution Ψ k+1 (η N k+1 ). The IPS is nothing else that a sequence of nonhomogeneous Markov chains on the product space E N with transition kernels given by

P( ξ k ∈ dx|ξ k ) = N i=1 Ψ k (η N k )(dx i ), P(ξ k ∈ dz| ξ k-1 ) = N i=1 M k ( ξ i k-1 , dz i ).
Nevertheless, the classical IPS algorithm is not really suitable for switching jump diffusion, mainly because of the potential existence of discrete modes with very small initial probability. To avoid the particles never been drawn in these "light" modes, a conditional "sampling per mode" algorithm has been proposed in [START_REF] Krystul | Modelling of Stochastic Hybrid Systems with Applications to Accident Risk Assessment[END_REF]; instead of starting the algorithm with N 0 particles randomly distributed in A 0 \ A 1 according to η 0 , we draw in each mode j, a fixed number N j particles in (D 0 \ D 1 ) × {j}, randomly distributed according to the conditional law η j 0 . Resampling per mode allows us to avoid loss of "light" particles in "light modes", and so helps to maintain fixed number of particles in each mode. We will see hereafter, that the empirical measure η N k is a weighted sum of the conditional empirical measure η j,N k (see (2.5))

η N k = j ω j,N k-1 η j,N k = κ β κ k δ ξ κ k , with η j,N k = 1 N j κ δ ξ κ k ,
where the three sums are taken over, respectively, all discrete modes containing at least one particle, all particles and finally all particles in the discrete mode j. Nevertheless, the total number of particles can decrease, typically if one or several modes become empty at some time, and it can also increase, typically if one or several of these empty modes become non empty at a later time. That means we have to introduce the total number N k of particles, at each step k.

Detailed description

Prior to the detailed description of the IPS, it is convenient to introduce some notations. Let J k be the set of non empty discrete modes after the end of the step k, with the convention J 0 = M, and for each j ∈ J k , let

J j k = {κ : π(ξ κ k ) ∈ D k × {j}}, J j k = {κ : π( ξ κ k ) ∈ D k × {j}}, I N k = j∈J k J j k ,
be respectively the set of (labels of) particles ξ κ k which have reached before the final time T the set A k = D k ×M in the discrete mode j, the set of (labels of) selected particles ξ κ k whose terminal point is in the discrete mode j, and the set of (labels of) all the selected particles ξ κ k . As the total number of particles can decrease as soon as none of the particles have succeeded to reach the desired level in some mode, we need to introduce the following sequence of integers

N k = | I N k | = j∈J k N j = j∈M N j k ,
where N j k = N j if j ∈ J k and N j k = 0 otherwise. Thus, our model is not restricted to a fixed population size but it takes values in the state space

E = p∈N ({p} × [0, ∞) p × E p )
with the convention E 0 = {∆}; the parameter p represents the size of the system. It is advisable to observe that we can have N j k+1 = N j while N j k = 0, then the size of the population can increase or decrease by jumps. We associate with the time evolution of this model

(N k , β k , ξ k ) selection -----→ ( N k , β k , ξ k ) mutation ------→ (N k+1 , β k+1 , ξ k+1 ) (2.21) the canonical filtrations F k ⊂ F k ⊂ F k+1 .
Then the IPS algorithm is conducted inductively as follows:

Initialization: For each j ∈ J 0 , we sample N j particles ξ κ 0 = ξ κ 0 = (0, (X κ 0 , j)) ∼ η j 0 . Let ω j 0 = P(θ 0 = j), then the empirical measures of particles η N 0 and η N 0 are given by

η N 0 = j∈M ω j 0 η j,N 0 = N0 κ=1 β κ 0 δ ξ κ 0 , with η j,N 0 = 1 N j κ∈J j 0 δ ξ κ 0 , η N 0 = j∈M ω j 0 η j,N 0 = N0 κ=1 β κ 0 δ ξ κ 0 , with η j,N 0 = 1 N j κ∈ J j 0 δ ξ κ 0 ,
where β κ 0 = β κ 0 = ω j 0 /N j , for each κ ∈ J j 0 = J j 0 . At each step k, the empirical measure η N k will be given by

η N k = κ∈ I N k β κ k δ ξ κ k = j∈J k ω j,N k η j,N k , with η j,N k = 1 N j κ∈ J j k δ ξ κ k ,
and the weights ω j,N k are nonnegative and such that j=J k ω j,N k = 1. Clearly, β κ k = ω j,N k /N j for each κ ∈ J j k . We notice that the particles in the same discrete mode have the same weight, or in other words, the weight of a particle depends only on the mode, i.e. on its discrete component.

The mutation transition ξ k → ξ k+1 at time k + 1 is defined as follows. If N k = 0, the particle system dies and we set N k+1 = 0. Otherwise during mutation, independently of each other, each selected particle ξ κ k evolves randomly according to the Markov transition M k+1 ; in other words,

ξ κ k+1 = (t, X κ t , θ κ t ), T κ k ≤ t ≤ T κ k+1 ∧ T ,
is a random variable with distribution M k+1 ( ξ κ k , •). More precisely, we set T κ k = T κ k and the path ((t, X κ t , θ κ t ), t ≥ T κ k ) advances randomly as a copy of the process ((t, X t , θ t ), t ≥ T κ k ), i.e. according to the dynamic of the switching diffusion, starting at (T κ k , X T κ k , θ T κ k ) and up to the first time T κ k+1 it visits A k+1 , or up to T , whichever occurs first. During this transition, the total number of particles does not change, so we set N k+1 = N k .

The weight of each particle is set as β κ k+1 = β κ k and the N -particle approximation measure is given by

η N k+1 = κ∈ I N k β κ k+1 δ ξ κ k+1 = j∈J k ω j,N k η j,N k+1 , with η j,N k+1 = 1 N j κ∈ J j k δ ξ κ k+1 .
We easily verify that

E η N k+1 (f ) F k = η N k M k+1 f. (2.22)
The selection transition ξ k+1 → ξ k+1 is defined as follows. From the N k+1 particles ξ i k+1 , only some of them have succeeded to reach the desired set A k+1 ; we recall that

J j k+1 = {κ : π(ξ κ k+1 ) ∈ D k+1 × {j}}
and we set

I N k+1 = j∈J k J j k+1 .
If I N k+1 = ∅, then none of the particles have succeeded to reach the desired region; the algorithm is stopped and ξ k+1 = ∆. Otherwise, it may happen that there are some j for which J j k+1 = ∅, but as long as I N k+1 is not empty, we still continue the algorithm.

For each mode j such that J j k+1 = ∅, we need to sample N j particles in this mode. Nevertheless, more or less than N j particles may have reached the set D k+1 × {j}, so we need to resample N j particles among the particles ξ κ k+1 , with κ ∈ J j k+1 . If |J j k+1 | ≤ N j , then not enough particles have managed to reach the set D k+1 × {j} before the final time T , and these successful particles should be replicated, whereas if |J j k+1 | > N j , then too many particles have managed to reach the set D k+1 × {j} before the final time T , and some of these successful particles should be eliminated.

More precisely, we choose randomly the N j particles ξ κ k+1 , κ ∈ J j k+1 , identically distributed according to the distribution

Ψ j k+1 (η N k+1 ) = κ∈J j k+1 β κ k+1 κ∈J j k+1 β κ k+1 δ ξ κ k+1
.

By construction ξ κ k+1 is the copy of a successful particle ξ τ k+1 with τ ∈ J j k+1 ; necessarily T κ k+1 = T τ k+1 ≤ T . Each particle ξ κ k+1 for κ ∈ J j k+1 branches into a random number of offsprings M j,κ k+1 and the sequence (M j,κ k+1 , κ ∈ J j k+1 ) is distributed according to a

(M j,κ k+1 , κ ∈ J j k+1 ) = Multinomial N j , β κ k+1 κ∈J j k+1 β κ k+1 , κ ∈ J j k+1 .
For each j ∈ J k+1 , we obtain

η j,N k+1 = 1 N j κ∈ J j k+1 δ ξ κ k+1 = 1 N j κ∈J j k+1 M j,κ k+1 δ ξ κ k+1 ;
namely, we approximate the empirical measure Ψ j k+1 (η N k+1 ) by a new probability measure whose atom weights are integer multiples of 1/N j .

Furthermore, the mechanism is such that for any bounded test function f , we have

E η j,N k+1 (f )|F k+1 = Ψ j k+1 (η N k+1 )(f ), (2.23)
and

E η j,N k+1 (f ) -Ψ j k+1 (η N k+1 )(f ) 2 |F k+1 = 1 N j var f, Ψ j k+1 (η N k+1 ) ≤ f 2 N j , (2.24) where var(f, µ) = µ[(f -µ(f )) 2 ] and f = sup x∈E |f (x)|.
The total number N k+1 of particles ξ κ k+1 and the weights ω j,N k+1 are given respectively by

N k+1 = j∈J k+1 N j , and ω j,N k+1 = η N k+1 (g j k+1 ) = η N k+1 (g j k+1 ) η N k+1 (g k+1 )
.

It follows that

ω j,N k+1 = κ∈ J j k+1 β κ k+1 = κ∈J j k+1 β κ k+1 κ∈I N k+1 β κ k+1 .
As the particles ξ κ k+1 in the same mode have the same weight, we deduce that for any κ ∈ J j k+1

β κ k+1 = 1 N j κ∈J j k+1 β κ k+1 κ∈I N k+1 β κ k+1 .
Using (2.3) and (2.6), we also introduce the measures γ N n and γ j,N n defined respectively by

γ N n (f ) = η N n (f ) n-1 p=0 η N p (g p ) and γ j,N n (f ) = ω j,N n-1 γ N n (1)η j,N n (f ),
as approximations of γ n and γ j n . In particular for f ≡ 1, the IPS algorithm provides

γ N n+1 (1) = n p=0 η N p (g p ) = n p=0 κ∈I N p β κ p ,
as an estimate of the rare event probability P(T n ≤ T ) = γ n+1 [START_REF] Blom | Stochastic hybrid processes with hybrid jumps[END_REF]. In other words, γ N n+1 (1) is the product of proportions of excursions having entered levels A 1 , • • • , A n .

Asymptotic behavior

In this section, our aim is to examine the asymptotic behavior of particle approximation models as the number of particles tends to infinity. We start with the analysis of the unnormalized measure γ N n and we show that this approximation has no bias. We follow the approach used in [START_REF] Del | Genealogical and Interacting Particle Systems with Applications. Probability and its Applications[END_REF] which is based on a martinagle decomposition. Finally, we establish a central limit theorem for unnormalized particle approximation measures.

Law of large numbers

We begin by introducing some useful formulae and inequalities. Firstly, on the event {N k > 0}, we have

E( η N k (f )|F k ) = j∈J k E(ω j,N k η j,N k (f )|F k ) = j∈J k ω j,N k Ψ j k (η N k )(f ) = Ψ k (η N k )(f ), (3.1) since ω j,N k = η N k (g j k )/η N k (g k ) ∈ F k . Introducing the integer N inf defined by N inf = inf{N j : j = 1, • • • , M }, we deduce that E η N k (f ) -Ψ k (η N k )(f ) 2 F k = j∈J k (ω j,N k ) 2 N j var(f, Ψ j k (η N k )) ≤ f 2 j∈J k (ω j,N k ) 2 N j ≤ f 2 N inf . (3.2)
Secondly, when J k = ∅ we obtain by (2.22) that

E η N k+1 (f ) F k , F k = j∈J k ω j,N k E η j,N k (M k+1 f ) F k = j∈J k ω j,N k Ψ j k (η N k ) (M k+1 f ) = j∈J k ω j,N k Φ j k+1 (η N k )(f ) = j∈J k η N k (g j k ) η N k (g k ) Φ j k+1 (η N k )(f ) = Φ k+1 (η N k )(f ),
where we used (2.14) for the last line. It follows easily that

E η N k+1 (f )|F k = Φ k+1 (η N k )(f ). (3.3)
As the particles ξ κ k+1 are independent conditionally to F k , we get

E η j,N k+1 (f ) -Φ j k+1 (η N k )(f ) 2 F k = 1 N j η j,N k M k+1 [f -Φ j k+1 (η N k )(f )] 2 E η j,N k+1 (f ) -Φ j k+1 (η N k )(f ) 2 F k = 1 N j Φ j k+1 (η N k ) [f -Φ j k+1 (η N k )(f )] 2 .
Hence, we deduce the following

E η N k+1 (f ) -Φ k+1 (η N k )(f ) 2 F k = j∈J k (ω j,N k ) 2 N j var f, Φ j k+1 (η N k ) ≤ f 2 N inf . (3.4) RR n°7499
Remark 3.2 We can also express Γ p,n (f ) as Γ p,n (f ) = j∈M Γ j p,n (f ), with

Γ j p,n (f ) = 1 {|J j p-1 | > 0} γ j,N p (f p ) -γ j p (f p ), since γ N p (f ) = j∈M 1 {|J j p-1 | > 0} γ j,N p (f ), and
1 {N p > 0; |J j p-1 | > 0} = 1 { N p-1 > 0; |J j p-1 | > 0} = 1 {|J j p-1 | > 0}
.

Furthermore, from (3.5) we deduce that

Γ j p,n (f ) = p q=1 1 {|J j q-1 | > 0} γ j,N q (1) η j,N q (Q q,n f ) -Φ j q (η N q-1 )(Q q,n f ) + ω j 0 η j,N 0 (Q 0,n f ) -η j 0 (Q 0,n f ) .
We also can check that for each j ∈ M, the process

Γ j •,n (f ) is an F -martingale.
Corollary 3.3 For any n ≥ 0 and any bounded function f , we have

E(γ N n (f )1 {N n > 0} ) = γ n (f ),
and

sup f : f ≤1 E [1 {N n > 0} γ N n (f ) -γ n (f )] 2 ≤ b 2 (n) N inf .
Proof. The first assertion follows from the martingale property of (Γ p,n (f )) p whereas the second follows from the martingale property of (Γ 2 p,n (f ) -Γ •,n (f ) p ) p and the observation that in view of (3.4)

E ( Γ •,n (f ) n ) ≤ (n + 1) C N inf f 2 := b 2 (n) N inf f 2 .
This corollary shows that the IPS approximation γ N n of the unnormalized Feynman-Kac measure γ n has zero bias and mean-square error (or variance) of order 1/N inf . The end of this section is devoted to showing that similar results hold for the IPS approximation η N n of the normalized Feynman-Kac distribution η n as well: the bias is of order 1/N inf and the mean square error is also of order 1/N inf . The second statement follows readily from the decomposition

1 {N n > 0} η N n (f ) -η n (f ) = 1 {N n > 0} γ N n (f ) -γ n (f ) γ n (1) -1 {N n > 0} η N n (f ) 1 {N n > 0} γ N n (1) -γ n (1) γ n (1)
,

which implies

E 1 {N n > 0} η N n (f ) -η n (f ) 2 1/2 ≤   E 1 {N n > 0} γ N n (f ) -γ n (f ) γ n (1) 2   1/2 + f   E 1 {N n > 0} γ N n (1) -γ n (1) γ n (1) 2   1/2
, using the triangle inequality, hence

sup f : f ≤1 E 1 {N n > 0} η N n (f ) -η n (f ) 2 1/2 ≤ 2b 2 (n) (γ n (1)) 2 N inf .
Now, we address the estimation of the bias. Firstly, using Chebyshev's inequality, we also deduce the following corollary Corollary 3.4 We have

P γ N n (1)1 {N n > 0} ≥ γ n (1)/2 ≥ 1 - a 2 (n) N inf ,
for some constant a(n). Now, we use these results in the analysis of the normalized particle model. Arguing as in the proof of Theorem 7.4.3 in [START_REF] Del | Genealogical and Interacting Particle Systems with Applications. Probability and its Applications[END_REF], we write the following decomposition

η N n (f ) -η n (f ) 1 {N n > 0} = γ n (1) γ N n (1) γ N n (f n )1 {N n > 0} , (3.8)
where

f n = 1 γ n (1) (f -η n (f )). Since γ n (f n ) = 0, then (3.8) also reads η N n (f ) -η n (f ) 1 {N n > 0} = γ n (1) γ N n (1) γ N n (f n )1 {N n > 0} -γ n (f n ) 1 {N n > 0} . Now by Corollary 3.3, we have E γ N n (f n )1 {N n > 0} = γ n (f n ) this implies that E η N n (f ) -η n (f ) 1 {N n > 0} = E γ n (1) γ N n (1) 1 - γ N n (1) γ n (1) 1 {N n > 0} γ N n (f n )1 {N n > 0} -γ n (f n ) . If we set h n = 1 γ n (1)
, we get the formula

E η N n (f ) -η n (f ) 1 {N n > 0} = -E γ n (1) γ N n (1)
γ N n (h n )1 {N n > 0} -γ n (h n ) (3.9)
× γ N n (f n )1 {N n > 0} -γ n (f n ) 1 {N n > 0} .
Now, let Ω N n be the set of events defined by

Ω N n = {γ N n (1)1 {N n > 0} ≥ γ n (1)/2} = { γ n (1) γ N n (1) ≤ 2 and N n > 0} ⊂ {N n > 0}
which satisfies P(Ω N n ) ≥ 1a 2 (n)/N inf according to Corollary 3.3. If we combine this estimate with (3.9), we find that for any f with f ≤ 1

E η N n (f ) -η n (f ) 1 {N n > 0} ≤ E η N n (f ) -η n (f ) 1 Ω N n + 2P (Ω N n ) c ≤ 2E γ N n (h n )1 {N n > 0} -γ n (h n ) γ N n (f n )1 {N n > 0} -γ n (f n ) + b 2 (n) N inf .
By Corollary 3.3 and the Cauchy-Schwarz inequality, this implies that

E η N n (f ) -η n (f ) 1 {N n > 0} ≤ b 2 (n) N inf .
Finally, we get that

E η N n (f )1 {N n > 0} -η n (f ) ≤ b 2 (n) N inf + P(N n = 0).
Now, we need to estimate the extinction probability of the algorithm. In [START_REF] Del | Genealogical and Interacting Particle Systems with Applications. Probability and its Applications[END_REF]Theorem 7.4.1], a tricky proof gives the following bound for the extinction time τ N of the general particle algorithm

P(τ N ≥ n) ≤ a(n)e -N/c(n) .
Nevertheless, we can apply this bound with N inf instead of N , since the extinction time of our algorithm, defined by the first time n such that all the set J j n are empty, is greater than the extinction time for a classical IPS algorithm. Actually, we can imagine a classical IPS algorithm with only N j particles starting all in the mode j, whose extinction time is clearly less than the extinction time of our algorithm (remember that a mode could be empty at some time, and non empty again at a later time). Hence, we have obtained the following result Theorem 3.5 For each n ∈ N and for any bounded function f , we have

sup f : f ≤1 E η N n (f )1 {N n > 0} -η n (f ) ≤ b 2 (n) N inf + a(n)e -N inf /c(n) ,
and

sup f : f ≤1 E 1 {N n > 0} η N n (f ) -η n (f ) 2 1/2 ≤ 2b 2 (n) (γ n (1)) 2 N inf .

Central limit theorem

We now tackle the central limit theorem (CLT) whose importance for stochastic algorithms is well known. We will follow the approach based on the CLT for triangular arrays introduced in [START_REF] Del | Genealogical and Interacting Particle Systems with Applications. Probability and its Applications[END_REF]. Nevertheless, as the number of particles is random, we will need to adapt this approach according to [START_REF] François | A sequential algorithm that keeps the particle system alive[END_REF].

In order to introduce a triangular array of random variables, we split up the terminal term of the martingale (Γ •,n (f )) as a sum over the particles, so we obtain

√ N Γ n,n (f ) = n q=1 Nq κ=1 √ N β κ q 1 {N q-1 > 0} γ N q (1) f q (ξ κ q ) -Φ q (η N q-1 )(f q ) + √ N η N 0 (f 0 ) -η 0 (f 0 ) ,
with f q := Q q,n f for 0 ≤ q ≤ n. Introducing the random variables

X N q,κ := √ N β κ q 1 {N q-1 > 0} γ N q (1) f q (ξ κ q ) -Φ q (η N q-1 )(f q ) , 1 ≤ q ≤ n, X N 0,κ := √ N β κ 0 [f 0 (ξ κ 0 ) -η 0 (f 0 )],
we can rewrite √ N Γ n,n (f ) in the following form

√ N Γ n,n (f ) = n q=0 Nq κ=1 X N q,κ .
Furthermore, we can write also

√ N Γ n,n (f ) = j∈M N/N j √ N j Γ j n,n (f ), with √ N j Γ j n,n (f ) = 1 √ N j n q=1 κ∈ J j q-1 1 {|J j q-1 | > 0} γ j,N q (1) f q (ξ κ q ) -Φ j q (η N q-1 )(f q ) + 1 √ N j κ∈J j 0 ω j 0 f 0 (ξ κ 0 ) -η j 0 (f 0 ) .
We recall that | J j q-1 |= N j , and by introducing the random variables

X j,N q,κ := 1 √ N j 1 {|J j q-1 | > 0} γ j,N q (1) f q (ξ κ q ) -Φ j q (η N q-1 )(f q ) , 1 ≤ q ≤ n, X j,N 0,κ := 1 √ N j ω j 0 f 0 (ξ κ 0 ) -η j 0 (f 0 ) ,
we obtain the following form

√ N j Γ j n,n (f ) = n q=1 κ∈ J j q-1 X j,N q,κ + κ∈J j 0 X j,N 0,κ .
Finally, let us mention that X N q,κ = N/N j X j,N q,κ for κ ∈ J j q-1 . Henceforth, at the end of each selection/resampling step, the indices of each particle will be ordered according to the order induced by the modes. More precisely, setting N q = j∈M N j q with N j q = N j if j ∈ J q-1 and N j q = 0 otherwise, we label the N q = N q-1 particles ( ξ κ q-1 ) in such a way that κ ∈ J j q-1 if and only if the interval

I j := j-1 i=1 N i q + 1 , j i=1 N i q
with N 0 q := 0 is not empty and κ ∈ I j . We remind the reader that for κ ∈ J j q-1 a particle ξ κ q is an excursion started in D q-1 × {j} with j ∈ J q-1 . Now, let us introduce some new notations: firstly, we set

K N q = N 0 + • • • + N q , 0 ≤ q ≤ n,
with the convention K N -1 = 0. Secondly, we subdivide each interval [K N q-1 + 1 , K N q ] in a the reunion of the mutually disjoint sub-intervals [K N q,j-1 + 1 , K N q,j ] (j ∈ M), where

K N q,j = K N q-1 + N 1 q + • • • + N j q , K N q,0 = K N q and K N q,M = K N q+1 .
Obviously, for any j / ∈ J q-1 , such an interval is empty. We notice that the κ-th particle within the q-th generation can be associated in a unique way with an integer k between 1 and K N n and a mode j ∈ J q-1 : clearly k q,κ = K N q-1 + κ and j = inf{i : K N q,i ≥ k}. Conversely, for a fixed integer 1 ≤ k ≤ K N n , the random integers q k , κ k and j k are defined by

q k = inf{q ≥ 0 : K N q ≥ k}, κ k = k -K N q k -1
and j k = inf{j : K N q k ,j ≥ k}, or in other words q k = q and κ k = κ if and only if

K N q-1 + 1 ≤ k = K N q-1 + κ ≤ K N q .
We also check that the set of particles ξ κ q such that κ ∈ J j q-1 for any j ∈ J q-1 is the set of particles whose index κ belongs to the interval K N q,j-1 + 1 , K N q,j which is non empty as soon as j ∈ J q-1 . Now, we introduce a filtration G N = {G N k , k ≥ 1} in such a way that K N n is a stopping time w.r.t. G N . For any q = 0, 1, • • • , n and any integer κ ≥ 1, let F N q,κ = F N q,0 ∨ σ(ξ 1 q , • • • , ξ κ q ), where F N 0,0 = {∅, Ω} and F N q,0 = F q-1 (for q = 1, • • • , n). Since {N q = p} ∈ F N q,p by definition, the random number N q is a stopping time w.r.t. the filtration F N q = {F N q,κ , κ ≥ 0}, which allows to define the σ-algebra F N q,Nq = F q . Therefore, the random variable K N q is measurable w.r.t. F q .

For any q = 0, 1, • • • , n and any integer κ ≥ 1,

{q k = q, κ k = κ} = {k = K N q-1 + κ, κ ≤ N q } ⊂ F N q,κ-1 ⊂ F N q,κ , since {k = K N q-1 + κ} ∈ F q-1 and {κ ≤ N q } ∈ F N q,κ-1 .
Then, we can define in the usual way the σ-algebra

G N k = F N q k ,κ k by: A ∈ G N k if and only if A ∩ {q k = q, κ k = κ} ∈ F N q,κ
, for any q = 0, 1, • • • , n and any integer κ ≥ 1. Using this new labelling of the particle system yields

√ N Γ n,n (f ) = K N n k=1 U N k , where U N k := X N q k ,κ k is measurable w.r.t. G N k , for any k = 1, • • • , K N n : indeed for any Borel subset B {U N k ∈ B} ∩ {q k = q, κ k = κ} = {X N q,κ ∈ B} ∩ {q k = q, κ k = κ}, hence {U N k ∈ B} ∈ G N k , since {X N q,κ ∈ B} ∈ F N q,κ and {q k = q, κ k = κ} ∈ F N q,κ-1 .
Moreover, the random variable K N n is a stopping time w.r.t. G N , since

{K N n = k} ∩ {q k = q, κ k = κ} = {K N n = k} ∩ {k = K N q-1 + κ, 1 ≤ κ ≤ N q }, = ∅ if q = n, {k = K N n-1 + κ} ∩ {N n = κ} if q = n, hence {K N n = k} ∈ G N k since {k = K N n-1 + κ} ∈ F n-1 and {N n = κ} ∈ F N n,κ .
We also obtain the following expression

√ N Γ n,n (f ) = n q=0 j∈M K N q,j
k=K N q,j-1 +1

U N k = n q=0 j∈M κ∈ J j q-1 X N q,κ = n q=0 j∈M N/N j κ∈ J j q-1 X j,N q,κ . Now, since K N n < ∞ a.s., to apply the Theorem VIII.3.33 in [START_REF] Jacod | Limit Theorems for Stochastic Processes[END_REF] we need to check the following three conditions

(i) E(U N k |G N k-1 ) = 0, (ii)
K N n k=1 E |U N k | 2 |G N k-1 P → σ 2 ,
(iii) for all ε > 0,

K N n k=1 E |U N k | 2 1 {|U N k | > ε} |G N k-1 P → 0.
However, since U N k = X N q k ,κ k is a time changed random variable, we need the following result [11, Lemma 4, Corollaries 1 and 2] Lemma 3.6 If for any q = 0, 1, • • • , n and any integer κ ≥ 1

E[F q,κ |F N q,κ-1 ] = F q ,
where the random variable F q is measurable w.r.t. F N q,0 , then for any integer k ≥ 1, the time changed random variables G k = F q k ,κ k and

G k = F q k satisfy E[G k |G N k-1 ] = G k .
If for any q = 0, 1, • • • , n and any integer κ ≥ 1

F q,κ ≤ F * q ,
where the random variable F * q is measurable w.r.t. F N q,0 , then for any integer k ≥ 1, the time changed random variables

G k = F q k ,κ k and G * k = F * q k satisfy E[G k |G N k-1 ] ≤ G * k .
Firstly, for any κ = 1, • • • , N 0 , the random variable X N 0,κ is measurable w.r.t. F N 0,κ . Moreover, E X N 0,κ |F N 0,κ-1 = 0, and for any κ ∈ J j 0 E |X j,N 0,κ | 2 |F N 0,κ-1 = 1 N j (ω j 0 ) 2 var f 0 , η j 0 := V N 0,j .

Notice that

|X j,N 0,κ | ≤ 1 √ N j 2 f 0 ,
hence for any ε > 0

|X j,N 0,κ | 2 1 {|X j,N 0,κ | > ε} ≤ 1 N j (2 f 0 ) 2 1 { 1 √
N j 2 f 0 > ε} := Y N 0,j (ε).

For any q = 1, • • • , n, and any j ∈ J q-1 , the random weight γ j,N q (1) is measurable w.r.t. F q-1 = F N q,0 . Furthermore, for any κ ∈ J j q-1 the random variable X j,N q,κ is measurable w.r.t. F N q,κ , where conditionally w.r.t. the σ-algebra F q-1 , the particles ξ κ q , with κ ∈ J j q-1 , are i.i.d. with common distribution Φ j q (η N q-1 ). Moreover, E X j,N q,κ |F N q,κ-1 = 0, and for κ ∈ J j q-1 E[|X j,N q,κ | 2 |F N q,κ-1 ] = 1 N j 1 {|J j q-1 | > 0} γ j,N q (1) 2 var(f q , Φ j q (η N q-1 )) := V N q,j ,

where the random variables V N q,j are measurable w.r.t. F N q,0 . Notice that |X j,N q,κ | ≤ γ j,N q (1) √ N j 2 f q , hence for any ε > 0, |X j,N q,κ | 2 1 {|X j,N q,κ (f )| > ε} ≤ (γ j,N q (1)) 2 N j (2 f q ) 2 1 { γ j,N q (1) √ N j 2 f q > ε} := Y N q,j (ε),

where the random variable Y N q,j (ε) is measurable w.r.t. F N q,0 . It follows from Lemma 3.6 that

E U N k |G N k-1 = 0 E |U N k | 2 |G N k-1 = (N/N j k )V N q k ,j k , if κ k ∈ J j k q k -1 ,
and

E |U N k | 2 1 {|U N k | > ε} |G N k-1 ≤ (N/N j k ) Y N q k ,j k (ε N j k /N ),
hence,

K N n k=1 E |U N k | 2 |G N k-1 = j∈M N V N 0,j + n q=1 j∈Jq-1 N V N q,j
and

K N n k=1 E |U N k | 2 1 {|U N k | > ε} |G N k-1 ≤ n q=0 j∈M
N Y N q,j (ε N j /N ).

We deduce from Corollary 3.3 and Theorem 3.5 that γ j,N q (1)1 {|J j q-1 | > 0} → γ j q (1) and var f q , Φ j q (η N q-1 ) → var f q , Φ j q (η q-1 ) . Now, let ρ j := N j /N and let N → ∞ in such a way that for any j ∈ M, the ratio ρ j is preserved, or at least the ratio N j /N → ρ j . Then, we deduce that N V N 0,j → (ω j 0 ) 2 ρ j var f 0 , η j 0 ,

RR n°7499

This work was partially supported by the European Commission under the project Safety, Complexity and Responsibility-Based Design and Validation of Highly Automated Air Traffic Management (iFLY) (contract number TREN/07/FP6AE/S07.71574/037180) within the 6th Framework Programme FP6-2005-Aero-4 (Aeronautics and Space). The authors gratefully acknowledge Henk Blom, for his continuing support and interest in this work.

Now, we study the difference between the particle measure γ N n and the limiting Feynman-Kac measures γ n . Following the approach given in [START_REF] Del | Genealogical and Interacting Particle Systems with Applications. Probability and its Applications[END_REF], we use the decomposition for each bounded function f

In other respects, since

1 {N p-1 > 0, N p = 0} η N p = 0, we conclude that

This yields the formula

On taking expectation and using (3.3) we thus deduce that

Proposition 3.1 For any n ≥ 0 and bounded function f , the R-valued process Γ •,n (f ) defined by

is an F -martingale with increasing process given by the formula

Proof. For all function φ, we deduce from (3.5) and (3.6) that

and (3.7) is a clear consequence of the above decomposition.

and N V N q,j → (γ j q (1)) 2 ρ j var f q , η j q in probability. We remark also that |J j q-1 | > 0 if and only if η N q-1 (g j q-1 ) > 0, but this probability converges to P j q-1 as N tends to infinity, so if we assume P j q-1 = 0 (a reasonable assumption), we can conclude that

.

To obtain the last line, we used the formula γ j q (1) = ω j q-1 γ n (1)/η q (Q q,n 1) valid for q ≥ 1, and the convention ω j -1 = ω j 0 . Moreover, we can check that n q=0

j∈M N Y N q,j (ε N/N j ) → 0 in probability. So, we have proved the CLT. Theorem 3.7 Let N tends to ∞ in such a way that the ratios ρ j = N j /N are preserved for all j ∈ M. Then, the sequence of random variables

converges in law to a Gaussian random variable with mean 0 and variance W n := W n (g n ).

Remark 3.8 The asymptotic variance of the classical algorithm i.e. without sampling per mode is given by [START_REF] Cérou | Genetic genealogical models in rare event analysis[END_REF] V n (f ) = (γ n (1)) 2 n q=0 var(f q , η q ) η 2 q (Q q,n 1)

.

But, we have var(f q , η q ) = j∈M ω j q-1 var(f q , η j q ) + j∈M ω j q-1 [(η j q (f q )) 2η 2 q (f q )],

then V n (f ) can be written as

.

Consequently, we check that

hence, if we are able to adapt, at each step q, the number of resampled particles N j q in order that ω j q ≈ N j q /N , we will obtain an asymptotic variance less than the asymptotic variance of the classical algorithm. Remark 3.9 For any q ≥ 0, the function g q,n := Q q,n g n is defined for any excursion e = (z(u) , s ≤ u ≤ t) by g q,n (e) = g q (e) P(T n ≤ T |(T q , Z Tq ) = π(e)).

Setting

∆ n q (t, z) = P(T n ≤ T |T q = t, Z Tq = z), and introducing the entrance distribution µ q := η q • π -1 give the following identities, since g 2 q = g q , η q (g q,n ) = η q g q ∆ n q • π = η q (g q ) η q ∆ n q • π = P q µ q ∆ n q , η q [g 2 q,n ] =

Moreover, from (2.1), we also get η q (g q,n ) = j∈M P j q µ j q ∆ n q , η q (g 2 q,n ) = j∈M P j q µ j q [∆ n q ] 2 , with µ j q := η j q • π -1 . We also notice that, since ∆ n q-1 • π = M q g q,n , we obtain η j q (g q,n ) = η j q-1 (M q g q,n ) = µ j q-1 (∆ n q-1 ).

However, we have no so simple expression for η j q (g 2 q,n ), except perhaps by introducing the Markov kernel R

(n) q defined by [4, Proposition 2.7.1], for any function f q acting on excursions e such that π(e) ∈ A q-1 R (n) q f q = M q (g q,n f q ) M q g q,n , so that we can write

As with stratified sampling, a small asymptotic variance can be obtained only if the function g q,n is relatively homogeneous for each measure η j q , i.e. if var(g q,n , η j q ) is relatively small for each j and each q. This is possible if and only if we have a great variability between the values (η j q (g q,n )) j∈M for each q; but the sampling per mode algorithm has been introduced precisely in order to improve the classical algorithm in that case.

Conclusion

In this paper we considered the rare event simulation problem for a switching diffusion, using a multilevel splitting method adapted to the discrete modes: the conditional "sampling per mode" algorithm. Using the Feynman-Kac and interacting particle theory, we established a law of large numbers and a central limit theorem for the estimate of the rare event probability and thus we confirmed that this algorithm has a better asymptotic variance as soon as the probability to hit the target set fluctuates according to the mode. We also observe that an adaptive algorithm which will update the number of resampled particles N j q , at each step q, in order that ω j q ≈ N j q /N , will give a lower asymptotic variance. It will also be valuable to deduce from the expression of the asymptotic variance some informations about the tuning of the algorithm; for example the optimal number N j of particles in each mode. To improve again the quality of our estimate, an importance sampling technique can be added in order to make the rare switches more frequent. This idea has already been explored in [START_REF] Krystul | Modelling of Stochastic Hybrid Systems with Applications to Accident Risk Assessment[END_REF], and now we think that it will be possible to obtain a central limit theorem also for this kind of algorithm. Let also mention that a possible Rao-Blackwellisation strategy could be investigated, based on a partition of the state space in the continuous component and the discrete modes.


MD, Researcher, Kim Kronström

MD Hasse Karlsson

PhD Hermann Nabi

MD Tuula Oksanen

PhD Paula Salo

PhD Noora Sjösten

PhD Marianna Virtanen

BS Jaana Pentti

PhD Mika Kivimäki

PhD Jussi Vahtera

Optimism and pessimism as predictors of work disability with a diagnosis of : a prospective cohort study

Keywords: optimism, pessimism, depression, work disability

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

OPTIMISM AND PESSIMISM AS PREDICTORS OF WORK DISABILITY WITH A DIAGNOSIS OF DEPRESSION: A PROSPECTIVE COHORT STUDY OF ONSET AND RECOVERY

Background: Personality characteristics are assumed to affect to the vulnerability to depression and its outcomes. The aim of this study was to examine optimism and pessimism as predictors of depression-related work disability and subsequent return to work.

Methods: A prospective cohort study of 38,214 public sector employees with no record of diagnosed depression. Optimism and pessimism were measured using the Revised Life Orientation Test (LOT-R). Records of long-term (>90 days) work disability with a diagnosis of depression and subsequent return to work until the end of 2005 were obtained from national health registers.

Results: During the mean follow-up of 4.0 (SD=2.3) years, 287 employees encountered work disability with a diagnosis of depression. Of them, 164 (57%) returned to work during the follow-up. One unit increase in the optimism mean score (range 1-4) was associated with a 25% lower risk of work disability due to depression and a 37% higher probability of returning to work after a work disability period when adjusted for age and sex. In the fully-adjusted

INTRODUCTION

Vulnerability to depression and the course of the depressive disorder once occurred are assumed to be affected by several factors, including personality [START_REF] Major | Personal resilience, cognitive appraisals and coping[END_REF][START_REF] Bagby | Personality and depression[END_REF]. Dispositional optimism and pessimism are potentially relevant personality variables in this context as they conceptualize how people perceive, react, and adapt to the challenges of their lives [START_REF] Scheier | Optimism, coping and health: assessment and implications of generalized outcome expectancies[END_REF][START_REF] Scheier | Distinguishing optimism from neurotism (and trait anxiety, self-mastery, and self-esteem):a reevaluation of the Life Orientation Test[END_REF][START_REF] Hart | Relationships among depressive symptoms, benefitfinding, optimism, and positive affect in multiple sclerosis patients after psychotherapy for depression[END_REF][START_REF] Steptoe | Positive affect and psychosocial processes related to health[END_REF][START_REF] Brydon | Dispositional optimism and stress-induced changes in immunity and negative mood[END_REF][START_REF] Prati | Optimism, social support, and coping strategies as factors contributing to posttraumatic growth. A Meta-Analysis[END_REF].

The majority of studies focusing on the relationship between optimism, pessimism and depression have used uni-dimensional model, where optimism and pessimism represent polar opposites of single continuum. This view has been challenged by several studies suggesting that optimism and pessimism may act more like two separate constructs [START_REF] Herzberg | Separating optimism and pessimism: a robust psychometric analysis of the revised Life Orientation Test (LOT-R)[END_REF][START_REF] Robinson-Whelen | Distinguishing optimism from pessimism in older adults: is it more important to be optimistic or not to be pessimistic?[END_REF][START_REF] Kivimäki | Optimism and pessimism as predictors of change in health after death or onset of severe illness in family[END_REF][START_REF] Conway | Optimism and Pessimism as a predictors of physical and psychological health among grandmothers raisin their grandchildren[END_REF][START_REF] Szalma | Individual differences in performance, workload and stress in sustained attention: Optimism and pessimism[END_REF][START_REF] Kubzansky | Optimism and pessimism in the context of health: bipolar opposites or separate constructs?[END_REF]. Thus, it may be hypothesized that optimism and pessimism have distinct effects on the risk of developing depression, as well as the likelihood of depression related work disability. The aim of this study was to investigate whether optimism and/or pessimism are independent predictors of depressionrelated work disability and subsequent return to work in a large cohort of public sector employees.

METHOD

Study population and design

Data were from the Finnish Public Sector Study, which includes a prospective follow-up of employees in the service of ten municipalities [START_REF] Vahtera | Employee control over working times and risk of cause-specific disability pension: the Finnish Public Sector Study[END_REF]. The eligible population for the study was all 63,460 full-time employees at work when the surveys were carried out (from 1997 to 2004). In total, 46,352 employees responded to the baseline survey (response rate 73%). We linked the participants to their records in the national health registers. We excluded the respondents with missing data on depression, optimism or pessimism, and those who were eligible to special imbursement for medication for severe mental disorders, were retired, or died during the survey year. We also excluded participants who reported that they had been diagnosed with depression or who were on a long-term work disability period at baseline for any reason (including depression), or had been hospitalized due to depression, or who had purchased antidepressants or received psychotherapy for depression in the survey year (n=6599 altogether). Thus the final cohort included 38,214 subjects with no indication of depression at the baseline. The study was approved by the Ethics Committee of the Finnish Institute of Occupational Health.

Optimism and pessimism

Dispositional optimism and pessimism were measured with the revised Life Orientation Test (LOT-R; [START_REF] Scheier | Distinguishing optimism from neurotism (and trait anxiety, self-mastery, and self-esteem):a reevaluation of the Life Orientation Test[END_REF] at baseline. The measure issues six statements, of which three are worded positively for optimism (e.g., "In uncertain times, I usually expect the best") and three negatively to indicate pessimism (e.g., "If something can go wrong for me, it will"). The response scale ranges from 1 (not at all) to 4 (very much so), a 4-point modification of the standard 5-point response format [START_REF] Kivimäki | Optimism and pessimism as predictors of change in health after death or onset of severe illness in family[END_REF]. Mean of the positively worded items was calculated to yield the level of optimism (Cronbach's alpha = 0.65) and mean of the negatively worded items comprised the level of pessimism (Cronbach's alpha = 0.74).

Work disability

The work disability outcomes were beginning of a new period of work disability (≥90 days) and returning to work from such a period. Data on work disability were obtained from the registers kept by the Social Insurance Institution and the Finnish Centre for Pensions. Both registers require physician assigned diagnoses of disability coded according to the International Classification of Diseases, 10th Revision (ICD-10). In the present study, only periods of work disability with depression (ICD-10 codes F32-F34) as the main diagnosis were considered.

Baseline covariates

The following variables were treated as potential confounders in the analyses: age, sex, socioeconomic status (SES), and marital status. SES was categorized to upper-grade nonmanual workers, lower-grade non-manual workers and manual workers. Marital status was dichotomized to married or cohabiting vs. single.

Several covariates obtained from the survey responses were treated as potential mediators for the association between optimism/pessimism and the outcomes.

Alcohol consumption was classified as low (0-210 g pure alcohol per week) or high (> 210 g per week) consumption. Current smoking and low physical activity (<2 Metabolic Equivalent Task hours per day) were coded yes/no [START_REF] Vahtera | Employee control over working times and risk of cause-specific disability pension: the Finnish Public Sector Study[END_REF].

Participants who had purchased, according the Drug Prescription Register, any anxiolytic or hypnotic medication during the year of the baseline survey were coded as being on that treatment. Data on somatic disease, i.e. hypertension, cardiac failure, ischemic heart disease, diabetes, asthma or other chronic obstructive lung disease, rheumatoid arthritis and cancer, were obtained from the Drug Reimbursement Register and the Finnish Cancer register.

Statistical analysis

The associations of baseline covariates, and optimism and pessimism, with the risk of work disability due to depression and the likelihood of return to work were studied with Cox proportional hazards models. Hazard ratios (HR) and their 95% confidence intervals (CI) were sequentially adjusted for (1) age and sex, (2) socioeconomic and marital status and (3) alcohol use, smoking, physical activity, purchases of anxiolytics or hypnotics, and baseline health. Since optimism and pessimism were considered as continuous variables, HR reflected the change in the risk of work disability or probability of returning to work per one point increase in the scale measuring optimism or pessimism (range 1-4). Given the higher prevalence of depressive symptoms in women, we examined sex differences in these associations by including an interaction term "sex x optimism/pessimism" in the model containing all main effects. Cumulative hazard rates for work disability and return to work (Figures 1 and2) were estimated by Kaplan-Meier survival analysis. Optimism and pessimism scores were rounded to the nearest integer. In figure 2 infrequent pessimism score 4 (0,4%) was pooled together with pessimism score 3.

All statistical analyses were carried out using the SAS 9.1.3 program package (SAS Institute Inc., Cary, NC, USA).

RESULTS

During a mean follow-up of 4.0 (SD 2.3) years, 287 employees encountered work disability with a diagnosis of depression .Of those employees, 164 (57%) returned to work during the follow-up.

The baseline characteristics and their associations with optimism, pessimism and work disability are presented in table 1. After adjustment for age and sex, one unit increase in the optimism score was associated with a 25% lower risk of work disability due to depression (HR 0.75, 95% Cl 0.63-0.91) whereas the pessimism score was not associated with work disability (HR 1.19 , 95% CI 0.98-1.46)(figure 1,table 2).

Among the 287 participants who were disabled due to depression, one unit increase in optimism score was associated with a 37% higher probability of returning to work after long-term work disability in a model adjusted for age and sex (HR 1.37, 95% CI 1.08-1.73). Participants with higher pessimism scores, in turn, were less likely to return to work, with one unit increase in pessimism being associated with a 35% lower probability (age-and sex-adjusted HR 0.65, Cl 0.49-0.85) (Figure 2, table 2). The results remained materially unchanged after further adjustments for SES, marital status, smoking, physical inactivity, alcohol or medication use, and somatic disease. These findings were replicated even when optimism and pessimism were included in the same fully adjusted model (work disability: HR 0.80, 95% CI 0.65-0.98 and 1.02, 0.81-1.28; return to work: HR 1.12, 95% CI 0.85-1.48 and 0.69, 0.50-0.96 for optimism and pessimism, respectively). Pearson correlation coefficient between optimism and pessimism scales was -0.35.

DISCUSSION

The results of this large prospective study of Finnish municipal workers show that optimism predicts the development of long-term work disability with a diagnosis of depression and both optimism and pessimism predicted the likelihood of returning to work.

To our knowledge, there are only two previous longitudinal studies on depression and separate effects of optimism and pessimism. In those studies, depression was either not predicted by optimism or pessimism [START_REF] Robinson-Whelen | Distinguishing optimism from pessimism in older adults: is it more important to be optimistic or not to be pessimistic?[END_REF] or was predicted only by pessimism [START_REF] Chang | Irrational beliefs, optimism, pessimism and psychological distress: a preliminary examination of differential effects in a college population[END_REF]. The result of the former study conflicts with the previous studies using uni-dimensional model for optimism and pessimism, where being in the optimism-end of the continuum has repeatedly been shown to be associated with a reduced likelihood of the development of depression [START_REF] Carver | Optimism, Pessimism and postpartum depression[END_REF][START_REF] Achat | Optimism and depression as predictors of physical and mental health functioning: the normative ageing study[END_REF][START_REF] Brissette | The role of optimism in social network development, coping, and psychological adjustment during a life transition[END_REF][START_REF] Giltay | Dispositional optimism and the risk of depressive symptoms during 15 years of follow-up: the Zutphen Eldery Study[END_REF]. A drawback in the latter study is that baseline depression symptoms were not evaluated which, in addition to the short follow-up time (six weeks), limits the longitudinal nature of the study. Our findings support the distinction between optimism and pessimism as these concepts seemed to have different predictive validity on depression-related work disability outcomes. This finding is in agreement with a previous study showing that low optimism, but not high pessimism, predicts an increased likelihood of sickness absence after major negative life events [START_REF] Kivimäki | Optimism and pessimism as predictors of change in health after death or onset of severe illness in family[END_REF].

It is possible that lack of optimism predisposes to depression by weakening individual resources to cope with the burden of life and leads to longer periods of work disability. Previous studies have reported that childhood adversities [START_REF] Korkeila | Childhood adversities, parent-child relationships and dispositional optimism in adulthood[END_REF], lower education, and discontinuous working history [START_REF] Ellen | Social and developmental predictors of optimism from infancy to early adulthood[END_REF]) are all associated with decreased optimism and a higher probability of developing depression [START_REF] Danese | Adverse childhood experiences and adult risk factors for age related disease: depression, inflammation, and clustering of metabolic risk markers[END_REF][START_REF] Ritchie | Association of adverse childhood environment with late-life depression[END_REF][START_REF] Andersen | Social inequality in the prevalence of depressive disorder[END_REF]. Thus, there are common risk factors behind both optimism and depression, and this could explain in part the increased depressionrelated work disability among those with low optimism. According to the study by [START_REF] Plomin | Optimism, pessimism and mental health: a twin/adoption analysis[END_REF], individuals with genetic propensity towards low optimism and high pessimism are also at risk for depression with heritability accounting about a third of the phenotypic associations between optimism, pessimism, and depression. High optimism is associated with lower levels of stress, increased social support (Brissette el al., 2002[START_REF] Hakanen | Work engagement among breast cancer survivors and the referents: the importance of optimism and social resources at work[END_REF][START_REF] Bozo | The moderating role of different sources of perceived social support on dispositional optimism-posttraumatic growth relationship in postoperative breast cancer patients[END_REF] and superior coping strategies [START_REF] Scheier | Distinguishing optimism from neurotism (and trait anxiety, self-mastery, and self-esteem):a reevaluation of the Life Orientation Test[END_REF][START_REF] Szalma | Individual differences in performance, workload and stress in sustained attention: Optimism and pessimism[END_REF][START_REF] Fry | Perfectionism, humor, and optimism as moderators of health outcomes and determinants of coping styles of women executives[END_REF], which all may protect against depression and its outcomes, such as increased rates of sick leaves and work disability. High optimism may enhance placebo effects [START_REF] Geers | Reconsidering the role of personality in placebo effects: dispositional optimism, situational expectations, and the placebo response[END_REF][START_REF] Geers | Further evidence for individual differences in placebo responding: an interactionist perspective[END_REF][START_REF] Morton | Reproducibility of placebo analgesia: Effect of dispositional optimism[END_REF][START_REF] Brunoni | Placebo response of nonpharmacological and pharmacological trials in major depression: a systematic review and meta-analysis[END_REF] to the treatment interventions received. Furthermore, it is possible that a high level of optimism affects the person's own or treating physicians´ judgment on the working ability, which could lead to faster return to work after a depressive episode.

This study benefitted from a large sample size, longitudinal study design and high response rate (73%). Due to the use of extensive national health registers, there was practically no loss to follow-up. The severity of depression has previously been reported to associate with the risk and duration of sickness absence [START_REF] Rytsälä | Functional and work disability in major depressive disorder[END_REF][START_REF] Bültman | Depressive symptoms and the risk of long-term sickness absence[END_REF][START_REF] Lerner | What does research tell us about depression, job performance, and work productivity?[END_REF][START_REF] Lagerveld | Factors associated with work participation and work functioning in depressed workers: A Systematic Review[END_REF]. Our outcome measures on risk of and recovery from depression-related work disability are clinically highly relevant and provide complementary evidence for studies based on self-report depression scales. However, our study population was relatively homogeneous and therefore our results cannot be generalized to non-European non-white populations. Despite the high response rate, we cannot exclude the possibility of selection bias. Although we excluded baseline respondents with evidence of previous or ongoing depression, it is possible that some individuals experienced subclinical depressive symptoms at baseline potentially introducing reverse causation bias with depression affecting optimism rather than vice verse.

In conclusion, this longitudinal study suggests that personality variables, such as optimism and pessimism are associated with the onset of depression-related work disability and returning to work. The level of optimism seems to be a stronger predictor of work disability with a diagnosis of depression than the level of pessimism, while both optimism and pessimism predicted returning to work. These findings may implicate that more emphasis should be put on supporting persons with low optimism or high pessimism in their efforts to return to work

Table 1 .

 1 Baseline characteristics and the risk of work disability due to depression and return to work.

				Optimism	Pessimism	Work disability	Return to work
						287 events		164 events
			N (%)	mean (sd)	mean (sd)	HR (95% CI)	1)		HR (95% CI)	1)
	All			2.73 (0.61)	1.45 (0.54)
	Sex			p<.001	p<.001
		Men	9269 (24)	2.67 (0.61)	1.48 (0.56)	1.00 (ref.)			1.00 (ref.)
		Women	28945 (76)	2.75 (0.61)	1.44 (0.53)	1.56 (1.14-2.13)		1.07 (0.71-1.63)
	Age	mean (sd)	44.4 (9.6)	p=0.111 0.008 2)	p<.001 0.042 2)	1.54 (1.34-1.77)	3)	0.51 (0.43-0.61)	3)
	SES			p<.001	p<.001
		Manual	8029 (21)	2.61 (0.62)	1.63 (0.61)	1.00 (ref.)			1.00 (ref.)
		Lower-grade non-manual	16919 (44)	2.74 (0.61)	1.45 (0.53)	0.80 (0.59-1.09)		1.86 (1.22-2.84)
		Upper-grade non-manual	13156 (35)	2.80 (0.61)	1.33 (0.47)	0.73 (0.53-1.01)		1.76 (1.12-2.75)
	Marital status		p<.001	p<.001
		Married/cohabiting	29155 (77)	2.74 (0.60)	1.43 (0.52)	1.00 (ref.)			1.00 (ref.)
		Single	8630 (23)	2.71 (0.64)	1.52 (0.58)	0.82 (0.61-1.11)		0.85 (0.57-1.26)
	Alcohol consumption/wk		p<.001	p<.001
		0-210g	34573 (91)	2.74 (0.61)	1.44 (0.53)	1.00 (ref.)			1.00 (ref.)
		>210g	3479 (9)	2.69 (0.63)	1.50 (0.58)	1.53 (1.06-2.21)		1.01 (0.62-1.64)
	Smoking		p<.001	p<.001
		No	30158 (81)	2.74 (0.61)	1.43 (0.52)	1.00 (ref.)			1.00 (ref.)
		Yes	7235 (19)	2.70 (0.62)	1.52 (0.58)	1.27 (0.95-1.69)		0.86 (0.58-1.28)
	Physical inactivity		p<.001	p<.001
		No	29107 (77)	2.76 (0.60)	1.42 (0.52	1.00 (ref.)			1.00 (ref.)
		Yes	8937 (23)	2.63 (0.63)	1.52 (0.59)	1.21 (0.93-1.57)		0.80 (0.55-1.16)
	Use of anxiolytics/hypnotics		p=.003	p<.001
		No	37495 (98)	2.73 (0.61)	1.45 (0.54)	1.00 (ref.)			1.00 (ref.)
		Yes	719 (2)	2.67 (0.62)	1.52 (0.58)	4.12 (2.77-6.11)		1.30 (0.79-2.14)
	Somatic disease		p<.001	p<.001
		No	33732 (88)	2.74 (0.61)	1.44 (0.53)	1.00 (ref.)			1.00 (ref.)
		Yes	4482 (12)	2.70 (0.61)	1.51 (0.57)	1.41 (1.03-1.94)		0.77 (0.48-1.23)
	1) Adjusted for age and sex
	2) Pearson correlation coefficient
	3) HR / 10 years

Table 2 .

 2 The associations between optimism/pessimism and the risk of work disability and return to work.Model 1 adjusted for age and sex Model 2 adjusted for age, sex, SES and marital status Model 3 adjusted for age, sex, SES, marital status, alcohol consumption, smoking, physical inactivity, use of anxiolytics/hypnotics and somatic disease Figure 1. Cumulative hazard rates for work disability due to depression differed by optimism and pessimism scores

		Model 1	Model 2	Model 3
		HR (95% CI)	HR (95% CI)	HR (95% CI)
	DEPRESSION
	Work disability (287 events)
	Optimism	0.75 (0.63-0.91)	0.77 (0.64-0.93)	0.79 (0.66-0.96)
	Pessimism	1.19 (0.98-1.46)	1.15 (0.93-1.42)	1.11 (0.90-1.37)
	Return to work (164 events)
	Optimism	1.37 (1.08-1.73)	1.29 (1.01-1.64)	1.30 (1.01-1.66)
	Pessimism	0.65 (0.49-0.85)	0.68 (0.51-0.90)	0.66 (0.49-0.88)

This study was supported by the Academy of Finland (projects 124271, 124322 and 129262), the Social Insurance Institution of Finland and the participating organizations. Mika Kivimäki is supported by the BUPA Foundation, UK, the National Institute on Aging (R01AG034454-01) and the National Heart, Lung, and Blood Institute (R01HL036310-20A2), NIH, USA. Tuula Oksanen is supported by Otto A Malm Foundation.