Effectiveness of Random Sampling : With Replacement vs. Without Replacement

Question

I was watching the following video on "Optimization through Random Sampling"(https://www.youtube.com/watch?v=7WWnWSPymdc), where a very interesting point was brought up:

• Suppose there are a total of "m" possible solutions to an optimization problem

• Out of these "m" possible solutions, let's call the "best solution" (i.e. the solution which returns the lowest value of the function) as "m0"

• As a result, if m = n = large number AND if you sample with replacement: Probability(finding "m0" in "n" trials) = 1 - [(1 - (1/m))^n]: 1 - (1/e) = 0.63

My Question: The above result suggests that if you were to evaluate the function you are optimizing using as many random draws as there exists number of total possible solutions (i.e. m = n ) - you will still only have a 63% chance of finding the best solution! I can't help but notice - if you had done sampling without replacement, you would have surely found the best solution!

If this is the case, can someone please explain why popular implementations of random search are done "with replacement" instead of "without replacement"? Is this because if you wanted to do "without replacement", the effort (i.e. computer resources) required to constantly store/check whether each new sample has been previously chosen in the past, and then regenerate a new candidate sample - and this would paradoxically make this more ineffective compared to sampling "with replacement"?

If you sample "without replacement", the computer would then have to store the results of all previous iterations - and I am not sure to what extent this would slow down the computer and make this more ineffective compared to "with replacement".

Can someone please comment on this?

Thanks!

Answer 1

There are a number of drawbacks of random sampling without replacement:

1. As you point out, you need to keep a list of all the solutions you have visited so far (generally in a hash map), which can be memory intensive.
2. It's harder to parallelize, since you would need to coordinate the list of previously explored solutions across all your computing nodes.
3. It might actually slow the search down considerably if you are sampling all or nearly all of the solution space -- the most common implementation would be rejection sampling, where you randomly sample a solution and reject it if it's already been explored. However, once you've explored most of the solution space you'll be rejecting a bunch of solutions before you find one you haven't explored before, ultimately causing you to need to randomly generate O(n^2) solutions to explore a solution space of size n.
4. It makes your code more complex than random sampling with replacement.

Unfortunately, we often have to suffer all these drawbacks for extremely limited possible benefit from sampling without replacement. Usually we're only interested in random sampling for optimization if we have a very large space of possible solutions, e.g. a combinatorial optimization problem such as the traveling salesman problem (number of solutions is exponential in the number of nodes) or a continuous problem like optimizing a function over the space of real numbers (infinite number of solutions in the space). In this common scenario, the probability of ever randomly sampling the same solution twice approaches 0.

So, in short, enumeration makes sense for small solution spaces, random sampling with replacement makes sense for large solution spaces, and random sampling without replacement rarely makes sense (the only real example I can think of would be small solution spaces where evaluating the objective function is exceptionally computationally expensive).