Morgane Mokhtari

Christophe Le Bourlot
email: christophe.le-bourlot@insa-lyon.fr

Jérome Adrien

Anne Bonnin

Wolfgang Ludwig

Pierre-Antoine Geslin

Takeshi Wada

Jannick Duchet-Rumeau

Hidemi Kato

Eric Maire

In situ observation of liquid metal dealloying and etching of porous FeCr by X-ray tomography and X-ray diffraction

Keywords:

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

Introduction

In the last decades, the attraction of nanoporous metals due to their excellent functional properties have risen [START_REF] Erlebacher | Hard materials with tunable porosity[END_REF][START_REF] Snyder | Oxygen reduction in nanoporous metal-ionic liquid composite electrocatalysts[END_REF][START_REF] Lang | Nanoporous metal/oxide hybrid electrodes for electrochemical supercapacitors[END_REF][START_REF] Chen | Study on the two dealloying modes in the electrooxidation of Au-Sn alloys by in situ Raman spectroscopy[END_REF] . Because of their availability, cost and abundance, porous structures of common metals such a-Ti-based, Fe-based…) alloys are highly desired for various applications including energy-harvesting devices [START_REF] Sivula | Photoelectrochemical water splitting with mesoporous hematite prepared by a solution-based colloidal approach[END_REF] . A well-known technique to prepare nanoporous metal is dealloying in an aqueous solution. An attempt was made to dealloy an Fe-Mn precursor in an aqueous solution but the resulting nanoporous Fe was partially oxidized [START_REF] Hakamada | Less noble nanoporous metals fabricated by dealloying[END_REF] . Because less noble metals are unstable in water, dealloying in an aqueous solution remains challenging. To overcome this limitation, aqueous dealloying was generalized to all liquids and one method based on liquid metalwas developed in [START_REF] Wada | Dealloying by metallic melt[END_REF] .

Dealloying with the metallic melt or also called liquid metal dealloying, is a selective dissolution phenomenon from a solid precursor alloy into a metallic melt. Suppose that the precursor is composed of at least two components, one or more being soluble and the others insoluble in the metallic melt. When the solid precursor alloys is immersed in the metallic melt, only atoms of the soluble components dissolve into the melt and the atoms of the insoluble components remain at the melt/precursor interface and spontaneously organize at nanoscale level. After cooling down to room temperature, a bicontinous structure composed by insoluble components and solidified metallic melt (including soluble components) phases is obtained. One phase (in our case the solidified metallic melt) can be removed by selective chemical etching to obtain the final nanoporous material. This technique enables the preparation of nanoporous structures with less noble elements such as pure Ti, Fe, Cr, Nb, Ta, Mg [START_REF] Wada | Dealloying by metallic melt[END_REF][START_REF] Wada | Three-dimensional open-cell macroporous iron, chromium and ferritic stainless steel[END_REF][START_REF] Kim | Sub-micron porous niobium solid electrolytic capacitor prepared by dealloying in a metallic melt[END_REF][START_REF] Mccue | Kinetics and morphological evolution of liquid metal dealloying[END_REF][START_REF] Okulov | Nanoporous magnesium[END_REF] , alloys (TiCrZr, TiHf, TiZr, TiNb, NiCr, FeCr, stainless steels) [ 8 , 12-18 ] and non-metals (Si, C) [ 19 , 20 ].

The mechanical properties of these porous materials are controlled by their microstructure (solid phase fraction, ligament size, anisotropy etc.) and are also influenced by the formation of defects appearing during the process. A good understanding of the whole dealloying process is therefore needed to control the final properties of these materials.

