Kai Christian Bader

Tilo Eissler

Nathan Evans

Chris Gauthierdickey

Christian Grothoff

Krista Grothoff

Jeff Keene

Harald Meier

Craig Ritzdorf

Matthew J Rutherford

Tilo Eißler

Distributed Stream Processing with DUP

Keywords: coordination language, parallel programming, productivity

à 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.

Introduction

The widespread adoption of multi-core processors and the commoditization of specialized co-processors like GPUs [START_REF] Lindholm | NVIDIA Tesla: A unified graphics and computing architecture[END_REF] and SPUs [START_REF] Flachs | A stream processing unit for a cell processor[END_REF] requires the development of tools and techniques that enable non-specialists to create sophisticated programs that leverage the hardware at their disposal. Mainstream and productive development cannot rely on teams of domain and hardware experts using specialized languages and hand-optimized code, though this style of development will remain applicable to high-performance computing (HPC) applications that demand ultimate performance.

This paper introduces the DUP System 1 , a language system which facilitates productive parallel programming for stream processing on POSIX platforms. It is not the goal of the DUP System to provide ultimate performance; we are instead willing to sacrifice some performance gain for significant benefits in terms of programmer productivity. By providing useful and intuitive abstractions, the DUP System enables programmers without experience in parallel programming or networking to develop correct parallel and distributed applications and obtain speed-ups from parallelization.

The key idea behind the DUP System is the multi-stream pipeline programming paradigm and the separation of multi-stream pipeline specification and execution from the language(s) used for the main computation. Multistream pipelines are a generalization of UNIX pipelines. However, unlike UNIX pipelines, which are composed of processes which read from at most one input stream and write to a single output stream (and possibly an error stream), multistream pipelines are composed of processes that can read from any number of input streams and write to any number of output streams. In the remainder of this document, we will use the term "stage" for individual processes in a multi-stream pipeline. Note that UNIX users -even those with only rudimentary programming experience -can usually write correct UNIX pipelines which are actually parallel programs. By generalizing UNIX pipelines to multi-stream pipelines, we eliminate the main restriction of the UNIX pipeline paradigmnamely, the inherently linear data flow.

In order to support the developer in the use of multi-stream pipelines, the DUP System includes a simple coordination language which, similar to syntactic constructs in the UNIX shell, allows the user to specify how various stages should be connected with streams. The DUP runtime then sets up the streams and starts the various stages. Key benefits of the DUP System include:

1. Stages in a multi-stream pipeline can run in parallel and on different cores; 2. Stages can be implemented, compiled and tested individually using an appropriate language and compiler for the given problem and architecture; 3. Stages only communicate using streams; streams are a great match for networking applications and for modern processors doing sequential work; 4. If communication between stages is limited to streams, there is no possibility of data races and other issues that plague developers of parallel systems; 5. While the DUP System supports arbitrary data-flow graphs, the possibility of deadlocks can be eliminated by only using acyclic data-flow graphs; 6. Applications built using multi-stream pipelines can themselves be composed into a larger multi-stream pipeline, making it easy for programmers to express hierarchical parallelism

In addition to introducing the DUP System itself, this paper also presents experimental results from a case study involving the DUP System. The case study shows that it is possible to rapidly parallelize and distribute an existing complex legacy bioinformatics application and obtain significant speed-ups using DUP.

Approach

The fundamental goal of multi-stream pipelines is to allow processes to read from multiple input streams and write to multiple output streams, all of which may be connected to produce the desired data-flow graph. This generalization of linear UNIX pipelines can be implemented using traditional UNIX APIs,2 especially the dup2 system call. Where a typical UNIX shell command invocation only connects stdin, stdout and stderr, the DUP System establishes additional I/O streams before starting a stage. Using this method, traditional UNIX filters (such as grep) can be used as stages in the DUP System without modification. New stages can be implemented in any language environment that supports POSIXlike input-output operations (specifically, reading and writing to a file). Since dup2 also works with TCP sockets, the DUP System furthermore generalizes multi-stream pipelines to distributed multi-stream pipelines.

The DUP Assembly Language

The DUP Assembly language allows developers to specify precisely how to connect stages and where those stages should be run. Figure 1 lists the DUP Assembly code for a distributed "Hello World" example program. s @10.0.0.1[0<in.txt,1|g1:0,3|g2:0]$ fanout; g1@10.0.0. Fig. 1. DUP specification. in.txt is passed to fanout ("0<in.txt") which copies the stream to all outputs; in this case output 1 to stream 0 (≡ stdin) at g1 ("1|g1:0") and output 3 to stream 0 at g2 ("3|g2:0"). g1 and g2 run grep, the outputs (1 ≡ stdout) flowing into stage in as streams 0 and 3 respectively. in merges those streams and writes the output into out.txt. The resulting data flow is illustrated in Figure 3.

In essence, the DUP language allows developers to specify a directed graph using an adjacency list representation and IO redirection syntax similar to that of well-known UNIX shells [START_REF] Quigley | UNIX Shells[END_REF]. The nodes in the directed graph are the stages initiated by DUP. A DUP program consists of a list of statements, each of which corresponds to one such node. Statements start with a label that is used to reference the respective stage in the specification of other stages. The keyword DUP is used to reference streams associated with the controlling dup command in the case that the dup command itself is used as a stage.

The label is followed by a hostname specifying on which system the stage will be run. A helper process, dupd, will be started on the specified host, listen on a port to establish network connections and eventually supervise stages run there. The address is followed by a comma-separated list of edges representing primarily the outgoing streams for this stage. Input streams are only explicitly specified in the case of input from files or the controlling dup command. Inputs from other stages are not specified because they can be inferred from the respective entry Fig. 2. Simplified grammar for the DUP Assembly language. Note that we do not expect programmers to need to develop applications by directly using this language in the future; this language is the "assembly" language supported by the DUP runtime system. Higher-level languages running on top of DUP that facilitate (static) process scheduling and aspect oriented programming are under development.

of the producing stage. DUP supports four different ways to create streams for a stage:

Read An input file edge consists of an integer, the "<" operator and a path to the file to be used as input. The integer is the file descriptor from which the stage will read the input stream. dupd is responsible for opening the input stream and validating that the file exists and is readable. Write An output file edge for writing consists of an integer, the ">" operator and a path to the file to be overwritten or created. The integer is the file descriptor to which this stage will write. dupd checks that the specified path can be used for writing.

Append

An output file edge for appending consists of an integer, the ">>" operator and a path to the file. The integer is the file descriptor to which this stage will write. Pipe Non-file output edges consist of an integer, the "|" operator, a stage label, the ":" character and another integer. The first integer specifies the file descriptor to which this stage will write. The label specifies the process on the other end of the pipe or TCP stream and the second integer is the file descriptor from which the other stage will read. If an edge list contains a label that is not defined elsewhere in the configuration file then the program file is considered malformed and rejected by dup.

The final component of a complete stage statement is the command (with arguments) that is used to start the process. Figure 2 contains a formal grammar for the DUP language. The grammar omits I/O redirection from/to the controlling dup command for clarity.

DUP System Architecture

The dup client interprets the mini-language from Section 2.1 which specifies how the various stages for the application should be connected. dup then connects to hosts running ssh servers and starts dupd helper processes which then receive control information via the SSH tunnel. The control information specifies the binary names and arguments for the stages as well as how to establish TCP streams and UNIX pipes to connect the stages with each other.

Figure 3 illustrates how the components of the system work together. The primary interaction between dup and the dupds involves four key steps [START_REF] Grothoff | The DUP protocol specification v2.0[END_REF]:

1. dup starts the dupds and transmits session information. This includes all of the information related to processes that are supposed to be run on the respective dupd. 2. When a stage is configured to transmit messages to a stage initiated by another dupd, the dupd responsible for the data-producing stage establishes a TCP connection to the other dupd and transmits a header specifying which stage and file descriptor it will connect to the stream. If dup is used as a filter, it too opens similar additional TCP streams with the respective dupds. The main difference here is that dup also initiates TCP connections for streams where dup will ultimately end up receiving data from a stage. 3. Once a dupd has confirmed that all required TCP streams have been established, that all required files could be opened, and that the binaries for the stages exist and are executable, it transmits a "ready" message to the controlling dup process (using the connection on which the session information was initially received). 4. Once all dupds are ready, dup sends a "go" message to all dupds. The dupds then start the processes for the session.

Generic DUP Stages

Taking inspiration from stages available in CMS [START_REF] Hartmann | CMS Pipelines Explained[END_REF][START_REF]IBM: CMS Pipelines User's Guide[END_REF], the DUP System includes a set of fundamental multi-stream stages. UNIX already provides a large number of filters that can be used to quickly write non-trivial applications with a linear pipeline. Examples of traditional UNIX filters include grep [START_REF] Goebelbecker | Using grep: Moving from DOS? Discover the power of this Linux utility[END_REF], awk [START_REF] Dougherty | Sed and AWK[END_REF], sed [START_REF] Dougherty | Sed and AWK[END_REF], tr, cat, wc, gzip, tee, head, tail, uniq, buffer and many more [START_REF] Quigley | UNIX Shells[END_REF]. While these standard tools can all be used in the DUP System, none of them support multiple input or output streams. In order to facilitate the development of multi-stream applications with DUP, we provide a set of primitive stages for processing multiple streams. Some of the stages currently included with the DUP System are summarized in Table 1. Many of the stages listed in Table 1 are inspired by the CMS multi-stream pipeline implementation [START_REF]IBM: CMS Pipelines User's Guide[END_REF]. Naturally, we expect application developers to write additional application-specific stages.

DUP Programming Philosophy

In order to avoid the common data consistency issues often found in parallel programming systems, stages and filters for DUP should not perform any updates to shared storage outside of the memory of the individual process. While the DUP System has no way to enforce this property, updates to files or databases could easily cause problems; if stages were allowed to update storage, changes in the order of execution could easily result in unexpected non-determinism. This might be particularly problematic when network latency and stage scheduling cause non-deterministic runs in a larger system that replicates parts of the computation (e.g., in order to improve fault-tolerance).

For applications that require parallel access to shared mutable state, the DUP System can still be used to parallelize (and possibly distribute) those parts that lend themselves naturally to stream processing. Other parts of the code should then be designed to communicate with the DUP parts of the application through streams.

We specifically expect stages developed for the DUP System to be written in many different languages. This will be necessary so that the application can take advantage of the specialized resources available in heterogeneous multi-core or HPC systems. Existing models for application development on these systems often force the programmer to use a particular language (or small set of languages) for the entire application. For example, in a recent study of optimization techniques for CUDA code [START_REF] Ryoo | Optimization principles and application performance evaluation of a multithreaded GPU using CUDA[END_REF], twelve benchmark programs were modified by porting critical sections to the CUDA model. On average, these programs were only 14% CUDA-specific, yet the presence of CUDA sections limits the choice of languages and compilers for the entire program. The implications are clear: the use of a monolithic software architecture for programs designed to operate efficiently on high-performance hardware will severely restrict choices of development teams and possibly prevent them from selecting the most appropriate programming language and tool-chain for each part of a computation. Using the DUP System, developers will be able to compose larger applications from stages written in the most appropriate language available.

Another important use-case for DUP is the parallel and distributed execution of legacy code. In contrast to other new languages for parallel programming, which all too often advocate for large-scale (and often manual) program translation efforts, the DUP philosophy calls for writing thin wrappers around legacy code to obtain a streaming API. As we experienced in our case study, it is typically easy to adapt legacy applications to consume inputs from streams and to produce outputs as streams.

Case Study: Distributed Molecular Sequence String Matching

Exact and inexact string searching in gene sequence databases plays a central role in molecular biology and bioinformatics. Many applications require string searches, such as searching for gene sequence relatives and mining for PCRprimers or DNA-probes in DNA sequences [START_REF] Nordberg | YODA: selecting signature oligonucleotides[END_REF][START_REF] Linhart | The degenerate primer design problem[END_REF][START_REF] Kaderali | Selecting signature oligonucleotides to identify organisms using DNA arrays[END_REF]; both of these applications are important in the process of developing molecular diagnostic assays for pathogenic bacteria or viruses based upon specific DNA amplification and detection.

In the ARB software package, a suffix-tree-based search index, called the PT-Server, is the central data structure used by applications for fast sequence string matching [START_REF] Ludwig | ARB: a software environment for sequence data[END_REF]. A PT-Server instance is built once from the sequence entries of a gene sequence database of interest and is stored permanently on disk.

