# Particle Filter: Confidence Intervals

Context

This is a basic question about confidence intervals. So the standard way to estimate a confidence interval.Assuming we have a set of $N$ random variables $\{X^i\}$ such that all of them are i.i.d. We know that the mean of is converges to the central limit of a $N(\mu,\frac{\sigma^2}{N})$, where $\mu$ is the true mean of $X^i$ and $\sigma^2$ is the true variance of $X^i$. Note: we are not assuming $X^i$ are normally distributed. The confidence interval can be estimated

$$CI_{upper}=\bar{x}+1.96\frac{s}{\sqrt{N}}$$

where $s$ is the square root of the sample variance. The idea to me here is quite simple. Assuming $N$ is large enough, we carry out an experiment ONCE, compute $\bar{x}=\frac{1}{N}\sum x^i$, which is an unbiased estimate of $\mu$ and compute $s=\frac{1}{N-1} \sum (x^i-\bar{x})^2$ which is an unbiased estimate of $\sigma^2$. So our confidence interval gives as the uncertainty of repeating the experiment $M$ times, i.e. if we repeated $M$ times we will expect $\mu$ to be inside the confidence interval 95% of the time. In code this can be written as,(this can also be seen as estimating only mean and variance of a single random variable)

x<-rnorm(100)
mean(x)
var(x)
mean(x)+1.96*var(x)/sqrt(N)


Note: I am assuming i.i.d and I will come to a situation where I am uncertain whether i.i.d applies and if it doesn't how do we compute non-i.i.d confidence intervals.

Particle Filter

I am constructing a particle filter estimating , $p(x_t|y_{1:t})$. I want to estimate confidence intervals for the mean estimates of my particles at time $t$. I hypothesize that my mean estimates are the best estimate of the state,although this is not entirely true. In effect I have an approximation of , $p(x_t|y_{1:t})$ by a set of weighted samples $\{x^i_t, w^i_t\}$. Therefore, I compute the weighted mean

$$\bar{x}_t=\frac{1}{N}\sum w^i_tx^i_t$$

I intend to compute two quantities the variance of $\bar{x}_t$ and the confidence intervals around $\bar{x}_t$.The purpose of this is really to see how frequent resampling occurs effects variance, therefore, keep in mind that I may have resampled my particles $\{x^i_t, w^i_t\}$ from the previous time step and the index $i$ is not representative of the particle at time $t-1$.

Some theoretical consequences