Dealloying by free corrosion in an aqueous solution has already been studied by various methods such as in situ electrochemical noise or Raman spectroscopy, for example [ 4 , 21-23 ]. It was even 3D imaged in situ to study the evolution of the dealloying front and coarsening and the effect of different parameters on the dealloying process such as precursor composition or acid concentration [START_REF] Chen-Wiegart | Structural evolution of nanoporous gold during thermal coarsening[END_REF][START_REF] Chen-Wiegart | In situ imaging of dealloying during nanoporous gold formation by transmission X-ray microscopy[END_REF][START_REF] Chen-Wiegart | Effect of Ag-Au composition and acid concentration on dealloying front velocity and cracking during nanoporous gold formation[END_REF] . The fundamentals of dealloying were studied by in situ X-ray diffraction of the initial dealloying step of a Cu 3 Au precursor [START_REF] Zegenhagen | In situ X-ray analysis of solid/electrolyte interfaces: electrodeposition of Cu and Co on Si(1 1 1):h and GaAs(0 0 1) and corrosion of Cu 3 Au(1 1 1)[END_REF][START_REF] Renner | Initial corrosion observed on the atomic scale[END_REF][START_REF] Renner | In-situ X-ray diffraction study of the initial dealloying of Cu 3 Au(001) and Cu 0.83 Pd 0.17 (001[END_REF][START_REF] Renner | In situ x-ray diffraction study of the initial dealloying and passivation of Cu3 Au(111) during anodic dissolution[END_REF] . Dealloying was followed by in situ X-ray diffraction during the whole dealloying process and some residual stresses were measured [START_REF] Van Petegem | On the microstructure of nanoporous gold: an X-ray diffraction study[END_REF][START_REF] Mahr | Measurement of local crystal lattice strain variations in dealloyed nanoporous gold[END_REF][START_REF] Chen-Wiegart | Evolution of dealloying induced strain in nanoporous gold crystals[END_REF] . Contrary to dealloying by free corrosion which occurs at room temperature, the liquid metal dealloying process occurs at high temperature (more than 923 K), making the in situ observation of the process more difficult, explaining why LMD has not yet been followed in situ.

On the other hand, the LMD process has already been studied either by simulation [START_REF] Geslin | Topology-generating interfacial pattern formation during liquid metal dealloying[END_REF] or by postmortem 2D/3D observations. Moreover, the evolution of a liquid metal dealloying front with dealloying parameters was already studied in 2D, with postmortem SEM observations for different materials Ti, Nb, Ta [ 10 , 35-36 ], Regarding porous FeCr formation, the evolution of the dealloying front was investigated in 2D in the case of solid metal dealloying [START_REF] Wada | Evolution of a bicontinuous nanostructure via a solid-state interfacial dealloying reaction[END_REF] . Concerning the etching step, the ligaments and pore size were already 3D imaged before and after the etching step [ 16 , 38 ].

FeCrNi precursors with the same composition as the one used in this analysis have already been studied: after dealloying from a FeCrNi precursor in an Mg melt, the structure was 3D imaged by X-ray tomography [ 39 , 40 ]. A bicontinous structure in the bulk was obtained when the amount of Ni included is between 30 and 70 at% [ 39 , 40 ]. However in [START_REF] Mokhtari | Microstructure characterization by X-ray tomography and EBSD of porous FeCr produced by liquid metal dealloying[END_REF] , the process was not monitored experimentally in situ .

In materials science, the word microstructure is usually used to describe grain size and crystallographic phases etc. In the case of architectured materials, the word microstructure can also be used to describe the macroscopic arrangement (density, pore size, ligament size etc.). Our material architecture will be referred to as the morphology, and the grain and crystallographic microstrucure will be known as the microstructure.

The morphology was shown to be mainly determined by the dealloying parameters (liquid bath temperature and immersion time). For example, ligament size was independent on the precursor amount of Ni [START_REF] Mokhtari | Microstructure characterization by X-ray tomography and EBSD of porous FeCr produced by liquid metal dealloying[END_REF] . However, the grain microstructure was totally different depending on the initial Ni amount inside the precursor: a low Ni amount led to the formation of a few large grains while a large amount of Ni induced numerous very small grains [START_REF] Mokhtari | Microstructure characterization by X-ray tomography and EBSD of porous FeCr produced by liquid metal dealloying[END_REF] . Therefore, to better understand the different phase transformations occurring during liquid metal dealloying, it is very important to follow the process with an in situ method.

In this paper we are combining various in situ X-ray experimental methods to get a better understanding of the liquid metal dealloying phenomenon. Since measurements of the dealloying process require both high spatial resolution and fast acquisition, the reported experiments are performed at large scale synchrotron facilities. Both steps of the dealloying process are on the one hand, directly imaged by in situ Xray tomography, and on the other, followed by in situ X-ray diffraction. The combination of the two different techniques gives a direct insight into not only the evolution of the microstructure and the morphology, but also the strain field evolution. The in situ nature of the experiments allows us to monitor the samples though the entire process and prevents any possible ambiguity that could arise from an ex situ study.

Materials and methods

Precursors samples preparation

To select suitable precursor alloy composition and metallic melt, mixing enthalpy values are checked. As described in detail in [START_REF] Wada | Dealloying by metallic melt[END_REF] , a negative mixing enthalpy corresponds to soluble components and a positive one to insoluble ones.

In this study, we select a FeCrNi precursor alloy; Ni dissolves in liquid Mg while both Fe and Cr are non-dissolvable into Mg. (FeCr) [START_REF] Renner | In situ x-ray diffraction study of the initial dealloying and passivation of Cu3 Au(111) during anodic dissolution[END_REF] Ni 70 and (FeCr) 70 Ni 30 ingots are prepared using arc melting as previously described in [ 8 , 40 ]. Both precursors exhibit a face-centered cubic (FCC) crystal structure with no allotropic transformation bellow 900 °C [START_REF] Marsh | Limits of new phase in the Fe-Cr-Ni system[END_REF][START_REF] Hayes | Thermodynamics of stainless steels[END_REF][START_REF] Pugh | Iron-chromium-nickel ternary system[END_REF] . In contrast, the Fe 80 Cr 20 targeted composition has a body-centered cubic (BCC) lattice at high temperature; the cooling rate used in the experiment prevents any evolution at low temperature, especially the formation of the gamma-phase [START_REF] Massalski | Fe-Cr phase diagram, binary alloy phase diagrams[END_REF] . The Mg melting temperature is 923 K and the Ni solubility in Mg liquid is at least 18%. The Ni is quasi non-soluble in solid Mg, therefore, if the Ni density is too high, an eutectic Mg/Mg 2 Ni is formed during solidification (visible in Fig. 1 (c) in Okulov et al. [START_REF] Okulov | Anomalously low modulus of the interpenetrating-phase composite of Fe and Mg obtained by liquid metal dealloying[END_REF] ); both phases have a hexagonal crystalline structure (respectively P6 3 /mmc and P6 2 22 for Mg and Mg 2 Ni) [START_REF] Voss | Die Legierungen: nickel-zinn, nickel-blei, nickel-thallium, nickel-wismut, nickel-chrom, nickel-magnesium, nickel-zink und nickel-cadmium[END_REF][START_REF] Straumanis | The precision determination of lattice constants by the powder and rotating crystal methods and applications[END_REF][START_REF] Noréus | Structural studies of hexagonal Mg 2 NiH X[END_REF] .

To reproduce the lab experiment and have an in situ observation of the very same laboratory process, we decided to prepare the precursor with the same experimental procedure as used in previous studies [ 8 , 30 , 39 , 45 ] which does not include annealing prior to dealloying.

The precursor ingots are cold-rolled with a large reduction factor to obtain a thin plate of material. This plate is cut into slices and polished until a 300 μm precursor tip shape is obtained. The electron backscattered diffraction map of this precursor displays a large amount of stored energy within the microstructure and shows almost no trace of the initial as-cast millimetric microstructure, presented in [START_REF] Mokhtari | Microstructure characterization by X-ray tomography and EBSD of porous FeCr produced by liquid metal dealloying[END_REF] . This same study also showed that the microstructure after dealloying, with and without a thermal treatment prior to dealloying, are similar.

To ensure the presence of precursor samples on the center of the setup, precursor tips are fixed with high temperature resistance glue on top of steel sticks, drilled with a 1 mm diameter hole in their center. We observed that Mg clearly reacts locally with the glass tube but we carefully checked that enough liquid Mg remained in contact with the precursor sample to avoid any influence of the parasitic glass/Mg reaction on the dealloying process. The in situ dealloying experiments require a dedicated reactor to handle the liquid magnesium at more than 923 K and a 360°field of view for tomography. It is achieved by encapsulating the precursor and Mg flakes under vacuum in a 2 mm internal diameter quartz tube. An illustration of the set-up is presented on Appendix 1 .

Dealloyed sample preparation

For the in situ chemical etching part, the same precursor samples are cut from the cold-rolled plate with a precision micro-cutting machine into rectangular sheets of 20 × 10 × 1 mm 3 and dealloyed at a temperature of 1093 K for 1 hr in a Mg melt bath. The EBSD maps in [START_REF] Mokhtari | Microstructure characterization by X-ray tomography and EBSD of porous FeCr produced by liquid metal dealloying[END_REF] illustrate the characteristic microstructure of a dealloyed sample: a bicontinuous foam with ligament size of around 5 μm. In this case, the average FeCr grain size is around 30 μm, which implies that each ligament is a single grain.

The obtained FeCr-Mg composites are cut into a 0.5-1 mm x 1 cm rectangular rod and then polished into a tip shape. This FeCr-Mg composite sample is introduced in a 5 mm internal diameter polymer capillary with low concentrated nitric acid (4% volume concentration). The dissolution of the solid-state solution of Mg is followed in situ by tomography and X-ray diffraction. Porous samples elaborated from (FeCr) 30 Ni 70 and (FeCr) [START_REF] Wada | Preparation of hierarchical porous metals by two-step liquid metal dealloying[END_REF] Ni 30 precursors will be referred to as 30%FeCr and 70%FeCr, respectively.

X-ray tomography acquisitions

The dealloying and the etching steps are both followed in situ by Xray phase contrast tomography at Tomcat beamline (SLS, PSI, Switzerland), with an energy of 25 keV on a range of 0-180°rotation with an exposure time of 90 ms, and continuous acquisition of 45 s (dealloying 501 projections) and 135 s (etching 1501 projections) respectively. The full volumes are reconstructed from a phase contrast imaging with an isotropic voxel size of 0.32 μm in lateral dimension in an 8 bit floating point using a single distance phase retrieval algorithm [START_REF] Paganin | Simultaneous phase and amplitude extraction from a single defocused image of a homogeneous object[END_REF] and the GridRec reconstruction algorithm [START_REF] Hintermüller | Image processing pipeline for synchrotron-radiation-based tomographic microscopy[END_REF][START_REF] Marone | Fast reconstruction algorithm dealing with tomography artifacts[END_REF][START_REF] Marone | Regridding reconstruction algorithm for real time tomographic imaging[END_REF] , and are analyzed with Fiji free software [START_REF] Schindelin | Fiji: an open-source platform for biological-image analysis[END_REF] using 3D analysis. For calculating dealloying kinetics and ligament/pore size, we use the Fiji "local thickness " function which enables us to precisely measure the thickness of a phase in a 3D image [START_REF] Hildebrand | A new method for the model-independent assessment of thickness in three-dimensional images[END_REF] . The average thickness corresponds to the top of the thickness value distribution peak in the image. For the dealloying part, to ensure a homogeneous specimen temperature, transparent black X-ray painting was applied on the outside of the tubes. A laser heater [START_REF] Fife | Development of a laser-based heating system for in situ synchrotron-based X-ray tomographic microscopy[END_REF] provided on the Tomcat beamline was used at a power intensity of 16A to heat the sample prior to dealloying. A rough calibration showed that this intensity was just enough to reach a temperature higher than the Mg melting point. Laser heating often results in localized heating but in our case, it was impossible to experimentally control this homogeneity. Note however that our specimen is rather small and that the two lasers used for heating purposes were focused at its tip. As the dealloying process occurs rapidly, there is a risk that Mg flake melting. This was not, however, observed in our experiments and dealloying occurred in a reproducible manner.

X-ray diffraction acquisitions

The dealloying and the etching steps are both followed in situ by transmission X-ray diffraction on the ID11 beamline (ESRF, France) on a 100 μs side window taken at the center of the sample on the top of the tip, with an energy of 35.1 keV, and a ± 1°wobbling movement during acquisitions. The acquisition process comprises 200 ms long exposures followed by 1 s and 10 s breaks for the dealloying and etching steps, respectively (etching kinetics are much slower than those of dealloying). Calibration is carried out using CeO 2 powder. X-ray diffraction ring data is extracted with the caking method in the PyFai software suite [ 55 , 56 ]. Lattice parameters are extracted using the statistical momentum method, based on the approach exhibited by Groma [START_REF] Groma | X-ray line broadening due to an inhomogeneous dislocation distribution[END_REF] . An induction heater is used to heat the sample during the dealloying experiment and is stopped to perform the cooling step. A rough temperature calibration is performed with a thermocouple in contact with a precursor sample inside a quartz crucible (without vacuum encapsulation and Mg). The cooling rate is very difficult to measure precisely but can be estimated at about 17 K/s.

Scanning electron microscopy -electron backscatter diffraction (SEM-EBSD)

(FeCr) [START_REF] Renner | In situ x-ray diffraction study of the initial dealloying and passivation of Cu3 Au(111) during anodic dissolution[END_REF] Ni 70 and (FeCr) 70 Ni 30 precursor sheets ( cf. Section 2.1 ) are dealloyed for 3 min at 933 K to obtain partial dealloying and for us to be able to directly observe the dealloyed grain formation. The SEM-EBSD acquisitions are performed on a JEOL 7100F (JEOL, Japan) and are analyzed with Orientation Imaging Microscopy (OIM) analysis software on crossection polished with Ar ion beam polisher (EM-3500 Hitachi, Japan).

Simulation

To better understand the dealloying kinetics observed experimentally, we adapt a simple diffusion model based on [ 10 , 34 ] to the geometry of the needle-shape samples used in situ experiments. Therefore, the progression of the dealloying front in time, can be modeled cylindrically. Following our previous study [ 10 , 34 ], we consider the sharp-interface problem given by the Fick equation in the dealloyed region (we assume zero diffusion in the precursor) and the Stefan condition giving the velocity of the precursor interface.

𝜕𝑐 ( 𝑟,𝑡 ) 𝜕𝑡 = 𝐷 ∇ 2 𝑐 ( 𝑟, 𝑡 ) , ∀𝑟 ∈ [ 𝑅 ( 𝑡 ) , 𝑅 ∞ ] 𝑑𝑅 𝑑𝑡 = 𝐷 𝑐 0 -𝑐 𝑖𝑛𝑓 ( 𝜕𝑐 𝜕𝑟 )

𝑖𝑛𝑓

Where c(r,t) is the concentration field of the soluble element (here Ni) and R(t) denotes the evolution of precursor radius during its dissolution. D is the effective diffusion coefficient of Ni in the dealloying region. anddenote respectively the concentrations in Ni of the precursor and at the dealloying interface, assumed to be fixed by a local equilibrium condition. Combined with a no-flux boundary condition at . This sharp-interface problem can be solved numerically using finite differences: time and space are discretized with Δx = 0.01 μm and Δt = 10 μs finite steps and a forward Euler scheme is used for the time integration. To mimic experimental conditions, the following values are chosen for the parameters: D = 0.2 10 -9 m. s -2 . Effective diffusion coefficients in liquid metal are usually around D = 10 -9 m. s -2 [START_REF] Frohberg | Odelius Diffusion in liquid alloys under microgravity[END_REF] . However, to the best of our knowledge, there is no reported value for the Ni diffusion coefficient in an Mg melt so we used it as a varying parameter for the model to fit the experimental results. The fitted value has the same order of magnitude as a standard diffusion coefficient of atoms in a metallic melt, much higher than the diffusion coefficient of Ni in solid Mg ( D = 10 -15 m. s -2 ) [START_REF] Pavlinov | Self-diffusion in calcium and diffuse of barely soluble impurities in magnesium and calcium[END_REF]. This lower obtained value can be explained by the presence of solid phase (FeCr ligaments) in the Mg liquid which is not considered in the model. It should also be noticed that this parameter does not change the overall shape of the curve but only the time required to perform dealloying. c_intf is taken equal to 18%, corresponding to the maximum Ni solubility in a Mg bath measured by SEM-EDX after partial dealloying at a low dealloying temperature.

R_0 corresponds to the experimental size measured on the X-ray tomography reconstruction of our precursor sample.

R_intf is equal to 1000 μm corresponding to our quartz crucible radius.

Results

In this section we will analyze the dealloying and etching processes by both X-ray tomography and X-ray diffraction for one precursor composition with a high Ni content ((FeCr) 30 Ni 70 ).

Dealloying process imaged by X-ray tomography

Fig. 1 shows 2D cross-sections extracted from a 3D reconstruction. It corresponds to raw images without further image treatment. The gray values are proportional to the material's absorption (linked to its atomic number), therefore air/vacuum and magnesium are dark-gray while the precursor tip is pale-gray. Due to the use of phase contrast imaging, a contrast between Mg and air can be observed even if their densities are much lower than Ni and Fe. The dealloyed part of the tip, a bi-phased microstructure rich in magnesium, is less attenuating than the precursor phase which contains nickel and it exhibits an intermediate gray value. The dealloyed front is therefore clearly visible. In the background, Mg flakes are visible around the precursor tip. Due to the shape of the Mg flakes, there is a lot of space between the flakes, but it is evident that there is enough magnesium around the tip and touching the precursor to allow the dealloying process to occur.

Heating is started at t = 0 s from room temperature. Dealloying is not observed to occur before 45 s. From t = 90 s to t = 345 s, both precursor and dealloyed phases are visible. At t = 390 s (not shown in Fig. 1 ) the visible part of the sample is dealloyed completely. A first important observation is that the global shape of the sample remains almost unchanged (the volume change corresponds to around 1%, which is included in the error due to the threshold process) during the dealloying process, while the microstructure evolves strongly. For this sample, the dealloying process took approximately 5 mins to be completed, including an incubation time necessary to heat from room temperature. During the heating ramp, the sample moved slightly and acquisitions had to be stopped (between t = 90 s and t = 165 s) to allow us to recenter the sample. Even though the dealloying front moved during the acquisition, reconstructions at low magnification are not blurred, therefore reconstructions can be considered as an average state between the acquisition beginning and end. A systematic error is introduced by considering the reconstruction as the final state.

In the dealloyed area, FeCr ligaments cannot be resolved individually as they are smaller than the voxel. From results performed on Fe-Ni samples, ligament sizes around 0.8 μm are expected [START_REF] Wada | Three-dimensional open-cell macroporous iron, chromium and ferritic stainless steel[END_REF] . The spatial resolution of X-ray imaging detectors is often taken as two times the pixel size [START_REF] Maire | Quantitative X-ray tomography[END_REF] , leading in this case, to a value of 0.64 μm, which is too large to resolve the ligament microstructure. The irregularities of the dealloying front highlighted by red arrows, as observed in Fig. 1 ( t = 165 s / z 1 ) for example, did not seem to be connected to the Mg flake distribution but are similar to observations of grain boundary positions as achieved by [START_REF] Mccue | Kinetics and morphological evolution of liquid metal dealloying[END_REF] . It was previously observed, that dealloying first affects grain boundaries [START_REF] Mccue | Kinetics and morphological evolution of liquid metal dealloying[END_REF] . This would suggest either a precursor with large grains or a cold-rolled precursor which underwent a first step of recrystallization before dealloying started, transforming the highly deformed cold-rolled microstructure into a partially recrystallized microstructure containing large grains [START_REF] Mokhtari | Microstructure characterization by X-ray tomography and EBSD of porous FeCr produced by liquid metal dealloying[END_REF] . Therefore, and from previous studies [START_REF] Mokhtari | Microstructure characterization by X-ray tomography and EBSD of porous FeCr produced by liquid metal dealloying[END_REF] , it can be hypothesized that these irregularities are linked to the position of the grain boundaries. For every reconstructed volume, dealloyed and precursor phases are segmented and phase thickness is measured using Fiji's "local thickness " function. As the tips are manually prepared, cross-sections are not perfectly circular and tip thickness is not constant along the length: tips are thinner on the top (see Fig. 1 ). To quantify the dealloying evolution, only the body part of the tips is used, far from the top, as illustrated in Fig 1 (part below the black dashed lines). From the phase thickness distribution, the 3D average dealloyed phase thickness can be extracted and is shown with black dots and labeled as 3D in Fig. 2 . From Fig. 1 , the 2D dealloying thickness for different heights (z 1 , z 2 , z 3 ) are manually measured by taking the average of around ten measurements and plotted in Fig. 2 (labeled as z 1 , z 2 , z 3 ). Error bars correspond to the standard deviation. At a given time the dealloying thickness along the tip appears rather constant, suggesting that in spite of the heterogeneity of the Mg flake distribution around the tip, the dealloying process occurs everywhere. Moreover, all experimental data are very close, validating the previous assumption that the dealloying rate is homogeneous in the whole sample height. Even if the dealloying rate is higher at grain boundaries, this difference is small enough to lead to an apparent homogeneous behavior. From Fig. 2 , the calculated dealloying rate on the linear part is 0.42 ± 0.03 μm/s and incubation time 61 ± 3 s.

The observation of the dealloying front evolution of Au-Ag precursor by free corrosion on a cylindrical shaped precursor have been observed in [START_REF] Chen-Wiegart | In situ imaging of dealloying during nanoporous gold formation by transmission X-ray microscopy[END_REF] . These authors also demonstrated that the dealloying fron propagated homogeneously in three dimensions leading to the preservation of the sample morphology. The dealloying kinetic curves showed also a linear part. However, the rate was around 17 times lower, probably due to a very low temperature, compared to this experiment where the temperature was higher [START_REF] Chen-Wiegart | In situ imaging of dealloying during nanoporous gold formation by transmission X-ray microscopy[END_REF] . These results confirm similarities in mechanisms between liquid metal dealloying with conventional electrochemical dealloying.

The dealloying kinetics observed in Fig. 2 do not seem to follow a t 1/2 behavior characteristic of a diffusive process and previously observed in post mortem experiments [ 10 , 35 , 37 ]. When comparing these experiments however, the precursor shape is a major difference (a tip, not a plate) therefore diffusion occurs in all directions. To better understand the influence of the precursor shape, simulations are performed assuming a local equilibrium at the dealloying front and a dealloying kinetic limited by the diffusion of Ni in a cylindrical geometry with the data listed in Section 2.6 and is plotted as a continuous line on Fig. 2 . To perform this simulation, R_0 = 160 μm was measured from the X-ray tomography reconstruction. Experimentally, dealloying did not start be-Fig. 3. Evolution of relative strain (continuous lines) and intensity (dashed lines) of 2 different FCC precursors and 2 different BCC dealloyed diffraction peaks during dealloying. The arrows highlight interaction between the 2 phases during the cooling step. fore t = 45 s. However, for the simulation, dealloying started at t = 0 s. Therefore, to compare both results, 2 different axes are used: blue for the experimental data and black for the simulation. The qualitative agreement of the model to the experimental results is good. To match the results, the diffusion coefficient value is adjusted ( D = 0.2 10 -9 m/s). This low value can be explained by the presence of ligaments inside the bath which modifies the kinetics and are not considered in the model. The deviation from the square-root behavior characteristic of diffusionlimited kinetics can be directly related to the sample morphology: the reduction of the dealloying front section during the dealloying process explains the acceleration of the dealloying rate at the end of reaction. Therefore, liquid dealloying kinetics are controlled by the Ni diffusion in the bath.

Dealloying process followed by X-ray diffraction (XRD)

XRD measurements give access to phase quantification and lattice parameters of the phases. The evolution of the different phases during the experiment was estimated by directly following the peak intensity or by following the evolution of the lattice parameter compared to a reference, expressed as an average strain: 𝜀 = (d -d 0 )/ d 0 where d 0 is a selected reference state at room temperature here: first acquisition for the FCC precursor and last acquisition for the BCC dealloyed sample. This is illustrated in Fig. 3 , using the (111) and (200) peaks for the FCC precursor and the (110) and (200) peaks for the BCC dealloyed sample. The intensity of the different peaks is shown using dashed lines while the relative strains are plotted with continuous lines. In this case, following the dealloying steps means following a FCC-BCC phase transformation.

At the beginning, only FCC peaks are present because the precursor is entirely FCC. When heating starts, the relative strain increases because of thermal dilatation. From this curve, the sample temperature is evaluated to be around 938 K, which is consistent with the calibration performed prior to this experiment, with only the precursor tip (around 933 K).

At high temperature, the decrease in intensity for the FCC phase indicates the beginning of the dealloying process: the amount of the FCC phase decreases because the Ni dissolution induces a phase transformation. The newly created BCC phase is detected at around 25 s (increasing BCC peak intensity).

However, the exact time when the two phases coexist is not detectable here as the signal to noise ratio is too low to be analyzed. This can be due to the fact that i) part of the precursor is replaced with the liquid (decrease of the diffracting volume) ii) atoms migrate at the dealloying front leading to a high disorder (loss of coherency) iii) crystallites are very small before coarsening (peak intensity spread due to nanosize effect).