In order to perform efficient searches, the PT-Server is loaded into main memory in its entirety -if the entire data structure cannot fit into the available main memory (the PT-Server requires ∼ 36 bytes of memory per sequence base), the database cannot be efficiently searched.

In addition to memory consumption, the runtime performance of the search can be quite computationally intensive. An individual exact string search -in practice, short sequence strings of length 15-25 base pairs are searched for -is quick (3-15 milliseconds). However, the execution time can become significant when millions of approximate searches are performed during certain bioinformatic analyses, such as probe design.

In the near future, the number of published DNA sequences will explode due to the availability of new high-throughput sequencing technology [START_REF] Shendure | Next-generation DNA sequencing[END_REF]. As a result, current sequential analysis methods will be unable to process the available data within reasonable amounts of time. Furthermore, rewriting more than halfa-million lines of legacy C and C++ code of the high-performance ARB software package is prohibitively expensive. The goal of this case study was to see how readily the existing ARB PT-Server could be distributed and parallelized using the DUP System. Specifically, we were interested in parallelization in order to reduce execution time and in distribution in order to reduce per-system memory consumption.

Material and Methods

The study used 16 compute nodes of the Infiniband Cluster in the Faculty of Informatics at the Technische Universität München [START_REF] Klug | SILVA: a comprehensive online resource for quality checked and aligned ribosomal RNA sequence data compatible with ARB[END_REF]. Each node was equipped with an AMD Opteron 850 2.4 GHz processor with 8 GB of memory, and the nodes were connected using a 4x Infiniband network. The SILVA database (SSURef 91 SILVA 18 07 07 opt.arb) [16], which stores sequences of small subunit ribosomal ribonucleic acids and consists of 196,890 sequence entries (with 289,563,473 bases), was used for preparing test database sets and respective PT-Servers. We divided the original database into 1, 2, 4, 8, and 16 partitions, and a random sampling algorithm was used for composing the partitioned database sets (within each database analysis set, each partition is about the same size). The PT-Servers used in this study were created from these partitions. Table 2 characterizes the resulting partitions and PT-Servers.

For the queries, we selected 800 inverse sequence strings of rRNA-targeted oligonucleotide probe sequences of length 15-20 from probeBase, a database of published probe sequences [START_REF] Loy | probeBase -an online resource for rRNA-targeted oligonucleotide probes: new features 2007[END_REF]. Each retrieved sequence string has matches in the SILVA database and the respective PT-Server instance. Applying these real world query sequence strings ensured that every search request required non-trivial computation and communication. We generated four sets of inverse sequence strings (400 strings each) by random string distribution of the original dataset from probeBase, and every test run was performed with these four datasets. The presented performance values are the means of the four individually recorded runs.

Adapting ARB for DUP

In the ARB software package, arb probe is a program which performs, per execution, one string search using the PT-Server when a search string and accompanying search parameters are specified (these are passed as command line arguments). For DUP, arb probe had to be modified to read the parameters and the search string as a single line from stdin and pass one result set per line to stdout. It took one developer (who had experience with ARB but not DUP or distributed systems) about three hours to create the modified version arb probe dup and another two hours to compile DUP on the Infiniband Cluster, write adequate DUP scripts and perform the first run-time test. Debugging, testing, optimization and gathering of benchmark results for the entire case study was done in less than two weeks. All searches were conducted using the program arb probe dup with similar parameters: id 1 mcmpl 1 mmis 3 mseq ACGTACGT. The first parameter (id 1) set the PT-Server ID; the second activated the reverse complement sequence (mcmpl 1). For each dataset and approach, the third parameter was used to perform an exact search (mmis 0) in order to find matches identical with the search string and an approximate search (mmis 3) in order to find all identical strings and all similar ones with maximum distance of three characters to the search string. The last parameter indicated the match sequence.

Figure 4 shows the DUP assembly code for the replicated run with two servers. Here, identical PT-Servers are used with the goal of optimizing execution time. Figure 5 shows the equivalent DUP assembly code for the partitioned setting. In this case, since each PT-Server only contains a subset of the overall database, all requests are broadcast to all PT-Servers using fanout.

Results and Discussion

As shown in Table 2, partitioning the original database into n partitions results in almost proportional reductions in per-node memory consumption: doubling the number of partitions means almost halving the memory consumption per s @opt1[0<in.txt,1|r1:0,3|r2:0] $ deal; r1@opt1[1|re:0] $ arb_probe_dup; r2@opt2[1|re:3] $ arb_probe_dup; re@opt2[1>out.txt] $ faninany; Fig. 4. DUP specification for the replicated configuration that uses identical ARB servers. The queries are simply distributed round-robin over the two available ARB PT-Servers and the results collected as they arrive.

s @opt1[0<in.txt,1|p1:0,3|p2:0] $ fanout; p1@opt1[1|pe:0] $ arb_probe_dup; p2@opt2[1|pe:3] $ arb_probe_dup; pe@opt2[1>out.txt] $ gather; Fig. 5. DUP specification for the partitioned configuration where each ARB server only contains a slice of the database. The queries are broadcast to the available ARB PT-Servers and the results collected in round-robin order (to ensure that results for the same query arrive in one batch).

PT-Server partition. practice we expect significantly larger databases to be partitioned, resulting in partition sizes close to the size of the main memory of the HPC node responsible for the partition. Speed-up # Nodes replicated,exact replicated,approximate Fig. 6. Speedup of sequence string matches for the replicated PT-Server. The plot shows the average speed-up over five runs for an exact search and an approximate search (with up to three mismatches).

Figure 6 summarizes the speedup we obtained using n PT-Server replicas (each processing a fraction of the queries). This answers the question as to how much performance could be gained by distributing the queries over n identical (replicated) PT-servers, each containing the full database. Compared with a local version (direct communication between a PT-Server and arb probe dup) we have measured a speedup of 5.84 for 16 compute nodes.

The available bandwidth of the compute cluster using TCP is about 107 MB/s, which is close to the 85 MB/s consumed on average by the collector node for 16 compute nodes. For this run, the average CPU utilization of the 16 compute nodes is about 34% and the master node uses about 56%. The legacy ARB code produces rather verbose output, which explains why this benchmark is IO-bound on our cluster when run with more than approximately 8 compute nodes. Converting the human-readable output to a compact binary format would likely result in a significant performance improvement; however, the purpose of this study was to evaluate possible speed-ups for legacy code without significant changes to the existing infrastructure and changing the message format of the ARB framework would be a significant change.

The overall runtime for querying a partitioned PT-Server with one sequence string set (400 requests) was in a range of 2 seconds (16 partitions) to 8.25 seconds (one partition) for exact searches, and 16 seconds (16 partitions) to 73 seconds (one partition) for approximate searches. For the replicated PT-Servers, execution time for exact searches ranged from approximately 8.3 seconds on one node to 1.5 seconds on 16 nodes. The approximate search (up to three mismatches) ranged from 72 seconds on one node to 13 seconds on 16 nodes. In an additional test run with the replicated servers, we increased the number of requests (to 2000) by repeating the string set to increase the measured time and reduce possible side effects. The execution time ranged from 140.91 seconds (one node) to 27.09 seconds (16 nodes) for exact searches, and 1479.60 seconds (one node) and 222.26 (16 nodes) for the approximate search.

Conclusion and Future Work

The speed-ups achieved in this case study are by themselves clearly not sensational; however, the ratio of speedup to development time is. Programmer productivity is key here, especially since researchers in bioinformatics are rarely also experts in distributed systems. Furthermore, the improvements in performance and memory consumption are significant and have direct practical value for molecular biologists and bioinformaticians, especially since, aside from the acceleration of sequence string searches by a factor 3.5 to 5.8, this approach also offers biologists the possibility to search very large databases using the ARB PT-Server without having to access special architectures with extreme extensions to main memory.

In the future, we plan to use DUP to drive large-scale bioinformatics analyses. Depending on the problem size, we also expect to use DUP to combine partitioning and replication in one system. For example, it would be easy to create n replicas of m partitions in order to improve throughput while also reducing the memory consumption of the PT-Servers. Finally, assuming additional performance is desired, the ARB data format could be changed to be less verbose and thereby avoid bandwidth limitations.

The closest work to the DUP System presented in this paper are multi-stream pipelines in CMS [START_REF]IBM: CMS Pipelines User's Guide[END_REF]. CMS multi-stream pipelines provide a simple mini-language for the specification of virtually arbitrary data-flow graphs connecting stages from a large set of pre-defined tools or arbitrary user-supplied applications. The main difference between CMS and the DUP System (which uses parallel execution of stages) is that CMS pipelines are exclusively record-oriented and implemented through co-routines using deterministic and non-preemptive scheduling with zero-copy data transfer between stages. CMS pipelines were designed for efficient execution in a memory-constrained, single-tasking operating system with record-oriented files. In contrast, DUP is designed for modern applications that might not use record-oriented I/O and need to run in parallel and on many different platforms.

Another close relative to the DUP System are Kahn Process Networks (KPNs) [START_REF] Kahn | The semantics of a simple language for parallel programming[END_REF]. A major difference between DUP and KPNs is that buffers between stages in DUP are bounded, which is necessary given that unbounded buffers cannot really be implemented and that in general determining a bound on the necessary size of buffers (called channels in KPN terminology) is undecidable [START_REF] Parks | Bounded Scheduling of Process Networks[END_REF]. Note that the UNIX command buffer can be used to create buffers of arbitrary size between stages in DUP. Another major difference with KPNs is that DUP does not require individual processes to be deterministic. Non-determinism on the process level voids some of the theoretical guarantees of KPNs; however, it also enables programmers to be much more flexible in their implementations. While DUP allows non-determinism, DUP programmers explicitly choose nondeterministic stages in specific places; as a result, non-determinism in DUP is less pervasive and easier to reason about compared to languages offering parallel execution with shared memory.

Where CMS pipelines focus on the ability to glue small, reusable programs into larger applications, the programming language community has extended various general-purpose languages and language systems with support for pipelines. Existing proposals for stream-processing languages have focused either on highlyefficient implementation (for example, for the data exchange between stages [START_REF] Giacomoni | Fastforward for efficient pipeline parallelism: a cache-optimized concurrent lock-free queue[END_REF]) or on enhancing the abstractions given to programmers to specify the pipeline and other means of communication between stages [START_REF] Thies | Streamit: A language for streaming applications[END_REF]. The main drawback of all of these designs is that they force programmers to learn a complex programming language and rewrite existing code to fit the requirements of the particular language system. The need to follow a particular paradigm is particularly strong for real-time and reactive systems [START_REF] Spring | Streamflex: high-throughput stream programming in java[END_REF][START_REF] Lee | Ptolemy project[END_REF]. Furthermore, especially when targeting heterogeneous multi-core systems, quality implementations of the particular language must be provided for each architecture. In contrast, the DUP language implementation is highly portable (relying exclusively on canonical POSIX system calls) and allows developers to implement stages in any language.

On the systems side, related research has focused on maximizing performance of streaming applications. For example, StreamFlex [START_REF] Spring | Streamflex: high-throughput stream programming in java[END_REF] eliminates copying between filters and minimizes memory management overheads using types. Other research has focused on how filters should be mapped to cores [START_REF] Kudlur | Orchestrating the execution of stream programs on multicore platforms[END_REF] or how to manage data queues between cores [START_REF] Giacomoni | Fastforward for efficient pipeline parallelism: a cache-optimized concurrent lock-free queue[END_REF]. While the communication overheads of DUP applications can likely be improved, this could not be achieved without compromising on some of the major productivity features of the DUP System (such as language neutrality and platform independence).

In terms of language design and runtime, the closest language to the DUP Assembly language is Spade [START_REF] Hirzel | Spade language specification[END_REF] which is used to write programs for InfoSphere Streams, IBM's distributed stream processing system [START_REF] Amini | Spc: A distributed, scalable platform for data mining[END_REF]. The main differences between Spade and the DUP Assembly language is that Spade requires developers to specify the format of the data stream using types and has built-in computational operators. Spade also restricts developers of filters to C++; this is largely because the InfoSphere runtime supports migrating of stages between systems for load-balancing and can also fuse multiple stages for execution in a single address space for performance. Dryad [START_REF] Isard | Dryad: Distributed dataparallel programs from sequential building blocks[END_REF] is another distributed stream processing system similar to Spade in that it also restricts developers to developing filters in C++. Dryad's scheduler and fault-tolerance provisions further require all filters to be deterministic and graphs to be free of cycles, making it impossible to write stages such as faninany or holmerge in Dryad. In comparison to both Spade and Dryad, the DUP System provides a simpler language with a much more lightweight and portable runtime system. DUP also does not require the programmer to specify a specific stream format, which enables the development of much more generic stages. Specifically, the Spade type system cannot be used to properly type stream-format agnostic filters such as cat or fanout. Finally, DUP is publicly available whereas both Spade and Dryad are proprietary.

