How to calculate probability of particle survival for particle filter?

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?

• Multinomial and systematic re-sampling – Bar Dec 4 '13 at 9:14
• Deleted: My comment was unnecessary, as you clearly provided the information I was asking for in the question...my mistake. – Andrew Capodieci 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}$$

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