Annealing by Increasing Resampling (AIR, for short) is a stochastic hill-climbing optimization algorithm that evaluates the objective function for resamplings with increasing size. At the beginning stages, AIR makes state transitions like a random walk, because it uses small resamplings for which evaluation has large error at high probability. At the ending stages, AIR behaves like a local search because it uses large resamplings very close to the entire sample. Thus AIR works similarly as the conventional Simulated Annealing (SA, for short). As a rationale for AIR approximating SA, we show that both AIR and SA can be regarded as a hill-climbing algorithm according to objective function evaluation with stochastic fluctuations. The fluctuation in AIR is explained by the probit, while in SA by the logit. We show experimentally that the logit can be replaced with the probit in MCMC, which is a basis of SA. We also show experimental comparison of SA and AIR for two optimization problems, sparse pivot selection for dimension reduction, and annealing-based clustering. Strictly speaking, AIR must use resampling independently performed at each transition trial. However, it has been demonstrated by experiments that reuse of resampling within a certain number of times can speed up optimization without losing the quality of optimization. In particular, the larger the samples used for evaluation, the more remarkable the superiority of AIR is in terms of speed with respect to SA.