Fetching the paper…

Reading the bibliography…

2015

The sample size required in importance sampling

Chatterjee, Sourav, Diaconis, Persi

Original
PDF
Post on X

Understand

The goal of importance sampling is to estimate the expected value of a given function with respect to a probability measure $\nu$ using a random sample of size $n$ drawn from a different probability measure $\mu$.

If the two measures $\mu$ and $\nu$ are nearly singular with respect to each other, which is often the case in practice, the sample size required for accurate estimation is large.
In this article it is shown that in a fairly general setting, a sample of size approximately $\exp(D(\nu||\mu))$ is necessary and sufficient for accurate estimation by importance sampling, where $D(\nu||\mu)$ is the Kullback-Leibler divergence of $\mu$ from $\nu$.
In particular, the required sample size exhibits a kind of cut-off in the logarithmic scale.

The sample size required in importance sampling · Around

Built on

Rosenbluth, M. N
1955
Earlier work this paper cites.
Bahadur, R. R
1960
Earlier work this paper cites.
Hammersley, J. M
1965
Earlier work this paper cites.
Knuth, D. E
1976
Earlier work this paper cites.
Siegmund, D
1976
Earlier work this paper cites.
Torrie, G. M
1977
Earlier work this paper cites.
Baxter, R. J
1982
Earlier work this paper cites.
Naiman, D. Q
1983
Earlier work this paper cites.
Diaconis, P
1991
Earlier work this paper cites.
Hesterberg, T
1995
Earlier work this paper cites.
Liu, J. S
1995
Earlier work this paper cites.
Knuth, D. E
1996
Earlier work this paper cites.
Efron, B
1997
Earlier work this paper cites.
Gelman, A
1998
Earlier work this paper cites.
Madras, N
1998
Earlier work this paper cites.
Madras, N
1999
Earlier work this paper cites.
Doucet, A., de Freitas, N
2001
Earlier work this paper cites.
Srinivasan, R
2002
Earlier work this paper cites.

Similar

Del Moral, P
2004
Cited alongside, same era.
Dupuis, P
2004
Cited alongside, same era.
Owen, A. B
2004
Cited alongside, same era.
Robert, C. P
2004
Cited alongside, same era.
Cappé, O., Moulines, E
2005
Cited alongside, same era.
Chen, Y., Diaconis, P., Holmes, S. P
2005
Cited alongside, same era.
Owen, A. B
2005
Cited alongside, same era.
Bassetti, F
2006
Cited alongside, same era.

Then

Lelièvre, T., Rousset, M
2010
Later among the works it cites.
McCoy, B
2010
Later among the works it cites.
Chan, H. P
2011
Later among the works it cites.
Blanchet, J., Glynn, P
2012
Later among the works it cites.
Dupuis, P., Spiliopoulos, K
2012
Later among the works it cites.
Chatterjee, S
2013
Later among the works it cites.
Del Moral, P
2013
Later among the works it cites.
Mukherjee, S
Original

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Asmussen, S

2007

Cited alongside, same era.

Chan, H. P

2007

Cited alongside, same era.

Shi, J., Siegmund, D

2007

Cited alongside, same era.

Blanchet, J

2008

Cited alongside, same era.

2013

Later among the works it cites.

Bousquet-Mélou, M

2014

Later among the works it cites.

Kenyon, R., Radin, C., Ren, K

2014

Later among the works it cites.

2014

Later among the works it cites.

Agapiou, S., Papaspiliopoulos, O., Sanz-Alonso, D

2015

Closest in time.

Bhattacharya, B. B., Ganguly, S., Lubetzky, E

2015

Closest in time.

Del Moral, P., Kohn, R

2015

Closest in time.

2015

Closest in time.

Kenyon, R., Kral, D., Radin, C

2015

Closest in time.

Whiteley, N., Lee, A

2016

Closest in time.