What unequal probability sampling methods exist for weights which are extremely different from each other? Suppose I have $N$ samples, each having a relative weight of $w_1, \ldots, w_N$. Assume that the largest weight is $10,000$, while the smallest weight is just $1$.
Suppose I wanted to get $m\leq N$ samples. If we were to sample this by weighted sampling, such that the largest weight is 10000x more likely to be chosen than the rest, we would almost always get the sample corresponding to the largest weight.
Are there methods which exist for dealing with extreme weight sampling problems that can maximize the Effective Sample Size?
EDIT: For example, I have heard of methods such as weight trimming, etc. Is there a part of the literature which deals with this?
 A: For Monte Carlo Simulations, there is a whole branch of research dealing with what is called "rare event sampling". Rare events are events which have low chance to occur (or in your language "have a small weight").
In computational physics and computational chemistry, rare event sampling techniques are employed to sample states from the state space which are otherwise not accessible within reasonable amount of compute time. Those rare states may be needed to compute highly accurate estimates of ensemble averages. An ensemble average could be highly biased if a free energy barrier would otherwise prevent the system from exploring the whole state space.
The most obvious example of a physical system requiring a rare event system to be correctly simulated is a system with two stable states of equal energy which are connected by a pathway which requires very high energy. If the system starts in one energy minimum it is unlikely to see the other energy minimum within a reasonable amount of Monte Carlo steps.
One way to overcome this issue is for example Wang-Landau sampling. You can find the implementation details in the corresponding Wikipedia article.
The essence of the algorithm is to iteratively reduce the weights for states which you already visited so that it is not revisited so frequently again (while additionally keeping track of the way the weights were modified for each state - this will later provide you with a reweighing factor). In your case, a state would be a unique sample and the ratio $\frac{g(\boldsymbol{r}'\rightarrow \boldsymbol{r})}{g(\boldsymbol{r}\rightarrow \boldsymbol{r}')}$ is given by the ratio of weights e.g. 1000/1.
A simulation could then evolve like this:

*

*draw a sample according to the initial weighs

*Maintain the Wang landau histogram S

*Transition to a new sample with the Wang-Landau acceptance probability (which punishes states already visited)

(Repeat steps 2 and 3 many times).
This will result in drawing all the samples of within your sample space. If you want to compute e.g. a simple averages from these enforced samples, then you need to perform a reweighing:
$E[X] = \frac{\sum_i \exp(S_i) x_i}{\sum_i \exp(S_i)},$
where $i$ indexes unique samples and $x_i$ is their value. $S_i$ is the corresponding value of the Wang-Landau histogram which is a result of the MC simulation.
Other methods like Metadynamics are essentially equivalent to Wang-Landau sampling. The wikipedia entry on meta dynamics contains a nice video illustrating the iterative punishment of already visited states (along a potentially binned collective variable used for defining states in a continuous interval). Intuitively the biasing Potential modiefies the underlying energy landscape (and therefore the "weights" of the sates) forcing the simulation to explore new states.
A: If using weighted random sampling (the $w$'s being weights) then this behavior is completely understandable, a sample with weight 1 will almost never be present in a random sample if max weight is say 10000 (and assuming the other weights are more or less uniformly distributed between the min and max).
Two options with no guarantees come to mind, 1) use some sort of transformation for the weights, e.g. sqrt(weights), 2) replace the weights with... ranks (especially useful if you have outliers).
A: This sounds similar to a problem in finance / stock index arbitrage, where one may want to "sample" a small number of assets in a large portfolio to estimate (or "track") the performance (weighted investment return) of a larger portfolio. E.g., "track" the performance of a 1000 stock portfolio with a 50 stock portfolio.
This problem is "easy" if $m=N$, "sample" every case.
With $m<N$, one approach that works pretty well in practice but is not provably optimal (with the method described below) is to sample using the inverse cumulative distribution method; and to consider two phases.
Sort the cases by declining weight.
In the first phase, select immediately all cases (stocks) with weight exceeding what you hope to represent in the remaining samples, for instance at first iteration, select the largest weighted case if $w_1 \ge \frac{1}{m}$. At the second iteration select the largest remaining case if $w_2 \ge \frac{1-w_1}{m-1}$ $\ldots$
When $w_{J+1} < \frac{1-\sum\limits_1^J w_j}{m-J}$, in phase two, sample $m-J$ cases identified by samples from the uniform distribution over the interval $\textrm{U}\left(\sum\limits_1^J w_j,1\right)$ and the inverse cumulative distribution function.
When constructing a parameter estimate (e.g., portfolio return), use the exact weights $w_1 \ldots w_J$ for the large weight cases, and use the average residual weight $\tilde{w}=\frac{1-\sum\limits_1^J w_j}{m-J}$ for the sampled smaller cases. For example $\hat{\mu}_x = \sum\limits_1^J \left(w_j x_j\right) + \sum\limits_{J+1}^{m}\left(\tilde{w} x_j\right)$.
A final "trick" to consider with $K$ multiple samples of size $m$ is to use antithetic variates when selecting $m-J$ uniform variates for the smaller weighted cases in the distinct $K$ repeats.
