You are given weights for \(N\) data points as [w1, w2, ... wn]. These weights represent the probability of each data point being selected. Your task is to sample \(M\) data points based on this probability distribution.

Contraint : \(M > N\), which means sampling will be done with replacement.

Inputs

• \(w\) : List of weights [w1, w2, ... wn]
• \( M \) : Number of data points to sample

Output

• A list (size \(M\)) of indices corresponding to the sampled elements.

Example

• Input:
  • w = [0.1, 0.3, 0.2, 0.4]
  • M = 10
• Output:
  • [1, 3, 3, 2, 3, 1, 0, 3, 1, 2] (indices of sampled elements, values may vary)
• Explanation:

  - The input weights \(w = [0.1, 0.3, 0.2, 0.4]\) define the probabilities for selecting the elements with indices 0, 1, 2, and 3.
  - Since \(M = 10\), we sample 10 elements with replacement. Indices may repeat due to the probabilities.

Solution

---

Check this solution article.