# 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$$ directly, but instead a random variable $$Y$$ with density $$p_Y(y)$$ and samples $$y_t\sim Y$$. I would like to use importance sampling to compute the mean.

The naive approach is with $$w_t=\frac{p_X(y_t)}{p_Y(y_t)}$$

$$\mu_{t+1}=\left(1- cw_t\right)\mu_t + c w_t y_t$$

This works, as long as the importance weights are small. However, if $$w_t> \frac 1 c$$ the above formula is obviously not correct any more. Is there a way to correct for this? It should be clear that as $$w_t \rightarrow \infty$$, $$\mu_{t+1}\rightarrow y_t$$

//edit the approach I tried to is using a sample-size estimate, but i am not sure this is correct.

The initial estimate has an estimated $$1/c$$ samples stored. Assuming we can interpret $$w_t$$ as sample-size correction, we can just try to average according to how many samples we got:

$$\mu_{t+1}=\left(1- \frac{w_t}{w_t + \frac 1 c -1}\right)\mu_t + \frac{w_t}{w_t+\frac 1 c-1} y_t$$

for $$w_t=1$$ this gives the original update $$\frac 1 c-1$$ is the totally stored number of samples in the path after "forgetting the oldest"

but i have no idea how to show that this is correct, this is just an educated guess

I am answering myself. Still not with a proof, but with a better solution.

Assume first a slightly different setup, where instead of a single number $$y_t$$, we get a sample average $$\bar{y}_t$$ from $$n_t$$ samples. Clearly, if $$n_t$$ is large, we would like to trust it a lot and unlearn much of the previous samples. if afterwards, $$n_{t+1}$$ is small, we would not want to unlearn the good sample quickly.

The correct way to handle this is to have two variables: one which is an exponentially decaying sum of the number of samples

$$N_{t+1}= (1-c) N_t + n_t$$ Note that when $$n_t=1$$ for all $$t$$, this will converge to $$N=1/c$$.

The update of the mean $$\mu_{t+1}$$ is just the correctly weighted average of two means with different number of samples: $$\mu_{t+1}=(1-\frac {n_t}{N_{t+1}}) \mu_t + \frac {n_t}{N_{t+1}} \bar{y}_t$$

The same now holds trivially when replacing $$n_t$$ with $$w_t$$.

I have no doubt about the $$\mu_{t+1}$$ update and it also makes sense with importance sampling. I am not sure about the $$N_t$$, but I think it is probably hard to come up with a perfect justification for any type of exponential moving average.