How to calculate probability of particle survival for particle filter?

Question

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?

Answer 1

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} $$

Answer 2

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$.