If the sample is kept at high temperature, the microstructure coarsens, leading to an increase in ligament size. Because ligaments are single crystals, the grains grow along with the ligaments. This can explain the increase of the intensity (larger grain, less disorder). From phase diagrams [START_REF] Marsh | Limits of new phase in the Fe-Cr-Ni system[END_REF][START_REF] Hayes | Thermodynamics of stainless steels[END_REF][START_REF] Pugh | Iron-chromium-nickel ternary system[END_REF] and previous studies [ 37 , 39 ], it is known that after the phase transformation, the amount of Ni in the ligaments is still high, while the final amount is measured as null at the end of the experiment. Therefore, there is still Ni dissolution from the BCC phase which explains the shape of the relative strain curves during coarsening, exhibiting reduced cell size, until the remaining Ni in a solid solution diffuses towards Mg [START_REF] Doroeolskii | Solid solutions in the V-Ti, V-Fe, Fe-Cr and Fe-Ni systems[END_REF][START_REF] Dyson | Effect of alloying additions on the lattice parameter of austenite[END_REF][START_REF] Mohammadzadeh | Correlation between stacking fault energy and lattice parameter in nanocrystalline Fe-Cr-Ni austenitic stainless steels by atomistic simulation study[END_REF] .

Literature indicates that the FeCr phase ( 𝛼Fe 75 Cr 25 = 11.7 10 -6 /K at 600 K) has a lower linear dilatation coefficient than the Mg phase ( 𝛼Mg 95 Ni 5 = 29.7 10 -6 /K at 600 K) [START_REF] Touloukian | Thermophysical properties of matter[END_REF] . At dealloying temperature, Mg is liquid so both phases are in equilibrium. The shape of the strain evolution during cooling is mostly due to the temperature change. At the end of cooling, when the magnesium solidifies, the curves become disrupted due to both temperature cooling and possible incompatibility strains building between both interconnected solid metals with two different dilation coefficients. This point is highlighted by an arrow in Fig. 3 . By extrapolating the relative strain slope before phase interactions (around from 95 s to 105 s) during cooling until the 125 s mark, we can estimate the relative strain without thermal residual strain. Then, by subtracting the relative strain without thermal residual strain and the experimentally measured relative strain, the residual thermal strains are estimated between 0.1% and 0.2%. Taking into account the difference in the mechanical properties, the first material, which will present a plastic deformation, is expected to be the Mg phase (the yield strength of pure Mg is about 190 MPa, however the Ni in a solid solution may increase this value [START_REF] Kaye | Tables of Physical and Chemical Constants[END_REF] ). Therefore, while taking FeCr Young's modulus value as 210 GPa and considering the differing thermal expansion coefficient, the maximum residual elastic strain inside FeCr is evaluated to be 0.09%, which is consistent with the measured one.