DUP is a coordination language [START_REF] Gelernter | Coordination languages and their significance[END_REF] following in the footsteps of Linda [START_REF] Carriero | Linda in context[END_REF]: the DUP System is used to coordinate computational blocks described in other languages. The main difference between DUP and Linda is that in DUP, the developer specifies the data flow between the components explicitly, whereas in Linda, the Linda implementation needs to match tuples published in the tuplespace against tuples published by other components. The matching of tuples in the Linda system enables Linda to execute in a highly dynamic environment where processes joining and leaving the system are easily managed. However, the matching and distribution of tuples also causes significant performance issues for tuplespace implementations [START_REF] Wells | A Programmable Matching Engine for Application Development in Linda[END_REF]. As a result, Linda implementations are not suitable for distributed stream processing with significant amounts of data.

Conclusion

The significant challenges with writing efficient parallel high-performance code are numerous and well-documented. The DUP System presented in this paper addresses some of these issues using multi-stream pipelines as a powerful and flexible abstraction around which an overall computation can be broken into independent stages, each developed in the language best suited for the stage, and each compiled or executed by the most effective tools available. Our experience so far makes us confident that DUP can be used to quickly implement parallel programs, to obtain significant performance gains, and to experiment with various dataflow graph configurations with different load-distribution characteristics.

  <LABEL> '@' <ADDRESS> '[' <EDGELIST> ']' '$' <COMMAND> ';' <EDGELIST> ::= <EDGE> (',' <EDGE>)* <EDGE> ::= <INTEGER> <OP> <NODE> <NODE> ::= <REMOTEPR> | <UNIX_PATH> <REMOTEPR> ::= <LABEL> ':' <INTEGER> <OP> ::= '|' | '<' | '>' | '>>'

Fig. 3 .

 3 Fig. 3. Overview for one possible configuration of the DUP System. Red (dashed) lines show application data flow. Black (solid) lines correspond to actions by DUP. Examples for DUP Assembly corresponding to the illustration are given in Figures 1, 4 and 5 respectively: the three code snippets specify the same data-flow graph, but with different commands.

Table 1 .

 1 Summary of general-purpose multi-stream stages to be used with DUP in addition to traditional UNIX filters. Most of the filters above can either operate lineby-line in the style of UNIX filters or using a user-specified record length.

	Stage	Description	I/O Streams
			in	out
	fanout	Replicate input n times	1	n
	faninany Merge inputs, any order	n	1
	gather	Merge inputs, round-robin (waits for input)	n	1
	holmerge Forward input from stream that has sent the most data so	n	1
		far, discard data from other streams until they catch up
	deal	Split input round robin to output(s), or per control stream	2	n
	mgrep	Like grep, except non-matching lines output to secondary	1	2
		stream
	lookup	Read keys from stream 3; tokens to match keys from stream	2	3
		0; write matched tokens to 1, unmatched to 4 and unmatched
		keys to 5
	gate	forward 1st input to 1st output until 2nd input ready	2	1

Table 2 .

 2 Resulting problem sizes for the different numbers of partitions. This table lists the average number of sequences and bases for the PT-Server within each partition and the resulting memory consumption for each PT-Server as well as the total memory consumption for all partitions.

	# Part. # Sequences # MBases Memory (MB)
			Part.	total
	1	196,890	289.6 1,430	1,430
	2	98,445	144.7 745	1,489
	4	49,222	72.4 402	1,609
	8	24,611	36.2 231	1,849
	16	12,305	18.1 145	2,327

Available at http://dupsystem.org/

The APIs needed are supported by all platforms conforming to the POSIX standard, including BSD, GNU/Linux, OS X, and z/OS.

Acknowledgements

The authors thank Prof. Dr. Matthias Horn, University of Vienna, for providing us with probe sequences from probeBase for the bioinformatics case study. This work was funded in part by the Deutsche Forschungsgemeinschaft (DFG) under ENP GR 3688/1-1 and by the Bayerische Forschungsstiftung (BFS) under AZ 767-07 (the NANOBAK Projekt).


Céline Duval

When is it no longer possible to estimate a compound Poisson process?

Keywords: AMS subject classifications: 62B15, 62K99, 62M99 Discretely observed random process, Compound Poisson process, Information loss

We consider centered compound Poisson processes with finite variance, discretely observed over [0, T ] and let the sampling rate ∆ = ∆ T → ∞ as T → ∞. From the central limit theorem, the law of each increment converges to a Gaussian variable. Then, it should not be possible to estimate more than one parameter at the limit. First, from the study of a parametric example we identify two regimes for ∆ T and we observe how the Fisher information degenerates. Then, we generalize these results to the class of compound Poisson processes. We establish a lower bound showing that consistent estimation is impossible when ∆ T grows faster than √ T . We also prove an asymptotic equivalence result, from which we identify, for instance, regimes where the increments cannot be distinguished from Gaussian variables.

Introduction 1.Motivation and statistical setting

Continuous diffusive models are often used for phenomena observed at large sampling rate, even though they present discontinuities or jumps at lower frequencies. For example in finance, asset prices or volumes change at discrete random times (see for instance Gerber and Shiu [START_REF] Gerber | Pricing perpetual options for jump processes[END_REF], Russell and Engle [START_REF] Russell | A discrete-state continuous-time model of financial transactions prices and times[END_REF] or Guilbaud and Pham [START_REF] Guilbaud | Optimal high-frequency trading in a pro-rata microstructure with predictive information[END_REF]), however it is common to use continuous diffusive processes to model them when the sampling rate is large (see e.g. Masoliver et al. [START_REF] Masoliver | Direct and inverse problems with some generalizations and extensions[END_REF], Önalan [START_REF] Önalan | Fractional Ornstein-Uhlenbeck Processes Driven by Stable Lévy Motion in Finance[END_REF] or Hong and Satchell [START_REF] Hong | Defining Single Asset Price Momentum in Terms of a Stochastic Process[END_REF]). This opposition in the observations' behavior between small frequencies and large sampling rate is evoked in Cont and de Larrard [START_REF] Cont | Price dynamics in a Markovian limit order market[END_REF]: "over time scales much larger than the interval between individual order book events, prices are observed to have diffusive dynamics and modeled as such." In physics the opposition between large scale diffusive behavior and point process at small scale is also popular (see e.g. Metzler and Klafter [START_REF] Metzler | The restaurant at the end of the random walk: recent developments in the description of anomalous transport by fractional dynamics[END_REF] or Uchaikin and Zolotarev [START_REF] Uchaikin | Chance and stability. Stable Distributions and their Applications[END_REF]). The usual justification for using diffusive approximations is as follows. Suppose we have discrete observations of a centered pure jump process X observed at a sampling rate ∆ > 0, e.g. a centered compound Poisson process with finite variance, namely we observe X ∆ , . . . , X ⌊T ∆ -1 ⌋∆ .

(

) 1
To lighten notation we set n T := ⌊T ∆ -1 ⌋, the number of observations. We make explicit the dependence in T since it is the asymptotic of the paper. If ∆ is large, between two observations of X many jumps occurred, the central limit theorem gives for every increments the approximation

X i∆ -X (i-1)∆ ≈ σ W i∆ -W (i-1)∆
where W is a standard Wiener process and σ is positive. Hence, only the variance parameter σ 2 should be identifiable from [START_REF] Alexandersson | A Simple Stochastic mode of a Precipitation Process[END_REF]. If X depends on more parameters their identifiability should be lost. Yet the use of diffusive approximations conceals the jump's dynamic observed at lower frequencies. The following questions naturally come across.

i) Is it possible to estimate the parameters characterizing X from (1)?

ii) Is the experiment generated by [START_REF] Alexandersson | A Simple Stochastic mode of a Precipitation Process[END_REF] asymptotically equivalent to a Gaussian experiment when ∆ = ∆ T → ∞ as T → ∞?

The asymptotic equivalence of a Poisson experiment with variable intensity has been studied in Brown et al. [START_REF] Brown | Equivalence theory for density estimation, Poisson processes and Gaussian white noise with drift[END_REF]. Shevtsova [START_REF] Shevtsova | On the accuracy of the normal approximation to the distributions of Poisson random sums[END_REF] looks at the accuracy of Gaussian approximations for Poisson random sums.

Definition 1. Observations (1) are said to be on a macroscopic regime if ∆ = ∆ T → ∞ and T /∆ T → ∞ as T → ∞.

The condition T /∆ T → ∞ ensures there are asymptotically infinitely many observations (⌊T ∆ -1 ⌋ → ∞ as T → ∞). A typical example of macroscopic regime is a sampling rate ∆ T of the order of T α as T → ∞ for α in (0, 1) as T → ∞. In this paper we restrain our study to homogeneous compound Poisson processes. A compound Poisson process X is defined as

X t = Rt i=1 ξ i , t ≥ 0
where R is a Poisson process of intensity λ and (ξ i ) are independent and identically distributed random variables independent of R. The process X is characterized by the the pair r = (λ, f ), where f is the probability law of ξ 1 . We denote by P the class of compound Poisson processes.

Main results

Investigating questions i) and ii) directly is difficult. Hence in Section 2 we first build and study a toy model: a compound Poisson process plus a drift that depends on a 2-dimensional parameter. This process does not belong to P. From this toy model, we identify two distinct macroscopic regimes,

• A regime where ∆ goes to infinity faster than √ T , where the parameters cannot be consistently estimated from [START_REF] Alexandersson | A Simple Stochastic mode of a Precipitation Process[END_REF], providing a negative answer to i) (see Theorem 1 hereafter).

• A regime where ∆ goes to infinity slower than √ T , where the parameters can be estimated answering positively to i). However, optimal rates are much slower than usual parametric ones (see Proposition 1 hereafter).

From the study of the toy model, we derive a lower bound in Theorem 2. It identifies regimes in which consistent estimation of the law generating a process in P is impossible, leading to a negative answer to i). Theorem 3 gives an asymptotic equivalence result; according to the behavior of ∆ T with regard to T , the following occurs.

• The experiment generated by the observation of a process in P is asymptotically equivalent to a Gaussian experiment, answering positively to ii).

• Compound Poisson processes depending on a large number of parameters are not identifiable, providing a negative answer to i). The limit number of parameters beyond which consistent estimation is not possible is made explicit.

This paper is organized as follows, in Section 2 we construct and study our toy model. In Section 3 we establish the main Theorems 2 and 3. A discussion is proposed in Section 4. Finally, Section 5 is devoted to the proofs.

Information loss: A parametric example 2.1 Building up a parametric model

Consider the Lévy process Y defined by

Y t = X t - λt β = Rt i=1 ξ i - λt β , t ≥ 0, ( 2
)
where R is Poisson process of intensity λ ∈ (0, ∞) independent of (ξ i ) i≥0 which are independent and exponentially distributed random variables with parameter β ∈ (0, ∞).

Due to the drift part, Y does not belong to P (unlike X). This model, known as the Cramér-Lundberg model, is used by insurance companies to model big claims of subscribers (see e.g. Embrechts et al. [START_REF] Embrechts | Modeling Extremal Events[END_REF] or Miksoch [START_REF] Mikosch | Non-life Insurance Mathematics: An Introduction with the Poisson Process[END_REF]). Without the drift part, it is also used in Alexandersson [START_REF] Alexandersson | A Simple Stochastic mode of a Precipitation Process[END_REF] to model rainfall.

Suppose we observe ⌊T ∆ -1 ⌋ increments of Y , conditional on the event {R i∆ -R (i-1)∆ = 0}. Namely we observe Y over [0, S(T )∆] at a sampling rate ∆ > 0, where S(T ) is random and such that

S(T ) i=1 1 {R i∆ -R (i-1)∆ =0} = ⌊T ∆ -1 ⌋. Remark 1.
The following results on S(T ) can be easily checked. Since the probability of occurrence of a zero increment of X is e -λ∆ , we have

P(S(T ) = ⌊T ∆ -1 ⌋) = 1 -(1 -e -λ∆ ) ⌊T ∆ -1 ⌋ ∼ ⌊T ∆ -1 ⌋e -λ∆ → 0 as T → ∞
if ∆ goes to infinity as a power of T . Moreover, S(T ) is negative binomial with parameters (1e -λ∆ , ⌊T ∆ -1 ⌋).

