Charly Andral
email: andral@ceremade.dauphine.fr

An attempt to trace the birth of importance sampling

Context

Importance sampling is now well known but when compared to other methods (e.g. Metropolis algorithm), its birthdate is difficult to establish. Two researchers in the United States seem to have had a role in the birth of importance sampling : Herman Kahn, Gerald Goertzel. They are part of a larger group of scientists who worked on the problem of neutron and gamma ray attenuation in thick shields. It includes J. von Neumann, S. Ulam., H. Bethe, W. DeMarcus, R. Echols, U. Fano, T.E. Harris, A.S, Householder G. Goertzel, N. Metropolis, L.A. Ohlinger, R.D, Richtmyer, and S.W.W. Shor [START_REF] Kahn | Stochastic (Monte Carlo) Attenuation Analysis[END_REF].

Chronology

1949: Quota Sampling

The true chronology is difficult to establish as papers exist in different versions and with different dates and as the thinking and writing of the corresponding articles may have occurred much earlier than the publication date. No article mentions work on importance sampling before 1949.

The first mention of the idea of importance sampling is found in two papers of June 1949, one from Kahn [START_REF] Kahn | Stochastic (Monte Carlo) Attenuation Analysis[END_REF](June 14), and the other from Goertzel [START_REF] Goertzel | Quota Sampling and Importance Functions in Stochastic Solution of Particle Problems[END_REF] (June 21) under the name quota sampling. Note that [START_REF] Kahn | Stochastic (Monte Carlo) Attenuation Analysis[END_REF] exists under another reference from the RAND Corporation (where Kahn worked) with a revised version [START_REF] Kahn | Stochastic (Monte Carlo) Attenuation Analysis[END_REF] with the date July 14, 1949. Goertzel's article is more focused on the physical applications of the method while [START_REF] Kahn | Stochastic (Monte Carlo) Attenuation Analysis[END_REF] contains already the classical justification of importance sampling

J = g(x)f (x) f * (x) f * (x)dx,
where f is the target density, g the function to integrate, and f * an arbitrary density function, meaning that one can sample according to f * to estimate J. However, no article published in 1949 mentions importance sampling. The term importance only appears in [START_REF] Goertzel | Quota Sampling and Importance Functions in Stochastic Solution of Particle Problems[END_REF] as importance function.

1950: Importance Sampling

At least three 1950 papers use the term importance sampling as what was previously known under the name quota sampling. The first two are in the proceedings of an IBM conference hold in New York in November 1949, published in 1950 [START_REF]Proceedings, seminar on scientific computation[END_REF]. One is by Kahn (presenting work done with T.E. Harris) [START_REF] Kahn | Modification of the Monte Carlo Method[END_REF] and has a very informative paragraph about importance sampling : Generalizing a little, we can say that in making the f (x) → f * (x) transformation we are trying to sample every portion of the phase space that we are studying, with a frequency proportional to the importance of that part of phase space times the probability of getting into it. For this reason the name "importance sampling" a has been suggested by G. Goertzel for this procedure. In this terminology g(x) is called the importance function. In general the importance of any region is directly proportional to the amount that the region contributes to the answer.

a We had previously called this process "quota sampling." This last terminology is a little misleading as it is not identical with the quota sampling of the statisticians.

The second article in [START_REF]Proceedings, seminar on scientific computation[END_REF] is from J.H. Curtiss [START_REF] Curtiss | Sampling Methods Applied to Differential and Difference Equations[END_REF] and contains the following footnote about importance sampling See also the paper by Kahn and Harris. The method is called that of "importance sampling" by these writers. Dr. W. Edwards Deming pointed out to the author that the method has been known for many years in various forms to sampling experts working in the social sciences, who have sometimes called it "sampling with probability in proportion to size". At this point, the chronology starts to get fuzzy. The Kahn and Harris paper has the following reference :

The Monte Carlo Method: Proceedings of a Symposium held in Los Angeles, Calif., on June 29, 30 and July 1, 1949. To be published by the National Bureau of Standards.

...but it was in fact published in 1951 [START_REF] Kahn | Estimation of particle transmission by random sampling[END_REF] in [START_REF] Andral | Monte Carlo Method[END_REF].

The third 1950 paper [START_REF] Goertzel | Monte Carlo Methods for Shield Computation[END_REF] is dated from February 1950, where Goertzel and Kahn write this footnote:

Importance sampling is the term used herein for what has in several reports been called "quota sampling." "Importance sampling" is considered to be a more descriptive term.

1951: a 1949 paper?

The last paper we will mention here is the Kahn and Karris paper [START_REF] Kahn | Estimation of particle transmission by random sampling[END_REF]. It is published in the proceedings of a symposium held in June 1949 but published in 1951 [START_REF] Andral | Monte Carlo Method[END_REF]. However, it is cited in 1950 in [START_REF] Curtiss | Sampling Methods Applied to Differential and Difference Equations[END_REF]. It seems that the expression importance sampling may have been used during the symposium. However, in this paper, there is no real explanation of the expression:

For convenience, we refer to this second type of sampling where the neutrons are forced into the more important regions, as importance sampling.

Nor is there a mention of Goertzel as the one who suggested the term as in [START_REF] Kahn | Modification of the Monte Carlo Method[END_REF]. Note that [GK50] mentions an article with the same title but with the reference RAND Report R-148. If the numbering of RAND reports is chronological, it would make it precede [START_REF] Kahn | Stochastic (Monte Carlo) Attenuation Analysis[END_REF], which has the reference R-163. However we were not able to find any copy of this report online, and there is no guarantee that this draft contains the expression importance sampling that may have been introduced afterwards in the final version.

Conclusion

It thus seems to us that the first time that importance sampling was used was in [START_REF] Kahn | Estimation of particle transmission by random sampling[END_REF] in 1949, maybe during the aforementioned June symposium. However, there is no mention of Goertzel found in this paper, while [START_REF] Kahn | Modification of the Monte Carlo Method[END_REF] written afterwards, mentions Goertzel as the one who suggested the name. Did Kahn mention it only in [START_REF] Kahn | Modification of the Monte Carlo Method[END_REF] because he knew the paper would be published before [START_REF] Kahn | Estimation of particle transmission by random sampling[END_REF], even though the conference had been held later ?

The author is supported by a grant from Région Ile-de-France