Etching process imaged by X-ray tomography

To image the etching step of a dealloyed sample using X-ray tomography, a coarsened microstructure is necessary. For this reason, we use a sample dealloyed in the laboratory for 1 hr at 1093 K from a (FeCr) 30 Ni 70 precursor.

Fig. 4 (a) presents a 2D slice extracted from a 3D reconstruction after t = 1048s of etching. Both phases are present: FeCr ligaments (bright) and Mg phase (dark gray). The red ellipse highlights either a microstructural defect such as a precursor grain boundary position, or a defect introduced during the sample preparation prior to the etching process. In this case, this microstructural defect corresponds to a crack due to sample preparation. As mentioned in a previous study, the propagation of the dissolution front is perpendicular to the reaction interface [START_REF] Mokhtari | Cold-rolling influence on microstructure and mechanical properties of NiCr-Ag composites and porous NiCr obtained by liquid metal dealloying[END_REF] . Chemical etching is performed in the whole bulk sample. Fig. 4 (b) shows the evolution of FeCr ligaments and the second phase Mg/air phase thickness during the etching step, measured on a cube of about 100 μm, taken in the center of the tip corresponding to a representative elementary volume taken in a "defect-free " area. At the beginning of the experiment, the second phase corresponds to Mg and during etching it corresponds to a mix of etchant and Mg. At the end, when etching is completed, the second phase corresponds to aqueous liquid only. Both systems present unimodal distribution which is similar to previous studies [ 40 , 67 , 68 ]. The average FeCr ligament size is estimated to be 4.5 ± 0.5 μm similar to that measured in [START_REF] Mokhtari | Microstructure characterization by X-ray tomography and EBSD of porous FeCr produced by liquid metal dealloying[END_REF] and is constant during the process. On the contrary, the average thickness of the Mg/etchant phase increases from 5.5 μm to more than 6.7 μm. The final pore size is consistent with that measured in [START_REF] Mokhtari | Microstructure characterization by X-ray tomography and EBSD of porous FeCr produced by liquid metal dealloying[END_REF] . This shift in the average thickness of Mg/air, means that the space between ligaments becomes larger when the etching step occurs. The FeCr phase volume ratio decreases ( cf. the inset of Fig. 4 (b)) during the process and indicates that the sample expands. It can be noticed that this expansion is greater locally, where the sample presents defects.

From Fig. 4 (a) and all reconstructions, the evolution of the etching front can be measured manually by taking the average of around five Mg phase thickness measurements. The evolution of the etching front is linear with time and can be evaluated to be roughly equal to 20 nm/s (corresponding to an evolution of around 8 voxels for each acquisition) which is quite low to compare with the 130 s of acquisition time. This very low etching rate can be increased by increasing nitric acid concentration [START_REF] Wada | Dealloying by metallic melt[END_REF] .

As mentioned in the previous section, after the cooling process, the FeCr phase is under compression. The suggested lattice strain estimated in the previous section is very small so it cannot be detected in the images visually. However, this global expansion (except peeling) is not observed for bulk samples [START_REF] Mokhtari | Microstructure characterization by X-ray tomography and EBSD of porous FeCr produced by liquid metal dealloying[END_REF] . Before the X-ray tomography experiment, 1 mm side square samples are polished to obtain a < 300 μm diameter tip. Therefore, one can imagine that mechanical stresses are accumu-lated during this preparation. The stress releases observed here denotes the relaxation of mechanical stresses leading to peeling formation due to the cold-rolling step of the precursor sample [START_REF] Detsi | Enhanced Strain in Functional Nanoporous Gold with a Dual Microscopic Length Scale Structure[END_REF] .

Previous studies on dealloyed TiCrZr-Mg to give porous TiCrZr after Mg etching, also showed that TiCrZr ligament sizes were almost not affected by the etching step (slight increase) [START_REF] Chen-Wiegart | 3D morphological evolution of porous titanium by x-ray micro-and nano-tomography[END_REF] . However, these authors calculated a smaller pore thickness than that using Mg ligaments. The difference between these two results can be explained by different measuring techniques: in this study, pore size was measured while in [START_REF] Chen-Wiegart | 3D morphological evolution of porous titanium by x-ray micro-and nano-tomography[END_REF] , pore size was calculated as the ratio between the volume and surface area.

Etching process followed by X-ray diffraction

The etching step is also followed by X-ray diffraction. The reference state (d 0 ) is taken at room temperature prior to the etching solution immersion. Fig. 5 shows the XRD diffraction pattern after chemical etching and the evolution of the relative lattice parameters of the dealloyed phase for 30%FeCr and 70%FeCr samples in red and gray respectively. The acquisition for the 70%FeCr XRD experiment is very noisy due to large grains, implying a more erratic diffraction signal. Despite the very noisy data, two steps can be distinguished. On the first step, up to around 500 s, the lattice parameters are stable because enough Mg should be removed before stress relaxation. A first part, where the Mg/air average thickness is stable, has already been noticed in the previous section. Then the lattice parameters increase by 0.15%. Examining a stainless steel with E = 210 GPa, this strain is equivalent to 315 MPa of residual stress relaxation. A relative strain relaxation of 0.15% is in good agreement compared to the strains created during the cooling step (estimated between 0.1 and 0.2%).

Discussion

In the previous section, we analyzed the dealloying and etching behavior of a (FeCr) 30 Ni 70 precursor. The same procedure is used for analyzing all different precursor compositions and in this section, we will discuss the influence of the Ni content in the precursor on the dealloy-

Discussion on the influence of precursor composition on the etching process

Whereas the strain evolution during the etching process seems similar for different precursor composition ( cf. Fig. 5 ), the acquisition for 70%FeCr XRD experiment is very noisy due to large grains implying lower diffraction signal, therefore it is difficult to discuss the detailed behavior. However, the stress relaxation level seems independent of the initial FeCr/Mg phase ratio.

Contrary to the similarities noticed by X-ray diffraction, a different behavior depending on precursor composition is observed with the X-ray tomography data. For both samples, the etching front is perpendicular to the reaction interface, however the expansion observed for 30%FeCr is not detectable for 70%FeCr as shown in appendix 3 . For the 70%FeCr sample, the FeCr phase thickness, Mg/etchant phase thickness and phase ratio are preserved during the etching process. The preservation of the 70%FeCr shape is probably due to the higher amount of FeCr and a stronger FeCr phase connectivity [START_REF] Mokhtari | Microstructure characterization by X-ray tomography and EBSD of porous FeCr produced by liquid metal dealloying[END_REF] .

Discussion on the influence of precursor composition on the dealloying process

However, the use of two different heaters to perform dealloying in situ leads to a different temperature gradient/temperature that leads to different dealloying kinetics. For this reason, the results obtained from X-ray tomography and X-ray diffraction cannot be directly compared to each other.

Considering the X-ray tomography data, the effect of the amount of the Mg near the sample have been investigated with the simulation tool, by changing the R_intf. If the R_intf decreases, dealloying still occurs. The dealloying kinetics, however, are decreased. If different kinetics are observed between 2 differently composed samples and we are not able to de-correlate the influence of the precursor composition with the amount of Mg, then we are not able to discuss the influence of precursor composition on dealloying kinetics.

However, for all samples (other samples are shown in appendix 2 and 3 ), the dealloying front kinetic is homogeneous within the sample and the tip shape is preserved during the process. The curve of the evolution of dealloying thickness with time also shows a linear section and presents a good agreement with simulation.

On the other hand, the result obtained by diffraction can be analyzed depending on precursor compositions. Fig. 6 (a) displays the evolution of the strain of the dealloyed phase for (FeCr) 30 Ni 70 and (FeCr) 70 Ni 30 precursors, with red and gray lines analyzed on the (111) peak respectively. The choice of the value of d 0 in the strain calculation is always crucial. We chose this reference as the value of d 0 at room temperature, which explains why the strains are identical in the two samples after dealloying and cooling down to room temperature. And the different strain level at high temperature before cooling can possibly be due to a slight variation in the dealloying temperature in these two different experiments. We estimated that a temperature difference of about 60 K could explain the observed strain difference.

