Example of resampling

This process is commonly used in particle resampling during particle filtering. Here's an example to illustrate the steps:

Scenario:

We have 5 particles with the following weights:

\[ \text{weights} = [0.1, 0.2, 0.4, 0.2, 0.1]\]

We want to resample these particles based on their weights to produce 5 new particles.

Step-by-Step Explanation:

1. Normalize the weights:

Ensure the weights sum to 1 (if not already). In this case, they are already normalized:

\[ \text{normalized weights} = [0.1, 0.2, 0.4, 0.2, 0.1] \]

2. Calculate the cumulative sum of the weights:

The cumulative sum creates intervals that represent the range of selection for each particle:

\[ \text{cumulative weights} = [0.1, 0.3, 0.7, 0.9, 1.0] \]

This means:

• Particle 1 corresponds to the range ( [0, 0.1) )
• Particle 2 corresponds to the range ( [0.1, 0.3) )
• Particle 3 corresponds to the range ( [0.3, 0.7) )
• Particle 4 corresponds to the range ( [0.7, 0.9) )
• Particle 5 corresponds to the range ( [0.9, 1.0] )

3. Randomly generate numbers:

Generate 5 random numbers between 0 and 1 to select particles. For example:

\[ \text{random numbers} = [0.15, 0.85, 0.05, 0.45, 0.75] \]

4. Determine which range each number belongs to:

Check each random number against the cumulative weights to determine the corresponding particle:

1. 0.15 falls in the range ( [0.1, 0.3) ) → Select Particle 2.
2. 0.85 falls in the range ( [0.7, 0.9) ) → Select Particle 4.
3. 0.05 falls in the range ( [0, 0.1) ) → Select Particle 1.
4. 0.45 falls in the range ( [0.3, 0.7) ) → Select Particle 3.
5. 0.75 falls in the range ( [0.7, 0.9) ) → Select Particle 4.

5. Repeat until the desired number of samples is achieved:

The resampled particles based on this example would be:

\[ \text{resampled particles} = [2, 4, 1, 3, 4] \]

Summary of Steps in Code:

import numpy as np

# Initial weights
weights = np.array([0.1, 0.2, 0.4, 0.2, 0.1])

# Cumulative sum of weights
cumulative_weights = np.cumsum(weights)

# Generate random numbers
random_numbers = np.random.uniform(0, 1, size=5)

# Resample particles
resampled_indices = np.searchsorted(cumulative_weights, random_numbers)

print("Random Numbers:", random_numbers)
print("Resampled Indices:", resampled_indices)

This will output a similar result, resampling particles based on their weights.