Why is random sampling good? First, is there any theory for random sampling being optimal?
Second, consider the following example. Suppose there are two balls in an urn. Their colors can be either white or red. So there are three states: two red, one red on white, and two white.
In random sampling, one randomly draws a ball, puts it back, and draws once again. In this case, she cannot perfectly learn the states.
In a non-random sampling, one randomly draws a ball and draws the remaining ball. In this case, she can perfectly learn the states.
So it looks non-random sampling is better.
Edit: Maybe I confused "random" and "independent". In sampling without replacement, the result of the first draw is (conditionally) correlated with the second draw. In this sense, my question may be rephrased as whether and why (conditionally) independent sampling is good.

You seem to be conflating the idea of random sampling with the separate question of whether objects are sampled with or without replacement.  The first method you describe is a simple-random-sample with replacement and the second is a simple-random-sample without replacement.  In the second case the sample is the whole population so you do indeed perfectly learn the states --- that occurs whenever you take a simple-random-sample without replacement that has the same size as the population.
As to your initial question, there is a large statistical literature on the properties of random sampling and why it is desirable for making inferences from a sample to a larger population.  Simple random sampling does not favour any object in the population over any other object, which makes it easy to make unbiased inferences about the larger population of interest.  Whether or not a sampling method is "optimal" would require more detailed specification of the problem and the optimality criteria.  In any case, it is reasonable to say that simple random sampling performs well in a wide range of sampling problems.
