# 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, 2013 at 9:14
• Deleted: My comment was unnecessary, as you clearly provided the information I was asking for in the question...my mistake. Dec 4, 2013 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? Jan 28, 2018 at 20:29

Survival rate for the case of multinomial resampling and the case of $$w \geq \frac{1}{n}$$ has been covered well by the accepted answer.

However, I didn't find the case of $$w < \frac{1}{n}$$ intuitive enough for myself, so I will share my own intuitive understanding about it, even though it might not be as formal. Forgive me for the lack of pictures.

How I visualize systematic resampling - Casino roulette: First, I visualize systematic resampling similarly to a casino roulette over which we spread our cumulative distribution, starting from 0 and draw samples from the start of each roulette field, after spinning the roulette by the randomly sampled value $$r_0 \in [0,1/n]$$. The variable $$n$$ here is the number of particles.

A bit more formally: we split the cumulative distribution into $$n$$ bins of size $$1/n$$ each, with the first bin starting from $$0$$. Then we shift the position of those bins by the sampled random number $$r_0$$, sampling a weight from the beginning of each bin.

Survival (or no survival) of a weight $$w$$: If $$0 \leq w \leq \frac{1}{n}$$, then the probability of $$w$$ surviving depends on the value of the random variable $$r_0$$. In order for $$w$$ to not survive, we need to generate an $$r_0$$ so that $$w$$ falls between two of our equally spaced indices that define our bins after shifting the position of the bins by $$r_0$$. In terms of casino roulettes, we should spin the roulette so that after the spin $$w$$ falls within a single roulette field and not between them.

We can visualize this $$r_0$$ offset sampling procedure as having a single $$1/n$$ sized bin from which we sample the starting position of all bins after the spin (each roulette field) at the same time, with $$w$$ not surviving if we sample an offset that results in no starting position being covered by $$w$$ for any of the $$n$$ bins.

That is equivalent to the probability of $$r_0$$ having a value in $$[0, 1/n]$$ but not falling on the part of the space covered by $$w$$ in any of the $$1/n$$ sized bins ($$w$$ can actually be present in 2 bins at most). More formally:

$$\begin{equation} prob(\bar{w}) = \frac{1/n - w}{1/n} = 1 - nw \end{equation}$$

where $$prob(\bar{w})$$ is the probability of $$w$$ not surviving. Hence, the probability of surviving is equal to $$nw$$.