Define J = {i ∈ {1, . . . , S(T )}, R i∆ -R (i-1)∆ = 0}, by construction |J| = ⌊T ∆ -1 ⌋.
Consider the ⌊T ∆ -1 ⌋ independent and identically distributed observations

Y = Y i∆ T -Y (i-1)∆ T = Y i ∆ -Y (i-1)∆ |R i∆ -R (i-1)∆ = 0, i ∈ J . (3)
We introduce the family of experiments indexed by ∆ generated by the conditional observations (3)

Y ∆ := R ⌊T ∆ -1 ⌋ , P(R ⌊T ∆ -1 ⌋ ), { P T,∆ θ , θ ∈ Θ}
, where θ denotes the unknown parameter θ = (λ, β) ∈ Θ = (0, ∞) × (0, ∞) and P T,∆ θ the law of Y .

Remark 2. The natural experiment to work with is the experiment

Y ∆ generated by the observations of ⌊T ∆ -1 ⌋ increments of Y Y = Y i∆ -Y (i-1)∆ , i = 1, . . . , ⌊T ∆ -1 ⌋ .
But the law of Y is not dominated and the Fisher information in Y ∆ does not exist. Indeed the distribution of Y ∆ can be decomposed in

P(R ∆ = 0)δ {-λ∆ β } (•) + P(R ∆ > 0) p ∆,θ (•),
where p ∆,θ is dominated by the Lebesgue measure but δ{-λ∆ β }, the mass concentrated at -λ∆ β , cannot be dominated over Θ. Removing null increments of the Poisson part gives the experiment Y ∆ , dominated by the Lebesgue measure, where the Fisher information exists. Since the probability of a null increments of X is e -λ∆ , which is negligible as ∆ → ∞, we show in Section 2.4 that the results established for Y hold also for Y : the experiments Y ∆ and Y ∆ are asymptotically equivalent.

The intuition of the problem is the following, as ξ 1 has finite variance, the central limit theorem applies for each increments and gives for i in J

Y i∆ T -Y (i-1)∆ T √ ∆ T d -→ N 0, 2λ β 2 , as T → ∞.
Thus each observation converges in law to a Gaussian random variable depending on one parameter: the parameter θ should no longer be identifiable when ∆ gets large, only the ratio λ/β 2 should be.

Study of the Fisher information

The increments of Y are independent and identically distributed, it follows that the Fisher information of Y ∆ satisfies

I ⌊T ∆ -1 ⌋,∆ (θ) = ⌊T ∆ -1 ⌋I 1,∆ (θ)
where I 1,∆ (θ) is the Fisher information corresponding to one increment. It has no closed form expression but the following Proposition gives its asymptotic behavior.

Proposition 1. Let ∆ = ∆ T such that ∆ T → ∞ and T /∆ T → ∞ as T → ∞. Then lim T →∞ I 1,∆ T (θ) = I(θ) := 1 2λ 2 -1 λβ -1 λβ 2 β 2
and the eigenvalues of

I ⌊T ∆ -1 T ⌋,∆ T (θ)
, denoted e 1,∆ T (θ) and e 2,∆ T (θ), satisfy

e 1,∆ T (θ) = 2 β 2 + 1 2λ 2 ⌊T ∆ -1 T ⌋ + 3(7β 4 +40β 2 λ 2 +56λ 4 ) 8β 2 λ 3 (β 2 +4λ 2 ) ⌊T ∆ -1 T ⌋ ∆ + O ⌊T ∆ -1 T ⌋ ∆ 3/2 T e 2,∆ T (θ) = 3 4β 2 λ+16λ 3 ⌊T ∆ -1 T ⌋ ∆ + O ⌊T ∆ -1 T ⌋ ∆ 3/2 T .
Remark 3. The matrix I(θ) is the Fisher information of an experiment consisting in one variable of distribution N (0, 2λ/β 2 ).

From Proposition 1, whenever ∆ T goes to infinity faster than √ T the Fisher information degenerates to a rank 1 matrix: the second eigenvalue e 2,∆ T goes to 0 as ⌊T ∆ -1 T ⌋/∆ T ∼ T /∆ 2 T . Theorem 1 below shows that it is indeed not possible to build a consistent estimator of θ in those scales. Conversely, when ∆ T is slower than √ T , both eigenvalues of the Fisher information go to infinity. Since the experiment Y ∆ is regular we deduce that the parameter θ remains identifiable and that consistent estimators of θ do exist. This is surprising, even if each observation is close to a Gaussian variable depending on one parameter, the whole sample still permits to estimate consistently all unknown parameters. However the optimal rate of convergence, determined by the slowest eigenvalue e 2,∆ T (θ), is in (⌊T ∆ -1 T ⌋/∆ T ) 1/2 . It is much slower than usual parametric rates in ⌊T ∆ -1 T ⌋ 1/2 , the square root of the sample size.

A lower bound

In what follows • denotes a norm on R 2 . Define the diameter of a set A as

diam(A) = sup a 1 ,a 2 ∈A a 2 -a 1 . Theorem 1. Let ∆ T be such that ∆ T → ∞ and T ∆ -2 T → l ∈ [0, ∞) as T → ∞.
Then, for all θ 0 ∈ Θ and δ > 0 there exists V δ (θ 0 ) ⊂ Θ a neighborhood of θ 0 such that diam(V δ (θ 0 )) ≤ δ and lim

T →∞ inf θ sup θ∈V δ (θ 0 ) E ⌊T ∆ -1 T ⌋ P θ θ -θ > 0
where the infimum is taken over all estimators.

From Theorem 1, there is no consistent estimator of θ when ∆ T grows rapidly to infinity, faster than √ T . This was expected as the Fisher information degenerates to a rank 1 matrix in those regimes (see Proposition 1). Notice that if Theorem 1 holds for every δ > 0, possibly small, it is not uniform in δ. It is not possible to apply it along a vanishing sequence of δ.

Generalization to the unconditional experiment

The asymptotic equivalence of Y ∆ and Y ∆ (defined in Remark 2) is an immediate consequence of the following Lemma. Lemma 1. Define the probability measures,

p n (θ, x) = f n (θ, x)dx q n (θ, x) = a n (θ)w n,θ (dx) + (1 -a n (θ))f n (θ, x)dx,
where θ ∈ Σ, where Σ is a compact subset of R d , d ≥ 1, a n (θ) ∈ (0, 1), f n (θ, •) is a density absolutely continuous with respect to the Lebesgue measure and w n,θ is a probability measure. Consider the statistical experiments E n and G n generated by the independent and identically distributed observation of n random variables of density p n (θ, •) and q n (θ, •) respectively. If sup θ∈Σ a n (θ) = o( 1 n ), then E n and G n are asymptotically equivalent. Proof of Lemma 1 is given in Section 5. Since Y is a Lévy process, observations Y , and Y , are independent and identically distributed. The distribution of Y ∆ is

p ∆,θ (x) = e -λ∆ δ {-λ∆ β } (dx) + (1 -e -λ∆ ) p ∆,θ (x)dx, x ∈ R (4)
where δ {-λ∆/β} is the measure concentrated at -λ∆ β and p ∆,θ is the density of Y ∆ absolutely continuous with respect to the Lebesgue. We consider macroscopic regimes such that ∆ = 0(T α ) for some α ∈ (0, 1), it follows that e -λ∆ T = o(⌊T

∆ -1 T ⌋ -1 ) = o(⌊T ∆ -1 T ⌋ -1
) and Lemma 1 applies with a ⌊T ∆ -1 T ⌋ (θ) = e -λ∆ T and w T,θ (dx) = δ {-λ∆ T /β} (dx). The experiments Y ∆ and Y ∆ are asymptotically equivalent and the results established for Y ∆ hold for Y ∆ .

Identifiability loss for compound Poisson processes 3.1 A lower bound

In Section 2 we exhibit on a parametric example a regime where estimation is impossible. We generalize here Theorem 1 to the class of compound Poisson processes P whose norm

r 2,P = (λ, f ) 2,P := λf 2 , is finite, • 2 stands for the usual L 2 norm. Theorem 2. Let ∆ T → ∞ be such that T /∆ 2 T = o((log(T /∆ T )) -1/4
) and T /∆ T → ∞ as T → ∞. Then, for all r 0 ∈ P, r 0 2,P , and δ > 0, there exists V δ (r 0 ), a neighborhood of r 0 such that diam(V δ (r 0 )) ≤ δ and

lim T →∞ inf r sup r∈V δ (r 0 ) E ⌊T ∆ -1 T ⌋ r r -r 2,P > 0
where the infimum is taken over all estimators.

It follows that if ∆ T is of the order of T α for α ∈ (1/2, 1) it is not possible to build a consistent estimator of (λ, f ) from (1) when f is unknown.

Remark 4. A compound Poisson process is a renewal reward process and a Lévy process. Thus, we immediately derive from

Theorem 2 that if ∆ T is such that T /∆ 2 T = o((log(T /∆ T )) -1/4
) as T → ∞, it is not possible to build consistent estimators of the law generating a renewal reward process or a Lévy process with jumps from (1).

Remark 5. The rate restriction T /∆

2 T = o((log(T /∆ T )) -1/4
) is technical and might be weakened in T /∆ 2 T = O(1). Indeed we derive Theorem 2 from Theorem 1, which holds under the restriction T /∆ 2 T = O(1). To apply Theorem 1 in the present setting, we show that the experiment Y ∆ T introduced in Section 2 is asymptotically equivalent to an experiment generated by increments of a compound Poisson process. This asymptotic equivalence result imposes the constraint T /∆ 2 T = o((log(T /∆ T )) -1/4 ).

An asymptotic equivalence result

Building up asymptotically equivalent experiments

A parameter transformation function. Consider some density f θ with respect to the Lebesgue measure, centered with finite K first moments, K ∈ N. Let

xf θ (x)dx = 0 and x k f θ (x)dx = m k , k = 2, . . . , K. Define the parameter θ = (λ, m 2 , . . . , m K ) ∈ Σ K , where Σ K is a compact subset of R + × [R + × R] × • • • × [R + × R] × R + if K is even R + × [R + × R] × • • • × [R + × R] if K is odd,
where R + denotes (0, ∞). Let γ > 0, consider the parameter transformation function

h γ : θ ∈ Σ K → h γ (θ) = γλ, m 2 γ , . . . , m K γ . Fix γ ∈ (0, ∞) \ {0, 1} such that h γ (θ) ∈ Σ K .
In the sequel we consider X and Z two compound Poisson processes, X has intensity λ and compound density f θ and Z has intensity γλ and compound density f hγ (θ) . Namely f hγ (θ) is a density with respect to the Lebesgue measure such that

xf hγ (θ) (x)dx = 0 and x k f hγ (θ) (x)dx = m k γ , k = 2, . . . , K. (5)
To establish Theorem 3 below, we do not need to know f hγ (θ) , only to make sure of its existence and that it is in the Sobolev space W 1,1 (i.e. f hγ (θ) ∈ C 1 with f ′ hγ (θ) ∈ L 1 , see the class of densities (9) below). The existence of f hγ (θ) is an immediate consequence of the truncated Hamburger moment problem. A necessary and sufficient condition for [START_REF] Duval | Statistical inference across time scales[END_REF] to have a solution is that the associated Hankel matrices are positive definite (see e.g. Athanassoulis and Gavriliadis [START_REF] Athanassoulis | The truncated Hausdorff moment problem solved by using kernel density functions[END_REF] or Tagliani [START_REF] Tagliani | Hausdorff moment problem and maximum entropy: A unified approach[END_REF]). Since (0, m 2 , . . . , m K ) are the first moments of the density f θ , the associated Hankel matrices are positive definite. Then, the Hankel matrices of (0, m 2 γ , . . . , m K γ ), for any γ > 0, are positive definite as well and existence of a density f hγ (θ) , absolutely continuous with respect to the Lebesgue measure, is thus ensured. Note that the number of solutions is infinite. A lot of papers study methods to build explicit solutions of (5); for instance maximum entropy approaches (see e.g. Tagliani [START_REF] Tagliani | Hausdorff moment problem and maximum entropy: A unified approach[END_REF] or Sobezyk and Trȩbicki [START_REF] Sobezyk | Maximum entropy principle in stochastic dynamics[END_REF]), polynomial solutions (see e.g. Rodriguez and Seatzu [START_REF] Rodriguez | On the solution of the finite moment problem[END_REF]) or solutions based on kernel density functions (see e.g. Athanassoulis and Gavriliadis [START_REF] Athanassoulis | The truncated Hausdorff moment problem solved by using kernel density functions[END_REF]). All these solutions are C 1 with integrable derivative, which ensures that f hγ (θ) can be chosen in W 1,1 . In practice if K is large, building f hγ (θ) is difficult and the shape of the solution highly depends on the construction method considered. Above references provide explicit examples.

