Efficient randomized algorithms are developed for solving robust feasibility problems with multiple parameter-dependent convex constraints. Two complementary strategies are presented, both of which exploit the multiplicity to achieve fast convergence. One is the stochastic ellipsoid method with multiple updates. In each iteration of this algorithm, an ellipsoid which describes a candidate of the solution set is updated many times via the multiple constraints with one random sample, while at most one update is allowed in the original method. The other is the stochastic ellipsoid method with multiple cuts. Here, a new update rule is presented to construct a smaller ellipsoid directly via multiple subgradients given by the constraints. A quantitative analysis of the volume of the ellipsoid is also provided, which guarantees the advantage of the proposed algorithm over the original one. The above features lead to a reduction of the total number of random samples necessary for convergence, which is extensively demonstrated through numerical examples. (C) 2010 Elsevier Ltd. All rights reserved.