Isn’t the probability of finding a bit 1⁄4 in each sample? Because you have to sample both sides. If you randomly sample without repetitions you can do even better than that. You can even bound the worse case for the random algorithm at n/4+1 as well by seeing if you ever pick n/4+1 0s from any side. So there is no downside to doing it randomly as such.
However if it is an important problem and you think you might be able to find some regularities, the best bet would to be to do bayesian updates on the most likely positions to be ones and preferentially choose those. You might be bitten by a super intelligence predicting what you think most probable, and doing the opposite, but as you have made the system more complex the world has to be more complex to outsmart you, which may be less likely. You can even check this by seeing whether you are having to do n/4+1 samples or close to it on average.
Isn’t the probability of finding a bit 1⁄4 in each sample? Because you have to sample both sides. If you randomly sample without repetitions you can do even better than that. You can even bound the worse case for the random algorithm at n/4+1 as well by seeing if you ever pick n/4+1 0s from any side. So there is no downside to doing it randomly as such.
However if it is an important problem and you think you might be able to find some regularities, the best bet would to be to do bayesian updates on the most likely positions to be ones and preferentially choose those. You might be bitten by a super intelligence predicting what you think most probable, and doing the opposite, but as you have made the system more complex the world has to be more complex to outsmart you, which may be less likely. You can even check this by seeing whether you are having to do n/4+1 samples or close to it on average.