Abstract: Complex systems are often modeled with black-box functions that are ill-structured and are available only through computer programs. Random search algorithms (e.g., simulated annealing, cross-entropy) have been shown to be very effective at making use of probability distributions to focus samples on “good” regions. We analyze an idealized adaptive random search algorithm as a marked Poisson process, and use it to motivate sampling distributions. Then we apply a Markov chain Monte Carlo sampler, namely Hit-and-Run, to approximate the sampling distribution. Recent work extends the analysis to noisy functions, and motivates a partition-based random search optimization algorithm.