4
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Multinomial and systematic re-sampling $\endgroup$
    – Bar
    Dec 4, 2013 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, 2013 at 16:02

2 Answers 2

6
$\begingroup$

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

$\endgroup$
1
  • $\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, 2018 at 20:29
1
$\begingroup$

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

$\endgroup$

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.