Definition of the experiments. Consider also a Gaussian process W with quadratic variation λm 2 . We associate the parameter φ = (λ, m 2 ) in Σ 2 . Suppose X, Z and W are discretely observed at a sampling rate ∆ > 0 over [0, T ], namely

X i∆ -X (i-1)∆ , i = 1, . . . , ⌊T ∆ -1 ⌋ , (6)
Z i∆ -Z (i-1)∆ , i = 1, . . . , ⌊T ∆ -1 ⌋ , (7)
W i∆ -W (i-1)∆ , i = 1, . . . , ⌊T ∆ -1 ⌋ . ( 8
)
Define the families of statistical experiments indexed by ∆

X ∆ := {P T,∆ θ , θ ∈ Σ K }, Z ∆ := {Q T,∆ θ , θ ∈ Σ K } and W ∆ := {D T,∆ φ , φ ∈ Σ 2 },
where P T,∆ θ denotes the law of ( 6), Q T,∆ θ the law of ( 7) and D T,∆ φ the law of (8).

Statement of the result

Define the subclass of densities

F = f ∈ F(R), |ξf * (ξ)| = |ξ|→∞ O(1) , (9)
where F(R) is the class of densities with respect to the Lebesgue measure and f * denotes the Fourier transform of f . The class F contains any density sufficiently regular. For instance all densities in the Sobolev space W 1,1 , i.e. densities with integrable derivatives.

Theorem 3. Let f θ be in F and suppose sup θ∈Σ K | x 3 f θ (x)dx| < ∞,let ∆ T → ∞ be such that T /∆ T → ∞ as T → ∞. 1. Let K ≥ 2, if T ∆ -(K+1)/2 T = o((log(T /∆ T )) -1/4
), the experiments X ∆ T and Z ∆ T are asymptotically equivalent.

Moreover, if either one of the following holds

i. T ∆ -3/2 T = o((log(T /∆ T )) -1/4 ) ii. T ∆ -2 T = o((log(T /∆ T )) -1/4 ) and m 3 = 0 the experiment X ∆ T is asymptotically equivalent to the Gaussian experiment W ∆ T .
The assumptions of Theorem 3 focus on f θ only as it is possible to select f hγ (θ) solution of (5) satisfying the same assumptions (see Section 3.2.1).

Interpretation

Part 2 of Theorem 3 can be easily interpreted. It states that when ∆ T goes rapidly to infinity, the Gaussian approximation is valid. The increments of a compound Poisson process cannot be distinguished from the increments of a Brownian motion. Using a diffusive model even though the phenomena is per se discontinuous is justified in those regime (see e.g. Cont and de Larrard [START_REF] Cont | Price dynamics in a Markovian limit order market[END_REF]).

Part 1 of Theorem 3 is more general since it holds regardless of the rate ∆ T . It should be interpreted as follows: for a given rate ∆ T , with regard to T, how many parameters are not identifiable? The response given by the theorem is if ∆ T is of the order of T α as T → ∞, α ∈ (0, 1), it is not possible to identify more than K α = ⌈ 2 α -1⌉ moments of the compound law and the intensity. Indeed, it is possible to exhibit two different compound Poisson processes that cannot be distinguished from their discrete observation. Thus, compound laws characterized by their M ≥ K α first moments cannot be estimated consistently from observations (1).

The case K = 1, where parameter θ reduces to θ = λ, is not covered by Theorem 3. Indeed θ appears in the limit variance and is always identifiable. This case is studied for a particular discrete compound law in Duval and Hoffmann [START_REF] Duval | Statistical inference across time scales[END_REF], where an efficient estimator of θ is given and the asymptotic equivalence with a Gaussian experiment is established for ∆ going rapidly to infinity, namely T /∆ 1+1/4 T = o((log(T /∆ T )) -1/4 ). This constraint is more restrictive than the one of Theorem 3 due to the discreteness of the compound law, a regularizing kernel is needed to prove the equivalence and imposes the condition. In the case K = 2, the parameter becomes θ = (λ, m 2 ), a particular example is studied in Section 2. Corroborating Theorem 3, Theorem 2 shows that it is not possible to estimate θ whenever T ∆ -2 T → 0 as T → ∞ since two parameters have to be estimated.

Discussion

Consequences and extensions. An immediate consequence of the results of the paper is that nonparametric estimation for compound Poisson processes is impossible when ∆ goes to infinity as a power of T , since it requires to estimate an infinite number of parameters (see Theorem 3). In this paper we did not investigate the existence and properties of consistent estimation procedures when they exist. From the example of Section 2, we may expect that such procedures exist but have optimal rates of convergence that deteriorate as the number of parameters increases.

A natural generalization of Theorem 3 would be to relax the constraint on the third moment of the compound law in | R x η f θ (x)dx| < ∞ for some η > 0, and more specifically for η ∈ (0, 2). This allows to exhibit at the limit a convergence to any stable process and not only to a Brownian motion (see for instance Kotulski [START_REF] Kotulski | Asymptotic Distributions of the Continuous-Time Random Walks: A Probabilistic Approach[END_REF] or Levy and Taqqu [START_REF] Levy | Renewal reward processes with heavy-tailed interrenewal times and heavy-tailed rewards[END_REF]). The stable limit law is parametric, then if the initial process depends on too many parameters questions i) and ii) (modifying the limit experiment accordingly) of Section 1.1 may also be extended. However, the methodology used in this paper highly rely on the hypothesis | R x 3 f θ (x)dx| < ∞ (see the proof of Theorem 3 and the use of Edgeworth expansions). Another generalization might be to add a long range dependence structure between the jump times or the jumps themselves that remains at the macroscopic limit. But our methodology uses heavily the Lévy structure of the process.

On the difficulty of giving identifiability results. Section 3 contains mostly negative results (see Theorems 2 and 3). Establishing positive results in the general case such as "parametric estimation is possible for K parameters if ∆ goes to infinity slower than T h(K) ", for some function h, is much more involved, even without specifying a rate of convergence. When ∆ goes to infinity, the law of each observation is asymptotically Gaussian and depends on one parameter, the asymptotic variance. If this variance is insufficient to recover the initial parameter, one has to study the limit experiment to derive identifiability and not just the law of one observation. The successful study of the example of Section 2 entirely relies on the fact that modified Bessel functions of the first kind appears in the density of the increments. Asymptotic expansions of such functions are known rendering possible the study of the limit Fisher information. Thus, the methodology adopted in Section 2 cannot be generalized to other cases.

The multivariate case. The results of the paper should apply also to multivariate compound Poisson models. In that case the limit distribution of the increments is a multivariate Gaussian variable, additional information might be extracted from the covariance structure between coordinates.

A particular model is worth mentioning. Consider the bidimentional compound Poisson model where we observe for each increment the number of events R i∆ -R (i-1)∆ and the value of the increment X i∆ -X (i-1)∆ . One may think this additional information may improve identifiability, it is not the case. Observing R enables to estimate the intensity of the Poisson process with high accuracy; indeed a sufficient statistics is the terminal value

R n T ∆ = R ⌊T ∆ -1
T ⌋∆ T and the maximum likelihood estimator R n T ∆ /T converges at the rate √ T which is much faster than √ n T ! Consequently, it does improve identifiability when two parameters are to be estimated: the intensity and one jump parameter that appears in the variance. In that case, the example studied in Section 2 remains identifiable in all macroscopic regimes. Still, identifiability of the jump probability law remains to be studied. Intuitively, if f depends on parameters that cannot be fully identified from the asymptotic variance there might be a loss of identifiability: the variance of f is identifiable but maybe not its shape. Moreover, if the construction that permits to derive Theorem 3 part 1 becomes obsolete, the results of Theorem 3 part 2 still hold.

Proof

Proof of Proposition 1

Preparation

The increments of Y are independent and identically distributed. Conditional on the presence of jumps, the density of Y ∆ + λ∆/β is

P ∆ [f β ](x) = ∞ m=1 P(R ∆ = m|R ∆ = 0)f ⋆m β (x) = e -λ∆ 1 -e -λ∆ ∞ m=1 (λ∆) m m! f ⋆m β (x)
where f β is the density of an exponentially distributed random variable with parameter β and ⋆ denotes the convolution product. It follows that f ⋆m β is the density of a gamma distribution. Then, for x ≥ 0

P ∆ [f β ](x) = e -λ∆ 1 -e -λ∆ e -βx λ∆β ∞ m=0 (λ∆βx) m m!(m + 1)! .
Let k ∈ N and introduce the function

g k (x) = ∞ m=0 x m m!(m + k)! , x ∈ [0, ∞). (10)
It is related to the modified Bessel function of the first kind I k as follows

g k (x) = 1 x k/2 I k (2 √ x), x > 0, (11)
where

I k (x) = ∞ m=0 x 2 2m+k 1 m!Γ(m + k + 1)
.

Rewriting P ∆ [f β ] and adding the drift part we get the density p ∆,θ of Y ∆ , for x ≥ -λ∆/β

p ∆,θ (x) = e -2λ∆-βx 1 -e -λ∆ λ∆βg 1 λ∆βx + λ 2 ∆ 2 .
Technical Lemmas Lemma 2. Let k ∈ N, the modified Bessel function of the first kind

I k (x) satisfies for all M ∈ N e -x I k (x) = 1 (2πx) 1/2 M m=0 (-1) m (2x) m Γ(k + m + 1 2 ) m!Γ(k -m + 1 2 ) + O 1 x M +3/2 ,
where the remainder depends on k and M .

Proof. See Watson [START_REF] Watson | A Treatise on the Theory of Bessel Functions[END_REF].

We need to control the moments of Y ∆ and compute the first ones. For that we use relation [START_REF] Cont | Price dynamics in a Markovian limit order market[END_REF] and the moments of Y ∆ derived from the Lévy-Kintchine formula

φ Y ∆ (w) = E e iwY ∆ = exp λ∆((1 -iw/β) -1 -1 -iw/β) by the relation E Y m ∆ = 1 i m ∂ m φ Y ∆ (w) ∂w m w=0 , m ∈ N.
The control of the moments of Y ∆ is given in Lemma 4 hereafter, which is a consequence of the following Lemma, whose proof can be found in the Appendix.

Lemma 3. Let K ∈ N, suppose X is a compound Poisson process whose compound law is centered and has moment up to order K. Then for ∆ large enough and

m ≤ K we have |E[X m ∆ ]| ≤ C∆ ⌊m/2⌋
, where C continuously depends on λ and the K first moments.

Remark 6. Lemma 3 and Cauchy-Schwarz inequality imply E[|X

2m+1 ∆ |] ≤ C∆ m+1/2 . Lemma 4. Let K ≥ 2, then |E[ Y m ∆ ]| ≤ C∆ ⌊m/2⌋
, where C continuously depends on θ.

Proof of Lemma 4. The process Y is not in P, nevertheless a convex inequality leads to

E Y m ∆ ≤ 2 m E R ∆ i=1 ξ i -1 β m + 1 β m E (R ∆ -λ∆) m .
We apply Lemma 3 to the first term of the right hand part of the inequality. We control the second term using Faà di Bruno's formula; we compute the nth derivative of the Laplace transform of R ∆ -λ∆ at 0 as follows

d n dt n E e t(R ∆ -λ∆) = d n dt n e λ∆(e t -t-1) = d n dt n F (G(t))
where F (t) = e λ∆(t-1) and G(t) = e tt, which satisfy

F (n) (t)| t=0 = (λ∆) n and G (n) (t)| t=0 = 1 n =1 for all n ≥ 1.
Applying Faà di Bruno's formula we get

d n dt n F (G(t)) = m 1 ,m 2 ,...,mn m 1 +2m 2 +•••+nmn=n n! m 1 !m 2 !2! m 2 ...mn!n! mn F (m 1 +•••+mn) (G(t)) n j=1 G (j) (t) j! m j .
Let t = 0. All the terms corresponding to m 1 = 0 are null, we obtain

