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?