While the strain decreases at the beginning of the coarsening step of a dealloyed sample from (FeCr) 30 Ni 70 precursor, the stain increases for the dealloyed sample from (FeCr) 70 Ni 30 precursor which is not consistent with a Ni dissolution from the BCC phase, which leads to a reduction in cell size. Moreover, in our previous studies [ 40 , 70 ] precursor. The main difference comes from the microstructure: the dealloyed area from the (FeCr) 30 Ni 70 precursor presents small grains composed of a couple of ligaments which look randomly oriented while large grains including many ligaments are visible in the dealloyed area from the (FeCr) 70 Ni 30 precursor. This columnar grain suggests an epitaxial grain growth with a grain growth orientation competition [START_REF] Kurtz | Fundamentals of Solidification[END_REF] which can imply the tensile strain observed on Fig. 6 (a) for a dealloying time less than 50 s. Usually, for the FCC/BCC system, the < 100 > direction is the dominant one. However our card is not large enough to be able to make a conclusion about favorite directions [ 72 , 73 ]. From literature, it seems that the large grains observed after dealloying from (FeCr) 70 Ni 30 precursors suggests that their orientation is not linked with the precursor grain orientation. In opposition, the smaller grains observed after dealloying from (FeCr) 30 Ni 70 precursors, compared to the precursor grains, suggest that the precursor and dealloyed grains could have some orientation relationships corresponding to a diffusionless phase transformation [ 74 , 75 ].

Summary of the suggested scenario

Fig. 6 thus highlights the different dealloyed grain transformation mechanisms. We compile all differences between the two samples and explain the different grain formation mechanisms in a schematic in Fig. 7 .

If one considers the same interface precursor/dealloyed sample, when the amount of FeCr is low ( i.e. (FeCr) 30 Ni 70 precursor), the dealloying front reaction moves quickly, which promotes diffusion with the formation of FCC ligaments followed (ligaments in red color) by a displacive transformation to form BCC ligaments leading to a decrease in lattice parameters ( Fig. 6 (a)). As a consequence, the nucleation of new grains is easier ( cf. Fig. 7 (a)). However, when the amount of FeCr is high ( i.e. (FeCr) 70 Ni 30 precursor), the dealloying front reaction moves slowly. Due to their high quantity, Fe and Cr atoms are closer to each other and due to the low dealloying rate, Ni has time to diffuse in Mg, therefore it is easier to have a diffusive phase transformation with the direct formation of BCC ligaments, leading to an epitaxial grain growth rather than nucleation of new grains ( cf. Fig. 7 (b)). This ultimately leads to an increase in the relative strain ( cf. Fig. 6 (a)) [ 71 , 74 ].

Conclusion

Porous FeCr is prepared in situ using liquid metal dealloying by immersing (FeCr) 30 Ni 70 and (FeCr) 70 Ni 30 precursors into a Mg metallic melt bath to create a FeCr-Mg rich bicontinuous structure, then the Mg rich phase is chemically etched.

This entire process is analyzed by X-ray tomography and X-ray diffraction measurements.

For a (FeCr) 30 Ni 70 cylindrical shape precursor, the dealloying kinetics present a large linear section with a dealloying rate of about 0.42 ± 0.03 μm/s constant in the three directions. The morphology of the sample shape is preserved during the dealloying step. Using a phase field model and accounting for the cylindrical sample shape, it is possible to simulate the evolution of the dealloying front. The consistence between experimental and simulated values proves that the process is controlled by the diffusion of Ni in the Mg bath.

XRD measurements show different behavior depending on precursor composition. For a low amount of FeCr at the early stage of coarsening, a slight decrease in the lattice parameter of the BCC phase is observed, while for a sample with a high amount of FeCr, an increase in the lattice parameter is observed. This difference is clarified by the dealloyed grain formation mechanism. On the one hand, in the case of a low FeCr/Ni ratio in the precursor, a displacive transformation occurs, with new grain nucleation leading to the decrease in the crystal lattice when the remaining Ni atoms leave the crystal lattice. On the other hand, in the case of a large FeCr/Ni ratio in the precursor, we observed a diffusive phase transformation with an epitaxial growth leading to tensile stress.

During cooling, the interaction of ligaments and the Mg phase is noticeable. This interaction creates a large residual thermal strain due to the different thermal dilation coefficients and this thermal strain is relaxed during the etching step.

This paper shows the feasibility of in situ observations during the dealloying and etching process with a qualitative analysis with an appropriate set-up. As a perspective, the set-up can be improved to have a better control of temperature and the amount of Mg around the precursor tip, to evaluate the influence of more parameters like precursor composition/preparation or the dealloying temperature on dealloying kinetics.

Fig. 1 .

 1 Fig. 1. Evolution of a dealloying front during the dealloying process from (FeCr)30Ni70 (a) sagittal slices of the sample at different intervals (b) 3 different horizontal slices at 3 intervals corresponding approximately to the position of the dashed colored lines in (a). Black dashed lines correspond to the volume used to quantify the evolution of the dealloying process. Red arrows highlighted some irregularities noticed at the precursor/dealloying part boundaries.

Fig. 2 .

 2 Fig. 2. Evolution of dealloying thickness with time for 2D and 3D measurements (blue axis). The continuous line corresponds to the simulation (black axis).

Fig. 4 .

 4 Fig. 4. (a) 2D view extracted from a 3D reconstruction for t = 1048s. The red ellipse highlights a defect (b) Evolution of FeCr and Mg/air-etchant phase thickness during the sacrificial phase etching step. As inset, the evolution of the FeCr phase volume ratio (relative density) is plotted.

Fig. 5 .

 5 Fig. 5. (a) XRD diffraction pattern after chemical etching ( t = 1700s) (b) Evolution of the relative lattice parameter during the Mg phase etching of 30%FeCr (red) and 70%FeCr samples (gray).

Fig. 6 .

 6 Fig. 6. (a) XRD diffraction pattern of the BCC phase ( t = 80 s) (b) Evolution of relative strain and of BCC dealloyed diffraction peaks (111) during dealloying of a (FeCr) 30 Ni 70 (red) and (FeCr) 70 Ni 30 (gray) precursors (c) IQ + IPF SEM-EBSD map after 3 mins dealloying at 933 K from (FeCr) 30 Ni 70 (left) and (FeCr) 70 Ni 30 (right). The bottom part corresponds to the precursor and the top part to dealloyed portion. Arrows correspond to the cold-rolling direction (RD) and dealloying reaction direction (DD).

  ing and etching behavior by comparing experiments carried out using (FeCr) 30 Ni 70 and (FeCr) 70 Ni 30 precursors.

Fig. 7 .

 7 Fig. 7. Grain formation during dealloying. The red part corresponds to the FCC phase. (a) for a low amount of FeCr, the high kinetics of dealloying promotes a morphological transformation with the formation of FCC ligaments followed by a displacive transformation, (b) for a high amount of FeCr, the slow kinetics of dealloying promotes a diffusive transformation with the direct formation of BCC ligaments.

Appendix 1 .

 1 post mortem XRD acquisition and EBSD maps also show a difference, especially on the dealloyed grain microstructure between (FeCr) 70 Ni 30 and (FeCr) 30 Ni 70 precursor samples. To explain the difference observed between the two samples ( cf. Fig 6 (a)), partial dealloying is performed to directly observe the dealloyed grain formation. Fig. 6 (b) presents the grain microstructure after dealloying for 3 mins at 933 K with Index Quality (IQ) + Inverse Pole Figure (IPF) maps. The top part corresponds to the dealloyed area and the bottom part to the precursor area. Arrows correspond to the cold-rolling direction (RD) and dealloying reaction direction (DD), respectively. The precursor portion is totally recrystallized for the (FeCr) 30 Ni 70 precursor while we observe a partial recrystallization only for the (FeCr) 70 Ni 30 precursor. The deal-Illustration of experimental set-up. loying thickness layers (only partially shown here) are also different: 240 μm for the (FeCr) 30 Ni 70 precursor versus 50 μm for the (FeCr) 70 Ni 30

Appendix 2 .

 2 Sagittal slices extracted from the 3D reconstruction showing the evolution of dealloying front during dealloying process from (FeCr) 70 Ni 30 precursor sample. Light gray and median gray correspond respectively to precursor area and to dealloyed area. Appendix 3. (a) Evolution of dealloying thickness with time from (FeCr) 70 Ni 30 precursor sample. To be able to compare simulation and experimental values, the experimental incubation time was subtracted from the experimental time. The continuous line corresponds to the simulation. (b) Evolution of FeCr and Mg/air phase thickness during sacrificial phase etching step of a dealloyed sample from a (FeCr) 70 Ni 30 precursor.

Acknowledgment

This work was supported by Région Rhone-Alpes, Erasmus + program and the French ministry of research. We acknowledge the Paul Scherrer Institut, Villigen, Switzerland for provision of synchrotron radiation beamtime at beamline TOMCAT of the SLS and European Synchrotron Radiation Facility, Grenoble, France for provision of synchrotron radiation beamtime at beamline ID11. Authors acknowledge François Cadiou and Julie Devillard for their help during synchrotron experiments, Kader Benaziza for manufacturing sample holders and Tomcat and ID11 beamline staff.

Declaration of Competing Interest

The authors have no conflicts of interest to declare.


Keywords: Événements rares, simulation multi-niveaux adaptative, normalité asymptotique, probabilité de fausse alarme

Simulation d'événements rares pour une loi de probabilité fixée Résumé : Cet article traite de la simulation d'événements rares pour une loi de probabilité donnée. Il trouve son origine dans des problèmes d'estimation de fausse alarme en watermarking et fingerprinting, domaines d'applications nouveaux pour les techniques d'événements rares. Nous proposons deux versions de notre algorithme, donnons une étude théorique des propriétés de convergence et détaillons les questions d'implémentation. Ceci est finalement illustré par des simulations dans le domaine du watermarking.

Introduction and motivation

The goal of this work is to deal with rare events for a fixed probability law. Unlike many other works concerning rare event estimation and simulation, we are simply concerned here with events of the type {X ∈ A} for some random element X, with P(X ∈ A) ≪ 1, and with no dynamical model for X (i.e. X is not a process indexed by the time). In order to use the framework developed for Markov processes (see [START_REF] Cérou | Genetic genealogical models in rare event analysis[END_REF][START_REF] Del Moral | Branching and interacting particle interpretation of rare event probabilities[END_REF]), we construct a family of Markov transition kernels whose invariant measures are the law of X restricted on smaller and smaller sets, the smallest being A. As usual when using a splitting technique in rare event simulation, we decompose the rare event in not so rare nested events, with the product of probabilities being the probability of the rare event.