E (R ∆ -λ∆) n = m 2 ,...,mn 2m 2 +•••+nmn=n n! m 1 !m 2 !2! m 2 ...mn!n! mn (λ∆) m 2 +•••+mn ≤ C∆ ⌊n/2⌋ ,
for large enough ∆. The last inequality follows from the fact that, due to the constraint

2m 2 +3m 3 +• • •+nm n = n, for large enough ∆, the exponent m 2 +• • •+m n is maximized for m 3 = • • • = m n = 0.
The constant C depends on λ. To conclude we control the moments of Y ∆ using (4)

E Y m ∆ = 1 (1 -e -λ∆ ) E Y m ∆ -e -λ∆ λ∆ β ≤ C∆ ⌊m/2⌋ ,
for ∆ large enough and where C continuously depends on θ.

Completion of the proof of Proposition 1

Since observations (3) are independent and identically distributed, the Fisher information satisfies

I ⌊T ∆ -1 T ⌋,∆ T (θ) = ⌊T ∆ -1 T ⌋I 1,∆ T (θ) I 1,∆ T (θ) = I ∆ T (λ, λ) I ∆ T (λ, β) I ∆ T (β, λ) I ∆ T (β, β)
where

I ∆ T (λ, λ) = -E P θ ∂ 2 ∂λ 2 log p ∆,θ ( Y ∆ T , λ, β) , I ∆ T (β, β) = -E P θ ∂ 2 ∂β 2 log p ∆,θ ( Y ∆ T , λ, β) , I ∆ T (λ, β) = I ∆ T (β, λ) = -E P θ ∂ 2 ∂λ∂β log p ∆,θ ( Y ∆ T , λ, β)
From ( 10) we derive g ′ k (x) = g k+1 (x). Straightforward computations lead to

I ∆ T (λ, λ) = E P θ ∆ 2 T e -2λ∆ T (1 -e -λ∆ T ) 2 + ∆ 2 T e -λ∆ T 1 -e -λ∆ T -2∆ 2 T g 2 (λ∆ T β Y ∆ T + λ 2 ∆ 2 T ) g 1 (λ∆ T β Y ∆ T + λ 2 ∆ 2 T ) + 1 λ 2 -(β∆ T Y ∆ T + 2λ∆ 2 T ) 2 × g 3 (λ∆ T β Y ∆ T + λ 2 ∆ 2 T ) g 1 (λ∆ T β Y ∆ T + λ 2 ∆ 2 T ) - g 2 (λ∆ T β Y ∆ T + λ 2 ∆ 2 T ) g 1 (λ∆ T β Y ∆ T + λ 2 ∆ 2 T ) 2 I ∆ T (λ, β) = E P θ -∆ T Y ∆ T g 2 (λ∆ T β Y ∆ T + λ 2 ∆ 2 T ) g 1 (λ∆ T β Y ∆ T + λ 2 ∆ 2 T ) -λ∆ T Y ∆ T (β∆ T Y ∆ T + 2λ∆ 2 T ) × g 3 (λ∆ T β Y ∆ T + λ 2 ∆ 2 T ) g 1 (λ∆ T β Y ∆ T + λ 2 ∆ 2 T ) - g 2 (λ∆ T β Y ∆ T + λ 2 ∆ 2 T ) g 1 (λ∆ T β Y ∆ T + λ 2 ∆ 2 T ) 2 I ∆ T (β, β) = E P θ 1 β 2 -(λ∆ T Y ∆ T ) 2 g 3 (λ∆ T β Y ∆ T + λ 2 ∆ 2 T ) g 1 (λ∆ T β Y ∆ T + λ 2 ∆ 2 T ) - g 2 (λ∆ T β Y ∆ T + λ 2 ∆ 2 T ) g 1 (λ∆ T β Y ∆ T + λ 2 ∆ 2 T ) 2 .
Finally equation ( 11), Lemma 2 applied with M = 8, Lemma 4 (with Remark 6) and the Taylor expansions around 0 of z → 1/(1 + z) up to order 4 in ∆ lead to Proposition 1. Computations are made with Mathematica.

Proof of Theorem 1

Preliminary Lemma 5. Let ∆ T be such that ∆ T → ∞ and T ∆ -2 T → l ∈ [0, ∞) as T → ∞, then for γ > 0 and γ = 1

E θ 0 log g 1 (λ 0 β 0 ∆ T Y ∆ T + λ 2 0 ∆ 2 T ) g 1 (γ 3 λ 0 β 0 ∆ T Y ∆ T + γ 4 λ 2 0 ∆ 2 T ) = 2λ 0 ∆ T (1 -γ 2 ) + 3 log(γ) - 9(γ 2 -1) 16γ 2 λ 0 ∆ T + O 1 ∆ 3/2 T .
Proof. It is a consequence of (11), Lemma 2 applied with M = 8 and Lemma 4 (with Remark 6). Computations are made with Mathematica.

Completion of the proof of Theorem 1

The following inequality holds for all θ 0 ∈ Θ and δ > 0 sup

θ∈V δ (θ 0 ) E ⌊T ∆ -1 T ⌋ P θ θ -θ ≥ V δ (θ 0 ) E ⌊T ∆ -1 T ⌋ P θ θ -θ µ(dθ)
where V δ (θ 0 ) is a neighborhood of θ 0 such that diam(V δ (θ 0 )) < δ and µ is the following measure on V δ (θ 0 )

µ(dx) = 1 2 δ θ 0 (dx) + δ hγ (θ 0 ) (dx)
where h γ (θ 0 ) ∈ V(θ 0 ) is a perturbation of θ 0 and δ θ denotes the Dirac distribution in θ.

For the reader convenience, wherever there is no ambiguity, we drop the super and sub scripts as follows,

E ⌊T ∆ -1 T ⌋ θ [•] := E ⌊T ∆ -1 T ⌋ P θ [•], P ⌊T ∆ -1 T ⌋ := P ⊗⌊T ∆ -1 T ⌋ θ 0 and P ⌊T ∆ -1 T ⌋ γ := P ⊗⌊T ∆ -1 T ⌋ hγ (θ 0 )
, with the convention P ⊗1 = P. It follows that

V δ (θ 0 ) E ⌊T ∆ -1 T ⌋ θ θ -θ µ(dθ) = 1 2 E ⌊T ∆ -1 T ⌋ θ 0 θ -θ 0 + E ⌊T ∆ -1 T ⌋ θ 0 θ -h γ (θ 0 ) dP ⌊T ∆ -1 T ⌋ γ dP ⌊T ∆ -1 T ⌋ ≥ E ⌊T ∆ -1 T ⌋ θ 0 e -s 2 ( θ -θ 0 + θ -h γ (θ 0 ) )1 dP ⌊T ∆ -1 T ⌋ γ dP ⌊T ∆ -1 T ⌋ > e -s (12)
for any s > 0. The triangle inequality applied to [START_REF] Levy | Renewal reward processes with heavy-tailed interrenewal times and heavy-tailed rewards[END_REF] gives

V δ (θ 0 ) E ⌊T ∆ -1 T ⌋ θ θ -θ µ(dθ) ≥ e -s 2 θ 0 -h γ (θ 0 ) P θ 0 dP ⌊T ∆ -1 T ⌋ γ dP ⌊T ∆ -1 T ⌋ > e -s .
Noticing that for any s > 0 and P and Q some probabilities

P dQ dP > e -s = 1 -P 1 - dQ dP > 1 -e -s ≥ 1 -P 1 - dQ dP > 1 -e -s ,
Markov's inequality and P -Q T V = |dP -dQ|, lead to

P dQ dP > e -s ≥ 1 - 1 1 -e -s P -Q T V .
Then, for all s > 0

V δ (θ 0 ) E ⌊T ∆ -1 T ⌋ θ θ -θ µ(dθ) ≥ θ 0 -h γ (θ 0 ) e -s 2 1 - 1 1 -e -s P ⌊T ∆ -1 T ⌋ -P ⌊T ∆ -1 T ⌋ γ T V . Hence, V δ (θ 0 ) E ⌊T ∆ -1 T ⌋ θ θ -θ µ(dθ) ≥ θ 0 -h γ (θ 0 ) Φ P ⌊T ∆ -1 T ⌋ -P ⌊T ∆ -1 T ⌋ γ T V (13)
where

Φ(x) = sup s∈(0,∞) e -s 2 1 - 1 1 -e -s x = (1 - √ x) 2 2 , x ∈ [0, 1].
If x is bounded away from 1, Φ is strictly positive. In the remaining of the proof we choose h γ such that

• P ⌊T ∆ -1 T ⌋ -P ⌊T ∆ -1 T ⌋ γ T V ≤ C 1 < 1 for some constant C 1 ,
• θ 0h γ (θ 0 ) ≥ C 2 > 0 for some constant C 2 possibly depending on θ 0 . Define the function h γ : θ → h γ (θ) = (γ 2 λ, γβ) where γ = 1 is positive. First, Pinsker's inequality gives

P ⌊T ∆ -1 T ⌋ -P ⌊T ∆ -1 T ⌋ γ T V ≤ ⌊T ∆ -1 T ⌋ 2 K P, P γ := ⌊T ∆ -1 T ⌋ 2 K P θ 0 , P hγ (θ 0 ) , ( 14
)
where K is the Kullback divergence and

K P θ 0 , P hγ (θ 0 ) = ∞ -∞ log( p θ 0 (x)) -log( p hγ (θ 0 ) (x)) p θ 0 (x)dx = E P θ 0 log g 1 (λ 0 β 0 ∆ T X ∆ T +λ 2 0 ∆ 2 T ) g 1 (γ 3 λ 0 β 0 ∆ T X ∆ T +γ 4 λ 2 0 ∆ 2 T ) -2λ 0 ∆(1 -γ 2 ) -3 log(γ).
In view of Lemma 5,

K P θ 0 , P hγ (θ 0 ) = 9(1 -γ 2 ) 16γ 2 λ 0 ∆ T + O 1 ∆ 3/2 T
, and

P ⌊T ∆ -1 T ⌋ -P ⌊T ∆ -1 T ⌋ γ T V ≤ 9(1 -γ 2 ) 32γ 2 λ 0 ⌊T ∆ -1 T ⌋ ∆ T + O T ∆ 5/2 T . (15)
Then, if T /∆ 2 T → 0 as T → ∞, for large enough T there exits C 1 < 1 such that

P ⌊T ∆ -1 T ⌋ -P ⌊T ∆ -1 T ⌋ γ T V ≤ C 1 < 1. ( 16
)
The inequality holds for any γ.

If T /∆ 2 T → l > 0 as T → ∞, take γ = 1 such that 0 < 16λ 0 9l + 1 -1 < γ 2 . ( 17
)
Then, [START_REF] Mikosch | Non-life Insurance Mathematics: An Introduction with the Poisson Process[END_REF] ensures that there exists C 1 < 1 such that

P ⌊T ∆ -1 T ⌋ -P ⌊T ∆ -1 T ⌋ γ T V ≤ C 1 < 1. ( 18
)
Second, we bound from below θ 0h γ (θ 0 ) , here • denotes the L 2 norm. Since 17) is satisfied and h γ (θ 0 ) ∈ V δ (θ 0 ). That latest condition can always be fulfilled since we can have either γ > 1 or γ < 1, avoiding boundary issues. Finally, there exists C 2 > 0, depending on γ and θ 0 , such that

