I'm trying to figure out a way that I can calculate the probability that a particle will survive the re-sampling step in the particle filter algorithm.

For the simple case of multinomial re-sampling, I can assume that we can model the process like a Binomial distribution if we only care about one sample/particle.

So if the particle has a weight of w that is also the probability that it will get selected in a step of the re-sampling. So we use 1 - P(k, p, n) where P is the Binomial distribution, k is 0 (we did not select the particle in all our tries), p is equal to w and n is equal to M, the number of particles.

What is the case though in the systematic re-sampling, where the probability of a particle being selected is proportional but not equal to its weight?

  • $\begingroup$ Multinomial and systematic re-sampling $\endgroup$
    – Bar
    Dec 4 '13 at 9:14
  • $\begingroup$ Deleted: My comment was unnecessary, as you clearly provided the information I was asking for in the question...my mistake. $\endgroup$ Dec 4 '13 at 16:02

Let $w_1 \dots w_n$ be the weights of $n$ particles, $p_i \triangleq \frac{w_i}{\sum\limits_{j=1}^{n}w_j}, \sum\limits_{j=1}^{n} p_j = 1$, then as you posted, the probability of the $i$th particle surviving in the resampling procedure for multinomial resampling is: $$ P(Survival_i) = 1 - (1 - p_i)^n $$

In systematic resampling, one concatenate $p_1 \dots p_n$ as a ring of interval [0,1). First select $\tilde{u} \sim U[0,1)$, and take $n$ points $u_k = \frac{k-1 + \tilde{u}}{n}, k = 0, \dots n-1$ equally spaced $\frac{1}{n}$ apart from each other on that ring, and take the $n$ samples which have partitions $p_i$ covering the $n$ points.

Therefore, if $p_i \geq \frac{1}{n}$, the probability of survival for the $i$th particle is 1. If $p_i < \frac{1}{n}$, the probability of survival depends on $u_k$. Without loss of generality, let's always assume $i=1, p_1 < \frac{1}{n}$, and consider the probability of the first particle not being selected (you can always re-index the particles to see this is valid for all $i$).

In order for the first particle not to be selected, there need to be two equally spaced points $\{u_j, u_{j+1}, | j = 0 \dots n-1\}$ such that $u_j < 0$ and $u_{j+1} > p_1$. The probability of this event happening for $j=0$ is equal to $\frac{1}{n}-p_1$ (consider the ring interval $[1-\frac{1}{n}+p_1, 1)$). The probability of the first particle not to be selected, is a combination of $n$ exclusive events $j=0, \dots n-1$. Therefore the probability of the first particle not selected is $n\times (\frac{1}{n}-p_1) = 1-n p_1$.

Same derivation for other particles $i=1\dots n$.

In conclusion, $$ P(Survival_i) = 1, \text{if } p_i >= \frac{1}{n}\\ P(Survival_i) = np_i, \text{if } p_i < \frac{1}{n} $$

  • $\begingroup$ @nil could you please cite a scientific paper that calculates the survival likelihoods of particles using the formula you described above? $\endgroup$
    – S.E.K.
    Jan 28 '18 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.