Our motivation for this framework comes from problems occurring in watermarking of digital contents. Here the term watermarking refers to a set of techniques for embedding/hiding information in a digital file (typically audio or video), such that the change is not noticed, and very hard to remove. See [17] for details. In order to be used in an application, a watermarking technique must be reliable.

Here are two application scenarii where a wrong estimation of the probability of error could lead to a disaster.

Copy protection. Assume commercial contents are encrypted and watermarked and that future consumer electronics storage devices have a watermark detector. These devices refuse to record a watermarked content. The probability of false alarm is the probability that the detector considers an original piece of content (which has not been watermarked) as protected. The movie that a user shot during his holidays could be rejected by this storage device. This absolutely non user-friendly behavior really scares consumer electronics manufacturers. In the past, the Copy Protection Working Group of the DVD forum evaluated that at most one false alarm should happen in 400 hours of video [17]. As the detection rate was one decision per ten seconds, this implies a probability of false alarm in the order of 10 -5 . An accurate experimental assessment of such a low probability of false alarm would demand to feed a real-time watermarking detector with non-watermarked content during 40,000 hours, i.e. more than 4 years! Proposals in response of the CPTWG's call were, at that time, never able to guarantee this level of reliability.

Fingerprinting. In this application, users' identifiers are embedded in purchased content. When content is found in an illegal place (e.g. a P2P network), the right holders decode the hidden message, find a serial number, and thus they can trace the traitor, i.e. the customer who has illegally broadcast their copy. However, the task is not that simple because dishonest users might collude. For security reason, anti-collusion codes have to be employed. Yet, these solutions (also called weak traceability codes [START_REF] Barg | Digital fingerprinting codes: problem statements, constructions, identification of traitors[END_REF]) have a non-zero probability of error (defined as the probability of accusing an innocent). This probability should be, of course, extremely low, but it is also a very sensitive parameter: anti-collusion codes get longer (in terms of the number of bits to be hidden in content) as the probability of error decreases. Fingerprint designers have to strike a trade-off, which is hard to conceive when only rough estimation of the probability of error is known. The major issue for fingerprinting algorithms is the fact that embedding large sequences implies also assessing reliability on a huge amount of data which may be practically unachievable without using rare event analysis.

Assumptions and ingredients

We assume that X is a random element on | d for some d > 0, and denote by µ its probability law on the underlying probability space (Ω, F, P). We denote by A the rare set of interest, and we assume that A = {x ∈ | d s.t. Φ(x) ≥ L} for some continuous function Φ : | d → | and some real number L. We also assume that we know how to draw i.i.d. samples from µ. Now to construct the algorithm, we will need to choose the following ingredients.

First we need to choose an increasing sequence in

| {L 0 , . . . , L n }, with L 0 = -∞ and L n = L. If we denote A j = {x ∈ | d , Φ(x) ≥ L j }, we get a family of nested sets | d = A 0 ⊃ A 1 ⊃ • • • ⊃ A n = A such that P(X ∈ A k |X ∈ A k-1 ) is not too small. For indices m > n, we assume that L m = L n and A m = A n . We also need to choose a Markov transition kernel K on | d which is µ-symmetric, that is ∀(x, y) ∈ | 2d , µ(dx)K(x, dy) = µ(dy)K(y, dx).
As a consequence, K has µ as an invariant measure. As we will see in the sequel, the choice of the L j 's can be made adaptive and is thus not an issue. But the choice of the kernel K is crucial. Even if any µ-symmetric kernel would eventually do the job, we need to carefully choose it to make the algorithm efficient. We will discuss this point later on. Now we can consider the following Markov chain: X 0 ∼ µ and the inhomogeneous transitions given by P (X k ∈ dy|X k-1 = x) = M K k (x, dy), with

M K k (x, dy) = K(x, dy)✶ A k (y) + K(x, A c k ) δ x (dy). For k ∈ {0, . . . , n}, let us denote µ k (dx) = 1 µ(A k ) ✶ A k (x) µ(dx) the normalized restriction of µ on A k .
Proposition 1. The measure µ k is invariant by the transition kernel M K k .

Proof We have

x µ k (dx)M K k (x, dy) = x µ k (dx)(K(x, dy)✶ A k (y) + K(x, A c k ) δ x (dy)) = x z µ k (dx)K(x, dz)(✶ A k (z)δ z (dy) + ✶ A c k (z)δ x (dy)) INRIA so that x µ k (dx)M K k (x, dy) = x 1 µ(A k ) ✶ A k (x)µ(dx)K(x, dy)✶ A k (y) + z 1 µ(A k ) ✶ A k (y)µ(dy)K(y, dz)✶ A c k (z) = x 1 µ(A k ) ✶ A k (x)µ(dx)K(x, dy)✶ A k (y) + z 1 µ(A k ) ✶ A k (y)µ(dz)K(z, dy)✶ A c k (z) = µ k (dy).
Proposition 2. For every test function ϕ, for k ∈ {0, . . . , n}, we have the following Feynman-Kac representation

µ k+1 (ϕ) = ❊[ϕ(X k ) k j=0 ✶ Aj+1 (X j )] ❊[ k j=0 ✶ Aj+1 (X j )]
.

Proof We use induction to show that

❊[ϕ(X k ) k j=0 ✶ Aj+1 (X j )] = µ(A k+1 ) µ k+1 (ϕ).
The case k = 0 is obvious. Then assume the property true for k -1. We write, using the Markov property and proposition 1,

❊[ϕ(X k ) k j=0 ✶ Aj+1 (X j )] = ❊[❊[ϕ(X k )✶ A k+1 (X k )|X 0 , . . . , X k-1 ] k-1 j=0 ✶ Aj+1 (X j )] = ❊[M K k (ϕ✶ A k+1 )(X k-1 ) k-1 j=0 ✶ Aj+1 (X j )] = µ(A k ) µ k (M K k (ϕ✶ A k+1 )) = µ(A k ) µ k (ϕ✶ A k+1 ).
Now it is obvious that

µ k (ϕ✶ A k+1 ) = µ k+1 (ϕ) µ(A k+1 ) µ(A k ) .
Then taking the case ϕ = ✶ we have

❊[ k j=0 ✶ Aj+1 (X j )] = µ(A k+1 ),
which concludes the proof.

3 The algorithm

Fixed levels

From proposition 2 we see that we are in the framework of Feynman-Kac formulae, and thus we can construct an approximation of the associated measures using an interacting particle method as the one studied in [START_REF] Moral | Feynman-Kac formulae, Genealogical and interacting particle systems with applications[END_REF]. Basically, at each iteration k, it consists in propagating the particles according to the transitions given by M K k , and then in selecting the particles according to the potentials, here ✶ A k+1 (i.e. a zero-one valued function in this case).

Also note that moving a particle according to M K k is twofold: first we propose a new transition according to K, and accept the transition only if it stays in A k , keeping the old position otherwise. Concerning the approximation of the rare event probability, we just consider the following obvious property

P(X ∈ A n ) = n-1 k=0 P(X ∈ A k+1 |X ∈ A k ) = ❊[ n-1 k=0 ✶ A k+1 (X k )] = n-1 k=0 ❊[✶ A k+1 (X k ) k-1 m=0 ✶ Am+1 (X m )] ❊[ k-1 m=0 ✶ Am+1 (X m )]
.

We see here that we can approximate at each stage P(X ∈ A k+1 |X ∈ A k ) by the proportion of the particles already in the next set, and the total probability is estimated as the product of those. This gives the algorithm 1, which can also be considered in the rare event simulation framework as a kind of importance splitting method, introduced for example by [START_REF] Kahn | Estimation of particle transmission by random sampling[END_REF] in the context of particle physics, or by [START_REF] Villén-Altamirano | RESTART : a straightforward method for fast simulation of rare events[END_REF] in the telecommunication area.

Algorithm 1

Parameters N the number of particles, the sequence {L 0 , . . . , L n } of levels.

Initialization

INRIA

Draw an i.i.d. N -sample ξ j 0 , j = 1, . . . , N of the law µ.

Iterations

for k = 0 to n -1 /* level number */ Let I k = {j / ξ j k ∈ A k+1 }. for j ∈ I k , let ξj k+1 = ξ j k
, and for j ∈ I k , let ξj k+1 be a copy of ξ ℓ k where ℓ is chosen randomly in I k with uniform probabilities.

Let

p k = |I k | N . From each sample ξj k+1 , j = 1, . . . , N , draw a new sample ξj k+1 ∼ K( ξj k+1 , .
).

If ξj

k+1 ∈ A k+1 then let ξ j k+1 = ξj k+1 , and ξ j k+1 = ξj k+1 otherwise. endfor

Output

Estimate the probability of the rare event by PA =

n-1 k=0 p k .
The last set of particles is a (non independent) identically distributed sample of the law of the rare event µ n .

The asymptotic behavior as the number of particles N → ∞ of the interacting particle model we have constructed has been extensively studied in [START_REF] Moral | Feynman-Kac formulae, Genealogical and interacting particle systems with applications[END_REF]. For example Proposition 9.4.1 and Remark 9.4.1 give that

√ N ( PA -P (X ∈ A)) D -----→ N →+∞ N (0, σ 2 )
Unfortunately, the asymptotic variance σ 2 is often not explicit, and depends on the kernel K in a complicated way. All we can say is that it would be minimal if we could (which is obviously unrealistic) draw an i.i.d. sample of the law of X conditionally on the event {Φ(X) ≥ L k } at each step k, or equivalently apply an infinite number of time the kernel M K k at each step k (see section 4.2). In this case, from the discussion in [START_REF] Cérou | Genetic genealogical models in rare event analysis[END_REF], we would have for the asymptotic variance

σ 2 = n-1 k=0 1 -p k p k , with p k = P(Φ(X) ≥ L k |Φ(X) ≥ L k-1
). This in turn would be minimal 1 , for a fixed value of P A and a fixed number of levels, if p k ≡ p 0 for all k. In this case, the asymptotic variance is simply n 1-p0 p0 , with p 0 = (P A )