θ 0 -h γ (θ 0 ) = (1 -γ 2 ) 2 λ 2 0 + (1 -γ) 2 β 2 0 = |1 -γ| (1 + γ) 2 λ 2 0 + β 2 0 , we choose γ = 1 such that (
θ 0 -h γ (θ 0 ) ≥ C 2 > 0. ( 19
)
We complete the proof plugging ( 16), ( 18) and ( 19) into ( 13) and taking limits.

Remark 7. To bound the total variation norm in [START_REF] Metzler | The restaurant at the end of the random walk: recent developments in the description of anomalous transport by fractional dynamics[END_REF] we prefer the Kullback divergence over the Hellinger distance since the logarithm makes easier the manipulation of the density p θ,∆ (see Lemma 5).

Proof of Lemma 1

Both experiments E n and G n are dominated by ν n,θ (dx) = µ n,θ (dx) + dx, where µ n,θ is a dominating measure for w n,∆ , therefore to establish the asymptotic equivalence it is sufficient to show (see Le Cam and Yang [START_REF] Le Cam | Asymptotics in Statistics: Some Basic Concepts[END_REF])

sup θ∈Σ P ⊗n θ -Q ⊗n θ T V → 0 as n → ∞,
where • T V denotes the total variation norm. Since each experiment is the n fold product of independent and identically distributed random variables 1 the result

P ⊗n θ -Q ⊗n θ T V → 0 as n → ∞. is implied by L(X) -L(Z) T V = o n -1 ,
if X has density p n (θ, •) and Z has density q n (θ, •). The connection between the total variation norm and the L 1 norm leads to

L(X) -L(Z) T V = 1 2 R p n (θ, x) -q n (θ, x) ν n,θ (dx) = a n (θ) 2 R f n (θ, x) -w n,θ (x) ν n,θ (dx) ≤ a n (θ).
The condition sup θ∈Σ a n (θ) = o( 1 n ) completes the proof of Lemma 1.

Remark 8. The last inequality is an equality when µ n,θ and the Lebesgue measure are orthogonal.

Proof of Theorem 2

Preliminary

The process Y defined in Section 2 is not in P, we build a compound Poisson process V close to Y in total variation norm. Keeping up with notation of Section 2, θ = (λ, β) ∈ Θ, where Θ is compact subset of (0, ∞) × (0, ∞), consider the process

V V s = Ns i=1 ǫ i , s ≥ 0 ( 20
)
1 For instance, by using the bound (see Tsybakov [START_REF] Tsybakov | Introduction to Nonparametric Estimation[END_REF] pp. 83-90)

P ⊗n -Q ⊗n T V ≤ √ 2 1 -1 -1 2 P -Q T V n 1/2 .
where N is a Poisson process of intensity 8 9 λ and independent of (ǫ i ) which are independent and identically distributed centered exponential variables with parameter 2 3 β. Their common density is

f θ (x) = 2 3 βe -2 3 β(x+1/( 2 3 β)) , x ≥ -1/ 2β 3 . (21)
Remark 9. The multiplicative constants 8 9 and 2 3 in front of λ and β ensure that Y ∆ defined by (2) and V ∆ have same moments of order 2 and 3.

Consider the observations (V i∆ -V (i-1)∆ , i = 1, . . . , ⌊T ∆ -1 ⌋) and denote by Q ⌊T ∆ -1
T ⌋ θ its law. We have the following Lemma.

Lemma 6. Let ∆ T → ∞ such that T /∆ 2 T = o((log(T /∆ T )) -1/4 ) and T /∆ T → ∞ as T → ∞. Then, for any compact set Θ ⊂ (0, ∞) × (0, ∞) sup θ∈Θ P ⊗⌊T ∆ -1 T ⌋ θ -Q ⊗⌊T ∆ -1 T ⌋ θ T V → 0, where P ⌊T ∆ -1 T ⌋ θ denotes the law of (Y i∆ -Y (i-1)∆ , i = 1, . . . , ⌊T ∆ -1 T ⌋).
Proof of Lemma 6 can be found in the Appendix. The steps of the proof follows the lines of the proof of Theorem 3 hereafter.

Completion of the proof of Theorem 2

Let r θ = (λ, f β ) defined from ( 20) and ( 21), for all r 0 ∈ F and δ > 0

sup r∈V δ (r 0 ) E ⌊T ∆ -1 T ⌋ Pr r -r 2,P ≥ sup r θ ∈V δ (r θ 0 ) E ⌊T ∆ -1 T ⌋ Q θ r -r θ 2,P where the neighborhood V δ (r 0 ) (resp. V δ (r θ 0 )) of r 0 (resp. r θ 0 ) is such that diam(V δ (r 0 )) < δ, diam(V δ (r θ 0 )) < δ and V δ (r θ 0 ) ⊂ V δ (r 0 ). Notice that inf r sup r θ ∈V δ (r θ 0 ) E ⌊T ∆ -1 T ⌋ Q θ r -r θ 2,P = inf r∈V δ (r θ 0 ) sup r θ ∈V δ (r θ 0 ) E ⌊T ∆ -1 T ⌋ Q θ r -r θ 2,P . Otherwise if r / ∈ V δ (r θ 0 ), define Π V δ (r θ 0 ) the projection operator onto V δ (r θ 0 ), we imme- diately get for all r θ ∈ V δ (r θ 0 ) r -r θ 2,P ≥ Π V δ (r θ 0 ) [r] -r θ 2,P .
It follows that for all r, r θ in V δ (r θ 0 ) we have rr θ 2,P ≤ 2(δ + r θ 0 2,P ).

(

) 22
The remainder of the proof is a consequence of Scheffé's theorem. Let F be a bounded function then for every measures P and

Q E P [F (X)] -E Q [F (X)] ≤ F ∞ |dP -dQ| = 2 F ∞ P -Q T V . (23)
It follows from ( 22) and ( 23)

E ⌊T ∆ -1 T ⌋ Q θ r -r θ 2,P ≥ E ⌊T ∆ -1 T ⌋ P θ r -r θ 2,P -2 2(δ + r θ 0 ) P θ -Q θ T V .
We conclude the proof with Lemma 6, Theorem 1 and taking limits.

Proof of Theorem 3

Preliminary Lemma 7. Let f be a density with respect to the Lebesgue measure, centered and with finite variance. Then, for every ρ > 0 there exists a < 1 such that |f * (ξ)| ≤ a, ∀|ξ| > ρ.

Proof of Lemma 7. First, we establish that |f * (ξ)| = 1 if and only if ξ = 0. Only the direct implication needs justification. Denote D = {x, f (x) > 0} and suppose |f * (ξ)| = 1, taking square leads to

0 = |f * (ξ)| 2 -1 = Re D 2 e iξ(x-y) f (x)f (y)dxdy - D 2 f (x)f (y)dxdy = D 2 cos(ξ(x -y)) -1 f (x)f (y)dxdy,
where Re(z) designates the real part of z. Since (cos(ξ(xy)) -1)f (x)f (y) ≤ 0 for all x, y ∈ D we derive that cos(ξ(xy)) = 1 for all x, y ∈ D. Since D is an interval of R we have ξ = 0.

Second, by Riemann-Lebesgue Lemma there exists A > 0 such that ∀|ξ| > A, |f * (ξ)| < 1/2. Since f has finite expectation ξ → |f * (ξ)| is continuous. It is continuous over the compact [ρ, A] and reaches its supremum, denoted S, which is by the first part of the proof strictly lower than 1. Finally, since f has finite variance f * ′′ (0) > 0 and for all ρ > 0 we have |f * (ρ)| < 1. Set a = S ∨ 1 2 ∨ |f * (ρ)|. Proof is now complete. To establish Theorem 3, we show that the total variation norm between the experiments vanishes, using the Lévy structure of the processes X, Z and W . The experiments X ∆ T , Z ∆ T and W ∆ T are dominated by the measure δ 0 (dx) + dx. Introduce

p ∆ T ,θ (x) = e -λ∆ T δ 0 (x) + (1 -e -λ∆ T ) p ∆ T ,θ (x) (24)
q ∆ T ,hγ (θ) (x) = e -γλ∆ T δ 0 (x) + (1 -e -γλ∆ T ) q ∆ T ,hγ (θ) (x) (25)
where p ∆ T ,θ and q ∆ T ,hγ (θ) are the distributions of X ∆ T and Z ∆ T and p ∆ T ,θ and q ∆ T ,hγ (θ) are absolutely continuous with respect to the Lebesgue measure. For the reader convenience, in absence of ambiguity we drop the subscripts and set p := p ∆ T ,θ and q := q ∆ T ,hγ (θ) .

Proof of Theorem 3.1

We prove that for K ≥ 2, ∆ T satisfying the rate restriction

T /∆ (K+1)/2 T = o((log(T /∆ T )) -1/4 ) as T → ∞ (26)
and the condition sup θ∈Σ K | x 3 f θ (x)dx| < ∞ the experiments X ∆ T and Z ∆ T are asymptotically equivalent. They live on the same state space and are the ⌊T ∆ -1 T ⌋ fold product of independent and identically distributed random variables, therefore it is sufficient to show (see Section 5.3 the proof of Lemma 1)

L(X ∆ T ) -L(Z ∆ T ) T V = o ⌊T ∆ -1 T ⌋ -1 . (27)
We have

L(X ∆ T ) -L(Z ∆ T ) T V = 1 2 R |(1 -e -λ∆ T ) p(x) -(1 -e -γλ∆ T ) q(x)|dx + 1 2 |e -λ∆ T -e -γλ∆ T |.
Where p and q are defined in ( 24) and ( 25), and |e

-λ∆ T -e -γλ∆ T | = o(⌊T ∆ -1 T ⌋ -1
), as ∆ is of the order of T α for some α > 0. Applying successively the triangle inequality and Cauchy-Schwarz we obtain R |(1e -λ∆ T ) p(x) -(1e -γλ∆ T ) q(x)|dx ≤ I + II + III where for any η > 0, Set η = η T = κ ∆ T log(T /∆ T ), we claim that for κ 2 > 2λm, the terms I, II and III are o((T /∆ -1 T )) hence ( 27) and the result. Bounding terms II and III. For II we use that

I = 2η R (1 -e -λ∆ T ) p(x) -(1 -e -γλ∆ T ) q(x)
(1 -e -λ∆ T ) |x|>η T p(x)dx = |x|>η T p ∆ T ,θ (x)dx = P θ (|X ∆ T | > η T )
and that X ∆ T is a centered compound Poisson process whose compound law has finite variance, it follows that

X ∆ T √ ∆ T → N (0, λm 2 ) as T → ∞.
Let D ∼ N (0, λm 2 ), the triangle inequality gives

P θ |X ∆ T | ≥ η T ≤ P |D| ≥ κ log(T /∆ T ) + P |D| ≥ κ log(T /∆ T ) -P X ∆ T √ ∆ T ≥ κ log(T /∆ T ) .
We readily obtain

P |D| ≥ κ log(T /∆ T ) ≤ 2(T /∆ T ) -κ 2 /(2λm 2 ) = o (T /∆ T ) -1 .
We bound the second term using Edgeworth series, even if it means conditioning on the value of the Poisson process associated to X. By assumption, the compound law has finite moment of order 3, denoted m 3 , uniformly bounded over Σ K , we derive

P |D| ≥ κ log(T /∆ T ) -P θ X ∆ T √ ∆ T ≥ κ log(T /∆ T ) ≤ C √ ∆ T ∂ 3 ∂x 3 ∞ x e -s 2 2λm 2 ds x=κ √ log(T /∆ T ) = C λm 2 √ ∆ T 1 - κ 2 log(T /∆ T ) λm 2 e - κ 2 log(T /∆ T ) 2λm 2 ≤ C log(T /∆ T ) √ ∆ T (T /∆ T ) -κ 2 /(2λm 2 ) = o (T /∆ T ) -1
where C continuously depends on λ, m 2 and m 3 and which is o((T /∆ T ) -1 ) for κ 2 ≥ 2λm 2 . The term III is treated similarly as II, the parameter γ simplifies. We do not reproduce computations. Thus II and III have the right order, the choice of κ and the bounds on II and III is made independent of θ taking the supremum over the compact set Σ K .

Bounding term I. Plancherel theorem gives

A = R (1-e -λ∆ T ) p(x) -(1 -e -γλ∆ T ) q(x) 2 dx = 1 2π R |(1 -e -λ∆ T ) p * (ξ) -(1 -e -γλ∆ T ) q * (ξ)| 2 dξ,
where f * denotes the Fourier transform of f . The Fourier transforms are computed using [START_REF] Watson | A Treatise on the Theory of Bessel Functions[END_REF] and ( 25) and the Lévy-Kintchine formula

(1 -e -λ∆ T ) p * (ξ) = exp λ∆ T (f * θ (ξ) -1) -e -λ∆ T (1 -e -γλ∆ T ) q * (ξ) = exp γλ∆ T (f * hγ (θ) (ξ) -1) -e -γλ∆ T .
Then, 2πA can be upper bounded as follows

R (1 -e -λ∆ T ) p * ( ξ √ ∆ T ) -(1 -e -γλ∆ T ) q * ( ξ √ ∆ T ) 2 dξ √ ∆ T ≤ IV + V + V I,
where for ρ ≥ 0

IV = 1 2π |ξ|≤ρ √ ∆ T (1 -e -λ∆ T ) p * ( ξ √ ∆ T ) -(1 -e -γλ∆ T ) q * ( ξ √ ∆ T ) 2 dξ √ ∆ T , V = 1 2π |ξ|>ρ (1 -e -λ∆ T ) p * (ξ) 2 dξ and V I = 1 2π |ξ|>ρ (1 -e -γλ∆ T ) q * (ξ) 2 dξ.
Bounding term IV . Since f θ and f hγ (θ) have their K first moments finite, we get the following expansion for any bounded ξ

f * θ (ξ) -1 - m 2 ξ 2 2 + • • • + i K m K ξ K K! = ξ K+1 α 1 (ξ) and f * hγ (θ) (ξ) -1 - m 2 ξ 2 2γ + • • • + i K m K ξ K K!γ = ξ K+1 α 2 (ξ)
for some bounded functions ξ ❀ α 1 (ξ) and ξ ❀ α 2 (ξ). It follows that IV is less than

|ξ|≤ρ √ ∆ T e -λm 2 ξ 2 2 +•••+i K λm K ξ K √ ∆ T K-2 K! 2 ξ 2K+2 ∆ K-1 T α 2 ( ξ √ ∆ T ) × exp 2 ξ K+1 √ ∆ T K-1 α ξ √ ∆ T dξ √ ∆ T + 2ρ ∆ T (e -λ∆ T + e -γλ∆ T ) for some bounded function ξ ❀ α(ξ). Set α = sup x |α(x)|, then IV is bounded by α 2 |ξ|≤ρ √ ∆ T ξ 2K+2 ∆ K-1 T exp -λ(m 2 - ⌊K/2⌋ k=2 (-1) k m 2k ρ 2k-2 2(2k)! ) + 2ρ K-1 α ξ 2 dξ √ ∆ T + 2ρ ∆ T (e -λ∆ T + e -γλ∆ T ).
We pick ρ such that ρ > 0

λ m 2 - ⌊K/2⌋ k=2 (-1) k m 2k ρ 2k-2 2(2k)! + 2ρ K-1 α > 0. (28)
Even if it means taking ρ small, condition (28) can always be satisfied. Using that the Gaussian density has finite moment of order 2K + 2, term IV is of order ∆

-(2K-1)/2 T . Bounding terms V and V I. For any A > ρ, V = (1 -e -λ∆ T ) 2π |ξ|>ρ p * (ξ) 2 dξ = e -λ∆ T 2π |ξ|>ρ e λ∆ T f * θ (ξ) -1 2 dξ = e -λ∆ T 2π A>|ξ|>ρ e λ∆ T f * θ (ξ) -1 2 dξ + e -λ∆ T 2π |ξ|>A e λ∆ T f * θ (ξ) -1 2 dξ = V II + V III.
First, by Lemma 7 V II is bounded by constant times Ae -(1-a)λ∆ T = o((T /∆ T ) -1 ) as a < 1. Second, since f θ belongs to F, there exist C > 0 such that for all ξ ≥ A, |f * (ξ)/ξ| ≤ C.

V III ≤ 2e -λ∆ T 2π ∞ A ∞ l=1 (λ∆ T C) l l! 1 ξ l 2 dξ ≤ e -λ∆ T π ∞ l 1 =1 ∞ l 2 =1 (λ∆ T C) l 1 +l 2 l 1 !l 2 ∞ A 1 ξ l 1 +l 2 dξ = e -λ∆ T π ∞ l 1 =1 ∞ l 2 =1 (λ∆ T C) l 1 +l 2 l 1 !l 2 ! 1 (l 1 + l 2 -1)A l 1 +l 2 -1 ≤ ρ π e -(1-2 C A )λ∆ T . Fix A > 2C, then, ( √ η T V ) 1/2 is of order ( √ ∆ T e -(1-2 C A )λ∆ T ) 1/2 = o((T /∆ T ) -1
). The term V I is treated similarly and is of the same order. Completion of the proof of Theorem 3.1. The leading quantity is IV , we deduce that I is of order η

Appendix Proof of Lemma 3

We prove the result by induction on m. The Lévy-Kintchine formula gives an explicit formula of the Fourier transform of X

∆ φ X ∆ (w) = E e iwX ∆ = exp λ∆(f * (w) -1)
where f * (w) = E[e iwξ ] denotes the Fourier transform of the compound law and λ is the intensity of the Poisson process. The moments of X ∆ are obtained with

E X m ∆ = 1 i m ∂ m φ X ∆ (w) ∂w m w=0 , m ∈ N. (29)
We prove by induction the following property, for all m

≤ ⌊ K-1 2 ⌋ ∂ 2m φ X ∆ (w) ∂w 2m = P 2m (w, ∆) + Q 2m (w, ∆) exp λ∆(f * (w) -1) ∂ 2m+1 φ X ∆ (w) ∂w 2m+1 = P 2m+1 (w, ∆) + Q 2m+1 (w, ∆) exp λ∆(f * (w) -1)
where the functions ∆ → P 2m (w, ∆), ∆ → Q 2m (w, ∆), ∆ → P 2m+1 (w, ∆) and ∆ → Q 2m+1 (w, ∆) are polynomials in ∆, the degree of Q 2m and Q 2m+1 is smaller than m and there exist C 1 functions (c 2m,j (•), c 2m+1,j (•), j = 1, . . . , m), continuously depending on λ, such that

P 2m (w, ∆) = m j=1 c 2m,j (w)f * ′ (w) 2j ∆ m+j P 2m+1 (w, ∆) = m j=1 c 2m+1,j (w)f * ′ (w) 2j-1 ∆ m+j .
Straightforward computations lead to the result for m = 1

∂ 2 φ X ∆ (w) ∂w 2 = λ∆f * (2) (w) + (λ∆f * ′ (w)) 2 exp λ∆(f * (w) -1) ∂ 3 φ X ∆ (w) ∂w 3 = λ∆f * (3) (w) + 2λ 2 ∆ 2 f * ′ (w)f * (2) (w) + λ∆f * ′ (w)(λ∆f * (2) (w) + (λ∆f * ′ (w)) 2 ) × exp λ∆(f * (w) -1) .
Assume that the property holds at rank m -1, we have

∂ 2m φ X ∆ (w) ∂w 2m = ∂ ∂w ∂ 2m-1 φ X ∆ (w) ∂w 2m-1 = ∂ w P 2m-1 (w, ∆) + ∂ w Q 2m-1 (w, ∆) + λ∆f * ′ (x)(P 2m-1 (w, ∆) + Q 2m-1 (w, ∆)) × exp λ∆(f * (w) -1)
where where P 2m have the desired property and from the property at rank m -1 the degree of Q 2m is lower than m. Similar computations give the result for P 2m+1 and Q 2m+1 . We complete on the proof with (29), f * (0) = 1 and using that f is centered:

∂ w P 2m-1 (w, ∆) = c 2m-1,1 (w) ′ f * ′ (w)∆ m + c 2m-
f * ′ (0) = 0. It follows that E X 2m ∆ ≤ C 1 ∆ m and E X 2m+1 ∆ ≤ C 2 ∆ m ,
where C 1 and C 2 continuously depend on λ.

Proof of Lemma 6

We adopt the same methodology as for the proof of Theorem 3. Computations are quite similar we do not develop all of them. Each experiment is the ⌊T ∆ -1 T ⌋-fold product of independent and identically distributed random variables the result is implied by (see Section 5.3 the proof of Lemma 1)

P θ -Q θ T V = o (T /∆ T ) -1 ,
uniformly over the compact set Θ. Let us further denote by p ∆ T ,θ and q ∆ T ,θ the densities of Y ∆ T and of V ∆ T respectively, which can be decomposed as follows p ∆ T ,θ (x) = e -λ∆ T δ 0 x -λ∆ T β + (1e -λ∆ T ) p ∆ T ,θ (x) (30) q ∆ T ,θ (x) = e -8 9 λ∆ T δ 0 (x) + (1e -8 9 λ∆ T ) q ∆ T ,θ (x)

where p ∆ T ,θ and q ∆ T ,θ are absolutely continuous with respect to the Lebesgue measure.

For the reader convenience we set p := p ∆ T ,θ and q := q ∆ T ,θ . Then, we have that 2 P θ -Q θ T V equals R

(1e -λ∆ T ) p(x) -(1e -8 9 λ∆ T ) q(x) dx + e - Bounding term I. We apply the Plancherel theorem to the integral in I, we denote by p * and q * the Fourier transforms of p and q respectively. They are computed with (30), (31) and the Lévy-Kintchine formula. We introduce the decomposition ). The proof is completed taking the supremum over Θ.

