# An attempt to trace the birth of importance sampling

Charly Andral

► To cite this version:

Charly Andral. An attempt to trace the birth of importance sampling. 2022. hal-03696061

HAL Id: hal-03696061

https://hal.science/hal-03696061

Preprint submitted on 15 Jun 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à 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.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# An attempt to trace the birth of importance sampling

Charly Andral*

andral@ceremade.dauphine.fr

CEREMADE, CNRS, UMR 7534, Université Paris-Dauphine, PSL University, 75016 Paris, France

June 15, 2022

## Abstract

In this note, we try to trace the birth of importance sampling (IS) back to 1949. We found the classical formulation of IS in a paper from Kahn in June 1949. As for the appearance of the expression *importance sampling* itself, it may have appeared a few months later, maybe in 1949 during conferences, but there is no published article with the name before 1950.

## 1 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 [Kah49a].

## 2 Chronology

### 2.1 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 [Kah49b](June 14), and the other from Goertzel [Goe49] (June 21) under the name *quota sampling*. Note that [Kah49b] exists under another reference from the RAND Corporation (where Kahn worked) with a revised version [Kah49a] with the date July 14, 1949. Goertzel's article is more focused on the physical applications of the method while [Kah49b] contains already the classical justification of importance sampling

$$J = \int \frac{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 [Goe49] as *importance function*.

<footnote>*The author is supported by a grant from Région Ile-de-France</footnote>
## 2.2 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 held in New York in November 1949, published in 1950 [Int50]. One is by Kahn (presenting work done with T.E. Harris) [Kah50] and has a very informative paragraph about *importance sampling*:

> Generalizing a little, we can say that in making the $f(x) \rightarrow 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"ª 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.

The second article in [Int50] is from J.H. Curtiss [Cur50] 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 [KH51] in [AU51].

The third 1950 paper [GK50] 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.

## 2.3 1951: a 1949 paper?

The last paper we will mention here is the Kahn and Karris paper [KH51]. It is published in the proceedings of a symposium held in June 1949 but published in 1951 [AU51]. However, it is cited in 1950 in [Cur50]. 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 [Kah50].

> 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 [Kah49a], 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.

# 3 Conclusion

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

<footnote>ª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.</footnote>
References

[AU51] Institute for Numerical Analysis (U.S.). *Monte Carlo Method: Proceedings of a Symposium Held June 29, 30, and July, 1, 1949, in Los Angeles, California, Under the Sponsorship of the Rand Corporation, and the National Bureau of Standards, with the Cooperation of the Oak Ridge National Laboratory*. U.S. Government Printing Office, 1951.

[Cur50] J. H. Curtiss. Sampling Methods Applied to Differential and Difference Equations, in Proceedings, seminar on scientific computation, November, 1949. New York, NY, 1950. IBM.

[GK50] Gerald Goertzel and H. Kahn. *Monte Carlo Methods for Shield Computation*. U.S. Atomic Energy Commission, Technical Information Division, 1950.

[Goe49] Gerald Goertzel. Quota Sampling and Importance Functions in Stochastic Solution of Particle Problems. 1949.

[Int50] International Business Machines Corporation. *Proceedings, seminar on scientific computation, November, 1949*. IBM, New York, NY, 1950.

[Kah49a] Herman Kahn. Stochastic (Monte Carlo) Attenuation Analysis. Technical Report P-88, RAND Corporation, July 1949.

[Kah49b] Herman Kahn. Stochastic (Monte Carlo) Attenuation Analysis. June 14, 1949. R-163. Technical report, RAND Corporation, 1949.

[Kah50] Herman Kahn. Modification of the Monte Carlo Method, in Proceedings, seminar on scientific computation, November, 1949. New York, NY, 1950. IBM.

[KH51] Herman Kahn and Theodore E Harris. Estimation of particle transmission by random sampling. *National Bureau of Standards applied mathematics series*, 12:27-30, 1951.