1 n . If one is not interested in a convergence in distribution like the CLT mentioned above, but only in the variance of our estimate of the rare event probability, then 1 This is a simple constrained optimization problem: min

P n-1 k=0 1-p k p k with the constraint Q n-1 k=0 p k = P A . RR n°6792
we can use the recent non asymptotic results obtained by some of the authors in [START_REF] Cérou | A non asymptotic variance theorem for unnormalized Feynman-Kac particle models[END_REF]. Under some regularity conditions (mainly mixing property of the kernel M K k ), using corollary 5.2 of [START_REF] Cérou | A non asymptotic variance theorem for unnormalized Feynman-Kac particle models[END_REF], we have that: there exist positive constants α k , for 0

≤ k ≤ n -1, such that for N ≥ N 0 = n-1 k=0 α k p k , ❊   PA -P A P A 2   ≤ 4 N 0 N ,
with p k defined as above. If we assume again the very optimistic (and also very unrealistic) case where we have an i.i.d. sample, then all the α j 's are equal to 1, and

N 0 = n-1 k=0 1 p k .
It is also worth mentioning that as discussed in [START_REF] Cérou | A non asymptotic variance theorem for unnormalized Feynman-Kac particle models[END_REF], non asymptotic results can be used to get efficiency result when the probability of the rare event goes to 0, at least for some favorable settings.

Adaptive version of the algorithm

As we may not have a great insight about the law µ, the choice of the levels L 1 , . . . , L n might prove to be quite tricky. For example, we want to avoid the particle system to completely die by choosing two consecutive levels too far apart. As proposed in [START_REF] Cérou | Adaptive multilevel splitting for rare event analysis[END_REF], the level sets can be chosen adaptively, ensuring that the particle system will not die, and that the levels are distributed in a way to minimize the asymptotic variance of the estimate of the rare event probability. The method is very simple. We choose a prescribed success rate p 0 between two consecutive levels. In practice, 0.75 ≤ p 0 ≤ 0.8 works very well. After each application of the kernel M K k , we sort the particles ξ j k+1 according to their scores Φ(ξ j k+1 ). Then we choose as the next level the empirical quantile Lk+1 = Φ(ξ j0 k+1 ) such that a proportion p 0 of the particles are above it. From this level Lk+1 , one defines A k+1 , and the rest of the algorithm is unchanged. We end up with a variant where the levels are evenly spaced in terms of probability of success, which, as mentioned in [START_REF] Lagnoux | Rare event simulation[END_REF] and [START_REF] Cérou | Genetic genealogical models in rare event analysis[END_REF], gives a minimal asymptotic variance. The algorithm then stops when some Ln0+1 ≥ L, and the probability is estimated by PA = p n0 0 r, with r being the actual number of particles in the last iteration being above level L. Note that the number n 0 of steps is in theory random, but with N reasonably large, it is fixed by the ratio of the logarithms log P(X ∈ A)

log p 0 (1)
with a probability very close to 1. The adaptive algorithm is given in Algorithm 2 below. The last set of particles is a (non independent) identically distributed sample of the law of the rare event µ n .

The cost of adaptive levels in term of complexity is just a log N factor (from the quick sort), and in terms of accuracy it introduces a bias which is asymptotically zero, as shown in [START_REF] Cérou | Adaptive multilevel splitting for rare event analysis[END_REF]. But the bias was not much discussed in the latter, so we will give an estimate of it below.

On the bias for the adaptive algorithm

To be able to use results in [START_REF] Cérou | Adaptive multilevel splitting for rare event analysis[END_REF], we will assume, that at each stage, the new sample is i.i.d., or equivalently that we apply the kernel an infinite number of times (see section 4.2 below). This is not realistic, but will provide a useful insight on how much we should worry about the bias. Let us write the rare event probability as p = P A = r p n0 0 , with n 0 = ⌊ log p log p0 ⌋ and r = p p -n0 0 . In the same way we write p = PA = r p n0 0 , with n0 the number of steps before the algorithm stops. As shown in [START_REF] Cérou | Adaptive multilevel splitting for rare event analysis[END_REF], the actual number n0 of steps is equal to n 0 with any large probability provided N is large enough, so we assume all the expectations will be taken on the subset of Ω on which n0 = n 0 .

We denote Z = Φ(X), F the cumulative distribution function of Z, and L n0 the exact level such that P(Z ≥ L n0 ) = p n0 0 . Thus the relative bias is

❊[p] -p p = ❊[r] -r r = ❊[P(Z ≥ L|Z ≥ Ln0 )] -P(Z ≥ L|Z ≥ L n0 ) P(Z ≥ L|Z ≥ L n0 ) = ❊ P(Z ≥ L n0 ) -P(Z ≥ Ln0 ) P(Z ≥ Ln0 ) = ❊ F ( Ln0 ) -F (L n0 ) 1 -F ( Ln0 ) = ❊ W a -W with W = F ( Ln0 )-F (L n0 ) = F ( Ln0 )-(1-p n0 0 )
, and a = 1-F (L n0 ) = p n0 0 ≈ 0. Now considering that (see e.g. [START_REF] Arnold | A first course in order statistics[END_REF])

W a = F ( Ln0 ) -(1 -p n0 0 ) p n0 0 a.s. -----→ N →+∞ 0, we rewrite ❊[p] -p p = 1 a ❊ W 1 1 -W a ,
and make an asymptotic expansion near 0,

❊[p] -p p = 1 a ❊ W (1 + W a + o P ( W a )) = 1 a ❊[W] + 1 a 2 ❊[W 2 ] + 1 a 2 o(❊[W 2 ]).
Then we will use the following lemma.

Lemma 1.

❊[W]

= ❊[F( Ln0 ) -(1 -p n0 0 )] = 0 and ❊[W 2 ] = var(F ( Ln0 ) -F (L n0 )) = n 0 N p 2n0-1 (1 -p) + o( 1 N ).
The proof is left to the appendix. From the lemma, we see that the bias is positive and of order 1 N :

❊[p] -p p ∼ 1 N n 0 (1 -p) p .
Using the result in [START_REF] Cérou | Adaptive multilevel splitting for rare event analysis[END_REF] on the asymptotic variance, we can write the following expansion:

p = p 1 + 1 √ N n 0 1 -p p + 1 -r r X + 1 N n 0 1 -p p + o P ( 1 N ) , INRIA
where X is a standard Gaussian variable. Of course if one does not want any bias, then the solution is to make a first run to compute the levels, and a second run to actually compute the probability, but we can see from the above formula that, for the same computational cost, it is better in term of relative error to use directly our algorithm 2 and compute the levels on the fly. Another remark worth mentioning is that the bias is always positive, giving a slightly over valued estimate. When we deal with catastrophic events, which is usually the case in rare event analysis, and provide an estimate, it is not a bad thing that the real value be a bit lower. This result will be later shown to prove efficient by a numerical example.

4 Tuning the algorithm

Choice of the kernel K

The choice of the transition kernel K is of course critical, and in practice will depend on the application, so that we cannot give a completely general way of finding it. But in the case of a Gibbs measure given by a bounded potential, we can use the Metropolis algorithm, as first proposed by [START_REF] Metropolis | Equation of state calculations by fast computing machines[END_REF], or a variant later proposed by Hastings [START_REF] Hastings | Monte Carlo sampling methods using Markov chains and their applications[END_REF].

Less dependent sample

Unlike all importance sampling based methods, our algorithm gives a sample distributed according to the real law of the rare event µ n , but not independent. This may lead to poor variance behavior in some cases. The samples are not independent because of the splitting of successful particles. But the effect of M K k is towards more independence among particles. Thus we can think of iterating the kernel a fixed number of times, or until a fixed number of particles, say 90 or 95%, have actually moved from their first position (i.e. at least one proposed K transition has been accepted). If we consider all the particles together, each application of the kernel can be seen as applying a kernel (M K k ) ⊗N . It is obvious from proposition 1 that (µ k ) ⊗N (the joint law of an i.i.d. sample) is an invariant measure for (M K k ) ⊗N . Then from [START_REF] Meyn | Markov chains and stochastic stability[END_REF], Proposition 13.3.2, we get that the total variation norm between the law of the sample as we iterate the kernel, and (µ k ) ⊗N , is non increasing. So even if it is not very helpful, these iterations at least do not harm. When the chosen kernel K is of Metropolis-Hastings type, so is M K k (with a potential that can be infinite). Then, using [START_REF] Tierney | Markov chains for exploring posterior distributions[END_REF], we can say a bit more, provided (which is generally the case) that the kernel used for the proposed transitions is aperiodic and irreducible. By Corollary 2 in [START_REF] Tierney | Markov chains for exploring posterior distributions[END_REF], the Metropolis is also Harris recurrent, and then by Theorem 13.3.3 in [START_REF] Meyn | Markov chains and stochastic stability[END_REF], we have for any initial distribution λ λ(dx

)(M K k ) m (x, .) -µ k → 0 when m → +∞,
where the norm is in total variation. Then we have for any initial cloud of particles Ξ = (ξ 1 , . . . , ξ N ), and any test function (φ 1 , . . . , φ N ),

|δ Ξ ((M K k ) ⊗N ) m ( N j=1 φ j ) - N j=1 µ k (φ j )| = | N j=1 (M K k ) m (φ j )(ξ j ) - N j=1 µ k (φ j )| → 0 when m → +∞.
By a standard density argument, we get that for all test functions φ on (

| d ) N , |δ Ξ ((M K k ) ⊗N ) m (φ) -µ ⊗N k (φ)| → 0 when m → +∞.
This means that the more iterations we do with the kernel, the closer we get to an independent sample.

Mixing property of the kernel K