2 dx 1 / 2 ,

 12 II = (1e -λ∆ T ) |x|>η p(x)dx and III = (1e -γλ∆ T ) |x|>η q(x)dx.

.

  The choice η T = κ ∆ T log(T /∆ T ) and restriction (26) imply I = o((T /∆ T ) -1 ). The proof of Theorem 3.1 is completed taking the supremum in θ over the compact set Σ K .Proof of Theorem 3.2Proof of part 2 of Theorem 3 is deduced from above computations replacing Z with W and applying modifications i. or ii.

1 , 1 2 j=1c

 112 (w)f * ′′ (w)f * ′ (w)∆ m + m-2 j=1 c 2m-1,j+1 (w) ′ f * ′ (w) 2j+1 ∆ m+j + c 2m-1,j+1 (w)(2j + 1)f * ′′ (w)f * ′ (w) 2j ∆ m+j λ∆f * ′ (x)P 2m-1 (w, ∆) = λ m-1 j=1 c 2m-1,j (w)f * ′ (w) 2j ∆ m+j .We setP 2m (w, ∆) = m-2m-1,j+1 (w) ′ f * ′ (w) + c 2m-1,j+1 (w)(2j + 1)f * ′′ (w) × f * ′ (w) 2j ∆ m+j Q 2m (w, ∆) = ∂ w Q 2m-1 (w, ∆) + λ∆f * ′ (x)Q 2m-1 (w, ∆)

8 9R( 1 -

 81 λ∆ Te -λ∆ T , where e -8 9 λ∆ Te -λ∆ T is o(⌊T ∆ -1 T ⌋ -1 ) as ∆ is of the order of T α for α > 0. Applying successively the triangle inequality and Cauchy-Schwarz inequality we getR (1e -λ∆ T ) p(x) -(1e -8 9 λ∆ T ) q(x) dx ≤ I + II + III,where for any η > 0,I = 2η e -λ∆ T ) p(x) -(1e -8 9 λ∆ T ) q(x) 2 dx 1/2 , II = P θ |Y ∆ T | ≥ η III = P θ |V ∆ T | ≥ η .Set η T = κ ∆ T log(T /∆ T ), we show that for κ 2 > 3λ, I, II and III are o((T /∆ -1 T )). Bounding terms II and III. The argument used in the proof of Theorem 3 to bound the similar terms II and III also holds here. Then II and III are o((T /∆ T ) -1 ).

R ( 1 ( 1 - 1 -- 2 (λ-ρ 2 α) ξ 2 β 2 ξ 8 α 2 2 dξV I = e - 8 9 λ∆ T |ξ|≥ρ exp 8 9 .

 111222289 e -λ∆ T ) p(x) -(1e -8 9 λ∆ T ) q(x)2 dx ≤ IV + V + V I, with for any ρ ≥ 0 and after replacing ξ by ξ/ e -λ∆ T ) p * ξ√ ∆ T -(1e -8 9 λ∆ T ) q * ξ i3ξ/(2β) e -i3ξ/(2β) -1e -8 9 λ∆ T 2 dξ.Bounding term IV . A first order expansion (seeRemark 9) gives that IV is less than T (e -8 9 λ∆ Te -λ∆ T ) for some bounded function ξ ❀ α(ξ). Set α = sup ξ |α(ξ)|, we obtain that IV is bounded by a constant times R e Choosing ρ such that λρ 2 α > 0, gives IV of order ∆ -5/2 T . Bounding terms V ad V I. Since V = e -λ∆ T |ξ|≥ρ exp λ∆ T /(1 -iξ β ) -1 λ∆ T e -i3ξ/(2β) / 1the proof of Theorem 3 (to bound the analogous terms V and V I) holds for C = β (C = 16β/27) for term V (for term V I), any A > 2C and any ρ > 0 leading to a = 1/ (1 + ρ 2 β 2 ) < 1. We derive that V and V I are of the right order. Completion of the proof of Lemma 6. Finally, R (p λ,∆ T (x)q λ,∆ T (x)) 2 dx is dominated by I which is in η The choice η T = κ ∆ T log(T /∆ T ) and the restriction condition T /∆ 2 T = o((log(T /∆ T )) -1/4 ) imply I = o((T /∆ T ) -1

Acknowledgment

The author is thankful to Marc Hoffmann for his valuable remarks on this paper.