Questions tagged [importance-sampling]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
27 views

Test for significant difference between two probability distributions sampled from a model

Let's say I use importance sampling to sample conditional probability distributions for variable X (categorical variable with 3 levels) 50 times, for example, P(X|Y=1) = { (0.11, 0.21, 0.68), (0.09, ...
0
votes
0answers
17 views

Central limit theorem in a multidimensional sphere

In the book of David MacKay there's a chapter on Monte Carlo methods (http://www.inference.org.uk/mackay/erice.pdf) where, when discussing the importance sampling, it gives this example: Suppose a ...
3
votes
2answers
118 views

Importance sampling estimation of power function

Problem Suppose we are given $\text{Poisson}(\theta)$ model, and the null hypothesis is as follows: $$ H_0 : \theta = 0.1 \ \ \text{vs}. \ \ H_1 : \theta < 0.1 $$ Suppose we take sample of $n=...
1
vote
0answers
27 views

Literature on design of importance sampling distribution using MLE or point-estimates of highest modes

Suppose I have many distributions $p_i(\theta)$ I wish to take expectations over $$\mathbb{E}_{p_i}[\mathbf{f}_i(\theta)]$$ where the $\mathbf{f}_i$ are vector-valued. In my problem the $p_i$ share ...
1
vote
0answers
33 views

How to evaluate double Integral with importance sampling

I am trying to recreate the Bayesian Hierarchical Clustering algorithm using Python. The example in section two requires evaluating the following double integral (univariate case): \begin{align} p(...
3
votes
1answer
378 views

Variance of Monte Carlo integration with importance sampling

I am following these lecture slides on Monte Carlo integration with importance sampling. I am just implementing a very simple example: $\int_{0}^{1} e^{x}dx$. For the importance sampling version, I ...
0
votes
0answers
14 views

Importance sampling with partly deterministic samples

I am trying to estimate an expectation with a certain set of unlikely, but important (for the value of the expectation) events. In particular, let’s say I have a (normal) distribution p(x). Now, I ...
1
vote
2answers
578 views

importance sampling from posterior distribution in R

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 ...
0
votes
0answers
45 views

importance sampling for conditional probability

Stats experts, I am trying to estimate $G(x)$ for $x$ in a very small subset $A$ of a finite space $U$, i.e $E(G(x | x \in A))$. Determining if $x$ in $A$ has a cost. So it is expensive to uniformly ...
1
vote
2answers
114 views

in reinforcement learning off policy mc may not work

I noticed off-policy mc prediction(or control) will not work, as being descripted by boxed algorithm in page 110 of the book "reinforcement learning an introduction". The weight W should before C's(...
1
vote
1answer
58 views

Generalization performance in Bayesian errors-in-covariates model

I'm working on a model with this basic structure: The square nodes are data, and the round nodes are parameters and/or latent variables. The left plate represents the "training observations" we ...
8
votes
1answer
144 views

Would an “importance Gibbs” sampling method work?

I suspect this is a fairly unusual and exploratory question, so please bear with me. I am wondering if one could apply the idea of importance sampling to Gibbs sampling. Here's what I mean: in Gibbs ...
1
vote
1answer
22 views

importance sampling and exponential moving average

Lets say i have got a random variable $X$ with samples $x_t\sim X$ and density $p_X(x)$ and want to compute its mean via a moving average $ \mu_{t+1}=(1-c)\mu_t + c x_t$ Assume, I can not observe $X$...
1
vote
1answer
84 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
36 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
54 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 $$ ...
2
votes
1answer
53 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/...
3
votes
2answers
65 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)})...
5
votes
3answers
86 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+...
3
votes
1answer
60 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
36 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 ...
1
vote
1answer
480 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
736 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
1answer
74 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
64 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
34 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 ...
6
votes
1answer
51 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
632 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
22 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
44 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(\...
3
votes
1answer
763 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
150 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
67 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 ...
2
votes
2answers
193 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
32 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
120 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
46 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
89 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
187 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}...
2
votes
0answers
213 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
39 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 ...
3
votes
1answer
198 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
151 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
18 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
505 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 ...
2
votes
1answer
269 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
71 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
132 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
95 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
174 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 ...