There exists central limit theorems that state that my weighted approximation, $E(\hat{p}(x_{t}|y_{1:t}))$ converges in distribution to a normal distribution with mean $E(p(x_{t}|y_{1:t})$ and some unknown variance $\sigma_{pf}^2$, where $\hat{p}(x_{t}|y_{1:t})=\frac{1}{N}\sum w^i_t\delta(x_t-x^i_t)$. I am unaware of any independence and identically distributed assumptions. Although I read somewhere that $\{x^i_t,w^i_t\}$ are independent but not identically distributed.

How do I calculate the variance?

I tried to calculated the variance using simulation of the the data $\{y_t\}$(I can generate $y_t$ because I know $x_t$) to compute $\bar{x}_t$.These are the steps I took 1) Generate $\{y_t\}$ 2) Run the filter 3)Obtain $\bar{x}_t$ 4) Repeat 1)-3) $M$ times 5)With my collection of $M$ pieces of $\bar{x}_t$, we will denote by $\{\bar{x}_t\}$ I compute the $mean(\{\bar{x}_t\})$ to get an estimate of $E(p(x_{t}|y_{1:t})$ and $var(\{\bar{x}_t\})$ to get an estimate $var(p(x_{t}|y_{1:t})$. My confidence interval is therefore,

$$CI_{upper}=mean(\{\bar{x}_t\})+1.96var(\{\bar{x}_t\})$$

Notice I do not divide by $\sqrt{M}$.

QUESTION

1. Have I computed the variance and confidence intervals correctly?I am really treating $\bar{x_t}$ as a random variable and getting monte carlo estimates from it.Also when I compute the confidence interval, I did not use the number of simulations. Also in consideration of the fact that $\{x^i_t\}$ might not be identically distributed am I estimating the $var(\{ \bar{x}_t\})$ correctly?

2. Is there a way I can compute confidence interval of $\bar{x}_t$ without needing to simulate?

3. Was it correct that I obtained instances of $\bar{x}_t$ by generating a new $\{y_t\}$ at each simulation. Does this not change the distribution I am estimating in the first place, $p(x_t|y_{1:t})$?

EDIT: in response to @Taylors comments

As you can see that my constructed confidence intrevals which are shown by the two red lines are too narrow. My true states which are shown by black dots are outside of the interval too frequently. I am using a simple random walk with fixed process variance of 1 and measurement variance of 3. The narrow interval was when I divide by $\sqrt{N}$ and the wide interval is when I don't divid by $\sqrt{N}$

You might want to check your formulas for the sample means and sample standard deviations once you start talking about particle filters. Also, the particles are not independent if you are resampling. But they are identical. I think you have that backwards.

Otherwise, if you weren't resampling, you would just be using the Law of Large Numbers, more basic Central Limit Theorems, and Slutsky's theorem to guarantee that sample means and standard deviations are the way to go. You've been asking a lot of questions about the Doucet/Johansen tutorial lately, and that tutorial mentions a few sources on the theorems you're asking about. Specifically they say:

SMC methods involve systems of particles which interact (via the resampling mechanism) and, consequently, obtaining convergence results is a much more difficult task than it is for SIS where standard results (iid asymptotics) apply. However, there are numerous sharp convergence results available for SMC; see [10] for an introduction to the subject and the monograph of Del Moral [11] for a complete treatment of the subject. An explicit treatment of the case in which resampling is performed adaptively is provided by [12].

To answer (1), you can drop the $1/N$ because your normalized weights sum to $1$ already: $$\bar{X}_t = \sum_i W_t^iX^i_t = \sum_i \frac{w_t^i}{\sum_jw_t^j} X^i_t$$ $$S^2_t = \sum_i W_t^i (X^i_t - \bar{X}_t)^2.$$

Regarding (2) and (3), you probably never want to simulate your observed data.

• @TaylorAhhhh. That makes so much more sense to think of it that way. Therefore, $x^i_t$ in a sense come from the same proposal distribution and when if $w^i_t$ is equal(in resampling) then $x^i_t$ are distributed according to posterior, $p(x_t|y_{1:t})$? So if I want to obtain my confidence intervals it would be $CI_{upper}=\bar{X}_t+1.96\frac{S^2_t}{\sqrt{N}}$, where $N$ is the number of particles and I do not need to run any simulations but I only need to rely on the central limit theorem. – tintinthong Mar 31 '17 at 23:42
• @tintinthong yeah but it's a fancy central limit theorem. Also I think you mean $CI_{upper}=\bar{X}_t+1.96\frac{\sqrt{S^2_t}}{\sqrt{N}}$ – Taylor Apr 1 '17 at 2:09
• Yes, indeed thanks for the correction. Taylor if you look in the confidence intervals plot I included, I found that when I divide by $\sqrt{N}$ it becomes too narrow. This is when I resample 50% of the time and with 500 particles for 100 time steps. Does this seem right? – tintinthong Apr 1 '17 at 9:05
• Note this is a particle filter, not a joint smooth – tintinthong Apr 1 '17 at 9:16
• @tintinthong you've gotta divide by $\sqrt{N}$. Maybe you have a bug somewhere else. It might be that you're using variance instead of standard deviation in the numerator. You've made this mistake a few times in your post. Also, variance is sometimes smaller than standard deviation, which might be what's going on. Lengthy comment discussions are ill-advised on this site, so if you have more questions, you should make another thread. – Taylor Apr 1 '17 at 20:13