Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Importance sampling is a variance reduction technique to approximate integrals/expectations which are not directly computable.

1
vote
1answer
21 views

Importance Sampling : t distribution

Given that X~t dist with v=1, and y=P(X>1000). 1. construct importance sampler estimating y and assess the quality of the estimate so far, I’ve have this : t dist v=1 pdf looks like : 1/[pi * (1+x^2)]...
0
votes
1answer
21 views

Given unnormalized weights in logs, how do I compute normalized weights in logs?

Setting Given a set of positive weights $\{w_i\}_{i=1}^n$, I can normalize them by computing $$W_i = \frac{w_i}{\sum_{j=1}^nw_j}\quad \forall i=1,...,n.$$ Easy enough. But for numerical reasons, it ...
1
vote
0answers
27 views

Flatten the target density in the Metropolis-Hastings algorithm

Let $(E,\mathcal E,\mu)$ be a measure space $F$ be a $\mathbb R$-Banach space $f\in\mathcal L^1(\mu;F)$ $f^\ast:E\to[0,\infty)$ be $\mathcal E$-measurable with $$b:=\int f^\ast\:{\rm d}\mu\in(0,\...
2
votes
1answer
38 views

importance sampling strategies

I am trying to approximate the expectation of the "complete-data likelihood" with respect to the distribution of some missing data, and I am having some trouble. This expectation can be written as $$ ...
0
votes
0answers
21 views

Compute Estimated Covariance matrix from weighted sample from importance sampling

Let $\bar{w}^{(i)}$ be the normalized weight for $i$-th sample. Let $X$ be the data set of $N$ sample and dimension $D$. So the covariance matrix will be a $DxD$ matrix. According to importance ...
2
votes
1answer
49 views

What's done with the expectations in this proof?

This is a proof of the per-decision importance sampling (theorem 1) from the appendix of: https://www.google.co.uk/url?sa=t&source=web&rct=j&url=http://scholarworks.umass.edu/cgi/...
2
votes
2answers
40 views

A doubt on the formula for updating the weights in Sequential Importance Sampling in a State-Space model

Let $x_{0:t}^{(i)}$ be the states from time $0$ to $t$ from sample $i$. Similarly for the observations $y_{1:t}$. The normalized weights are updated according to Where does the term $p(y_t|x_t^{(i)})...
4
votes
3answers
72 views

Conditional expectation on an estimator for defensive sampling

In Introducing Monte Carlo Methods, by Robert and Casella, we have How do we derive the second equality? Shouldn't it be $$E\left[\frac{f(X_i)}{g_{Y_i}(X_i)}|X_i\right]=\frac{f(X_i)}{g_1(X_i)}\rho+...
2
votes
1answer
46 views

SIR explanation in Robert and Casella Intro to Monte Carlo Methods - How to do this derivation?

Why is it an exact simulation from $f$, and not only an approximation? I get $\begin{split} P(X^*\in A) & = \sum_i^n P(X^*\in A , X^* = X_i)=\sum_i^n P(X^*\in A | X^* = X_i)P(X^* = X_i) \\ & ...
3
votes
0answers
16 views

Looking for a recursive formula for asymptotic variance of importance sampling estimator (self-normalized)

Looking for a recursive formula to approximate variance of importance sampling estimator $Var_q\big[\delta_{IS}\big]\approx\sum_{i=1}^n\tilde w(X_i)^2\big[h(X_i)-\delta_{IS}\big]^2$. This is an ...
0
votes
0answers
125 views

Optimal proposal for self-normalized importance sampling

Consider a function $f: \mathcal X \to \mathbb R$ and a probability distribution $p$ with the support on $\mathcal X$ which we can evaluate up to a normalizing constant, i.e. we can only evaluate $\...
2
votes
1answer
173 views

Why does Off-Policy Monte Carlo Control only learn from the “Tails of Episodes”?

I was reading through section 5.7 of the second edition of Sutton and Barto's "Reinforcement Learning: An Introduction" when I came across this passage: where the "method" that the author is ...
0
votes
0answers
21 views

How to prove that $\hat{\rm{var}} \left\{ w^*(X) \right\} = \hat{\rm{cv}}^2 \left\{ w(X) \right\}$? (Importance Sampling)

Text: Computational Statistics 2E by Givens and Hoeting Let $f$ be the target distribution and $g$ be an envelope for $f$. Let $X_1, \ldots, X_n \overset{\text{iid}}{\sim} g$ represent a sample. ...
0
votes
1answer
27 views

Derivation of squared coefficient of variation (Importance Sampling)

Text: Computational Statistics 2E by Givens and Hoetings Section: 6.3.2.3 Weight Degeneracy, Rejuvenation, and Effective Sample Size I am having trouble following another result in the text. Below ...
3
votes
1answer
48 views

Stuck on part of proof that a random variable $\bf X$ drawn with the SIR algorithm has distribution that converges to $f$ as $m \rightarrow \infty$

Text: Computational Statistics by Givens and Hoeting Section 6.3.1: Sampling Importance Resampling Algorithm The authors provide a proof that random variable $\bf X$ drawn with the SIR algorithm has ...
2
votes
0answers
32 views

Hyper-parameters which minimize the variance of transformed multi-variate Guassian variable

Let $k < p$ be positive integers and $g: \mathbb R^k \rightarrow \mathbb R^p$ be a smooth Lipschitz continuous function. Let $y_1,\ldots, y_N \in \mathbb R^p$ and $a = (a_1,\ldots,a_N) \in \mathbb ...
5
votes
1answer
41 views

how to sample data for regression that is the most informative?

Background I have a unknown function $$f(x_1, x_2)$$ But I have access to evaluate this function finite $L$ times, $$y_j = f(x_1^j, x_2^j), j=1,\ldots,L $$ Then I have a model $\hat{f}$ which I ...
3
votes
2answers
202 views

Understanding Sequential Importance Sampling and Particle Filtering

I am struggling with SIS for particle filtering in the following aspect: In particle filtering (as per this book), the objective is to estimate the full posterior $p( x_{0:k} \mid y_{1:k} )$ rather ...
1
vote
0answers
19 views

Low-variance estimate for the mean of the sotfmax transformation of a variable

Consider a set of infintiely-differentiable convex functions real-valued functions $f_i: \mathcal X \rightarrow \mathbb R$, where $i$ varies from $1$ to $m$, and suppose we know all the moments of $...
0
votes
0answers
25 views

how to prove that estimator converges to posterior distribution

Let $X_1, X_2, \dots X_n \sim f(x|\theta)$, $\theta$ has prior $\pi$. Generate $\theta_1, ... \theta_m$ from $\pi$, calculate $q_i = L(\theta_i|\textbf{x}) / \sum_j L(\theta_j|\textbf{x})$ where $L(\...
1
vote
1answer
262 views

Off-policy importance sampling for TD(0)

Consider the off-policy value update $V(s) \leftarrow V(s) + \alpha\frac{\pi(a\mid s)}{b(a\mid s)}[r_t+\gamma V(s') - V(s)]$ Where $\pi$ is the target policy (from which greedy actions are determined)...
2
votes
1answer
102 views

Monte Carlo - Importance sampling using normal distribution as sampling distribution

Suppose that I want to approximate an integral over finite range, say for example 0 to 10 using the Monte Carlo method. Can I choose a normal distribution as the sampling distribution even though the ...
5
votes
1answer
55 views

About the variance of a weighted sum

What can be said about the variance of the following quantity $$ \frac{1}{n}\sum_{i=1}^n \left(\frac{f(x_i)}{\sum_{j=1}^nf(x_j)}-b\right)g(x_i) ? $$ Here, $b \in [0, 1]$, and the $x_i$s are i.i.d ...
1
vote
2answers
158 views

ABC with non-uniform prior

I had asked some similar questions in the past, but I never got either the answers or the discussion I was hopping for. So I will rephrase the problem to see if I can understand it myself. I'm trying ...
1
vote
0answers
27 views

How can I use importance sampling to estimate $p$? [duplicate]

I have two density functions, $f$ and $g$. I generated a sample $X_1,\ldots, X_n$ using the distribution corresponding to density function $f$. I'm interested in the parameter $p_g = \operatorname{P}...
0
votes
1answer
74 views

Time limits in the Importance Sampling formula for Expected SARSA algorithm

In the Reinforcement Learning book (Prof. Sutton et al.) the authors explain a few basic algorithms of Reinforcement Learning. A particular kind of algorithms called n-step Temporal Difference ...
1
vote
1answer
31 views

In importance sampling, why do we “reapply” the trial distribution?

We are interested in the value of $\mu = \int f(x)dx$, and we have a factorization of $f$ as $f(x) = h(x)p(x)$, where $p(x)$ is a density. The general way to apply importance sampling is to follow the ...
0
votes
0answers
25 views

Exponential Tilting and Importance sampling

I am studying by myself a book about importance sampling. I am confused with the topic about exponential tilt. According to the algorithm is stated that I need to generate random variables $Z_1L_1,...
0
votes
0answers
40 views

How to prove $Var_f[\tilde{\mu}] \approx Var_p[\hat{\mu}](1+Var_f[W])$ is consistent estimator?

Here it's given a method of drawing an estimator for a variance in the context of importance sampling. http://www.stat.uchicago.edu/techreports/tr348.pdf My question is, how would one show $$Var_f[\...
0
votes
0answers
59 views

Importance Sampling for n dimensions

EDIT: I edited the question in order to make it clear. I'm having a problem with Importance Sampling and calculation of weights in more than one dimension. Because for me this is not obvious, I will ...
1
vote
2answers
105 views

How is this minimum variance worked out for this importance sampling estimator?

I was stuck with the function 17.13 in the open source book deep learning on page 590. For short, the question is that, For the importance sampling estimator: $$\hat s_q = \frac{1}{n}\sum_{i=1, x^{i}...
0
votes
0answers
28 views

Sampling strategy for estimation of probability distribution

Say I have a collection of random variables $X_1,\dots,X_k$, with a known joint distribution, and I want to estimate the probability density of $f(X_1,\dots,X_k)$ where $f$ is a known but very ...
0
votes
0answers
48 views

Importance sampling application

I am studying the importance sampling method. I am trying to perform an example given in Monte Carlo Methods and Models in Finance and Insurance written by Ralf Korn, Elke Korn, Gerald Kroisandt. ...
2
votes
0answers
111 views

Importance sampling: what is this bias?

I am experiencing what seems to be a bias in importance sampling, which, given that it's an unbiased procedure, should not be there. Consider linear regression $$ y = X\beta+\epsilon $$ where there ...
4
votes
0answers
37 views

Expected value of a “logistic uniform” multivariate

Let $\mathbf{a}_1,\ldots,\mathbf{a}_n \in \mathbb R^d$ and $b_1,\ldots,b_n \in \mathbb R$ be fixed. For $\mathbf{x} \sim \mathcal U([0,1]^d)$ and $j \in \{1,\ldots,n\}$, consider the real variable ...
2
votes
1answer
123 views

Importance Sampling

I want to solve the integral $$I =\int_{0}^{3} \frac{\exp(-s)}{1+\frac {1}{s}} \text{d}s $$ using importance sampling. I'm unsure as to how implement it. I have sampled random variables from an ...
1
vote
1answer
108 views

Exponential Twisting

I am with a difficult to prove the next relation about exponential twisting. According to Monte Carlo Methods and Models in Finance and Insurance by Ralf Korn, Elke Korn, Gerald Kroisandt. The ...
0
votes
0answers
17 views

Adjusting uniform sampling by relative weights

Assume a population of businesses, each given a size value which is proportional to their popularity. The sampling design is as follows, and cannot be changed: 1. Choose a random business uniformly, ...
2
votes
2answers
390 views

Off-policy evaluation of reinforcement learning: How to compute importance weights

I am working on a project that will use reinforcement learning to recommended products to customers in a mobile app. We have a few years of historical data available, which I would like to use for ...
0
votes
0answers
93 views

Importance Sampling Bias

I'm trying to solve the following problem related to importance sampling: The usual setting is: $\mu = \int_{\mathcal{D}} f(x) p(x) dx = \int \frac{p(x)q(x)}{q(x)}f(x) dx = \mathbb{E}_Q[\frac{f(X)p(...
2
votes
1answer
163 views

Sampling / Importance Resampling Poisson Weights

Another question from Introducing Monte Carlo Methods with R by Robert and Casella. Exercise 3.6 basically says the following. Suppose $f$ and $g$ are densities. Draw a random sample $X_1, \ldots,...
2
votes
1answer
50 views

Confusion: Conditioning a Discrete rv on a Continuous rv, “Sampling Importance Resampling”

Background In Introducing Monte Carlo Methods with R by Robert and Casella, in the discussion on "Sampling Importance Resampling", I'm confused by the following argument. Suppose $f$ and $g$ are ...
2
votes
1answer
101 views

Rejection/Importance Sampling for logit model

$\newcommand{\logit}{\operatorname{logit}}$I have the following model: ${y}_{j}\sim \operatorname{Bin}({n}_{j},{\theta}_{j})$, where ${\theta}_{j}={\logit}^{-1}(\alpha+\beta{x}_{j})$, for $j=1,...,J$,...
5
votes
0answers
88 views

Probabilistic upper bounds on importance sampling error

Consider the importance sampling estimation error $$ e_n(f) = \int f d\mu - \frac{1}{n}\sum_{i=1}^n f(x_i) \rho(x_i), \qquad x_i \sim \lambda,\, \rho = \tfrac{d\mu}{d\lambda}, $$ where $\mu$ and $\...
1
vote
1answer
121 views

Can someone explain Importance Sampling to me? [duplicate]

So even the combined efforts of my professor, my book and the internet have not been able to make me understand the concept of Importance Sampling. I know that it is a way to help with estimating the ...
0
votes
0answers
150 views

Under what conditions does off-policy SARSA with importance sampling converge?

Under what conditions does off-policy SARSA with importance sampling converge? I know function approximation can cause problems. In the tabular case, what is needed to get convergence (to the true Q)?...
1
vote
0answers
27 views

Can weighted sampling be more efficient than sampling?

Suppose that you have a normal distribution D with density f, which you sample. An estimator produces the maximum likelihood normal distribution $G_n$ given n samples. On the other hand you could ...
1
vote
0answers
169 views

How can we use importance sampling for drawing posterior distribution samples?

Today I read that Importance Sampling can be used to draw posterior distribution samples just like Rejection Sampling. However, my understanding of Importance Sampling is that its main purpose is to ...
4
votes
1answer
69 views

Difference between contrastive divergence and importance sampling

The terms Contrastive Divergence and Importance Sampling are sometimes used interchangeably. I understand that both are used to approximate partition functions (normalization terms for probabilities)...
2
votes
0answers
61 views

Discrete Kernel for Sequential Monte Carlo (population monte carlo)

I'm attempting understand, and use, the population Monte Carlo algorithm found here https://arxiv.org/abs/0805.2256 for approximate Bayesian computation. However I think this is a general SMC question,...