In the practical design process, uncertainty in the parameters should be appropriately taken into account. In particular, our interest focuses on design problems with dynamic analysis under uncertainty. One of the authors presented a worst-case design of structures based on a random sampling approach, in which constraints are assigned on the worst values of the structural responses. Key concept of the method is estimation of the worst value by Random Search (RS) with order of the function values. Predicting the exact extremes from small samples is difficult in general. Hence, we relax from the worst value to the k-th worst value. Then we can predict and control more accurately the behavior of RS. In two numerical examples, we verify the validity of the estimation by the k-th order statistics. The result indicates use of relatively small samples is enough to predict the large number of future samples even for the noisy and non-smooth dynamic analysis under uncertain parameters.