We have written the algorithms using a unique kernel K for all the iterations. Usually it is quite easy to construct not only one, but a family of kernel that are all µ-symmetric, and with different mixing properties. This fact can be useful when we see that, when applying M K k to the current particles, most of the transitions are refused (they are below the current threshold). In this case, we propose to change the kernel K for another one which is less mixing, that is in some way with "smaller steps", thus with a lower probability to go beyond the current level L k . On the other hand, when almost all the transitions are accepted, it means that the kernel is poorly mixing, and that we could decrease the variance by choosing a kernel K that is more mixing, i.e. with "larger steps". For example, in section 6.1 below, this is tuned by changing the parameter α.

Discussion about related works

We will not discuss here the large amount of literature on importance sampling approach, but only focus on interacting particle approaches for the analysis of static rare events. As far as we know, the first work where algorithm 1 was outlined to deal with static rare events is [START_REF] Del Moral | Sequential Monte Carlo samplers[END_REF]. This article is written in a much larger framework, and thus does not deal with the practical details of our precise setting. More recently, and independently from the authors of the present work, a very similar algorithm has been proposed in [START_REF] Botev | An efficient algorithm for rare-event probability estimation, combinatorial optimization, and counting[END_REF]. These authors propose a very similar algorithm, including the use of quantiles of the cost/importance function Φ on the swarm of particles to estimate the next level. One main difference here is that they propose to first run the algorithm just to compute the levels, and then restart from the beginning with the proposed levels (two stage procedure), like in [START_REF] Garvels | The splitting method in rare event simulation[END_REF]. Actually we show here that computing the levels on the fly (within the same run as the one to compute the rare event probability, see algorithm 2 above, one stage procedure) we only pay a small bias on the estimate. In this regard the remark 3.2 page 489 of [START_REF] Botev | An efficient algorithm for rare-event probability estimation, combinatorial optimization, and counting[END_REF] might be misleading: if the levels are chosen from start, or using a preliminary run, then the resulting probability INRIA estimate is unbiased, even if the level crossing probabilities are indeed dependent (see [START_REF] Cérou | Genetic genealogical models in rare event analysis[END_REF]). Note that in [START_REF] Botev | An efficient algorithm for rare-event probability estimation, combinatorial optimization, and counting[END_REF] the general construction of the kernel M K k is not addressed, as the authors consider only examples were they can derive a Gibbs sampler for each µ k . This is mainly possible because their function Φ is linear. Note that the authors stress that in the adaptive levels case, the resulting probability estimate is only asymptotically unbiased. They also mention that to increase the diversity, one can apply the MCMC move several times. Another very similar approach was proposed in the context of combinatorial counting in [START_REF] Rubinstein | The Gibbs cloner for combinatorial optimization, counting and sampling[END_REF]. This work is focused on discrete but very large state space, and mainly on optimization and counting problems in which µ is the uniform probability. The main difference between the proposed algorithm and ours is that, instead of a resampling with replacement procedure, the author uses what he calls a cloning procedure, where the number of offsprings is fixed (i.e. the same for all the particles in the sample), but adaptive to keep the number roughly constant. The algorithm also uses the specificity of the uniform law by removing redundant particles after the MCMC step (actually several applications of the MCMC transition kernel on each particle). This step is called screening. Note also that all the intermediate positions of the MCMC steps are kept, or only a fraction of them if he needs to improve the diversity of the sample. It should be mentioned that the author describes a variant which combines an interacting (cloning) particle approach with an importance sampling step using a change of measure given by cross entropy. Finally, here again the author uses a Gibbs sampler whose invariant law is exactly µ k . We also would like to mention that these last two papers do not provide rigorous mathematical analysis of the convergence properties of the proposed algorithms.

Applications

Zero-bit watermarking

The zero-bit watermarking is a toy example where X is a Gaussian vector in | d , with zero mean and identity covariance matrix, Φ(X) = X,u X and u is a fixed normalized vector. Then the region A = {x ∈ | d s.t. Φ(x) ≥ L} is a cone as shown on figure 1. For a Gaussian distribution, the obvious choice for the kernel is the following. If we start from any point x, then the new position is distributed like

x ′ = x + αW √ 1 + α 2 ,
where W is a N (0, I d ) | d valued random vector and α a positive number.

Note that here we can compare our estimates of the rare event probability with the result of a numerical integration. For example, in our simulations d = 20

and L = 0.95, so that P(Φ(X) ≥ L) ≈ 4.710 -11 . We have run our algorithm in this case with adaptive levels and iterations of the kernel until 90% of the particles have moved at each step.

For several numbers of particles, we have done the complete algorithm 200 times in order to estimate the bias and variance. Figure 2 shows the rate of convergence in N -1 for the relative bias, and figure 3 shows the convergence of u region detection the (normalized by the rare event probability) standard deviation to minimum achievable, which is that of i.i.d. samples at each stage, that is

√ N n 0 1 -p 0 p 0 + r 0
where n 0 is given by equation ( 1), and r 0 is such that P(X ∈ A) = p n0 0 r 0 (see [START_REF] Cérou | Adaptive multilevel splitting for rare event analysis[END_REF]).

Tardos probabilistic codes

We are interested here in embedding an identifier in each copy of a purchased content. Then a copy, maybe the result of several manipulations, or even a collusion, is found on the web, and we want to decide whether or not it can be originated from a certain user. The rare event will be to accuse an innocent user to be guilty for this. The embedded message consists of bits X = (X 1 , . . . , X m ), where each X i is independent from the others, and drawn from a Bernoulli B(p i ). The p i 's are themselves random, drawn from a given distribution with density f on [0, 1]. Then we find a copy with fingerprint y = (y 1 , . . . , y m ) ∈ {0, 1} m . We conclude that a user is guilty if the score S(X) = m i=1 y i g i (X i ) is larger than some value L, for some given functions g i 's. This approach was proposed by Tardos in [START_REF] Tardos | Optimal probabilistic fingerprint codes[END_REF], where he derives good choices for f and the g i 's.

Cérou & al.

To apply our algorithm, we need to choose the kernel K. As the X i 's are independent, we choose randomly r indices {j 1 , . . . , j r } ∈ {1, . . . , m}, with r being a fixed parameter. Then for each j l , we draw a new X ′ j l independently from B(p i ). Extensive numerical results for this type of fingerprinting using our algorithm can be found in [START_REF] Cérou | Experimental assessment of the reliability for watermarking and fingerprinting schemes[END_REF].

A Proof of lemma 1

First of all, some notation. Let U j , j = 1, . . . , N an i.i.d. family of random variables uniformly distributed on (0, 1). We denote by U (j) the jth largest sample. We have then 0 ≤ U (1) ≤ • • • ≤ U (j-1) ≤ U (j) ≤ U (j+1) ≤ • • • ≤ U (N ) ≤ 1. For simplicity, we will assume that p 0 = k N for some 1 ≤ k ≤ N . Then it is well known that (see e.g. [START_REF] Arnold | A first course in order statistics[END_REF] ❊[U (N -k) ] = 1 -p 0 .

(2) Expectation of W . We will show it is zero by induction on n 0 . Case n 0 = 1. F ( L1 ) has the same law as U (N -k) , thus the result is obvious by equation (2).

Induction. Assume ❊[F( Ln0-1 )] = 1p n0-1 . We use the notation: ❋(x, x ′ ) = F (x ′ ) -F (x) 1 -F (x) .

Clearly, we have, with the convention L0 = -∞, Which means that var(F ( Ln0 ) -

F (L n0 )) = 1 N σ 2 n0 + o( 1 N ),
which concludes the proof.

Algorithm 2 ParametersN

 2 the number of particles, the number N 0 < N of succeeding particles, and let p 0 = N 0 /N .INRIAInitializationDraw an i.i.d. N -sample ξ j 0 , j = 1, . . . , N of the law µ.Compute L1 the 1p 0 quantile of Φ(ξ j 0 ), j = 1, . . . , N k = 0;Iterations while Lk+1 < L do Let I k = {j / Φ(ξ j k ) ≥ Lk+1 }. for j ∈ I k , let ξj k+1 = ξ j k ,and for j ∈ I k , let ξj k+1 be a copy of ξ ℓ k where ℓ is chosen randomly in I k with uniform probabilities. From each sample ξj k+1 , j = 1, . . . , N , draw a new sample ξj k+1 ∼ K( ξj k+1 , .). If Φ( ξj k+1 ) ≥ Lk+1 then let ξ j k+1 = ξj k+1 , and ξ j k+1 = ξj k+1 otherwise. Compute Lk+2 the 1p 0 quantile of Φ(ξ j k+1 ), j = 1, . . . , N . k = k + 1; endwhile Let N L the number of particles ξ j k , j = 1, . . . , N , such that Φ(ξ j k ) ≥ L. Output Estimate the probability of the rare event by PA = N L N p k 0 .

Figure 1 :

 1 Figure 1: Detection region.

Figure 2 :

 2 Figure 2: Relative bias.

INRIA

Figure 3 :

 3 Figure 3: Normalized standard deviation.

( 1 -( 1 -

 11 ❋( Lk-1 , Lk )) = 1 -F ( Ln0 ), ❋( Lk-1 , Lk ))] = ❊[❊[1 -❋( Ln0-1 , Ln0 )| Ln0-1 ]

n0- 1 k=1( 1 - 1 k=1( 1 -( 1 -

 11111 ❋( Lk-1 , Lk ))].From lemma 5 in[START_REF] Cérou | Adaptive multilevel splitting for rare event analysis[END_REF], we have for any test function ϕ,❊[ϕ(❋( Ln0-1 , Ln0 ))| Ln0-1 ] = ❊[ϕ(U (N -k) )],from which we have❊[1 -❋( Ln0-1 , Ln0 )| Ln0-1 ] = ❊[1 -U (N -k) ] = p 0 . Thus ❊[1 -F ( Ln0 )] = p 0 ❊[ n0-❋( Lk-1 , Lk ))] = p n0 0 ,using the induction property for n 0 -1, which proves that W has zero mean.INRIAVariance of W . From the proof of theorem 2 in[START_REF] Cérou | Adaptive multilevel splitting for rare event analysis[END_REF], we have√ N n0 k=1 ❋( Lk-1 , Lk ))p n0 Ln0 ) -F (L n0 )) D -----→ N →+∞ N (0, σ 2 n0 ).

  formula (2.2.20) page 14)

RR n°6792